Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP)

• Published in: IEEE transactions on cybernetics 2009-04, Vol.39 (2), p.489-502
• Main Authors: Xie, Xiao-Feng, Liu, Jiming
• Format: Article
• Language: English
• Subjects: Algorithms; Assembly; Computation; Computer science; Cooperative systems; Cybernetics; Heuristic; Multiagent systems; Optimization; Optimization methods; Programming; Proteins; Runtime; Searching; Studies; Switches; Traveling salesman problem; Traveling salesman problems; traveling salesman problems (TSPs); Very large scale integration
• ISSN: 1083-4419; 2168-2267; 1941-0492; 2168-2275
• DOI: 10.1109/TSMCB.2008.2006910

The multiagent optimization system (MAOS) is a nature-inspired method, which supports cooperative search by the self-organization of a group of compact agents situated in an environment with certain sharing public knowledge. Moreover, each agent in MAOS is an autonomous entity with personal declarative memory and behavioral components. In this paper, MAOS is refined for solving the traveling salesman problem (TSP), which is a classic hard computational problem. Based on a simplified MAOS version, in which each agent manipulates on extremely limited declarative knowledge, some simple and efficient components for solving TSP, including two improving heuristics based on a generalized edge assembly recombination, are implemented. Compared with metaheuristics in adaptive memory programming, MAOS is particularly suitable for supporting cooperative search. The experimental results on two TSP benchmark data sets show that MAOS is competitive as compared with some state-of-the-art algorithms, including the Lin-Kernighan-Helsgaun, IBGLK, PHGA, etc., although MAOS does not use any explicit local search during the runtime. The contributions of MAOS components are investigated. It indicates that certain clues can be positive for making suitable selections before time-consuming computation. More importantly, it shows that the cooperative search of agents can achieve an overall good performance with a macro rule in the switch mode, which deploys certain alternate search rules with the offline performance in negative correlations. Using simple alternate rules may prevent the high difficulty of seeking an omnipotent rule that is efficient for a large data set.