DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. Its design departs from most other existing frameworks in that it seeks to make algorithms explicit and data structures transparent, as opposed to the more common black-box frameworks. Freely available with extensive documentation at http://deap.gel.ulaval.ca, DEAP is an open source project under an LGPL license.
Multiobjective evolutionary algorithms (MOEAs) have been widely used in real-world applications. However, most MOEAs based on Pareto-dominance handle many-objective problems (MaOPs) poorly due to a high proportion of incomparable and thus mutually nondominated solutions. Recently, a number of many-objective evolutionary algorithms (MaOEAs) have been proposed to deal with this scalability issue. In this article, a survey of MaOEAs is reported. According to the key ideas used, MaOEAs are categorized into seven classes: relaxed dominance based, diversity-based, aggregation-based, indicator-based, reference set based, preference-based, and dimensionality reduction approaches. Several future research directions in this field are also discussed.
In evolutionary multiobjective optimization, maintaining a good balance between convergence and diversity is particularly crucial to the performance of the evolutionary algorithms (EAs). In addition, it becomes increasingly important to incorporate user preferences because it will be less likely to achieve a representative subset of the Pareto-optimal solutions using a limited population size as the number of objectives increases. This paper proposes a reference vector-guided EA for many-objective optimization. The reference vectors can be used not only to decompose the original multiobjective optimization problem into a number of single-objective subproblems, but also to elucidate user preferences to target a preferred subset of the whole Pareto front (PF). In the proposed algorithm, a scalarization approach, termed angle-penalized distance, is adopted to balance convergence and diversity of the solutions in the high-dimensional objective space. An adaptation strategy is proposed to dynamically adjust the distribution of the reference vectors according to the scales of the objective functions. Our experimental results on a variety of benchmark test problems show that the proposed algorithm is highly competitive in comparison with five state-of-the-art EAs for many-objective optimization. In addition, we show that reference vectors are effective and cost-efficient for preference articulation, which is particularly desirable for many-objective optimization. Furthermore, a reference vector regeneration strategy is proposed for handling irregular PFs. Finally, the proposed algorithm is extended for solving constrained many-objective optimization problems.
Evolutionary algorithms (EAs) have shown to be promising in solving many-objective optimization problems (MaOPs), where the performance of these algorithms heavily depends on whether solutions that can accelerate convergence toward the Pareto front and maintaining a high degree of diversity will be selected from a set of nondominated solutions. In this paper, we propose a knee point-driven EA to solve MaOPs. Our basic idea is that knee points are naturally most preferred among nondominated solutions if no explicit user preferences are given. A bias toward the knee points in the nondominated solutions in the current population is shown to be an approximation of a bias toward a large hypervolume, thereby enhancing the convergence performance in many-objective optimization. In addition, as at most one solution will be identified as a knee point inside the neighborhood of each solution in the nondominated front, no additional diversity maintenance mechanisms need to be introduced in the proposed algorithm, considerably reducing the computational complexity compared to many existing multiobjective EAs for many-objective optimization. Experimental results on 16 test problems demonstrate the competitiveness of the proposed algorithm in terms of both solution quality and computational efficiency.
"Exploration and exploitation are the two cornerstones of problem solving by search." For more than a decade, Eiben and Schippers' advocacy for balancing between these two antagonistic cornerstones still greatly influences the research directions of evolutionary algorithms (EAs) . This article revisits nearly 100 existing works and surveys how such works have answered the advocacy. The article introduces a fresh treatment that classifies and discusses existing work within three rational aspects: (1) what and how EA components contribute to exploration and exploitation; (2) when and how exploration and exploitation are controlled; and (3) how balance between exploration and exploitation is achieved. With a more comprehensive and systematic understanding of exploration and exploitation, more research in this direction may be motivated and refined.
Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper proposes a multiobjective evolutionary algorithm based on decomposition (MOEA/D). It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D have lower computational complexity at each generation than MOGLS and nondominated sorting genetic algorithm II (NSGA-II). Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjective optimization problems. It has been shown that MOEA/D using objective normalization can deal with disparately-scaled objectives, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions for 3-objective test instances. The ability of MOEA/D with small population, the scalability and sensitivity of MOEA/D have also been experimentally investigated in this paper.
Balancing convergence and diversity plays a key role in evolutionary multiobjective optimization (EMO). Most current EMO algorithms perform well on problems with two or three objectives, but encounter difficulties in their scalability to many-objective optimization. This paper proposes a grid-based evolutionary algorithm (GrEA) to solve many-objective optimization problems. Our aim is to exploit the potential of the grid-based approach to strengthen the selection pressure toward the optimal direction while maintaining an extensive and uniform distribution among solutions. To this end, two concepts-grid dominance and grid difference-are introduced to determine the mutual relationship of individuals in a grid environment. Three grid-based criteria, i.e., grid ranking, grid crowding distance, and grid coordinate point distance, are incorporated into the fitness of individuals to distinguish them in both the mating and environmental selection processes. Moreover, a fitness adjustment strategy is developed by adaptively punishing individuals based on the neighborhood and grid dominance relations in order to avoid partial overcrowding as well as guide the search toward different directions in the archive. Six state-of-the-art EMO algorithms are selected as the peer algorithms to validate GrEA. A series of extensive experiments is conducted on 52 instances of nine test problems taken from three test suites. The experimental results show the effectiveness and competitiveness of the proposed GrEA in balancing convergence and diversity. The solution set obtained by GrEA can achieve a better coverage of the Pareto front than that obtained by other algorithms on most of the tested problems. Additionally, a parametric study reveals interesting insights of the division parameter in a grid and also indicates useful values for problems with different characteristics.
Decomposition-based evolutionary algorithms have been quite successful in solving optimization problems involving two and three objectives. Recently, there have been some attempts to exploit the strengths of decomposition-based approaches to deal with many objective optimization problems. Performance of such approaches are largely dependent on three key factors: 1) means of reference point generation; 2) schemes to simultaneously deal with convergence and diversity; and 3) methods to associate solutions to reference directions. In this paper, we introduce a decomposition-based evolutionary algorithm wherein uniformly distributed reference points are generated via systematic sampling, balance between convergence and diversity is maintained using two independent distance measures, and a simple preemptive distance comparison scheme is used for association. In order to deal with constraints, an adaptive epsilon formulation is used. The performance of the algorithm is evaluated using standard benchmark problems, i.e., DTLZ1-DTLZ4 for 3, 5, 8, 10, and 15 objectives, WFG1-WFG9, the car side impact problem, the water resource management problem, and the constrained ten-objective general aviation aircraft design problem. Results of problems involving redundant objectives and disconnected Pareto fronts are also included in this paper to illustrate the capability of the algorithm. The study clearly highlights that the proposed algorithm is better or at par with recent reference direction-based approaches for many objective optimization.
Obtaining efficient optimisation algorithms has become the focus of much research interest since current developing trends in machine learning, traffic management, and other cutting-edge applications require complex optimised models containing a huge number of parameters. At present, computers based on the classical Turing-machine are inefficient when intent to solve optimisation tasks in complex and wicked problems. As a solution, quantum computers that should satisfy the Deutsch-Church-Turing principle have been proposed but this technology is still at an early stage. quantum-inspired algorithms (QIA) have emerged trying to fill-up an existing gap between the theoretical advances in quantum computation and real quantum computers. QIA use classical computers to simulate some physical phenomena such as superposition and entanglement to perform quantum computations. This paper proposes the quantum-inspired Acromyrmex evolutionary algorithm (QIAEA) as a highly efficient global optimisation method for complex systems. We present comparative statistical analyses that demonstrate how this nature-inspired proposal outperforms existing outstanding quantum-inspired evolutionary algorithms when testing benchmark functions.
This paper contains a modern vision of the parallelization techniques used for evolutionary algorithms (EAs). The work is motivated by two fundamental facts: 1) the different families of EAs have naturally converged in the last decade while parallel EAs (PEAs) are still lack of unified studies; and 2) there is a large number of improvements in these algorithms and in their parallelization that raise the need for a comprehensive survey. We stress the differences between the EA model and its parallel implementation throughout the paper. We discuss the advantages and drawbacks of PEAs. Also, successful applications are mentioned and open problems are identified. We propose potential solutions to these problems and classify the different ways in which recent results in theory and practice are helping to solve them. Finally, we provide a highly structured background relating to PEAs in order to make researchers aware of the benefits of decentralizing and parallelizing an EA.