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