A crossover for complex building blocks overlapping

ABSTRACT

We propose a crossover method to combine complexly overlapping building blocks (BBs). Although there have been several techniques to identify linkage sets of loci o form a BB [4, 6, 7, 10, 11], the way to to realize effective crossover from the linkage information from such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu et al. [13] is the first and only known research, however it cannot perform well for problems with complexly overlapping BBs due to insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings minutely and defines which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. The method is combined with a scalable linkage identification technique to construct an efficient algorithm for problems with overlapping BBs. We design test functions with controllable complexity of overlap and test the method with the functions.

REFERENCES

• 1: L. Booker. Improving search in genetic algorithms. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, pp. 61--73. Morgan Kaufmann, 1987.
• 2: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 3: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 4: R. B. Heckendorn and A. H. Wright. Efficient linkage discovery by limited probing. In Genetic and Evolutionary Computation - GECCO2003 Part 1, Lecture Notes in Computer Science 2723, LNCS 2723, pp. 1003--1014. Springer-Verlag, 2003.
• 5: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 6: Hillol Kargupta , Byung-hoon Park, Gene Expression and Fast Construction of Distributed Evolutionary Representation, Evolutionary Computation, v.9 n.1, p.43-69, January 2001 [doi>10.1162/10636560151075112]
• 7: M. Munetomo and D. E. Goldberg. Identifying linkage groups by nonlinearity/non-monotonicity detection. In Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp. 433--440. Morgan Kaufmann Publishers, 7 1999.
• 8: M. Munetomo and D. E. Goldberg. Linkage identification by non-monotonicity detection for overlapping functions. Technical Report IlliGAL Report No.99005, University of Illinois at Urbana-Champaign, 1 1999.
• 9: M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp. 525--532. Morgan Kaufmann Publishers, 1999. ftp://ftp-illigal.ge.uiuc.edu/pub/src/sBOA/C++/sBOA.tar.Z.
• 10: M. J. Streeter. Upper bounds on the time and space complexity of optimizing additively separable functions. In Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science 3103, pp. 186--197. Springer-Verlag, 2004.
• 11: M. Tsuji, M. Munetomo, and K. Akama. Modeling dependencies of loci with string classification according to fitness differences. In Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science 3103, pp. 246--257. Springer-Verlag, 2004.
• 12: T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-P. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. In Proceedings of Artificial Neural Networks in Engineering 2003 (ANNIE 2003), pp. 327--332, 6 2003.
• 13: Tian-Li Yu , Kumara Sastry , David E. Goldberg, Linkage learning, overlapping building blocks, and systematic strategy for scalable recombination, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068209]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
building blocks, crossover, linkage