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.

One commonly used approach is fitness sharing, where the fitness of each individual is reduced based on its proximity to others. This discourages overcrowding in a single region of the search space and promotes exploration of other niches. For example, the adjusted fitness of an individual is calculated by dividing its original fitness by the sum of a sharing function applied to the distances between it and other individuals. This sharing function decreases with distance, ensuring that individuals in densely populated regions have lower adjusted fitness.

Another approach is crowding, which ensures that offspring replace their most similar parents. Deterministic crowding involves pairing offspring with their closest parents and allowing the better-performing individual to survive. Probabilistic crowding adds an element of randomness to this process, balancing exploration and exploitation. Niching methods, which partition the population into subgroups or niches, are also effective. Each niche focuses on a different area of the search space, preventing the dominance of any single solution. Speciation techniques, where individuals are grouped into species based on genetic similarity, further enhance diversity.

Island models divide the population into subpopulations, or islands, which evolve independently with occasional migrations. This allows each island to explore different regions of the search space while sharing information periodically to prevent stagnation.

The steps of an evolutionary multimodal optimization algorithm typically include initialization, evaluation of fitness, application of diversity-preserving mechanisms, selection, genetic operations such as crossover and mutation, and population replacement. For instance, in an EA with fitness sharing, individuals are evaluated for their fitness, and the shared fitness is calculated using the sharing function. Selection is then performed based on the shared fitness, followed by the application of genetic operators to generate offspring. The process iterates until a termination condition, such as a maximum number of generations, is met.

The effectiveness of these methods depends on the proper tuning of parameters, such as the niche radius in fitness sharing or the migration rate in island models. The assumptions underlying EMO include the existence of multiple optima in the problem landscape and the ability to maintain diversity within the population.

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 EMMO.

Steps in the EMMO 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]$

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.

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.

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.