Inequality’s Arrow: The Role of Greed and Order in Genetic Algorithms

Anil Menon

Abstract. Moderated greedy search is based on the idea that it is helpful for greedy search algorithms to make non-optimal choices “once in a while.” This notion can be made precise by using the majorization-theoretic approach to greedy algorithms. Majorization is the study of pre-orderings induced by doubly stochastic matrices. A majorization operator when applied to a distribution makes it “less unequal,” where inequality is defined with respect to a very wide class of measures known as Schur-convex functions. It is shown that proportional selection, point crossover and point mutations are all majorization operators. It is also shown that with respect to the majorization-theoretic definition, the standard GA is a moderated greedy algorithm. Some consequences of this result are discussed.

LNCS 3102, p. 1352 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004