5627

Acceleration of genetic algorithms for sudoku solution on many-core processors

Yuji Sato, Naohiro Hasegawa, Mikiko Sato
Hosei University, Tokyo, Japan
Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, GECCO ’11, 2011

@inproceedings{sato2011acceleration,

   title={Acceleration of genetic algorithms for sudoku solution on many-core processors},

   author={Sato, Y. and Hasegawa, N. and Sato, M.},

   booktitle={Proceedings of the 13th annual conference companion on Genetic and evolutionary computation},

   pages={407–414},

   year={2011},

   organization={ACM}

}

Download Download (PDF)   View View   Source Source   

770

views

In this paper, we use 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 genetic 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 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 Corei7 and NVIDIA GTX460, respectively, and that a correct solution rate of 100% can be achieved in either case.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: