Overview of SPEA2 (Strength Pareto Evolutionary Algorithm 2), algorithm and implementation examples

Overview of SPEA2(Strength Pareto Evolutionary Algorithm 2)

SPEA2 (Strength Pareto Evolutionary Algorithm 2) is an evolutionary algorithm for solving multi-objective optimization problems and will be an improved method for finding Pareto optimal solutions. It is an improved version of the original SPEA (Strength Pareto Evolutionary Algorithm), specifically using strength and density-based selection pressure to find superior solutions more efficiently. and has become a very popular multiobjective evolutionary algorithm as NAGA-II described in “Overview of NSGA-II (Non-dominated Sorting Genetic Algorithm II), algorithm and implementation examples“.

SPEA2 has the following features

• Strength concept: The strength of each individual (solution) is a value that indicates how much better that individual is compared to other individuals. Individuals with higher strength are considered more dominant and are prioritized in the selection process.
• Density Consideration (Density): The concept of density is introduced to even out the distribution of solutions on the Pareto frontier. Density is a value that indicates how densely other solutions surround a solution, and tends to select solutions with low density (sparse solutions), thereby preserving solution diversity.
• Pareto dominance for adaptation: In SPEA2, Pareto dominance is used to evaluate individuals. If Solution A dominates Solution B, then Solution A is considered superior to Solution B. Based on this, the fitness of an individual is calculated by combining the number of dominated solutions and the density of solutions that dominate it.
• Use of an external archive: To search for multiple solutions simultaneously, SPEA2 uses an external archive. This maintains the set of Pareto-optimal solutions obtained in the current generation, and allows optimization to proceed while preserving the diversity of solutions during the evolutionary process.
• Selection, crossover, and mutation: During the evolutionary process, selection pressures based on strength and density are applied to individual selection, maintaining diversity by selecting solutions with low density while keeping solution strength high. Crossover and mutation are also implemented as standard evolutionary methods, but they serve as a means to explore the solution space.

The SPEA2 algorithm takes the following steps

1. Initialization: an initial population is generated. The external archive is also initialized with an empty one.
2. Adaptation evaluation: For each individual, intensity and density are computed to evaluate the degree of adaptation. Calculate the degree of adaptation based on how much each solution dominates the others and the density of that solution.
3. Selection: select highly adapted individuals to move on to the next generation. Selection is based on intensity and density, particularly to select a variety of solutions close to the Pareto frontier.
4. Crossover and mutation: Crossover and mutation are applied to the selected parents. This generates new solutions.
5. Update of external archive: The newly generated solution is added to the external archive and the Pareto optimal solution is retained from the solutions in the archive.
6. Termination condition: The algorithm continues to evolve until a defined number of generations or convergence condition is met.

Advantages and disadvantages of SPEA2 include

Advantages:

• Preserve diversity: Density considerations allow efficient search for optimal solutions while preserving solution diversity.
• Balanced intensity and density: Combining intensity and density allows for balanced pressure on solution selection to search for better solutions.
• External archive: The use of an external archive allows the search to proceed while preserving previous best solutions.

Disadvantages:

• Computational cost: Computing intensities and densities requires a lot of computational resources and can be computationally expensive.
• Possibility of falling into local optimum: as with other evolutionary algorithms, there is a possibility of falling into local optimum, which may depend on the initial population and selection pressure.

Implementation Example

The following is a basic example implementation of SPEA2 (Strength Pareto Evolutionary Algorithm 2). This example shows how to apply SPEA2 to the problem of optimizing two objective functions using Python and the DEAP (Distributed Evolutionary Algorithms in Python) library. library, which also makes SPEA2 easy to implement.

Example of SPEA2 implementation (Python + DEAP)

Install the required libraries: First, install the DEAP library.

pip install deap

implementation code

import random
from deap import base, creator, tools, algorithms
import numpy as np

# Define the objective function to be optimized
def objective1(individual):
    x, y = individual
    return x**2 + y**2,  # To treat as a minimization problem, return as a tuple

def objective2(individual):
    x, y = individual
    return (x - 1)**2 + (y - 1)**2,  # To treat as a minimization problem, return as a tuple

