Bayesian Optimization Algorithms for Multiobjective and Hierarchically Difficult Problems


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 component 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 finding boundedly difficult problems with variable interactions at a single level, mhBOA is also able to solve hierarchically difficult problems.