A key stage in the design of an effective and efficient genetic algorithm is the utilisation of dornain specific knowledge. Once appropriate features have been identified, genetic operators can then be designed which inanipulate these features in well defined ways. In particular, the crossover operátor is designed so as to preserve in any offspring features cominon to both parental solutions and to guarantee that ordy features that appear in the parents appear in the offspring. Forma analysis [1] provides a well-defined frarnework for such a design process.
In this paper we consider the class of bisection problems. Features proposed for set recombination [2] are shown to be redundant when applied to bisection problems. Despite this inherent redundancy, approaches based on such features háve been successfully applied to graph bisection problems [3].
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.