Solving Japanese nonograms by Taguchi-based genetic algorithm

摘要

A Taguchi-based genetic algorithm (TBGA) is proposed to solve Japanese nonogram puzzles. The TBGA exploits the power of global exploration inherent in the traditional genetic algorithm (GA) and the abilities of the Taguchi method in efficiently generating offspring. In past researches, the GA with binary encoding and inappropriate fitness functions makes a huge search space size and inaccurate direction for searching the solution of a nonogram. Consequently, the GA does not easily converge to the solution. The proposed TBGA includes the effective condensed encoding, the improved fitness function, the modified crossover, the modified mutation, and the Taguchi method for solving Japanese nonograms. The systematic reasoning ability of the Taguchi method is incorporated in the modified crossover operation to select the better genes to achieve crossover, and eventually enhance the GA. In this study, the condensed encoding can make sure 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 TBGA approach is effectively applied to solve nonograms and better than a GA does.