Analysis of the performance of genetic multi-step search in interpolation and extrapolation domain

ABSTRACT

In this paper, we examine overall performances and behaviors of deterministic multi-step search in interpolation / extrapolation domain, dMSXF and dMSMF, using NK model that is one of appropriate models for analyzing fundamental search mechanisms in combinatorial problems. We focus on the local property of landscape, such as epistasis that is comprehended as ruggedness in fitness function, and investigate the efficacy of dMSXF and dMSMF and the behavior observed by tuning the level of epistasis.

REFERENCES

• 1: Extrapolation-Directed Crossover for Job-shop Scheduling Problems: Complementary Combination with JOX, Proc. of GECCO 2000, pp. 973--980 (2000).
• 2: Kokolo Ikeda , Shigenobu Kobayashi, Deterministic Multi-step Crossover Fusion: A Handy Crossover Composition for GAs, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.162-171, September 07-11, 2002
• 3: Yoshiko Hanada , Tomoyuki Hiroyasu , Mitsunori Miki, Genetic multi-step search in interpolation and extrapolation domain, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277197]
• 4: Adaptation on rugged fitness landscapes, Lectures in the Sciences of Complexity, Vol. 1, pp.527--618, Addison Wesley (1989).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms

Keywords:
NK Model, combinatorial optimization, genetic algorithm, local search