1) TITLE gAcceleration of Genetic Algorithms for Sudoku Solution on Many-core Processorsh (gParallelization of Genetic Operations that Takes Building-Block Linkage into Accounth) -------------------------------------------------------------------------- 2) AUTHOR Yuji Sato, Hazuki Inoue and Naohiro Hasegawa Faculty of Computer and Information Sciences, Hosei University 3-7-2 Kajino-cho, Koganei-shi, Tokyo 184-8584, Japan yuji@k.hosei.ac.jp Mikiko Sato Faculty of Engineering, Tokyo University of Agriculture and Technology 2-24-16 Naka-cho Koganei-shi, Tokyo 184-8588, Japan mikiko@namikilab.tuat.ac.jp -------------------------------------------------------------------------- 3) CORRESPONDING AUTHOR Yuji Sato -------------------------------------------------------------------------- 4) ABSTRACT This paper shows the problem of solving Sudoku puzzles to demonstrate the possibility of achieving practical processing time through the use of many-core processors for parallel processing in the application of evolutionary computation. To increase accuracy, we propose a genetic operation that takes building-block linkage into account. As a parallel processing model for higher performance, we use a multiple-population coarse-grained genetic algorithm (GA) model to counter initial value dependence under the condition of a limited number of individuals. The genetic manipulation is also accelerated by the parallel processing of threads. In an evaluation using even very difficult problems, we show that execution times of several tens of seconds and several seconds can be obtained by parallel processing with the Intel Core i7 and NVIDIA GTX 460, respectively, and that a correct solution rate of 100% can be achieved in either case. In addition, genetic operations that take linkage into account are suited to fine-grained parallelization and thus may result in an even higher performance. -------------------------------------------------------------------------- 5) CRITERIA SATISFIED BY THE WORK B) "The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal." C) "The result is equal to or better than a result that was placed into a database or archive of results maintained by an internationally recognized panel of scientific experts." -------------------------------------------------------------------------- 6) Statement stating why the result satisfies the criteria that the contestant claims This work satisfies the criteria listed above for the following reasons. Sudoku was devised by an American architect and currently major fad in England and is spreading in popularity around the world, including Japan. Human can create the exact solution for the super difficult Sudoku [*1], but basically it takes more than several ten minutes. On the other hand, Genetic algorithms (GA), one method of stochastic search, are effective for large combinatorial optimization problems. That has motivated research on applying GA to solve Sudoku [*1], and there are reports on success with relatively simple puzzles that have many given numbers in the initial placement. For difficult puzzles in which there are fewer given numbers, however, the number of generations needed to reach the optimum solution becomes enormous and the probability of obtaining a solution in realistic time becomes small. To against that problem, we proposed genetic operation that takes building-block linkage into account for Sudoku and accelerated GAs on many-core processors. As a result, now we can solve the super difficult Sudoku in several seconds on GTX 460 or less than one second on GTX 580 GPU and a correct solution rate of 100% can be achieved. [*1] Project work ? Solving Sudokufs with using Evolutionary algorithms: http://lipas.uwasa.fi/~timan/sudoku/EA_ht_2008.pdf#search='CT20A6300%20Alternative%20Project%20work%202008' cited June 3, 2013 -------------------------------------------------------------------------- 7) CITATIONS This submission is based on the following book chapter and journal: [1] Yuji Sato, Naohiro Hasegawa and Mikiko Sato (2013) Acceleration of Genetic Algorithms for Sudoku Solution on Many-core Processors, S. Tsutsui and P. Collet (Eds.), Massively Parallel Evolutionary Computation on GPGPUs (Natural Computing Series), Chap. 19, Springer, ISSN 978-3642379581. [2] Yuji Sato, Hazuki Inoue, and Mikiko Sato (2012) Parallelization of Genetic Operations that Takes Building-Block Linkage into Account, Int'l J. Artificial Life and Robotics, 17/ 1, 17-23, Springer, DOI: 10.1007/s10015-012-0012-x. (http://link.springer.com/content/pdf/10.1007%2Fs10015-012-0012-x.pdf) Related support material: [3] Yuji Sato, Naohiro Hasegawa, and Mikiko Sato (2011) "Acceleration of Genetic Algorithms for Sudoku Solution on Many-core Processors", Proceedings of the 2011 ACM/SIGEVO GECCO Workshop on Computational Intelligence on Consumer Games and Graphics Hardware CIGPU-2011, 407-414. (http://delivery.acm.org/10.1145/2010000/2002027/p407-sato.pdf?ip=133.25.249.7&acc=ACTIVE%20SERVICE&key=C2716FEBFA981EF1CA5BE91BEAA67DAA342B57BF4F65CC15&CFID=334441982&CFTOKEN=91025499&__acm__=1370231071_1154f1be7b6b92e271f230a7700d9f2a) [4] Yuji Sato, Naohiro Hasegaw, and Mikiko Sato (2011) "GPU Acceleration for Sudoku Solution with Genetic Operations", Proceedings of the 2011 IEEE Congress on Evolutionary Computation (CEC-2011). (http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=05949632) [5] Yuji Sato and Hazuki Inoue (2010) "Solving Sudoku with Genetic Operations that Preserve Building Blocks", Proceeding of the 2010 IEEE Conference on Computational Intelligence and Games, 23-29. (http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=05593375) -------------------------------------------------------------------------- 8) STATEMENT OF PRIZE ALLOCATION The prize money, if any, is to be divided; 60% to Yuji Sato, 20% to Mikiko Sato, and the remaining equally among the co-authors. -------------------------------------------------------------------------- 9) WHY THE JUDGES SHOULD CONSIDER THIS ENTRY PUSHING EVOLUTION FURTHER ------------------------- This is the most difficult Sudoku puzzle for evolutionary computation can solved first time (so successfully in realistic time) with new approach. SEVERAL DEGREES OF IMPROVEMENT ----------------------------------------------- 1) At first, we have proposed genetic operation that takes linkage into account for Sudoku and improved the accuracy for the super difficult Sudoku from 5% [*1] to 83% (up to 100,000 generations). 2) Next, we implemented a multiple-population coarse-grained genetic algorithm (GA) model to counter initial value dependence under the condition of a limited number of individuals and the genetic manipulation is also accelerated by the parallel processing of threads. As a result, we have accelerated the execution time from about 20 minutes on CPU to several seconds on GTX 460 or less than one second on GTX 580 and a correct solution rate of 100% also can be achieved. SOLVING A DIFFICULT PROBLEM IN REAL WORLD ----------------------------------------------- Difficult puzzles, involving search and planning problems, have a longstanding tradition in the AI community. Among them, Sudoku is spreading in popularity around the world and one of the real world problems. We have showed that an appropriate design of genetic manipulation and parallelization on many-core processors can solve a difficult real-world problem (super difficult Sudoku) in realistic time.