MOPSO-CD: Multi-Objective Particle Swarm Optimization with Crowding Distance

MOPSO-CD: Multi-Objective Particle Swarm Optimization with Crowding Distance#

MOPSO-CD extends the traditional Particle Swarm Optimization (PSO) framework to handle multi-objective optimization problems through enhanced diversity mechanisms. The algorithm incorporates crowding distance-based leader selection and archive management to ensure a well-distributed Pareto front, making it particularly suitable for problems requiring good diversity preservation.

Key Features#

Crowding Distance-based Leader Selection: Uses crowding distance to select diverse leaders for particles, ensuring better exploration of the objective space.

External Archive Management: Maintains an external archive of non-dominated solutions with crowding distance-based pruning to preserve diversity.

Tournament Selection: Implements binary tournament selection with crowding distance to maintain diversity while keeping solution quality.

Enhanced Exploration: Increased inertia weight and velocity bounds for better exploration capabilities.

Algorithm Overview#

  1. Initialization: Initialize population, velocities, and personal bests

  2. Archive Management: Update external archive with non-dominated solutions using crowding distance pruning

  3. Diverse Leader Selection: Select leaders for particles using crowding distance-based tournament selection

  4. Velocity Update: Update velocities using cognitive and social components with selected leaders

  5. Position Update: Update particle positions with velocity bounds

  6. Personal Best Update: Update personal best solutions based on dominance

  7. Archive Pruning: Maintain archive size using crowding distance-based selection

Example#

[1]:

from pymoo.algorithms.moo.mopso_cd import MOPSO_CD
from pymoo.problems import get_problem
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter

problem = get_problem("zdt1")

algorithm = MOPSO_CD(
    pop_size=100,
    w=0.6,
    c1=2.0,
    c2=2.0,
    max_velocity_rate=0.5,
    archive_size=200,
    seed=1
)

res = minimize(problem,
               algorithm,
               ('n_gen', 200),
               seed=1,
               verbose=False)

plot = Scatter()
plot.add(problem.pareto_front(), plot_type="line", color="black", alpha=0.7)
plot.add(res.F, facecolor="none", edgecolor="red")
plot.show()

[1]:

<pymoo.visualization.scatter.Scatter at 0x1075a3070>
../../_images/algorithms_moo_mopso_cd_8_1.png

Customization#

MOPSO-CD can be customized with different parameters to balance exploration and exploitation:

[2]:

from pymoo.algorithms.moo.mopso_cd import MOPSO_CD
from pymoo.problems import get_problem
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter

problem = get_problem("zdt2")

# Customized MOPSO-CD with different parameters
algorithm = MOPSO_CD(
    pop_size=150,           # Larger population for better diversity
    w=0.729844,            # Standard PSO inertia weight
    c1=1.49618,            # Cognitive parameter
    c2=1.49618,            # Social parameter
    max_velocity_rate=0.2, # Lower velocity for more exploitation
    archive_size=100,      # Smaller archive for faster convergence
    seed=1
)

res = minimize(problem,
               algorithm,
               ('n_gen', 300),
               seed=1,
               verbose=False)

Scatter().add(res.F, facecolor="none", edgecolor="blue").show()

[2]:

<pymoo.visualization.scatter.Scatter at 0x1062d7be0>
../../_images/algorithms_moo_mopso_cd_10_1.png

Application to Multi-Objective Reinforcement Learning#

MOPSO-CD is particularly well-suited for multi-objective reinforcement learning problems like MO-HalfCheetah, where maintaining diversity in the objective space is crucial for finding a well-distributed set of trade-off solutions.

API#

class pymoo.algorithms.moo.mopso_cd.MOPSO_CD(pop_size=100, w=0.6, c1=2.0, c2=2.0, max_velocity_rate=0.5, archive_size=200, sampling=<pymoo.operators.sampling.rnd.FloatRandomSampling object>, output=<pymoo.util.display.multi.MultiObjectiveOutput object>, **kwargs)[source]

Multi-Objective Particle Swarm Optimization with Crowding Distance (MOPSO-CD) algorithm.

This implementation extends MOPSO with a crowding distance mechanism for leader selection and archive management to ensure a well-distributed Pareto front, suitable for problems like MO-HalfCheetah in multi-objective reinforcement learning.

Parameters:
pop_sizeint

The population size (number of particles)

wfloat

Inertia weight

c1float

Cognitive parameter (personal best influence)

c2float

Social parameter (global best influence)

max_velocity_ratefloat

Maximum velocity rate relative to the variable range

archive_sizeint

Maximum size of the external archive

samplingSampling

Sampling strategy for initialization

outputOutput

Output display

Algorithm Comparison#

MOPSO-CD differs from other multi-objective PSO variants in several key aspects:

  • Leader Selection: Uses crowding distance-based tournament selection instead of random selection

  • Archive Management: Implements sophisticated archive pruning using crowding distance

  • Exploration Focus: Higher inertia weight and velocity bounds for better exploration

  • Diversity Preservation: Enhanced mechanisms for maintaining solution diversity

References#

The algorithm is based on extensions of traditional MOPSO with crowding distance mechanisms for improved diversity preservation in multi-objective optimization problems.

Implementation#

This algorithm has been implemented by Rasa Khosrowshahi and extends traditional MOPSO with crowding distance mechanisms for leader selection and archive management. The implementation is particularly well-suited for multi-objective reinforcement learning problems where maintaining diversity in the objective space is crucial for finding well-distributed trade-off solutions.

Contents