The Limitations of Node Pair Features for Bisection Problems

A key stage in the design of an effective and efficient genetic algorithm is the utilisation of domain specific knowledge. Once appropriate features have been identified, genetic operators can then be designed which manipulate these features in well defined ways. In particular, the crossover operator is designed so as to preserve in any offspring features common to both parental solutions and to guarantee that only features that appear in the parents appear in the offspring. Forma analysis provides a well-defined framework for such a design process. In this paper we consider the class of bisection problems. Features proposed for set recombination are shown to be redundant when applied to bisection problems. Despite this inherent redundancy, approaches based on such features have been successfully applied to graph bisection problems. In order to overcome this redundancy and to obtain performance gains over previous genetic algorithm based approaches to graph bisection a natural choice of features is one based on node pairs. However, such features result in a crossover operator that displays degenerative behaviour and is of no practical use.