The limitations of node pair features for bisection problems

S. A. Harrison, V. J. Rayward-Smith

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)101-107
Number of pages7
JournalNeural Network World: International Journal on Neural and Mass-Parallel Computing and Information Systems
Issue number2
Publication statusPublished - 2001

Cite this