Evolutionary multimodal optimization

Author: Connor Clappin (cjc395) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Evolutionary Multimodal Optimization (EMO) involves the use of evolutionary algorithms (EAs) to locate and maintain multiple optimal solutions in problems with multiple optima. Traditional optimization approaches typically focus on identifying a single global optimum, often ignoring other potential solutions. EMO addresses this limitation by employing strategies to preserve diversity in the population, allowing the identification of multiple global and local optima.

Multimodal optimization problems arise in many practical domains. For example, in engineering design, alternative configurations might satisfy the same performance criteria but differ in material, cost, or other constraints. Similarly, in drug discovery, different compounds may achieve the desired therapeutic effect while varying side effects or production costs. EAs, inspired by the principles of natural selection, are well-suited to such challenges due to their stochastic nature and ability to explore complex, high-dimensional search spaces.

The primary motivation for studying EMO is its ability to provide comprehensive insights into a problem’s landscape. Identifying multiple solutions offers flexibility in decision-making, enabling stakeholders to choose solutions based on secondary criteria not included in the optimization. Moreover, EMO enhances robustness by offering alternatives that might perform well under varying or uncertain conditions.

Algorithm Discussion

Evolutionary algorithms are population-based optimization methods that inherently maintain a diverse set of solutions. However, standard EAs tend to converge to a single solution due to selection pressure. In multimodal optimization, preserving diversity is crucial to avoid premature convergence and to explore multiple peaks in the fitness landscape.

Diversity-Preserving Mechanisms

To prevent premature convergence and maintain diversity across the population, several strategies are employed. Below, these strategies are detailed with their respective equations.

Fitness Sharing

Fitness sharing reduces the fitness of individuals based on their proximity to others, thereby discouraging overcrowding in a single region of the search space. The adjusted fitness $f'_{i}$ of an individual $i$ is calculated as: $f'_{i}={\frac {f_{i}}{\sum _{j=1}^{N}sh(d_{ij})}}$ where:

• $f_{i}$: original fitness of individual $i$,
• $N$: total number of individuals,
• $d_{ij}$: distance between individual $i$ and individual $j$,
• $sh(d_{ij})$: sharing function:

$sh(d_{ij})={\begin{cases}1-\left({\frac {d_{ij}}{\sigma }}\right)^{\alpha },&{\text{if }}d_{ij}\leq \sigma ,\\0,&{\text{if }}d_{ij}>\sigma ,\end{cases}}$ where $\sigma$ is the niche radius, and $\alpha$ is a constant controlling the shape of the sharing function. This ensures individuals in densely populated regions receive lower adjusted fitness values.

Crowding and Deterministic Crowding

Crowding methods replace similar individuals, ensuring diverse genetic representation in the population.

In deterministic crowding:

1. Each offspring $o_{k}$ is compared to its most similar parent $p_{k}$, based on a distance measure $d(o_{k},p_{k})$, typically defined in the genotype or phenotype space.

2. The better-performing individual between $o_{k}$ and $p_{k}$ survives: ${\text{Survivor}}={\begin{cases}o_{k},&{\text{if }}f(o_{k})>f(p_{k}),\\p_{k},&{\text{otherwise.}}\end{cases}}$

Probabilistic crowding adds randomness to survivor selection. The probability of an offspring $o_{k}$ surviving over its parent $p_{k}$ is: $P(o_{k}{\text{ survives}})={\frac {f(o_{k})}{f(o_{k})+f(p_{k})}}.$

Niching and Speciation

Niching divides the population into subgroups focusing on different regions of the search space, promoting independent exploration of peaks.

Speciation groups individuals based on genetic similarity. Individuals $i$ and $j$ belong to the same species if: $d_{ij}\leq \sigma _{s},$ where $\sigma _{s}$ is the speciation threshold. Genetic similarity can be measured as: $d_{ij}={\sqrt {\sum _{k=1}^{m}(x_{i,k}-x_{j,k})^{2}}},$ where $x_{i,k}$ and $x_{j,k}$ are the $k$-th gene values of individuals $i$ and $j$, and $m$ is the number of genes.

