Redundant Genetic Encodings May Not Be Harmful Bryant A. Julstrom Department of Computer Science St. Cloud State University St. Cloud, MN 56301 USA julstrom@eeyore.stcloudstate.edu ------------------------------------------------------------------------ In /Proceedings of the Genetic and Evolutionary Computation Conference/ (GECCO'99) (Wolfgang Banzhaf, Jason Daida, Agoston E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith, Eds.). San Francisco, CA: Morgan Kaufmann Publishers, 1999, p.791. ------------------------------------------------------------------------ Summary In a redundant genetic encoding, several distinct chromosomes represent each candidate solution to the target problem. Such an encoding would seem to hinder genetic search by allowing competing representations of the same information. Tests using a GA for the 3-cycle problem (3CP), which seeks to partition /n/ = 3/k/ points in the plane into 3-cycles of minimum total length, indicate that this is not necessarily so. Three encodings of the problem's solutions have much, some, and no redundancy. All number the target instance's points and represent sets of 3-cycles as permutations of those numbers. In the most redundant encoding, the first three points a chromosome lists form a cycle, the next three points form another, and so on. In this encoding, 6^/n//3 (/n//3)! permutations represent each set of 3-cycles on /n/ points. A less redundant encoding sorts the integers within each triple, so that (/n//3)! chromosomes represent each set of 3-cycles. Finally, a non-redundant encoding also sorts the triples by their first values, so that the mapping from chromosomes to solutions is one-to-one. A reasonable crossover for these encodings is Partially Mapped Crossover (PMX) (Goldberg and Lingle, 1985) which randomly chooses a segment within one parent, then swaps symbols within that parent until the segment is identical to the same positions in the second parent. Mutation can swap the symbols in two random positions of the parent chromosome. The three encodings were compared in a generational genetic algorithm that initializes its population randomly, selects parents in 2-tournaments, and applies PMX and mutation independently. It is 1-elitist and runs through a fixed number of generations. This GA was run, with each encoding, on six instances of 3CP. Three of the data sets are well known traveling salesman problem instances. The others consist of points randomly placed on a 100 by 100 grid. The number of points used was always a multiple of three. In these tests, the GA's population contained 2/n/ chromosomes. The probability that crossover would produce an offspring was 70%; that of mutation therefore 30%. The GA ran through 10/n/ generations, and it was run 50 times with each encoding on each test instance. Table 1 shows the results of these trials. Contradicting conventional expectations, the GA performed best with the two redundant encodings and worst with the non-redundant encoding. *Table 1.* Averages over 50 trials with each encoding. Problem (/n/) Most redundant Less redundant Non- redundant rand42 (42) 603.25 608.62 613.68 eil51 (51) 501.63 498.70 503.37 rand60 (60) 679.17 685.80 694.89 eil76 (76) 629.22 629.16 653.45 rand90 (90) 887.95 895.20 927.42 kroA100 (99) 23981.87 24097.53 26796.28 There are several possible explanations for these results. First, the redundant encodings allow more locality. Second, cross-competition between building blocks may not hinder the GA's search as much as is often suggested. Third, with the redundant encodings, the population may form subpopulations around particular representations of good sub-solutions; one of these subpopulations eventually controls the population's evolution. Finally, under PMX, many pairs of redundant chromosomes are effectively the same. Reference D. E. Goldberg and R. Lingle, Jr. (1985). Alleles, loci, and the traveling salesman problem. In J. J. Greffenstette, ed., /Proceedings of the First ICGA/, pp.154-159. Hillsdale, NJ: Lawrence Erlbaum.