A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design

Chi Keong Goh, Kay Chen Tan, D. S. Liu, Swee Chiang ChiamEur. J. Oper. Res 2010 · DOI

TL;DR

This paper introduces a novel multi-objective particle swarm optimization (MOPSO) algorithm called CCPSO, which combines competitive and cooperative co-evolutionary strategies. CCPSO aims to improve the efficiency and effectiveness of MOPSO for complex, high-dimensional optimization problems by intelligently decomposing the problem and fostering collaboration and competition among sub-swarms.

What Problem Does This Paper Address?

Many real-world problems involve optimizing multiple, often conflicting, objectives simultaneously. Particle Swarm Optimization (PSO) is a popular metaheuristic for optimization, and its multi-objective variant (MOPSO) has shown promise due to its fast convergence. However, as optimization problems become more complex and higher-dimensional, MOPSO can struggle with premature convergence and computational cost. Existing co-evolutionary approaches have shown success in improving optimization algorithms by breaking down problems into smaller, manageable parts, but these have not been extensively applied to MOPSO. This paper addresses the need for a more robust and efficient MOPSO that can handle complex problems by integrating competitive and cooperative co-evolutionary principles.

Methods

The core innovation of this paper is the Competitive and Cooperative Co-evolutionary Multi-Objective Particle Swarm Optimization (CCPSO) algorithm. CCPSO decomposes the multi-objective optimization problem into several "subswarms," each responsible for a subset of the decision variables.

Here's how it works:

  • Cooperative Co-evolution: Subswarms collaborate to form complete solutions. To evaluate a particle from one subswarm, it's combined with the "representative" particles from all other subswarms. The representative is typically the best particle within that subswarm, determined by Pareto ranking and niche count to promote diversity.
  • Competitive Co-evolution: Subswarms compete for the right to represent specific decision variables. This competition is managed through a roulette wheel selection based on probabilities that are dynamically updated based on the outcome of the competition. This allows the problem decomposition to emerge organically rather than being fixed beforehand.
  • Problem Decomposition: The assignment of decision variables to subswarms is not static but evolves through the competitive process. This allows the algorithm to adapt to problem structures and interdependencies.
  • Global Best (gbest) Selection: For MOPSO, the concept of a single global best is replaced by a set of non-dominated solutions from an archive. Particles are assigned a gbest from this archive using independent binary tournament selection, with niche count used to encourage diversity.
  • Archiving: A fixed-size archive stores non-dominated solutions found during the search. When the archive is full, a recurrent truncation process based on niche count is used to remove the most crowded solutions, maintaining diversity.

Datasets

The CCPSO algorithm was evaluated on six established multi-objective test functions:

  • FON: A non-convex and non-linear tradeoff curve problem.
  • KUR: Characterized by a disconnected tradeoff curve.
  • ZDT4: A severely multi-modal landscape with many local fronts.
  • ZDT6: Features a biased search space and non-uniformly distributed solutions.
  • DTLZ2 & DTLZ3: Used to test performance in high-dimensional objective spaces. For these, the problem was formulated with five objectives.

The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • Emergent Problem Decomposition: The competitive co-evolutionary aspect is crucial. Instead of pre-defining how to split the problem, CCPSO allows the subswarms to "fight" for representation, leading to a more adaptive and potentially better decomposition that exploits problem structure.
  • Balancing Competition and Cooperation: The synergy between competitive (problem decomposition) and cooperative (solution building) mechanisms is key. Competition drives specialization and adaptation, while cooperation allows for the construction of full solutions and evaluation.
  • Diversity through Niche Count and Archiving: The use of niche count for selecting representatives and managing the archive is a deliberate strategy to prevent premature convergence and ensure a well-distributed Pareto front, a common challenge in MOPSO.
  • PSO's Speed Advantage: The paper acknowledges that PSO-based algorithms generally exhibit faster convergence than traditional evolutionary algorithms. CCPSO aims to retain this speed while mitigating its tendency for premature convergence in complex scenarios.

Key Results

CCPSO was compared against several state-of-the-art multi-objective evolutionary algorithms (MOEAs) like NSGAII, SPEA2, IMOEA, PAES, and other MOPSO variants (SMOPSO, CMOPSO).

  • Competitive Performance: CCPSO demonstrated competitive, and often superior, performance across various test functions and performance metrics (Generational Distance - GD, Maximum Spread - MS, Spacing - S).
  • Handling Complex Problems: CCPSO showed particular strength in challenging problems like ZDT4, where it was the only algorithm capable of consistently attaining the true Pareto front. It also showed good performance on DTLZ3, demonstrating its ability to escape local optima.
  • PSO Benefits: CCPSO leveraged the fast convergence of PSO, outperforming many MOEAs in speed. However, unlike some pure PSO approaches, it managed to achieve better convergence and distribution on difficult problems.
  • Parameter Sensitivity: The study included a sensitivity analysis, showing that CCPSO's performance is influenced by parameters like inertia weight, subswarm size, and archive size, providing guidance for tuning. For instance, smaller inertia weights generally led to better convergence, while adaptive inertia schemes and larger archive sizes contributed to better diversity.

Limitations and Future Work

  • Parameter Tuning: While a sensitivity analysis was performed, the optimal parameter settings might still be problem-dependent, and further research into adaptive parameter control could be beneficial.
  • Scalability: Although CCPSO is designed for high-dimensional problems, its scalability to extremely high dimensions or objective spaces was not exhaustively explored.
  • Computational Cost: While CCPSO aims to improve efficiency, the co-evolutionary process and multiple evaluations can still be computationally intensive for very large-scale problems.

The paper suggests that the competitive-cooperative co-evolutionary paradigm offers a promising avenue for enhancing MOPSO, and future work could explore its application to other complex optimization domains and investigate more advanced adaptive mechanisms.

Summary updated

BibTeX
@article{goh2010competitive,
  author = {Chi Keong Goh and Kay Chen Tan and D. S. Liu and Swee Chiang Chiam},
  title = {{A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design}},
  journal = {Eur. J. Oper. Res.},
  year = {2010},
  doi = {10.1016/j.ejor.2009.05.005},
}
Figure