Island Models

Island models split the population into separate subpopulations (islands) that evolve independently. Migration periodically allows individuals to move between islands.

1. Migration occurs every $t_{m}$ generations.

2. Migrants are selected based on their fitness, with the probability of selection: $P(i)={\frac {f_{i}}{\sum _{j=1}^{N_{\text{local}}}f_{j}}},$ where $f_{i}$ is the fitness of individual $i$ on an island and $N_{\text{local}}$ is the local island population size.

3. Migrants replace individuals in the target island, selected based on their least fitness: ${\text{Replace target individual }}k,{\text{ where }}f_{k}=\min(f_{1},f_{2},\ldots ,f_{N_{\text{local}}}).$

Algorithm Workflow

The workflow of an EMO algorithm involves the following key steps:

1. Initialization: Random generation of an initial population.
2. Evaluation: Each individual’s fitness is assessed.
3. Diversity Preservation: Application of mechanisms like fitness sharing, crowding, or island models.
4. Selection: Individuals are selected based on adjusted fitness for breeding. Commonly used methods include:

$P(i{\text{ is selected}})={\frac {f'_{i}}{\sum _{j=1}^{N}f'_{j}}},$ where $f'_{i}$ is the adjusted fitness of individual $i$.

1. Genetic Operations: Crossover and mutation are applied to generate offspring. Mutation, for example, may alter a gene $x_{k}$ with:

$x_{k}'=x_{k}+\Delta ,$ where $\Delta$ is a random perturbation.

1. Replacement: The population is updated with new individuals.
2. Termination: The algorithm stops when a condition, such as a maximum number of generations, is reached.

Parameter Tuning and Assumptions

The effectiveness of EMO depends on proper parameter settings:

• Niche radius $\sigma$: Determines the sensitivity of fitness sharing and speciation.
• Migration rate $m$: Balances exploration and exploitation in island models.

Assumptions:

1. The problem landscape contains multiple optima.
2. The algorithm can maintain sufficient diversity to explore the landscape effectively.

This structured explanation, with accompanying equations, highlights the mathematical foundation of evolutionary multimodal optimization mechanisms.

Numerical Example

Problem Statement

We aim to solve a multimodal optimization problem using the Rastrigin function, a common benchmark in optimization. The function is defined as:

$f(x)=10n+\sum _{i=1}^{n}\left[x_{i}^{2}-10\cos(2\pi x_{i})\right]$

- Domain: $x_{i}\in [-5.12,5.12]$ - Global Minimum: $f(0)=0$ at $x=0$ - Number of Variables: $n=1$ (for simplicity)

The function has multiple local minima, making it ideal for demonstrating EMO.

Figure 1: Rastrigin Function Plot

Steps in the EMO Process

Step 1: Initialize Population

We randomly generate a population of $P=10$ individuals within the range $[-5.12,5.12]$.

Initial Population: $x=[-4.5,-3.0,-2.1,-0.9,0.0,0.8,2.3,3.1,4.0,4.8]$

Figure 2: Rastrigin Function Initial Population

Step 2: Evaluate Fitness

The fitness of each individual is calculated using the Rastrigin function:

$f(x_{i})=10+x_{i}^{2}-10\cos(2\pi x_{i})$

Example calculations: - For $x=-4.5$: $f(-4.5)=10+(-4.5)^{2}-10\cos(2\pi (-4.5))=40.25$ - For $x=-3.0$: $f(-3.0)=10+(-3.0)^{2}-10\cos(2\pi (-3.0))=29$

Fitness values for the population: $f(x)=[40.25,29,14.61,9.81,0,9.81,15.89,28.61,40,49.29]$

