Illinois Genetic Algorithms Laboratory

Goldberg, D.E., Deb, K., Kargupta, H., Harik, G. (1993)
TR No.: 93004 | Download PDF | Download PS

Abstract:
Researchers have long sought genetic algorithms (GAs) that can solve difficult search, optimization, and machine learning problems quickly. Despite years of work on simple GAs and their variants it is still unknown how difficult a problem simple GAs can solve, how quickly they can solve it, and with what reliability. More radical design departures than these have been taken, however, and the messy GA (mGA) approach has attempted to solve problems of bounded difficulty quickly and reliably by taking the notion of building-block linkage quite seriously. Early efforts were apparently successful in achieving polynomial convergence on some difficult problems, but the initialization bottleneck that required a large initial population was thought to be the primary obstacle to faster mGA performance. This paper replaces the partially enumerative initialization and selective primordial phase of the original messy GA with probabilistically complete initialization and a primordial phase that performs building-block filtering via selection and random gene deletion. In this way, the fast mGA is able to evaluate the best building blocks from modestly sized populations of longer strings, thereafter cutting down the string length by throwing off the genes of lesser importance. Design calculations are performed for population sizing, selection-deletion timing, and genic thresholding. On problems of bounded difficulty, ranging from 30-bits to 150-bits, the fast mGA finds global optima reliably in a time that both theoretically and empirically grows no more quickly than a subquadratic function of the number of decision variables. The paper outlines the key remaining challenges and suggests extension of the technique to other-than-binary structures.