Solving the sudoku with the differential evolution

• Autorzy: Boryczka U. , Juszczuk P.

Warianty tytułu

PL

Ewolucja różnicowa w rozwiązywaniu Sudoku

• Języki publikacji: EN

Abstrakty

EN

In this paper, we present the application of the Differential Evolution (DE) algorithm to solving the combinatorial problem. The advantage of the DE algorithm is its capability of avoiding so-called "local minima" within the considered search space. Thanks to the special operator of the adaptive mutation, it is possible to direct the searching process within the solution space. The DE algorithm applies the selection operator that selects from the child population only the offspring with the greater value of the fitness function in comparison to their parents. An algorithm applied to a combinatorial optimization problem: Sudoku puzzle is presented. Sudoku consists of a nine by nine grid, divided into nine three by three boxes. Each of the eighty-one squares should be filled in with a number between one and nine. In this article we show, that the mutation schema has significant impact on the quality of created solution.

PL

W artykule przedstawimy propozycję zastosowania algorytmu ewolucji różnicowej do rozwiązywania problemów kombinatorycznych. Przewagą ewolucji różnicowej jest zdolność do unikania optimów lokalnych w przestrzeni przeszukiwań. Specjalny operator mutacji pozwala ukierunkować proces poszukiwań rozwiązania. W ewolucji różnicowej stosowany jest operator selekcji, który promuje tylko najlepiej przystosowane osobniki z populacji rodziców i potomków. Przedstawimy zastosowanie opisanego algorytmu do problemu rozwiązywania Sudoku. Sudoku składa się z planszy 9 na 9, podzielonej na 9 sekcji -każda o rozmiarze 3 na 3 elementy. Każda z 81 kratek powinna zostać wypełniona wartością z przedziału 1 do 9. W artykule pokażemy, że ewolucja różnicowa pozwala na rozwiązywanie Sudoku.

Słowa kluczowe

EN

differential evolution; sudoku; discrete optimization

PL

ewolucja różnicowa; sudoku; dyskretna optymalizacja

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2012
• Tom: Z. 9
• Strony: 5--16
• Opis fizyczny: Bibliogr. 21 poz., rys., tab., wykr.

Twórcy

autor

Boryczka U.

autor

Juszczuk P.

• Silesian University, Institute of Computer Science, ul. Bedzinska 39, Sosnowiec, Poland

Bibliografia

• [1] D. Ardel, TOPE and magic squares: a simple GA approach to combinatorial optimization, 1994, pp. 1–6.
• [2] B. Felgenhauer, Jarvis F.,Mathematics of Sudoku I, 2006.
• [3] B. Felgenhauer, Jarvis F., Mathematics of Sudoku II, 2006.
• [4] M. Gold, Using Genetic Algorithms to come up with Sudoku Puzzles, 2005.
• [5] K. U. Kasemir, K. Betzler., Detecting ellipses of limited eccentricity in images with high noise levels, Journal Image and Vision Computing, Vol. 21, 2003, pp. 221–227.
• [6] J. Lauriere, A language and a program for stating and solving combinatorial problems, Journal of Artificial Intelligence, Vol. 10, 1978, pp. 29–127.
• [7] E. Lawler, Kan A. Rinnooy, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, 1985.
• [8] I. Lynce, J. Ouaknine, Sudoku as a SAT Problem, Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics, 2006
• [9] George D. Magoulas, Michael N. Vrahatis, George S. Androulakis, Effective backpropagation training with variable stepsize, Journal of Neural Networks, Vol. 10, No. 1, 1997, pp. 69–82.
• [10] T. Mantere, J. Koljonen, Solving, rating and generating Sudoku puzzles with GA, IEEE Congress on Evolutionary Computation 2007, 2007, pp. 1382–1389.
• [11] S. McGerty, Solving Sudoku Puzzles with Particle Swarm Optimisation, Final Report, Macquarie University 2009.
• [12] A. Moraglio, C. Di Chio, J. Togelius and R. Poli, Geometric Particle Swarm Optimization - Research Article, Journal of Artificial Evolution and Applications, Vol. 2008, 2007.
• [13] A. Moraglio, J. Togelius, Geometric Particle Swarm Optimization for the Sudoku Puzzle, GECCO 2007, Genetic and Evolutionary Computation Conference, 2007.
• [14] A. Moraglio, J. Togelius, Geometric differential evolution, GECCO 2009, Genetic and Evolutionary Computation Conference, 2009, pp. 1705–1712.
• [15] D. Mullaney, Using Ant Systems to Solve Sudoku Problems, University College Dublin.
• [16] H. Simonis, Sudoku as a constraint problem, Proceedings 4th Int. Works. Modelling and Reformulating Constraint Satisfaction Problems, 2005, pp. 13–27
• [17] R. Storn, K. Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, Vol. 11, 1997, pp. 341–359.
• [18] R. Storn, Differential evolution design of an IIR-filter, IEEE International Conference on Evolutionary Computation ICEC’96, 1996, pp. 268–273
• [19] R. Storn, On the Usage of Differential Evolution for Function Optimization, AFIPS’96, 1996, pp. 519–523.
• [20] T. Weber, A SAT-based Sudoku solver, 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2005, 2005, pp. 11–15.
• [21] T. Yato, Complexity and Completeness of Finding Another Solution and its Application to Puzzles, IEICE - Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 5, 2003, pp. 1052–1060.