Strength Pareto Evolution Algorithm

Strength Pareto Evolution Algorithm #

Name #

Strength Pareto Evolution Algorithm (SPEA)

Taxonomy #

SPEA is an evolutionary algorithm for multi-objective optimization that belongs to the field of Evolutionary Computation, a subfield of Computational Intelligence. It is closely related to other multi-objective evolutionary algorithms such as the Non-dominated Sorting Genetic Algorithm (NSGA) and the Pareto Archived Evolution Strategy (PAES).

  • Computational Intelligence
    • Evolutionary Computation
      • Evolutionary Algorithms
        • Multi-objective Optimization
          • Strength Pareto Evolution Algorithm (SPEA)

Strategy #

SPEA maintains two populations: the main population and an external archive that stores non-dominated solutions found so far. The fitness of individuals in the main population is calculated based on the number of solutions in the archive that dominate them. This encourages the main population to evolve towards the Pareto front.

The archive has a fixed size. If the number of non-dominated solutions exceeds the archive size, a clustering technique is used to reduce the archive while preserving the diversity of solutions. This ensures that the archive represents a well-distributed approximation of the Pareto front.

In each generation, the main population undergoes selection, crossover, and mutation to create offspring. The offspring are then combined with the archive, and the non-dominated solutions from this combined population form the new archive. The main population for the next generation is filled by selecting individuals from the new archive using binary tournament selection.

Procedure #

Data Structures:

  • Population: The main population of individuals
  • Archive: The external archive storing non-dominated solutions
  • Individual: Represents a solution, containing decision variables and objective values

Parameters:

  • popSize: Size of the main population
  • archiveSize: Maximum size of the archive
  • maxGenerations: Maximum number of generations
  • crossoverRate: Probability of applying crossover
  • mutationRate: Probability of applying mutation

Steps:

  1. Initialize Population with popSize random individuals
  2. Evaluate the objective values of each individual in Population
  3. Initialize an empty Archive
  4. For each Individual in Population:
    • If Individual is not dominated by any member of Archive, add it to Archive
    • Remove any members of Archive that are dominated by Individual
  5. If the size of Archive exceeds archiveSize, reduce Archive using clustering
  6. Assign fitness to each Individual in Population based on the number of members in Archive that dominate it
  7. While the termination criterion (e.g., maxGenerations) is not met:
    1. Select parents from Population using binary tournament selection
    2. Apply crossover to the selected parents with probability crossoverRate to create offspring
    3. Apply mutation to the offspring with probability mutationRate
    4. Evaluate the objective values of the offspring
    5. Combine the offspring with Archive
    6. Update Archive by removing dominated solutions and reducing its size using clustering if necessary
    7. Fill Population for the next generation by selecting popSize individuals from Archive using binary tournament selection
  8. Return Archive as the approximation of the Pareto front

Considerations #

Advantages:

  • Maintains diversity in the Pareto front approximation through the use of an external archive and clustering
  • Encourages convergence towards the Pareto front by assigning fitness based on dominance
  • Can handle complex multi-objective optimization problems with many objectives and decision variables

Disadvantages:

  • The clustering technique used to reduce the archive size can be computationally expensive, especially for high-dimensional objective spaces
  • The performance of SPEA is sensitive to the choice of parameters, such as population size, archive size, and clustering parameters
  • Like other evolutionary algorithms, SPEA may require a large number of function evaluations to converge to a good approximation of the Pareto front

Heuristics #

Population and Archive Sizing:

  • The population size should be large enough to maintain diversity but not so large that computational efficiency suffers. A typical range is 50-200 individuals.
  • The archive size should be chosen to balance the quality of the Pareto front approximation with computational complexity. A common heuristic is to set the archive size equal to the population size.

Crossover and Mutation:

  • The crossover rate should be high enough to promote exploration of the search space but not so high that good solutions are frequently disrupted. A typical range is 0.7-0.9.
  • The mutation rate should be low enough to allow convergence but high enough to maintain diversity and avoid premature convergence. A typical range is 1/n to 1/2n, where n is the number of decision variables.

Clustering Parameters:

  • The clustering technique used to reduce the archive size should be chosen based on the characteristics of the problem, such as the number of objectives and the shape of the Pareto front.
  • The number of clusters should be set to balance the preservation of diversity with the computational complexity of clustering. A common heuristic is to set the number of clusters equal to the archive size divided by 10.

Termination Criteria:

  • The maximum number of generations should be set high enough to allow convergence but not so high that computational resources are wasted. A typical range is 100-1000 generations.
  • Additional termination criteria, such as the rate of improvement in the Pareto front approximation, can be used to stop the algorithm early if convergence has been achieved.