TY - GEN
T1 - How Autonomy Oriented Computing (AOC) tackles a computationally hard optimization problem
AU - Xie, Xiao Feng
AU - LIU, Jiming
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - The hard computational problems, such as the traveling salesman problem (TSP), are relevant to many tasks of practical interest, which normally can be well formalized but are difficult to solve. This paper presents an extended multi agent optimization system, called MAOSE, for supporting cooperative problem solving on a virtual landscape and achieving high-quality solution(s) by the self-organization of autonomous entities. The realization of an optimization algorithm then can be described in three parts: a) encode the representation of the problem, which provides the virtual landscape and possible auxiliary knowledge; b) construct the memory elements at the initialization stage; and c) design the generate-and-test behavior guided by the law of socially-biased individual learning, through tailoring to the domain structure. The implementation is demonstrated on the TSP in details. The extensive experimental results on real-world instances in TSPLIB show its efficiency as comparing to other algorithms.
AB - The hard computational problems, such as the traveling salesman problem (TSP), are relevant to many tasks of practical interest, which normally can be well formalized but are difficult to solve. This paper presents an extended multi agent optimization system, called MAOSE, for supporting cooperative problem solving on a virtual landscape and achieving high-quality solution(s) by the self-organization of autonomous entities. The realization of an optimization algorithm then can be described in three parts: a) encode the representation of the problem, which provides the virtual landscape and possible auxiliary knowledge; b) construct the memory elements at the initialization stage; and c) design the generate-and-test behavior guided by the law of socially-biased individual learning, through tailoring to the domain structure. The implementation is demonstrated on the TSP in details. The extensive experimental results on real-world instances in TSPLIB show its efficiency as comparing to other algorithms.
KW - Autonomy oriented computing (AOC)
KW - Cooperative problem solving
KW - Emergent and collective behavior
KW - Global optimization
KW - Multiagent system
KW - Search
KW - Traveling salesman problem (TSP)
UR - http://www.scopus.com/inward/record.url?scp=34247250291&partnerID=8YFLogxK
U2 - 10.1145/1160633.1160747
DO - 10.1145/1160633.1160747
M3 - Conference contribution
AN - SCOPUS:34247250291
SN - 1595933034
SN - 9781595933034
T3 - Proceedings of the International Conference on Autonomous Agents
SP - 646
EP - 653
BT - Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems
T2 - Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Y2 - 8 May 2006 through 12 May 2006
ER -