A deterministic annealing algorithm for a combinatorial optimization problem using replicator equations

被引:8
作者
Tsuchiya, K [1 ]
Nishiyama, T [1 ]
Tsujita, K [1 ]
机构
[1] Kyoto Univ, Grad Sch Engn, Dept Aeronaut & Astronaut, Kyoto 6068501, Japan
关键词
combinatorial optimization problem; replicator equation; bifurcation; deterministic annealing algorithm;
D O I
10.1016/S0167-2789(00)00196-2
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We have proposed an optimization method for a combinatorial optimization problem using replicator equations. To improve the solution further, a deterministic annealing algorithm may be applied. During the annealing process, bifurcations of equilibrium solutions will occur and affect the performance of the deterministic annealing algorithm. In this paper, the bifurcation structure of the proposed model is analyzed in detail. It is shown that only pitchfork bifurcations occur in the annealing process, and the solution obtained by the annealing is the branch uniquely connected with the uniform solution. It is also shown experimentally that in many cases, this solution corresponds to a good approximate solution of the optimization problem. Based on the results, a deterministic annealing algorithm is proposed and applied to the quadratic assignment problem to verify its performance. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:161 / 173
页数:13
相关论文
共 14 条
[1]  
BILBRO G, 1989, ADV NEURAL INFORMATI, V1, P91
[2]   QAPLIB - A quadratic assignment problem library [J].
Burkard, RE ;
Karisch, SE ;
Rendl, F .
JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (04) :391-403
[3]  
Guckenheimer J., 1983, NONLINEAR OSCILLATIO
[4]   Treatment of combinatorial optimization problems using selection equations with cost terms. Part I. Two-dimensional assignment problems [J].
Haken, H ;
Schanz, M ;
Starke, J .
PHYSICA D, 1999, 134 (02) :227-241
[5]  
HOPFIELD JJ, 1985, BIOL CYBERN, V52, P141
[6]   λ-opt neural approaches to quadratic assignment problems [J].
Ishii, S ;
Niitsuma, H .
NEURAL COMPUTATION, 2000, 12 (09) :2209-2225
[7]   Constrained neural approaches to quadratic assignment problems [J].
Ishii, S ;
Sato, M .
NEURAL NETWORKS, 1998, 11 (06) :1073-1082
[8]  
Pardalos P. M., 1994, Quadratic Assignment and Related Problems. DIMACS Workshop, P1
[9]  
Peterson C., 1989, International Journal of Neural Systems, V1, P3, DOI 10.1142/S0129065789000414
[10]  
Peterson C., 1988, Complex Systems, V2, P59