Multiagent optimization system for solving the traveling salesman problem (TSP).

Area of Science:

• Computational Intelligence
• Operations Research
• Artificial Intelligence

Background:

• The Traveling Salesman Problem (TSP) is a computationally challenging problem in combinatorial optimization.
• Existing metaheuristics often rely on complex local search mechanisms.
• Nature-inspired, self-organizing multiagent systems offer a novel approach to optimization.

Purpose of the Study:

• To adapt and refine the Multiagent Optimization System (MAOS) for solving the TSP.
• To develop and evaluate novel, efficient components for MAOS specifically for TSP.
• To investigate the cooperative search dynamics and macro-rule strategies within MAOS for TSP.

Main Methods:

• Implementation of a simplified MAOS version with agents possessing limited declarative knowledge.
• Development of two improving heuristics based on generalized edge assembly recombination.
• Experimental evaluation on two TSP benchmark datasets, comparing MAOS against established algorithms.

Main Results:

• MAOS demonstrates competitive performance against state-of-the-art algorithms like Lin-Kernighan-Helsgaun, IBGLK, and PHGA.
• The system achieves good performance without employing explicit local search during runtime.
• Analysis reveals the positive contribution of MAOS components and the effectiveness of cooperative search with a switch-mode macro rule.

Conclusions:

• The refined MAOS provides a competitive, nature-inspired alternative for solving the TSP.
• Cooperative search enabled by MAOS agents, guided by simple alternate rules, achieves robust performance.
• This approach avoids the complexity of seeking a single, universally optimal rule for diverse TSP instances.