In the last few decades, evolutionary algorithms have emerged as a revolutionary approach for solving search and optimization problems involving multiple conflicting objectives. Beyond their ability to search intractably large spaces for multiple solutions, these algorithms are able to maintain a diverse population of solutions and exploit similarities of solutions by recombination. However, existing theory and numerical experiments have demonstrated that it is impossible to develop a single algorithm for population evolution that is always efficient for a diverse set of optimization problems. Here we show that significant improvements in the efficiency of evolutionary search can be achieved by running multiple optimization algorithms simultaneously using new concepts of global information sharing and genetically adaptive offspring creation. We call this approach a multialgorithm, genetically adaptive multiobjective, or AMALGAM, method, to evoke the image of a procedure that merges the strengths of different optimization algorithms. Benchmark results using a set of well known multiobjective test problems show that AMALGAM approaches a factor of 10 improvement over current optimization algorithms for the more complex, higher dimensional problems. The AMALGAM method provides new opportunities for solving previously intractable optimization problems. evolutionary search ͉ multiple objectives ͉ optimization problems ͉ Pareto front E volutionary optimization is a subject of intense interest in many fields of study, including computational chemistry, biology, bioinformatics, economics, computational science, geophysics, and environmental science (1-8). The goal is to determine values for model parameters or state variables that provide the best possible solution to a predefined cost or objective function, or a set of optimal tradeoff values in the case of two or more conflicting objectives. However, locating optimal solutions often turns out to be painstakingly tedious, or even completely beyond current or projected computational capacity (9). Here, we consider a multiobjective minimization problem, with n decision variables (parameters) and m objectives: , where x denotes the decision vector, and y is the objective space. We restrict attention to optimization problems in which the parameter search space X, although perhaps quite large, is bounded: x ϭ (x 1 , . . . , x n ) ʦ X. The presence of multiple objectives in an optimization problem gives rise to a set of Pareto-optimal solutions, instead of a single optimal solution (10, 11). A Pareto-optimal solution is one in which one objective cannot be further improved without causing a simultaneous degradation in at least one other objective. As such, they represent globally optimal solutions to the tradeoff problem. Numerous approaches have been proposed to efficiently find Pareto-optimal solutions for complex multiobjective optimization problems (12-15). In particular, evolutionary algorithms have emerged as the most powerful approach for solving search and optimization problems involving multiple conflicting objectives. Beyond their ability to search intractably large spaces for multiple Pareto-optimal solutions, these algorithms are able to maintain a diverse set of solutions and exploit similarities of solutions by recombination. These attributes lead to efficient convergence to the Pareto-optimal front in a single optimization run (13). Of these, the nondominated sorted genetic algorithm II (NSGA-II) (14) has received the most attention because of its simplicity and demonstrated superiority over other methods. Although the multiobjective optimization problem has been studied quite extensively, current available evolutionary algorithms typically implement a single algorithm for population evolution. Reliance on a single biological model of natural selection and adaptation presumes that a single method exists that efficiently evolves a population of potential solutions through the parameter space. However, existing theory and numerical experiments have demonstrated that it is impossible to develop a single algorithm for population evolution that is always efficient for a diverse set of optimization problems (16). In recent years, memetic algorithms (also called hybrid genetic algorithms) have been proposed to increase the search efficiency of population based optimization algorithms (17). These methods are inspired by models of adaptation in natural systems, and use a genetic algorithm for global exploration of the search space, combined with a local search heuristic for exploitation. Memetic algorithms have shown to significantly speed up the evolution toward the global optimal solution for a variety of real-world optimization problems. However, our conjecture is that a search procedure that adaptively changes the way it generates offspring, based on the shape and local peculiarities of the fitness landscape, will further improve the efficiency of evolutionary search. This approach is likely to be productive because the nature of the fitness landscape (objective functions mapped out in the parameter space, also called the response surface) often varies considerably between different optimization problems, and dynamically changes en route to the global optimal solutions. Drawing inspiration from the field of ensemble weather forecasting (18), we present an innovative procedure employing genetically adaptive evolutionary optimization. The method combines two concepts, simultaneous multimethod search, and self-adaptive offspring creation, to ensure a fast, reliable, and computationally efficient solution to multiobjective optimization problems. We call this approach a multi-algorithm, genetically adaptive multiobjective, or AMALGAM, method, to evoke the image of a procedure that blends the attributes of the best available individual optimization algorithms. To successfully implement the AMALGAM method, three questions need to be addressed. First, how can we best make multiple algorithms meaningfully communicate with one another, and share their information? Second, what is the most effective method for adaptive offspring creation? Finally, which
Vrugt and Robinson REF proposed a multialgorithm genetically adaptive multiobjective (AMALGAM) method performing cooperative search using various MOEAs.
Improved evolutionary optimization from genetically adaptive multimethod search
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Computer Science Medicine