TY - JOUR
T1 - Self-organized combinatorial optimization
AU - LIU, Jiming
AU - Chen, Yu Wang
AU - Yang, Gen Ke
AU - Lu, Yong Zai
N1 - Funding Information:
The work reported in this paper has been supported in part by a HKBU Faculty Research Grant (FRG) ( FRG/06-07/II-66 ) and in part by a Hong Kong Research Grant Council (RGC) Central Allocation Group Research Grant ( HKBU 1/05C ).
PY - 2011/8
Y1 - 2011/8
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - Fitness network
KW - Microscopic characteristics
KW - NP-complete
KW - Phase transition
KW - Self-organized computing
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=79953674766&partnerID=8YFLogxK
U2 - 10.1016/j.eswa.2011.02.103
DO - 10.1016/j.eswa.2011.02.103
M3 - Journal article
AN - SCOPUS:79953674766
SN - 0957-4174
VL - 38
SP - 10532
EP - 10540
JO - Expert Systems with Applications
JF - Expert Systems with Applications
IS - 8
ER -