Landscape classification and problem specific reasoning for genetic algorithms

Abstract

Purpose

This paper addresses issues dealing with genetic algorithm (GA) convergence and the implications of the No Free Lunch Theorem which states that no single algorithm outperforms all others for all possible problem landscapes. In view of this, the authors propose that it is necessary for a GA to have the ability to classify the problem landscape before effective parameter adaptation may occur.

Design/methodology/approach

The new hybrid intelligent system for landscape classification is proposed. This system facilitates intelligent operator selection and parameter tuning during run time in order to achieve maximum convergence. This work introduces two adaptive crossover techniques, the runtime adaptation of crossover probability and the participation level of multiple crossover operators in order to refine the quality of the search and to regulate the trade‐off between local and global search respectively. In addition, a Rule‐Based reasoning system (RS) is presented which can be utilised to analyse the problem landscape and provide a supervisory element to a GA. This RS is capable of instigating change by utilising the analysis in order to counteract premature convergence, for various classes of problems.

Findings

Results are presented which show that the application of this Rule‐Based system and the adaptive crossover techniques proposed in this paper significantly improve performance for a suite of relatively complex test problems.

Originality/value

This work demonstrates the effectiveness of landscape classification and consequent rule‐based reasoning for GAs, particularly for problems with a difficult path to the optimal. Moreover, both adaptive crossover techniques proposed present improved performance over the traditional static parameter GA.

Citation

Mac Giolla Bhríde, F., McGinnity, T.M. and McDaid, L.J. (2005), "Landscape classification and problem specific reasoning for genetic algorithms", Kybernetes, Vol. 34 No. 9/10, pp. 1469-1495. https://doi.org/10.1108/03684920510614777