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', 80),
               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 0x74a3b1057dd0>
../../_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=100,           # 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', 120),
               seed=1,
               verbose=False)

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

[2]:

<pymoo.visualization.scatter.Scatter at 0x74a3b1091950>
../../_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: int = 100, w: float = 0.6, c1: float = 2.0, c2: float = 2.0, max_velocity_rate: float = 0.5, archive_size: int = 200, sampling: ~pymoo.core.sampling.Sampling = <pymoo.operators.sampling.rnd.FloatRandomSampling object>, output: ~pymoo.util.display.output.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_size – The population size (number of particles)

  • w – Inertia weight

  • c1 – Cognitive parameter (personal best influence)

  • c2 – Social parameter (global best influence)

  • max_velocity_rate – Maximum velocity rate relative to the variable range

  • archive_size – Maximum size of the external archive

  • sampling – Sampling strategy for initialization

  • output – 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.

Acknowledgement#

The MOPSO-CD implementation in pymoo was contributed by Rasa Khosrowshahi and Gideon Oludeyi, extending traditional MOPSO with a crowding-distance mechanism for leader selection and archive management.

Thank you for the contribution — pymoo grows through community contributions like this one.

Contents