# Definition of fitness and individuals
creator.create("FitnessMulti", base.Fitness, weights=(-1.0, -1.0))  # minimization problem
creator.create("Individual", list, fitness=creator.FitnessMulti)

# Function to generate initial population
def create_individual():
    return [random.uniform(-5, 5), random.uniform(-5, 5)]  # Randomly initialized in the range of -5 to 5

# Function to evaluate the degree of adaptation
def evaluate(individual):
    return objective1(individual), objective2(individual)

# Main evolutionary algorithm
def main():
    # Individual and group settings
    toolbox = base.Toolbox()
    toolbox.register("individual", tools.initIterate, creator.Individual, create_individual)
    toolbox.register("population", tools.initRepeat, list, toolbox.individual)

    # Register evaluation function
    toolbox.register("evaluate", evaluate)
    
    # Set up crossover, mutation, and selection
    toolbox.register("mate", tools.cxBlend, alpha=0.5)  # Crossover: Blend Crossover
    toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)  # Mutation: Gaussian
    toolbox.register("select", tools.selSPEA2)  # SPEA2 selection

    # Group initialization
    population = toolbox.population(n=100)

    # Algorithm Execution
    algorithms.eaSimple(population, toolbox, cxpb=0.7, mutpb=0.2, ngen=50, 
                        stats=None, halloffame=None, verbose=True)

    return population

if __name__ == "__main__":
    # execution
    final_population = main()

    # Show Results
    for ind in final_population:
        print(f"Individual: {ind}, Fitness: {ind.fitness.values}")

Code Description

1. Objective functions: objective1 and objective2 are two objective functions: objective1 returns the sum of squares of the individuals (x, y) and objective2 minimizes (x – 1)**2 + (y – 1)**2.
2. Definition of fitness and individual: creator.create is used to define the multiobjective fitness (FitnessMulti) and individual (Individual). weights=(-1.0, -1.0) is set to minimize both objective functions.
3. Generating the initial population: The initial population is randomly generated using tools.initIterate. Individuals are generated in the range of -5 to 5.
4. Setting up the evolutionary algorithms: cxBlend is used for the crossover operation, mutGaussian for the mutation operation, SPEA2 selection is used for select.
5. Running the algorithm: 50 generations of evolution using algorithms.eaSimple. The crossover probability (cxpb) is 70% and the mutation probability (mutpb) is 20%.
6. Display of final results: Display the individuals of the last generation and their adaptations (evaluation results).

Example of the run results: Upon execution, the optimal solution obtained during the evolutionary process is displayed.

Individual: [2.8, -3.1], Fitness: (9.950000000000001, 18.29)
Individual: [-1.3, 0.9], Fitness: (1.8299999999999998, 0.9699999999999998)
...

Key implementation points include

• Use SPEA2 selection (tools.selSPEA2) to select based on intensity and density.
  There are two objective functions, and an optimal solution is searched for each objective.
• This code is a template for performing basic multi-objective optimization and can be adapted to a variety of problems by changing the objective functions.

Application Examples

SPEA2 (Strength Pareto Evolutionary Algorithm 2) is widely used to solve multi-objective optimization problems. Specific applications of SPEA2 are described below.

1. engine design optimization: In automotive and aircraft engine design, multiple objectives (e.g., improving fuel economy, reducing emissions, and improving engine performance) need to be optimized simultaneously. Since these often contradict each other, a multi-objective evolutionary algorithm such as SPEA2 is used to optimize the trade-offs.

• Objective: Fuel economy, emissions, engine performance
• Application: optimization of engine design (engine components, combustion efficiency, exhaust gas treatment, etc.)
• Results: A set of designs that maximize fuel economy and emissions while improving engine performance is obtained.

2. production scheduling in manufacturing: Production planning and scheduling issues frequently arise in the manufacturing industry; SPEA2 is used to optimize production schedules. SPEA2 is used to optimize production schedules, for example, to optimize multiple objectives simultaneously, such as minimizing production time, maximizing equipment utilization, and minimizing energy consumption.

• Objectives: production time, facility utilization, energy consumption
• Application: production scheduling, resource allocation
• Result: schedule optimization across multiple factory lines to improve production efficiency while reducing manufacturing costs.

