The limitations of node pair features for bisection problems

Harrison, S. A. and Rayward-Smith, V. J. (2001) The limitations of node pair features for bisection problems. Neural Network World: International Journal on Neural and Mass-Parallel Computing and Information Systems, 11 (2). pp. 101-107. ISSN 1210-0552

Full text not available from this repository. (Request a copy)


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.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 18 Aug 2011 11:51
Last Modified: 15 Dec 2022 01:49

Actions (login required)

View Item View Item