Threshold selecting: best possible probability distribution for crossover selection in genetic algorithms

ABSTRACT

The paper considers the problem of selecting individuals in the current population in Genetic Algorithms for crossover to find a solution of high fitness of a given combinatorial optimization problem. Many different schemes have been considered in literature as possible selection strategies, such as Windowing, Exponential reduction, Linear transformation or normalization and Binary Tournament selection. It is shown that if one wishes to maximize any linear function of the final state probabilities, e.g. the fitness of the best individual of the final population of the algorithm, then the best probability distribution for selecting individuals in each generation is a rectangular distribution over the individuals sorted by their fitness values. This means uniform probabilities have to be assigned to a group of the best individuals of the population but probabilities equal to zero to individuals with fitness ranks higher than a fixed cutoff, which is equal to a certain rank in the sorted fitness vector. The considered strategy is called Threshold Selecting. The proof applies basic arguments of Markov chains and linear optimization and makes only a few assumptions on the underlying principles and hence applies to a large class of Genetic Algorithms.

REFERENCES

• 1: S. Boettcher and A. G. Percus. Extremal Optimization: Methods derived from Co-Evolution. In GECCO-99, Proceedings of the Genetic and Evolutionary Computation Conference, pages 825--832, Orlando, Florida, July 1999.
• 2: P. G. Busacca, M. Marseguerra, and E. Zio. Multiobjective Optimization by Genetic Algorithms: Application to Safety Systems. Reliability Engineering & System Safety, 72(1):59--74, April 2001.
• 3: M. Chakraborty and U. K. Chakraborty. An Analysis of Linear Ranking and Binary Tournament Selection in Genetic Algorithms. In Proceedings of the International Conference on Information, Communications and Signal Processing, pages 407--411, Singapore, September 1997.
• 4: Uday Kumar Chakraborty, A simpler derivation of schema hazard in genetic algorithms, Information Processing Letters, v.56 n.2, p.77-78, Oct. 27, 1995 [doi>10.1016/0020-0190(95)00116-T]
• 5: Uday Kumar Chakraborty, A branching process model for genetic algorithms, Information Processing Letters, v.56 n.5, p.281-292, Dec. 8, 1995 [doi>10.1016/0020-0190(95)00113-X]
• 6: Uday Kumar Chakraborty , Kalyanmoy Deb , Mandira Chakraborty, Analysis of selection algorithms: A markov chain approach, Evolutionary Computation, v.4 n.2, p.133-167, Summer 1996 [doi>10.1162/evco.1996.4.2.133]
• 7: Lance D. Chambers, The Practical Handbook of Genetic Algorithms: Applications, Second Edition, CRC Press, Inc., Boca Raton, FL, 2000
• 8: Gunter Dueck , Tobias Scheuer, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, v.90 n.1, p.161-175, Sept. 1990 [doi>10.1016/0021-9991(90)90201-B]
• 9: Astrid Franz , Karl Heinz Hoffmann, Optimal annealing schedules for a modified Tsallis statistics, Journal of Computational Physics, v.176 n.1, p.196-204, February 10, 2002 [doi>10.1006/jcph.2001.6975]
• 10: A. Franz and K. H. Hoffmann. Threshold Accepting as Limit Case for a Modified Tsallis Statistics. Applied Mathematics Letters, 16(1):27--31, January 2003.
• 11: A. Franz, K. H. Hoffmann, and P. Salamon. Best Possible Strategy for Finding Ground States. Physical Review Letters, 86(23):5219--5222, June 2001.
• 12: Patrice Godefroid , Sarfraz Khurshid, Exploring Very Large State Spaces Using Genetic Algorithms, Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.266-280, April 08-12, 2002
• 13: F. Heilmann, K. H. Hoffmann, and P. Salamon. Best Possible Probability Distribution over Extremal Optimization Ranks. Europhysics Letters, 66(3):305--310, March 2004.
• 14: B. Hemmateenejad, M. Akhond, R. Miri, and M. Shamsipur. Genetic Algorithm Applied to the Selection of Factors in Principal Component-Artificial Neural Networks: Application to QSAR Study of Calcium Channel Antagonist Activity of 1,4-Dihydropyridines (Nifedipine Analogous). Journal of Chemical Information and Modeling, 43(4):1328--1334, June 2003.
• 15: K. H. Hoffmann, F. Heilmann, and P. Salamon. Fitness Threshold Accepting over Extremal Optimization Ranks. Physical Review E, 70(4):046704--+, October 2004.
• 16: S. Kikuchi, D. Tominaga, M. Arita, K. Takahashi, and M. Tomita. Dynamic Modeling of Genetic Networks Using Genetic Algorithm and S-System. Bioinformatics, 19(5):643--650, 2003.
• 17: S. Kirkpatrick, C. Galatt, and M. Vecchi. Optimization by simulated annealing. Science, 4598, 1983.
• 18: A. Kolen. A Genetic Algorithm for the Partial Binary Constraint Satisfaction Problem: an Application to a Frequency Assignment Problem. Statistica Neerlandica, 61(1):4--15, February 2007.
• 19: Heinz Mühlenbein , Dirk Schlierkamp-Voosen, The science of breeding and its application to the breeder genetic algorithm (bga), Evolutionary Computation, v.1 n.4, p.335-360, Winter 1993 [doi>10.1162/evco.1993.1.4.335]
• 20: J.-P. Rennard. Introduction to Genetic Algorithms. http://www.rennard.org/alife/english/gavgb.pdf, 2000. {Online; accessed 29--February-2008}.
• 21: Dipti Srinivasan , Lily Rachmawati, An efficient multi-objective evolutionary algorithm with steady-state replacement model, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144122]
• 22: C. R. Stephens, M. Toussaint, D. Whitley, and P. F. Stadler, editors. Foundations of Genetic Algorithms: 9th International Workshop, FOGA 2007, Mexico City, Mexico, 2007. Springer Berlin.
• 23: C. Tsallis and D. A. Stariolo. Generalized Simulated Annealing. Physica A, 233:395--406, 1996.

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, Theory

Keywords:
crossover selection, genetic algorithms, markov process, master equation, threshold selecting