Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively.
| Published in | Automation, Control and Intelligent Systems (Volume 1, Issue 5) |
| DOI | 10.11648/j.acis.20130105.13 |
| Page(s) | 113-120 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2013. Published by Science Publishing Group |
Swarms, Agents, Elitist, Evolutionary Algorithms, Constraints, Fitness Function
| [1] | Abarghouei, A., Ghanizadeh, A and Shamsuddin, S., (2009): Advances in soft computing methods in edge detection, J. Advance Soft Comp. Applications, ISSN: 2074-8523, 1(2). |
| [2] | Cantu-Paz, E and Goldberg, D.E., (2000): Efficient parallel genetic algorithms: theory and practices, Computer methods in applied mechanics and engineering, 186(2-4), pp 221-238. |
| [3] | Coello, C. A., Pulido, G. T and Lechuga, M.S., (2002): Handling multiple objectives with particle swarm optimization, Evo. Comp., Vol. 8, pp 256–279. |
| [4] | Hassan, R and Crosswley, W., (2004): Variable population-based sampling for probabilistic design optimization and with a genetic algorithm, AIAA-2004-0452), 42nd Aerospace Science meeting, Reno, NV. |
| [5] | Hassan, R., Cohanin, B., De Wec and Venter, G., (2006): Comparism of PSO and GA, American Institute of Aeronautic and Astronautics (AIAA-2006), 44th Aerospace Science meeting, Washington–DC. |
| [6] | Heppner, H and Grenander, U (1990): A stochastic non-linear model for coordinated bird flocks, In Krasner, S (Ed.), The ubiquity of chaos, (pp. 233–238). Washington: AAAS. |
| [7] | History of Sudoku, Conceptis Editoria, [online]: www.conceptispuzzle.com/articles/sudoku, last accessed 17-01-2013. |
| [8] | Kilic, A. and Kaya, M.A (2001): A new local search algorithm based on genetic algorithms for the n-queens problem, Proc. Genetic and Evo. Comp. conf. (GECCO-2001), 158 – 161 |
| [9] | Lewis, R., (2007): Metaheuristics can solve Sudoku, J. Heuristics Archive, 13(8), pp 387 – 401 |
| [10] | Mantere, T and Koljonen, J., (2007): Solving and rating Sudoku puzzles via genetic algorithm, Proc. Congress on Evol. Comp.,1382-1389. |
| [11] | Moraglio, A and Togelius, J., (2007): Geometric particles swarm optimization for Sudoku puzzle, http://julian.togelius.com/Moraglio2007Geomet-ric.pdf, last accessed 16-January-2013. |
| [12] | Ojugo, A., Eboka, A., Yoro, E., Okonta, E and Aghware, F.O., (2012): Genetic algorithm rule-based intrusion detection system, J. Emerging Trends in Comp. Info. Syst., ISSN: 2079-8407, 3(8), pp 1182-1194 |
| [13] | Ojugo, A.A., (2012): Gravitational search neural network algorithm for rainfall runoff modeling, Unpublished PhD thesis, Abakiliki: Ebonyi State University, Nigeria. |
| [14] | Perez, M and Marwala, T., (2011): Stochastic optimization approaches for solving Sudoku, Proc. IEEE Congress on Evo. Comp., pp 256–279, Vancouver: Piscataway. |
| [15] | Poli, R., Wright A., McPhee, N and Langdon, W., (2006b): Emergent behaviour, population based search and low-pass filtering, Proc. on Comp. Intelligence and Evo.Comp., pp395-402, Vancouver: Piscataway |
| [16] | Reynolds, R., (1994): An introduction to cultural algorithms, Proc. of 3rd Annual Conf. on Evo. Programming, River Edge: New Jersey, World Scientific, pp 131-139. |
| [17] | Santos-Garcia, G and Palomino, M., (2007): Solving the Sudoku puzzle with rewriting rules, Notes on Theo. Computer Sci., 17(4), pp79-93 |
APA Style
A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, et al. (2013). A Comparative Evolutionary Models for Solving Sudoku. Automation, Control and Intelligent Systems, 1(5), 113-120. https://doi.org/10.11648/j.acis.20130105.13
ACS Style
A. A. Ojugo.; D. Oyemade.; R. E. Yoro.; A. O. Eboka.; M. O. Yerokun, et al. A Comparative Evolutionary Models for Solving Sudoku. Autom. Control Intell. Syst. 2013, 1(5), 113-120. doi: 10.11648/j.acis.20130105.13
AMA Style
A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, et al. A Comparative Evolutionary Models for Solving Sudoku. Autom Control Intell Syst. 2013;1(5):113-120. doi: 10.11648/j.acis.20130105.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.acis.20130105.13,
author = {A. A. Ojugo. and D. Oyemade. and R. E. Yoro. and A. O. Eboka. and M. O. Yerokun and E. Ugboh},
title = {A Comparative Evolutionary Models for Solving Sudoku},
journal = {Automation, Control and Intelligent Systems},
volume = {1},
number = {5},
pages = {113-120},
doi = {10.11648/j.acis.20130105.13},
url = {https://doi.org/10.11648/j.acis.20130105.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acis.20130105.13},
abstract = {Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively.},
year = {2013}
}
TY - JOUR T1 - A Comparative Evolutionary Models for Solving Sudoku AU - A. A. Ojugo. AU - D. Oyemade. AU - R. E. Yoro. AU - A. O. Eboka. AU - M. O. Yerokun AU - E. Ugboh Y1 - 2013/11/10 PY - 2013 N1 - https://doi.org/10.11648/j.acis.20130105.13 DO - 10.11648/j.acis.20130105.13 T2 - Automation, Control and Intelligent Systems JF - Automation, Control and Intelligent Systems JO - Automation, Control and Intelligent Systems SP - 113 EP - 120 PB - Science Publishing Group SN - 2328-5591 UR - https://doi.org/10.11648/j.acis.20130105.13 AB - Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively. VL - 1 IS - 5 ER -
Email: