Self-organized combinatorial optimization

Jiming Liu, Yu Wang Chen, Gen Ke Yang, Yong Zai Lu

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we present a self-organized computing approach to solving hard combinatorial optimization problems, e.g.; the traveling salesman problem (TSP). First of all, we provide an analytical characterization of such an approach, by means of formulating combinatorial optimization problems into autonomous multi-entity systems and thereafter examining the microscopic characteristics of optimal solutions with respect to discrete state variables and local fitness functions. Next, we analyze the complexity of searching in the solution space based on the representation of fitness network and the observation of phase transition. In the second part of the paper, following the analytical characterization, we describe a decentralized, self-organized algorithm for solving combinatorial optimization problems. The validation results obtained by testing on a set of benchmark TSP instances have demonstrated the effectiveness and efficiency of the proposed algorithm. The link established between the microscopic characterization of hard computational systems and the design of self-organized computing methods provides a new way of studying and tackling hard combinatorial optimization problems. © 2011 Published by Elsevier Ltd.
Original languageEnglish
Pages (from-to)10532-10540
Number of pages8
JournalExpert Systems with Applications
Volume38
Issue number8
DOIs
Publication statusPublished - Aug 2011

Keywords

  • Combinatorial optimization
  • Fitness network
  • Microscopic characteristics
  • NP-complete
  • Phase transition
  • Self-organized computing
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'Self-organized combinatorial optimization'. Together they form a unique fingerprint.

Cite this