Illinois Genetic Algorithms Laboratory

Khan, N. (2003)
TR No.: 2003021 | Download PDF | Download PS

Abstract:
In the last two decades significant progress has been made in the
theory and design of competent genetic algorithms—genetic algorithms
(GAs) that solve hard problems quickly, reliably, and accurately
(Goldberg, 2002). In contrast to the first generation GAs which use
fixed recombination operators, competent GAs employ recombination
operators that adapt linkages. Competent GAs have been shown to solve
problems of bounded difficulty in polynomial (usually subquadratic)
time.

Parallel to the progress in the theory of competent GAs,
there has been a growing interest in multiobjective optimization in
general and multiobjective genetic algorithms (MOGAs) in
particular. However, similar to the first generation GAs, existing
MOGAs use fixed genetic operators and there is a need to develop
competent MOGAs—GAs that solve hard multiobjective problems quickly,
reliably, and accurately.

This study combines the selection scheme
of NSGA-II (Deb, Agrawal, Pratap, & Meyarivan, 2000), a multiobjective GA, with the linkage learning capabilities of two powerful single objective competent GAs, BOA (Pelikan, Goldberg, & Cantú-Paz, 1999) and hBOA (Pelikan & Goldberg, 2000), to form two
competent MOGAs called multiobjective Bayesian optimization algorithm
(mBOA) and multiobjective hierarchical Bayesian optimization algorithm
(mhBOA), respectively. A test suite of additively decomposable
problems with controllable difficulty has also been developed in a
principled manner to test both mBOA and mhBOA. Results show that while
mBOA is capable of solving boundedly difficult problems with variable
interactions at a single level, mhBOA is also able to solve
hierarchically difficult problems.