Interval island model initialization for permutation-based problems

ABSTRACT

In the absence of a priori knowledge about global optima, initial populations in genetic algorithms (GAs) should at least be diversified, especially while dealing with large spaces. On the other hand, the use of parallel models for GAs helps to solve large instances. We will focus on the island model. In this paper we propose an island initialization technique for permutation-based problems. We exploit a virtual tree organisation commonly used in exact methods (Branch and Bound) to generate a fully disjoint and well distributed (over the search space) initial population in each island. This method can be used for all permutation-based problems (QAP, Flow-shop, Q3AP..). regardless of the number of permutations. Experiments are performed over Q3AP benchmarks using a $10$ island model. The results shows the efficiency of the proposed method especially for large instances.

REFERENCES

• 1: P. M. Hahn, B.-J. Kim, T. Stutzle, S. Kanthak, W. L. Hightower, Z. D. H. Samra, and M. Guignard. The quadratic three-dimensional assignment problem: Exact and approximate solution methods. European Journal of Operational Research, 184:416--428, 2008.
• 2: M. Mezmaz, N. Melab, and E.-G. Talbi. A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems. In In Proc. of 21th IEEE Intl. Parallel and Distributed Processing Symp., Long Beach, California, March 2007.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
genetic algorithms, island model, permutations and combinations, population initialisation