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

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 declarat...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1083-4419
2168-2267
1941-0492
2168-2275
DOI:10.1109/TSMCB.2008.2006910