Catálogo de publicaciones - libros

Genetic algorithms ⦓GAs) [53, 83] are stochastic optimization methods inspired by natural evolution and genetics. Over the last few decades, GAs have been successfully applied to many problems of business, engineering, and science [56]. Because of their operational simplicity and wide applicability, GAs are now becoming an increasingly important area of computational optimization.

The previous chapter showed that variation operators in genetic and evolutionary algorithms can be replaced by learning a probabilistic model of selected solutions and sampling the model to generate new candidate solutions. Algorithms based on this principle are called probabilistic model-building genetic algorithms ⦓PMBGAs) [133]. This chapter reviews most influential PMBGAs and discusses their strengths and weaknesses. The chapter focuses on PMBGAs working in a discrete domain but other representations are also discussed briefly.

The previous chapter argued that using probabilistic models with multivariate interactions is a powerful approach to solving problems of bounded difficulty. The Bayesian optimization algorithm (BOA) combines the idea of using probabilistic models to guide optimization and the methods for learning and sampling Bayesian networks. To learn an adequate decomposition of the problem, BOA builds a Bayesian network for the set of promising solutions. New candidate solutions are generated by sampling the built network.

The empirical results of the last chapter were tantalizing. Easy and hard problems were automatically solved without user intervention in polynomial time. This raises an important question: How is BOA going to perform on other problems of bounded difficulty?

Thus far, we have examined the Bayesian optimization algorithm (BOA), empirical results of its application to several problems of bounded difficulty, and the scalability theory supporting those empirical results. It has been shown that BOA can tackle problems that are decomposable into subproblems of bounded order in a scalable manner and that it outperforms local search methods and standard genetic algorithms on difficult decomposable problems. But can BOA be extended beyond problems of bounded difficulty to solve other important classes of problems? What other classes of problems should be considered?

The previous chapter has discussed how hierarchy can be used to reduce problem complexity in black-box optimization. Additionally, the chapter has identified the three important concepts that must be incorporated into black-box optimization methods based on selection and recombination to provide scalable solution for difficult hierarchical problems. Finally, the chapter proposed a number of artificial problems that can be used to test scalability of optimization methods that attempt to exploit hierarchy.

The last chapter designed hBOA, which was shown to provide scalable solution for hierarchical traps. Since hierarchical traps were designed to test hBOA on the boundary of its design envelope, it was argued that if hBOA can scalably solve hierarchical traps, it should also be applicable to other hierarchical and nearly decomposable problems. Because many real-world problems are hierarchical or nearly decomposable, hBOA should be a promising approach to solving challenging real-world problems.

The purpose of this chapter is to provide a summary of main contributions of this work and outline important conclusions.