Epistasis in Genetic Algorithms: An Experimental Design Perspective
Colin R. Reeves, Christine C. Wright · 1995
In an earlier paper we examined the relationship between genetic algorithms (GAs) and traditional methods of experimental design. This was motivated by an investigation into the problems caused by epistasis in the implementation and application of GAs to optimization problems. We showed how this viewpoint enables us to gain further insights into the determination of epistatic effects, and into the value of different forms of encoding a problem for a GA solution. We also demonstrated the equivalence of this approach toWalsh transform analysis. In this paper we consider further the question of whether the epistasis metric actually gives a good prediction of the ease or difficulty of solution of a given problem by a GA. Our original analysis assumed, as does the rest of the related literature, knowledge of the complete solution space. In practice, we only ever sample a fraction of all possible solutions, and this raises significant questions which are the subject of...