A Multi-start Simulated Annealing using Immunity-based Operations and its Application to the Quadratic Assignment Problems

S. Koakutsu, T. Hamagami, and H. Hirata (Japan)


Simulated Annealing, Immune System, Quadratic Assignment Problem


Simulated Annealing (SA) is known as one of useful heuristic optimization techniques. However the performance of standard SA depends on an initial state at starting temperature due to one-point search feature of SA. In this paper, to overcome the dependency on the initial state, we propose a novel optimization method named Multi-start Simulated Annealing using an Immunity based Operations (MSA/Io) introducing some features of immune system into Multi-start SA (MSA) which searches the solution space for optimal solutions in parallel starting from more than one initial state. We high light two mechanisms of immune system called “clonal selection” and “idiotypic network.” Clonal selection intensifies searching in the neighborhood of good solutions and idiotypic network maintains the diversification of the search. MSA/Io is expected to improve the local search ability using clonal selection and improve the global search ability using idiotypic network. We demonstrate the efficiency of MSA/Io by applying it to the quadratic assignment problems. Experimental results indicate that MSA/Io performs better than SA and MSA.

Important Links:

Go Back