Evolutionary algorithms, simulated annealing, and Tabu search: a comparative study

Habib Youssef; Sadiq M. Sait; Hakim Adiche

doi:10.1117/12.326701

13 October 1998 Evolutionary algorithms, simulated annealing, and Tabu search: a comparative study

Habib Youssef, Sadiq M. Sait, Hakim Adiche

Proceedings Volume 3455, Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation; (1998) https://doi.org/10.1117/12.326701
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1998, San Diego, CA, United States

Abstract

Evolutionary algorithms, simulated annealing (SA), and Tabu Search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are Genetic Algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains.Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. the three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time, and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem was is the floorplanning of very large scale integrated circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation function, which is then used to rate competing solutions.

Citation Download Citation

Habib Youssef, Sadiq M. Sait, and Hakim Adiche "Evolutionary algorithms, simulated annealing, and Tabu search: a comparative study", Proc. SPIE 3455, Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation, (13 October 1998); https://doi.org/10.1117/12.326701

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available