An Improved Discrete Particle Swarm Optimization Algorithm for TSP

Changsheng Zhang, Jigui Sun, Yan Wang, Qingyun YangWeb Intelligence/IAT Workshops 2007 · DOI

TL;DR

This paper introduces a novel Discrete Particle Swarm Optimization (DPSO) algorithm, PDPSO, designed to tackle the Traveling Salesman Problem (TSP). By incorporating a "depressor" mechanism and a diversity measure, PDPSO effectively combats premature convergence, a common pitfall in swarm intelligence algorithms, while maintaining rapid convergence.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization challenge where the goal is to find the shortest possible route that visits a set of cities exactly once and returns to the origin city. Despite its simple definition, TSP is notoriously difficult to solve, especially as the number of cities increases. Many evolutionary algorithms, including Particle Swarm Optimization (PSO), have been applied to TSP. However, a significant issue with these algorithms is "premature convergence," where the swarm gets stuck in a suboptimal solution due to a loss of diversity in the search space. While some efforts have been made to address this in continuous PSO, fewer have focused on discrete versions like DPSO, which are more directly applicable to permutation-based problems like TSP. This paper aims to bridge that gap by proposing an improved DPSO that enhances diversity and prevents premature convergence.

Methods

The core of this paper is the development of a Permutation-based Discrete Particle Swarm Optimization (PDPSO) algorithm. Key novelties include:

  • Diversity Measure: A new metric is introduced to quantify the diversity of the current swarm. This measure is independent of swarm size and problem dimensionality.
  • Depressor Mechanism: A "depressor" procedure is devised to actively push particles away from each other when diversity is low, thereby preventing the swarm from collapsing into a single region of the search space.
  • Attractor-Depressor Switching: The diversity measure is used to dynamically switch between an "attractor" (standard PSO behavior, encouraging convergence) and the "depressor" (encouraging exploration). When diversity falls below a threshold, the depressor activates; once diversity recovers, the attractor takes over.
  • Discrete Operations: The paper defines specific operators for manipulating particle positions and velocities in the context of permutations, such as slide, reverse, subtraction, addition, and a novel "©" operator. These are crucial for handling the discrete nature of TSP.

Datasets

The PDPSO algorithm was evaluated on three standard TSP benchmark instances:

  • burma14: A small instance with 14 cities.
  • Oliver30: A medium-sized instance with 30 cities, noted as being used extensively in the literature.
  • eil51: A larger instance with 51 cities.

These datasets are commonly used for evaluating TSP algorithms and are available from sources like TSPLIB.

Key Insights and Ideas

  • Diversity is Key to Avoiding Sub-optimality: The paper strongly advocates for maintaining high diversity as a crucial strategy to prevent premature convergence in swarm intelligence algorithms.
  • Dynamic Switching for Optimal Balance: The intelligent switching between exploration (depressor) and exploitation (attractor) based on swarm diversity is a clever way to balance the often-conflicting goals of fast convergence and thorough exploration.
  • Discrete Operations Matter: The success of PDPSO hinges on carefully designed discrete operators that correctly handle permutations, ensuring that particle movements and updates are meaningful within the TSP context.

Key Results

The PDPSO algorithm was compared against standard DPSO and Ant Colony Optimization (ACO) on the selected TSP instances. The results, averaged over twenty runs, indicate:

  • Improved Performance: PDPSO achieved better or comparable "best" and "average" results across all tested instances compared to DPSO and ACO.
  • High Robustness: The algorithm demonstrated a high probability of finding the optimal solution for the burma14 and Oliver30 instances.
  • Fast Convergence: The paper highlights that PDPSO not only avoids premature convergence but also maintains rapid convergence, similar to the basic DPSO. Figure 2 visually supports this, showing PDPSO converging quickly and reaching a better fitness value than DPSO.

Limitations and Future Work

  • Dominance over Lin-Kernighan: The authors acknowledge that PDPSO is not as dominant as highly specialized algorithms like Lin-Kernighan for solving TSP.
  • Generalizability: While the paper focuses on TSP, the authors suggest that the PDPSO algorithm could be adapted to solve other common routing problems and combinatorial optimization problems with appropriate adjustments.
  • Further Exploration: The paper implies that further research could explore different diversity measures, depressor strategies, and applications to a wider range of combinatorial problems.

Summary updated

BibTeX
@inproceedings{zhang2007improved,
  author = {Changsheng Zhang and Jigui Sun and Yan Wang and Qingyun Yang},
  title = {{An Improved Discrete Particle Swarm Optimization Algorithm for TSP}},
  booktitle = {Web Intelligence/IAT Workshops},
  year = {2007},
  doi = {10.1109/wiiatw.2007.4427534},
}
Figure