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

Xiao Feng Xie*, Jiming LIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

50 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)489-502
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume39
Issue number2
DOIs
Publication statusPublished - 2009

Scopus Subject Areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Cooperative systems
  • Multiagent systems
  • Optimization methods
  • Traveling salesman problems (TSPs)

Fingerprint

Dive into the research topics of 'Multiagent optimization system for solving the traveling salesman problem (TSP)'. Together they form a unique fingerprint.

Cite this