EVOLVE – A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation VII

In this chapter it is discussed, how the concept of diversity plays a crucial role in contemporary (multi-objective) optimization algorithms. It is shown that diversity maintenance can have a different purpose, such as improving global convergence reliability or finding alternative solutions to a (multi-objective) optimization problem. Moreover, different algorithms are reviewed that put special emphasis on diversity maintenance, such as multicriteria evolutionary optimization algorithms, multimodal optimization, artificial immune systems, and techniques from set oriented numerics. Diversity maintenance enters in different search operators and is used for different reasons in these algorithms. Among them we highlight evolutionary, swarm-based, artificial immune system-based, and indicator-based approaches to diversity optimization. In order to understand indicator-based approaches, we will review some of the most common diversity indices that can be used to quantitatively assess diversity. Based on the discussion, ’diversity oriented optimization’ is suggested as a term encompassing optimization techniques that adress diversity maintainance as a major ingredient of the search paradigm. To bring order into all these different approaches, an ontology on diversity oriented optimization is proposed. It provides a systematic overview of the various concepts, methods, and applications and it can be extended in future work.

Multi-objective optimization problems (MOPs) arise in many fields in engineering. In this chapter we argue that adaptation of cell mapping techniques, originally designed for the global analysis of dynamical systems, are well-suited for the thorough analysis of low-dimensional MOPs. Algorithms of this kind deliver an approximation of the set of global solutions, the Pareto set, as well as the set of locally optimal and nearly optimal solutions in one run of the algorithm which may significantly improve the underlying decision making process. We underline the statements on some illustrative examples and present comparisons to other algorithms.

We revise a method recently introduced by the authors for the estimation of robustness and reliability in design optimization problems with uncertainties in the input variable space. Percentile values of system output properties are estimated by means of polynomial chaos expansions used as stochastic response surfaces. The percentiles can be used as objectives or constraints in multiobjective optimization problems. We clarify the theoretical background and motivations of our approach, and we show benchmark results, as well as applications of multiobjective optimization problems solved with evolutionary algorithms. The advantages of the method are also presented.

Since most real life decisions are multiobjective, multicriteria games offer a more realistic modeling of real-life interactions. Although several equilibrium concepts have been proposed for solving multicriteria games, equilibria detection has not received much attention. Generative relations are proposed to characterize multicriteria equilibria. An evolutionary method based on generative relations is proposed for detecting various multicriteria equilibria: Nash-Pareto, Ideal Nash and Pareto equilibria. Numerical experiments on discrete and continuous games indicate the potential of the proposed approach.

One of the most popular solutions proposed for a noncooperative game is the concept of Nash equilibrium. An estimation of distribution algorithm is adapted to this problems’ particularities in order to detect a sample of Nash equilibria for games in normal form. A generative relation is used to select the new strategy profiles that will generate the offspring. Several numerical experiments are conducted to validate the method for games with different numbers and types of equilibria.

Evolutionary algorithms (EAs) have been used to tackle non-linear multi-objective optimisation (MOO) problems successfully, but their success is governed by key parameters which have been shown to be sensitive to the nature of the particular problem, incorporating concerns such as the numbers of objectives and variables, and the size and topology of the search space, making it hard to determine the best settings in advance. This work describes a real-encoded multi-objective optimising EA (MOOEA) that uses self-adaptive mutation and crossover, and which is applied to optimisation of an airfoil, for minimisation of drag and maximisation of lift coefficients. The MOOEA is integrated with a Free-Form Deformation tool to manage the section geometry, and XFoil which evaluates each airfoil in terms of its aerodynamic efficiency. The performance is compared with those of the heuristic MOO algorithms, the Multi-Objective Tabu Search (MOTS) and NSGA-II, showing that this GA achieves better convergence.

Atmospheric pressure on Mars is approximately 1 % of that on Earth and varies about 15 % during the year due to condensation and sublimation of its primarily CO\(_2\) atmosphere. Impacts of the uncertainties during the entry are difficult to be modeled. The situation becomes more complex when uncertainties are from different disciplines. In this work, a robust multi-disciplinary optimization method for Mars microentry probe design under epistemic uncertainties is presented. Objectives of the evidence-based robust design are set to minimize the interior temperature of thermal protection systems (TPS) and maximize its belief value under uncertainties. A population-based multi-objective estimation of distribution algorithm (MOEDA) is designed for searching the robust Pareto set. Candidate solutions are adaptively clustered into groups. In each group, principal component analysis (PCA) technique is performed to estimate population distribution, sample and reproduce individuals. Non-dominated individuals are sorted and selected through the NSGA-II-like selection procedure. Adaptive sampling and binary branching techniques are employed for computing the evidence belief functions. PCA dimensionality reduction technique is implemented for identifying and removing uncertain boxes with little contribution of the beliefs. With variable fidelity model management, analytical aerodynamic model is used first to initialize the optimization searching direction. Artificial neural network (ANN) surrogate model is used for reducing the computational cost. When the optimization goes close to the optima, more data from the high accuracy model are put into the aerodynamic database, making the optimization procedure converge on optima quickly while keeping high-level accuracy.

The probabilistic traveling salesman problem (PTSP) is a variation of the classic TSP and one of the most significant stochastic network and routing problems. Designing effective and efficient algorithms for solving PTSP is a really challenging task, since in PTSP, the computational complexity associated with the combinatorial explosion of potential solution is exacerbated by the stochastic element in the data. In general, researchers use two types of techniques in their search algorithms for PTSP: analytical computation and empirical estimation. The analytical computation approach computes the cost  f(\(\pi \)) of an a priori tour \(\pi \) using a closed-form expression. Empirical estimation simply estimates the cost through Monte Carlo simulation. This paper describes a simulation-based algorithm that constructs the solution attractor of local search for the PTSP and then finds the best a priori tour within the solution attractor. More specifically, our algorithm first uses a simple multi-start local search process to find a set of locally optimal a priori tours through Monte Carlo simulation and stores these tours in a matrix. Then, the algorithm uses an exhausted search process to find all tours contained in the solution attractor and identifies a globally optimal a priori tour \(\pi \) through Monte Carlo simulation.

The performance of a multi-objective evolutionary algorithm (MOEA) is evaluated with regard to the quality of the populations under two aspects: the distance of the non-dominated set of a population to the true Pareto front (\(PF_{true}\)) and the spread among these solutions. Diverse convergence indicators have been proposed in the past with different requirements: either \(PF_{true}\) or a reference set of Pareto-optimal solutions is required. Furthermore, most of the convergence indicators are restricted to a non-dominated solution set, and therefore, the quality of the entire population is only represented by the non-dominated solutions. This work presents a statistically reasonable convergence indicator that is able to reflect the quality of the entire population. The average cuboid volume (ACV) assigns desirable aspects regarding the classification of entire populations. These preferable features are demonstrated and discussed. Furthermore, ACV is used as selection criterion to determine the solutions of the succeeding generation in a proposed customized NSGA-II for biochemical optimization. Two selection strategies based on the ACV indicator are proposed and empirically compared to a Pareto rank-based selection strategy. These selection strategies depend on two parameters and the adaption of the selection pressure by a variation of these parameters is empirically investigated on a three-dimensional biochemical minimization problem.