Graph Based Evolutionary Algorithms - Advancing Artificial Intelligence Through Biological Process Applications - page 319

Table 1. Graphs used in this study with their index name for use in figures. The graphs listed here are
all population size 512.

String Problems

The second string problem is the self-avoiding
walk (SAW) problem. The self-avoiding walk
(SAW) problem uses a string over the alphabet
{up; down; left; right} as its chromosome which
dictate moves made on a grid. Problem difficulty
is related to the grid size, with grid sizes of 3x3,
3x4, 4x4, 4x5, 5x5, 5x6, and 6x6 used so far. The
length of the chromosome is equal to the number
of cells in the grid minus one. A fitness evaluation
is performed by starting in the lower left corner

The first and simplest problem examined is the
one-max problem. This problem uses a string
of 20 bits for a chromosome, with the fitness of
the string being the number of 1's in the string.
Two point crossover and single bit-flip mutation
are used in the problem. This results in a very
simple uni-modal problem with an easy to visual-
ize fitness landscape.