Learning Intelligent Genetic Algorithms Using Japanese Nonograms

An intelligent genetic algorithm (IGA) is proposed to solve Japanese nonograms and is used as a method in a university course to learn evolutionary algorithms. The IGA combines the global exploration capabilities of a canonical genetic algorithm (CGA) with effective condensed encoding, improved fitness function, and modified crossover and mutation. In this paper, the condensed encoding ensures that the chromosome is a feasible solution in all rows for Japanese nonograms. In the reconstruction process of a Japanese nonogram, the numbers in the left column are used as encoding conditions, and the numbers in the top row with the improved fitness function are employed to evaluate the reconstruction result. From the computational experiments, the proposed IGA approach is applied to solve Japanese nonograms effectively, with better results than using a CGA. The students of the Department of Computer Science, National Pingtung University of Education, Taiwan, have gained practical experience of applying evolutionary algorithms to solve Japanese nonograms using both the proposed IGA and a CGA. The students learn that the IGA can find the right solution of the puzzle effectively, but the CGA cannot. (Contains 4 figures.)