3. power system design and operation: In power system design, SPEA2 is used to optimize the generation, transmission, and distribution systems. The goal will be to optimize multiple measures of power grid reliability, energy efficiency, and operating costs.

• Objective: Reliability, efficiency, cost
• Application: power system design and operational optimization
• Results: Determine optimal placement of power plants and transmission lines to improve energy efficiency and system reliability while reducing overall system costs.

4. multi-objective optimization of vehicle design: Vehicle design requires simultaneous optimization of various objectives such as vehicle weight, aerodynamics, crash safety, and manufacturing cost. Since these often conflict, multi-objective optimization algorithms such as SPEA2 are effective.

• Objectives: weight, aerodynamics, crashworthiness, manufacturing cost
• Application: Vehicle design (optimization of body structure, engine, suspension, etc.)
• Result: Balanced optimization of multiple performance indicators in vehicle design to improve vehicle efficiency and safety.

5. communication network optimization: communication network design requires simultaneous optimization of multiple objectives such as traffic capacity, latency, cost, etc. SPEA2 is used to solve these optimization problems.

• Objective: Traffic capacity, latency, and cost
• Application: telecom network design (network topology, connection optimization)
• Result: Provide a network design that maximizes communication network performance and minimizes traffic capacity and latency.

6. optimize product pricing strategies: In the marketing field, multiple objectives must be simultaneously optimized in order to optimize product pricing and promotion strategies. For example, sales revenue, brand awareness, customer satisfaction, etc. SPEA2 can be applied to such multi-objective pricing problems.

• Objective: Sales revenue, customer satisfaction, brand awareness
• Application: Optimize product pricing and sales strategies
• Results: Achieve competitive pricing, increase customer satisfaction, and maximize sales revenue.

reference book

Describe reference books and resources related to SPEA2 (Strength Pareto Evolutionary Algorithm 2).

1. “Multi-Objective Optimization Using Evolutionary Algorithms”

Author: Kalyanmoy Deb
Publisher: John Wiley & Sons
Publication Year: 2001

This book introduces the fundamentals of multi-objective optimization theory and algorithms and describes evolutionary algorithms including SPEA2. It provides a comprehensive description of multi-objective optimization techniques and methods in evolutionary algorithms.

2. “Evolutionary Multi-Criterion Optimization.”

Editors: Carlos A. Coello Coello, Enrique Zitzler, Kalyanmoy Deb, Patrick Artz
Publisher: Springer
Publication year: 2004

This book summarizes important contributions in the field of evolutionary multi-objective optimization and covers many evolutionary optimization algorithms, including SPEA2. In particular, the theoretical background of evolutionary algorithms and their practical applications are explained in detail.

3. “The Strength Pareto Evolutionary Algorithm 2”

Authors: Eckart Zitzler, Lothar Thiele, Marco Laumanns, Christian M. Fonseca, Peter J. Fleming
Publication Year: 2002

This paper provides a detailed description of the principles of the SPEA2 algorithm, the design philosophy of the algorithm, and performance evaluation; it is an essential resource for a better understanding of SPEA2 implementation.

4. “Multiobjective Optimization: Interactive and Evolutionary Approaches”

Authors: Jürgen Branke, Kalyanmoy Deb, Keshav Dahal, Harutoshi Kishi
Publisher: Springer
Publication year: 2008

This book focuses on methods for solving multi-objective optimization problems using evolutionary approaches, describes SPEA2 and other multi-objective optimization algorithms, and introduces solutions that combine interactive and evolutionary approaches.

5. “Handbook of Evolutionary Computation.”

Editors: Thomas Bäck, David B. Fogel, Zbigniew Michalewicz
Publisher: Oxford University Press
Publication year: 1997

An extensive resource on evolutionary computation, including information on algorithms related to SPEA2 and multi-objective optimization. It will provide a comprehensive study of evolutionary algorithms from the basics to applications.

6. “Multi-Objective Optimization using Evolutionary Algorithms”

Authors: Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, T. Meyarivan
Publisher: Springer
Publication Year: 2002

The book is concerned with the design and analysis of algorithms for multi-objective optimization problems, and describes the theory and algorithmic evolutionary methods associated with SPEA2.