Messy Genetic Algorithms Revisited: Studies in Mixed Size and Scale
David E. Goldberg
University of Illinois at Urbana--Champaign, Urbana, IL 61801 USA
Kalyanmoy Deb
University of Alabama, Tuscaloosa, AL 35487 USA
Bradley Korb
McDonnell Douglas Space Systems Company, Huntsville, AL 35806 USA
Abstract
Genetic algorithms have been finding increasing application to difficult search and optimization problems in science and engineering. As more demands are placed on the methodology, the remaining challenges to the technique have become increasingly apparent, and that they have remained largely unanswered has become less than acceptable to a user base seeking to cash in on the method's oft-repeated promises of robustness. Foremost among these challenges is the so-called linkage problem. In difficult problems---so-called deceptive problems---if needed bits or features are not coded tightly on the artificial chromosome, simple genetic algorithms will be forced to bypass global optima and instead be misled toward less acceptable local optima. Standard suggestions to circumvent this problem through inversion or other reordering operators have not been successful, and it has been suggested that many of these operators are too slow to be of timely use. These difficulties led to the invention of so-called messy genetic algorithms that were introduced in a previous paper. Simply stated, messy genetic algorithms tackle the linkage problem by finding tightly coded building blocks initially and then juxtaposing them to find globally optimal structures. In the original study, a 30-bit, order-three deceptive problem was solved to global optimality, but a number of challenges were posed for the messy methodology. Specifically, nonuniform building block scale and size were highlighted as difficulties that must be overcome if mGAs were to become a technique of general applicability. These challenges have been overcome, and this paper presents theoretical and computational results using mGAs on problems of varying building block size and scale. The problem of nonuniform building block scale is tackled with a technique called genic selective crowding, and the problem of nonuniform building-block size is handled with null bits and tie breaking. Together, these techniques appear to overcome these difficult hurdles, yielding convergence to global optima in problems of bounded deception. Furthermore, this desirable convergence is performed with remarkable efficiency. Theoretical computations are presented that show that mGAs converge in time that grows only as a polynomial function of the number of decision variables on a serial machine and as a logarithmic function of the number of decision variables on a parallel machine with a polynomial number of processors. The paper also suggests a number of extensions and continuations of this work, including the trial of messy floating point codes, messy permutations, and messy classifiers (rules). Although additional basic work is both needed and recommended, the compelling convergence and efficiency demonstrated by mGAs recommends them for immediate application in some of the many tough, blind combinatorial optimization problems of science and engineering that have gone unsolved for want of more tractable solution techniques.
