How Autonomy Oriented Computing (AOC) tackles a computationally hard optimization problem

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 MAOS_E, 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.