Osama Abdel-Raouf; Ibrahim El-henawy; Mohamed Abdel-Baset

A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles

Full Text (PDF, 312KB), PP.38-44

Views: 0 Downloads: 0

Author(s)

Osama Abdel-Raouf ^1,* Ibrahim El-henawy ² Mohamed Abdel-Baset ³

1. Department of Operations Research, Faculty of Computers and Information, Menoufia University, Menoufia, Shebin-El-Kome, Zip code: 32511, Egypt

2. Department of Computer Science, Faculty of Computers and Informatics, Zagazig University, El-Zera Square, Zagazig, Sharqiyah, Zip code: 44519, Egypt

3. Department of Operations Research, Faculty of Computers and Informatics, Zagazig University, El-Zera Square, Zagazig, Sharqiyah, Zip code: 44519, Egypt

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2014.03.05

Received: 23 Dec. 2013 / Revised: 23 Jan. 2014 / Accepted: 12 Feb. 2014 / Published: 8 Mar. 2014

Index Terms

Flower pollination algorithm, Harmony search, meta-heuristics, optimization, Sudoku, chaos, evolutionary algorithms

Abstract

Flower Pollination algorithm (FPA) is a new nature-inspired algorithm, based on the characteristics of flowering plants.In this paper, a new hybrid optimization method called improved Flower Pollination Algorithm with Chaotic Harmony Search (FPCHS) is proposed. The method combines the standard Flower Pollination algorithm (FPA) with the chaotic Harmony Search (HS) algorithm to improve the searching accuracy. The FPCHS algorithm is used to solve Sudoku puzzles. Numerical results show that the FPCHS is accurate and efficient in comparison with standard Harmony Search, (HS) algorithm.

Cite This Paper

Osama Abdel-Raouf, Ibrahim El-henawy, Mohamed Abdel-Baset, "A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles", International Journal of Modern Education and Computer Science (IJMECS), vol.6, no.3, pp.38-44, 2014. DOI:10.5815/ijmecs.2014.03.05

Reference

[1]Web http://www.math.cornell.edu/~mec/Summer2009 /Mahmood/Intro.html . Nov. 30, 2013.
[2]Z. W. Geem, "Harmony search algorithm for solving sudoku," in Knowledge-Based Intelligent Information and Engineering Systems, 2007, pp. 371-378.
[3]D. Eppstein, "Nonrepetitive paths and cycles in graphs with application to Sudoku," arXiv preprint cs/0507053, 2005.
[4]A. Caine and R. Cohen, "MITS: A mixed-initiative intelligent tutoring system for sudoku," in Advances in Artificial Intelligence, ed: Springer, 2006, pp. 550-561.
[5]M. Nicolau and C. Ryan, "Solving sudoku with the gAuGE system," in Genetic Programming, ed: Springer, 2006, pp. 213-224.
[6]Y. Takayuki and S. Takahiro, "Complexity and completeness of finding another solution and its application to puzzles," IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, pp. 1052-1060, 2003.
[7]A. Moraglio, J. Togelius, and S. Lucas, "Product geometric crossover for the sudoku puzzle," in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, 2006, pp. 470-476.
[8]A. Kaur and S. Goyal, "A Survey on the Applications of Bee Colony Optimization Techniques," International Journal on Computer Science and Engineering (IJCSE), vol. 3, pp. 3037-3046, 2011.
[9]J. A. Pacurib, G. M. M. Seno, and J. P. T. Yusiong, "Solving sudoku puzzles using improved artificial bee colony algorithm," in Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on, 2009, pp. 885-888.
[10]R. Lewis, "Metaheuristics can solve sudoku puzzles," Journal of heuristics, vol. 13, pp. 387-401, 2007.
[11]A. Moraglio and J. Togelius, "Geometric particle swarm optimization for the sudoku puzzle," in Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, pp. 118-125.
[12]M. C. Machado and L. Chaimowicz, "Combining Metaheuristics and CSP Algorithms to Solve Sudoku," in Games and Digital Entertainment (SBGAMES), 2011 Brazilian Symposium on, 2011, pp. 124-131.
[13]X. Q. Deng and Y. Da Li, "A novel hybrid genetic algorithm for solving Sudoku puzzles," Optimization Letters, vol. 7, pp. 241-257, 2013.
[14]X-S. Yang," Flower pollination algorithm for global optimization", Unconventional Computation and Natural Computation, Lecture Notes in Computer Science, Vol. 7445, pp. 240-249,2012.
[15]H.-O. Peitgen, H. Jürgens, and D. Saupe, Chaos and fractals: new frontiers of science: Springer, 2004.
[16]B. Alatas, "Chaotic harmony search algorithms," Applied Mathematics and Computation, vol. 216, pp. 2687-2699, 2010.
[17]G. Heidari-Bateni and C. D. McGillem, "A chaotic direct-sequence spread-spectrum communication system," Communications, IEEE Transactions on, vol. 42, pp. 1524-1527, 1994.
[18]P. Gaspard, Chaos, scattering and statistical mechanics vol. 9: Cambridge University Press, 2005.
[19]C. Letellier, Chaos in nature vol. 81: World Scientific Publishing Company, 2013.
[20]P. Knight, "Deterministic Chaos: An Introduction," 1988.
[21]Web Sudoku. http://www.websudoku.com/ (Nov. 24, 2013)
[22]Z. Geem, J. Kim, and G. Loganathan, "Harmony search optimization: application to pipe network design," International journal of modelling & simulation, vol. 22, pp. 125-133, 2002.
[23]Z. W. Geem, C.-L. Tseng, and Y. Park, "Harmony search for generalized orienteering problem: best touring in China," in Advances in natural computation, ed: Springer, 2005, pp. 741-750.
[24]J. H. Kim, Z. W. Geem, and E. S. Kim, "Parametersestimationofthenonlinear muskingummodelusingHarmonysearch," JAWRA Journal of the American Water Resources Association, vol. 37, pp. 1131-1138, 2001.
[25]K. S. Lee and Z. W. Geem, "A new structural optimization method based on the harmony search algorithm," Computers & Structures, vol. 82, pp. 781-798, 2004.
[26]M. Mahdavi, M. Fesanghary, and E. Damangir, "An improved harmony search algorithm for solving optimization problems," Applied mathematics and computation, vol. 188, pp. 1567-1579, 2007.
[27]M. G. Omran and M. Mahdavi, "Global-best harmony search," Applied Mathematics and Computation, vol. 198, pp. 643-656, 2008.
[28]Q.-K. Pan, P. N. Suganthan, M. F. Tasgetiren, and J. J. Liang, "A self-adaptive global best harmony search algorithm for continuous optimization problems," Applied Mathematics and Computation, vol. 216, pp. 830-848, 2010.
[29]Q.-K. Pan, P. Suganthan, J. Liang, and M. F. Tasgetiren, "A local-best harmony search algorithm with dynamic subpopulations," Engineering Optimization, vol. 42, pp. 101-117, 2010.
[30]S. Das, A. Mukhopadhyay, A. Roy, A. Abraham, and B. K. Panigrahi, "Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 41, pp. 89-106, 2011.
[31]D. Zou, L. Gao, J. Wu, S. Li, and Y. Li, "A novel global harmony search algorithm for reliability problems," Computers & Industrial Engineering, vol. 58, pp. 307-316, 2010.
[32]Z. W. Geem, K. S. Lee, and Y. Park, "Application of harmony search to vehicle routing," American Journal of Applied Sciences, vol. 2, p. 1552, 2005.

International Journal of Modern Education and Computer Science (IJMECS)