Investigating the Effect of Imbalance Between Convergence and Diversity in Evolutionary Multiobjective Algorithms

There are two main tasks involved in addressing a multiobjective optimization problem (MOP) by evolutionary multiobjective (EMO) algorithms: 1) make the population converge close to the Pareto-optimal front and 2) maintain adequate population diversity. However, most state-of-the-art EMO algorithms are designed based on the “convergence first and diversity second” principle. It has been observed that although these EMO algorithms have been successful in optimizing many real-world MOPs, they fail to solve certain problems that feature a severe imbalance between diversity preservation and achieving convergence. This paper characterizes an imbalanced MOP by clearly defining properties and indicating the reasons for the existing EMO algorithms’ difficulties in solving them. We then present 14 imbalanced problems, with and without constraints. Computational results using four existing EMO algorithms—elitist non-dominated sorting genetic algorithm (NSGA-II), multiobjective evolutionary algorithm based on decomposition (MOEA/D), strength Pareto evolutionary algorithm 2 (SPEA2), and S metric selection EMO algorithm (SMS-EMOA) and a proposed generalized vector-evaluated genetic algorithm are then presented. It is seen that these EMO algorithms cannot solve these imbalanced problems, but they are able to solve the problems when augmented by multiobjective to multiobjective (M2M), an approach that decomposes the population into several interacting subpopulations. These results and the successful application of the EMO methods with the M2M approach even on standard so-called balanced problems indicate the usefulness of using the M2M approach.

There are two main tasks involved in addressing a multiobjective optimization problem (MOP) by evolutionary multiobjective (EMO) algorithms: 1) make the population converge close to the Pareto-optimal front and 2) maintain adequate population diversity. However, most state-of-the-art EMO algorithms are designed based on the “convergence first and diversity second” principle. It has been observed that although these EMO algorithms have been successful in optimizing many real-world MOPs, they fail to solve certain problems that feature a severe imbalance between diversity preservation and achieving convergence. This paper characterizes an imbalanced MOP by clearly defining properties and indicating the reasons for the existing EMO algorithms’ difficulties in solving them. We then present 14 imbalanced problems, with and without constraints. Computational results using four existing EMO algorithms—elitist non-dominated sorting genetic algorithm (NSGA-II), multiobjective evolutionary algorithm based on decomposition (MOEA/D), strength Pareto evolutionary algorithm 2 (SPEA2), and S metric selection EMO algorithm (SMS-EMOA) and a proposed generalized vector-evaluated genetic algorithm are then presented. It is seen that these EMO algorithms cannot solve these imbalanced problems, but they are able to solve the problems when augmented by multiobjective to multiobjective (M2M), an approach that decomposes the population into several interacting subpopulations. These results and the successful application of the EMO methods with the M2M approach even on standard so-called balanced problems indicate the usefulness of using the M2M approach.

Shape Optimization With Surface-Mapped CPPNs

Shape optimization techniques are becoming increasingly important in design and engineering. This growing significance reflects the need to exploit advances in digital fabrication technologies, and the desire to create new types of surface designs for various engineering applications. Evolutionary algorithms (EAs) offer several key advantages for shape optimization, but they can also be restricted, especially as design problems scale up in size. A key challenge for evolutionary shape optimization is to overcome these challenges in order to apply EAs to large-scale, “real-world” engineering problems. This paper presents a new evolutionary approach to shape optimization using what we call “surface-mapped compositional pattern producing networks (CPPNs).” Our method outperforms a state-of-the-art gradient-based method on a simple benchmark problem, and scales well as degrees of freedom are added to the design problem. Our results demonstrate that surface-mapped CPPNs offer practical ways of approaching large-scale, real-world engineering problems with EAs, opening up exciting new opportunities for engineering design.

Shape optimization techniques are becoming increasingly important in design and engineering. This growing significance reflects the need to exploit advances in digital fabrication technologies, and the desire to create new types of surface designs for various engineering applications. Evolutionary algorithms (EAs) offer several key advantages for shape optimization, but they can also be restricted, especially as design problems scale up in size. A key challenge for evolutionary shape optimization is to overcome these challenges in order to apply EAs to large-scale, “real-world” engineering problems. This paper presents a new evolutionary approach to shape optimization using what we call “surface-mapped compositional pattern producing networks (CPPNs).” Our method outperforms a state-of-the-art gradient-based method on a simple benchmark problem, and scales well as degrees of freedom are added to the design problem. Our results demonstrate that surface-mapped CPPNs offer practical ways of approaching large-scale, real-world engineering problems with EAs, opening up exciting new opportunities for engineering design.

How to Pack Trapezoids: Exact and Evolutionary Algorithms

The purposes of this paper are twofold. In the first, we describe an exact polynomial-time algorithm for the pair sequencing problem and show how this method can be used to pack fixed-height trapezoids into a single bin such that interitem wastage is minimized. We then go on to examine how this algorithm can be combined with bespoke evolutionary and local search methods for tackling the multiple-bin version of this problem—one that is closely related to 1-D bin packing. In the course of doing this, a number of ideas surrounding recombination, diversity, and genetic repair are also introduced and analyzed.

The purposes of this paper are twofold. In the first, we describe an exact polynomial-time algorithm for the pair sequencing problem and show how this method can be used to pack fixed-height trapezoids into a single bin such that interitem wastage is minimized. We then go on to examine how this algorithm can be combined with bespoke evolutionary and local search methods for tackling the multiple-bin version of this problem—one that is closely related to 1-D bin packing. In the course of doing this, a number of ideas surrounding recombination, diversity, and genetic repair are also introduced and analyzed.