Quality time tradeoff operator for designing efficient multi level genetic algorithms

ABSTRACT

We present a novel cost benefit operator that assists multi levelgenetic algorithm searches. Through the use of the cost benefitoperator, it is possible to dynamically constrain the search of thebase level genetic algorithms, to suit the users requirements. We note that the current literature has abundant studies on metaevolutionary GAs, however these approaches have not identifiedan efficient approach to the termination of base GA searchs or ameans to balance practical consideration such as quality ofsolution and the expense of computation. Our Quality timetradeoff operator (QTT) is user defined, and acts as a base leveltermination operator and also provides a fitness value for themeta-level GA. In this manner, the amount of computation timespent on less encouraging configurations can be specified by theuser. Our approach was applied to a computationally intensive test problem which evaluates a large set of configuration settings forthe base GAs to find suitable configuration settings (populationsize, crossover operator and rate, mutation operator and rate,repair or penalty and the use of adaptive mutation rates) forselected TSP problems.

REFERENCES

• 1: R. Sosic and G. D. Wilby, "Using the Quality-Time Tradeoff in Local optimization.," Proceedings of the IEEE Second ANZIIS Conference, pp. 253--257, 1994.
• 2: G. G. Mitchell, "Validity Constraints and the TSP-GeneRepair of Genetic Algorithms.," Artificial Intelligence and Applications, pp. 306--311, 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
cost benefit operator, fitness, multi level genetic algorithms