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

We have proposed an optimization method for a combinatorial optimization pr oblem using replicator equations. To improve the solution further, a determ inistic annealing algorithm may be applied. During the annealing process, b ifurcations of equilibrium solutions will occur and affect the performance of the deterministic annealing algorithm. In this paper, the bifurcation st ructure of the proposed model is analyzed in detail. It is shown that only pitchfork bifurcations occur in the annealing process, and the solution obt ained by the annealing is the branch uniquely connected with the uniform so lution. It is also shown experimentally that in many cases, this solution c orresponds to a good approximate solution of the optimization problem. Base d on the results, a deterministic annealing algorithm is proposed and appli ed to the quadratic assignment problem to verify its performance. (C) 2001 Elsevier Science B.V. All rights reserved.