Step 3: Apply Niching (Fitness Sharing)

To maintain diversity, we apply fitness sharing, which adjusts fitness values based on proximity to other individuals.

1. Sharing Function: $S(d)={\begin{cases}1-{\frac {d}{\sigma _{\text{share}}}},&{\text{if }}d<\sigma _{\text{share}}\\0,&{\text{otherwise}}\end{cases}}$

2. Adjusted Fitness: $f'(x_{i})={\frac {f(x_{i})}{\sum _{j=1}^{P}S(d_{ij})}}$

- Compute distances $d_{ij}$ between individuals and adjust fitness. Example: For $x_{1}=-4.5$, calculate distances and apply the sharing function.

Figure 3: Rastrigin Function Niching Process

Step 4: Selection

Using shared fitness values, select individuals for reproduction. Methods include: - Tournament Selection - Roulette Wheel Selection

Step 5: Variation (Crossover and Mutation)

1. Crossover: Combine two parent solutions: Parent 1: $x=-4.5$ Parent 2: $x=-3.0$ Child: $x=-3.75$

2. Mutation: Introduce random variation:

Mutated Child: $x=-3.75+random(-0.5,0.5)$

Step 6: Replace and Iterate

Replace the worst-performing individuals with offspring and repeat steps 2–5 for several generations.

Figure 4: Rastrigin Function Evolutionary Convergence

Final Results

After several generations, the algorithm identifies multiple optima:

$x=[-4.1,-2.0,0.0,2.0,4.1]$

These represent different peaks or valleys in the Rastrigin function.

Summary

Evolutionary Multimodal Optimization successfully discovers diverse solutions by: Maintaining population diversity through niching and exploring the multimodal landscape using evolutionary operators. This process ensures identification of both global and local optima.

Applications

Evolutionary multimodal optimization has a wide range of applications across various domains. In engineering design, EMO is used to identify multiple feasible configurations of mechanical components. For instance, an aircraft wing might be designed with different materials or structural layouts that all meet aerodynamic requirements. EMO allows engineers to evaluate trade-offs between cost, weight, and manufacturability.

In bioinformatics, EMO is applied to problems such as DNA sequence alignment. Multiple high-scoring alignments may have biological significance, and EMO helps discover these alternatives. By maintaining diversity, the algorithm ensures that rare but promising alignments are not overlooked.

Data clustering is another prominent application. In this context, EMO is used to optimize the placement of cluster centers in unsupervised learning. By exploring multiple solutions, the algorithm identifies distinct groupings in datasets, even when the number of clusters is not predefined.

Case studies highlight the practical utility of EMO. For example, in antenna design, EMO has been used to create antennas with multiple operating frequencies. By optimizing the design parameters, the algorithm identifies configurations that maximize efficiency across different frequency bands. In chemical engineering, EMO has been employed to optimize reaction conditions for processes with multiple operating points, balancing yield, cost, and safety.

Software tools like MATLAB, Python’s DEAP library, and GAlib support the implementation of EMO. MATLAB’s Global Optimization Toolbox includes built-in functions for niching and fitness sharing, while DEAP provides a flexible framework for developing custom evolutionary algorithms.

Conclusion

Evolutionary Multimodal Optimization extends traditional evolutionary algorithms to address problems requiring multiple optimal solutions. By incorporating techniques such as fitness sharing, crowding, and niching, EMO maintains diversity within the population, preventing premature convergence and enabling the exploration of multiple optima.

The key takeaways from this discussion include the importance of diversity preservation, the effectiveness of EMO in solving complex problems, and its versatility across domains. Applications in engineering, bioinformatics, and data science demonstrate its practical value, while advances in computational tools facilitate its adoption.

Future research in EMO may focus on adaptive niching parameters to enhance performance and scalability to handle high-dimensional optimization problems. Hybrid approaches combining EMO with other methods, such as local search, hold promise for further improving efficiency and solution quality.