Learning Representations for Evolutionary Computation
Thorsten Schnier, John S. Gero · 2007
Evolutionary systems have been used in a variety of applications, from turbine design to scheduling problems. The basic algorithms are similar in all these applications, but the representation is always problem specific. Unfortunately, the search time for evolutionary systems very much depends on efficient codings, using problem specific domain knowledge to reduce the size of the search space. This paper describes an approach, where the user only specifies a very general, basic coding that can be used in a larger variety of problems. The system then learns a more efficient, problem specific coding. To do this, an evolutionary system with variable length coding is used. While the system optimizes an example problem, a meta process identifies successful combinations of genes in the population and combines them into higher level evolved genes. The extraction is repeated iteratively, allowing genes to evolve that have a high level complexity and encode a high number of the original, basic genes. This results in a continuous restructuring of the search space, allowing potentially successful solutions to be found in much shorter search time. The evolved coding can then be used to solve other, related problems. While not excluding any potentially desirable solutions, the evolved coding makes knowledge from the example problem available for the new problem. The paper shows an example from the domain of two-dimensional shape designs. In this example, a coding is evolved that uses 320 evolved gene, encoding on average 17 basic genes. The evolved coding is successfully used to optimize a room layout, where the original coding converges to a local maximum in fitness and therefore does not find any feasible solutions. 1