phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes
Many complex problems can be solved by a sequence of steps or simple heuristics. In many cases a good solution relies on both good heuristics and proper ordering of their application. Problems such as creating a constrained path through a graph can be solved in this way if we can find a mechanism for ordering the heuristics. We propose using a genetic algorithm (GA) for this purpose to solve the snake-in-the-box problem. However, the additional layer of abstraction created by heuristics weakens the guiding effects of traditional GA operators. We also propose a new set of GA operators that solve this problem by, in the manipulation of the population, applying information from the paths (snakes) produced by the population members. In addition we show the efficacy of this approach by producing a new record length snake of 98 edges in an eight dimensional hypercube. We also compare our new operators with more traditional ones.
phenotype genetic algorithm heuristics snake hypercube genotype