lthough genetic algorithms are increasingly used in difficult problems, their principles of operation are oftentimes misunderstood. Moreover, it is not widely recognized that an integrated, bounding GA design theory was completed in 1993, and that the theory has been used to show (1) the performance shortcomings of simple GAs, and (2) how to overcome them with a new generation of broadly competent GAs.

This talk reviews the principles of selectorecombinative genetic algorithms and shows how a principled design methodology leads to a better understanding of extant GAs and a means to consistently overcome their limitations. Specifically, a design decomposition that combines an understanding of building blocks (BBs), BB supply, growth, decision making, difficulty, and mixing is examined, and key elements of that decomposition are used to show the connection between GA operations and convergence quality and speed. Three examples of next generation GAs that solve hard problems in what appears to be subquadratic PAC (probably approximately correct) time are also given: fast messy GAs (fmGAs), gene expression messy GAs (gemGAs), and linkage learning GAs (LLGAs). Beyond the development of such competent GAs is the realm of efficiency. The talk concludes by highlighting four avenues of efficient resource utilization: space (parallelization), time (multiple epochs), function evaluation (sampling and other error-prone relaxations), and hybridization (combinations of GAs with other procedures). Together, these efforts are leading to the everyday GA solution of difficult problems, quickly, reliably, and accurately.

Back to Workshop Schedule