An-Najah University Journal for Research - A (Natural Sciences)

Article info

Keywords

• Particle Swarm Optimization (PSO)
• Genetic algorithm (GA)
• Simulated Annealing (SA)
• Traveling Salesman Problem (TSP)

Abstract

The Traveling Salesman Problem (TSP) is a challenging computational problem in combinatorial optimization that aims to visit all cities exactly once and return to the first city. Despite that numerous theoretical solutions have been proposed in the literature, finding the exact optimal solution remains computationally infeasible due to the NP-hard nature of the problem. To address this, many heuristic and optimization approaches have been developed to generate probabilistic results that are often approximations. This paper presents a comparison between four popular algorithms: steepest ascent hill climbing, simulated annealing, genetic algorithm with partially matched crossover, and Particle Swarm Optimization (PSO). The study examines how these algorithms can solve the TSP and avoid local minimum values while achieving a balance between research exploration and exploitation for an optimal solution. For a relatively large number of cities, the simulated annealing algorithm and genetic algorithm produce promising results whilst the genetic algorithm takes longer time to execute due to the iterative application of its variation operators.

معلومات المقال

الكلمات الإفتتاحية

• Particle Swarm Optimization (PSO)
• Genetic algorithm (GA)
• Simulated Annealing (SA)
• Traveling Salesman Problem (TSP)

الملخص

The Traveling Salesman Problem (TSP) is a challenging computational problem in combinatorial optimization that aims to visit all cities exactly once and return to the first city. Despite that numerous theoretical solutions have been proposed in the literature, finding the exact optimal solution remains computationally infeasible due to the NP-hard nature of the problem. To address this, many heuristic and optimization approaches have been developed to generate probabilistic results that are often approximations. This paper presents a comparison between four popular algorithms: steepest ascent hill climbing, simulated annealing, genetic algorithm with partially matched crossover, and Particle Swarm Optimization (PSO). The study examines how these algorithms can solve the TSP and avoid local minimum values while achieving a balance between research exploration and exploitation for an optimal solution. For a relatively large number of cities, the simulated annealing algorithm and genetic algorithm produce promising results whilst the genetic algorithm takes longer time to execute due to the iterative application of its variation operators.