Related Experiment Videos
An efficient approach to the travelling salesman problem using self-organizing maps.
Frederico Carvalho Vieira1, Adrião Duarte Dória Neto, José Alfredo Ferreira Costa
1Computer Engineering Department, Universidade Federal do Rio Grande do Norte, Natal-RN, 59072-970, Brazil. fred@dca.ufrn.br
International Journal of Neural Systems
|August 19, 2003
Summary
This study introduces a novel approach to the Travelling Salesman Problem (TSP) using Self-Organizing Maps (SOM). The SOM-based algorithm achieves an average 3.7% deviation from optimal tour lengths for tested TSP instances.
Area of Science:
- Computational intelligence
- Operations research
- Artificial intelligence
Background:
- The Travelling Salesman Problem (TSP) is a classic combinatorial optimization challenge.
- Self-Organizing Maps (SOM) offer inherent topological properties suitable for optimization tasks.
Purpose of the Study:
- To present and analyze a novel algorithm for solving the TSP utilizing SOM.
- To investigate the initialization, parameter adaptation, and complexity of the SOM-based TSP approach.
Main Methods:
- Application of Self-Organizing Maps (SOM) to the Travelling Salesman Problem (TSP).
- Analysis of algorithm initialization and parameter adaptation strategies.
- Evaluation of the computational complexity of the proposed method.
Main Results:
- The SOM-based algorithm demonstrated effectiveness in solving TSP instances.
- An average deviation of 3.7% from the optimal tour length was achieved across 12 TSP instances.
- The study provides insights into the topological capabilities of SOM for optimization.
Conclusions:
- Self-Organizing Maps provide a viable and effective approach for tackling the Travelling Salesman Problem.
- The proposed SOM-based algorithm shows promising results with manageable deviations from optimal solutions.
- Further research can explore advanced SOM configurations for enhanced TSP performance.