An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem

Area of Science:

• Artificial Intelligence
• Computational Science
• Operations Research

Background:

• The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization challenge.
• Self-Organizing Maps (SOMs) are neural networks commonly applied to optimization problems.
• Existing SOM approaches for TSP have limitations in solution accuracy and efficiency.

Purpose of the Study:

• To develop a novel Self-Organizing Map (SOM) with an integrated learning rule for solving the Traveling Salesman Problem (TSP).
• To enhance the accuracy and efficiency of neural network-based solutions for TSP.
• To introduce the integrated SOM (ISOM) and its evolved variant (eISOM) for complex optimization tasks.

Main Methods:

• A novel learning rule integrating three mechanisms: neuron attraction to input, projection to convex hull, and attraction to neighbors.
• A genetic algorithm was employed to optimize the coordination of learning mechanisms and parameter settings, creating the evolved ISOM (eISOM).
• The eISOM was tested on three TSP datasets to evaluate its performance.

Main Results:

• The eISOM demonstrated quadratic computation complexity, comparable to other SOM-like networks.
• The eISOM achieved higher accuracy than several established TSP algorithms, including Budinich's SOM, expanding SOM, convex elastic net, and FLEXMAP.
• While not surpassing sophisticated heuristics, eISOM represents a significant advancement in neural network accuracy for TSP.

Conclusions:

• The developed integrated SOM (ISOM) with a genetic algorithm-optimized learning rule (eISOM) offers a powerful and efficient approach to the Traveling Salesman Problem.
• The eISOM provides a competitive neural network-based solution for TSP, outperforming several existing methods in accuracy.
• Further research may explore combining eISOM with advanced heuristics to achieve state-of-the-art performance in TSP solutions.