An evolutionary approach to search for NCR-boards
C.R. Chow · 2002
An NCR (non-chromatic rectangle) board is a chessboard in which the squares can be colored in such a way that no rectangle has four corners that are of the same color. The search space for finding a 10/spl times/10 NCR-board with three colors, is so large, 3/sup 100/, that traditional search techniques may be inefficient or even impractical. While genetic algorithms (GAs) usually have problems zeroing in on the global optimal solution, the NCR-board problem demands a perfect solution; a near-optimal solution is simply not good enough. A wrong-step in this case is frequently a big one. In addition, local hill-climbing, which usually helps a GA to reach the absolute global optimum, has been shown to be ineffective in the experiments. This paper investigates the application of GA techniques to search for a three-colored 10/spl times/10 NCR-board. Special strategies to avoid premature convergence to near-optimal solutions are analyzed and discussed.