Related Experiment Videos
Solving large scale traveling salesman problems by chaotic neurodynamics.
Mikio Hasegawa1, Tohru Ikeguch, Kazuyuki Aihara
1Wireless Communications Division, Independent Administrative Institution, Yokosuka-shi, Kanagawa, Japan. mikio@crl.go.jp
Summary
This study introduces a novel chaotic neural network approach to solve large Traveling Salesman Problems (TSPs). The method efficiently handles complex problems with significantly fewer neurons than traditional techniques.
Area of Science:
- Computational Intelligence
- Operations Research
- Artificial Neural Networks
Background:
- Traveling Salesman Problems (TSPs) are computationally intensive optimization challenges.
- Existing methods like stochastic and tabu searches have limitations in scalability for large problem instances.
Purpose of the Study:
- To develop a novel, efficient, and scalable approach for solving large-scale TSPs.
- To leverage chaotic dynamics within neural networks for enhanced search capabilities.
Main Methods:
- Realization of tabu search on a neural network using refractory effects as tabu effects.
- Extension to a chaotic neural network with two proposed search methods.
- Development of an automatic parameter tuning method for the chaotic neural network.
Main Results:
- A novel chaotic neural network approach for solving large-scale Traveling Salesman Problems (TSPs).
- Two types of chaotic search methods were proposed, with one requiring only n neurons for an n-city TSP.
- The n-neuron method demonstrated applicability to large TSPs (e.g., 85,900 cities) and outperformed conventional stochastic and tabu searches.
Conclusions:
- The proposed chaotic neural network method offers a scalable and effective solution for large-scale TSPs.
- The automatic parameter tuning simplifies the application of this method to diverse problems.
- This approach represents a significant advancement over existing search algorithms for complex combinatorial optimization.