Self-organized combinatorial optimization

Jiming LIU*, Yu Wang Chen, Gen Ke Yang, Yong Zai Lu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

13 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)10532-10540
Number of pages9
JournalExpert Systems with Applications
Issue number8
Publication statusPublished - Aug 2011

Scopus Subject Areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

User-Defined Keywords

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


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

Cite this