Evolutionary algorithms, simulated annealing (SA), and tabu search (TS) are
general iterative algorithms for combinatorial optimization. The term evol
utionary algorithm is used to refer to any probabilistic algorithm whose de
sign is inspired by evolutionary mechanisms found in biological species. Mo
st 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 num
erous problems from a wide range of application domains. Furthermore, they
are even suitable for ill-posed problems where some of the parameters are n
ot known before hand. These properties are lacking in all traditional optim
ization 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 pro
blem and compared with respect to (1) quality of the best solution identifi
ed by each heuristic, (2) progress of the search from initial solution(s) u
ntil stopping criteria are met: (3) the progress of the cost of the best so
lution as a function of time (iteration count), and (4) the number of solut
ions found at successive intervals of the cost function. The benchmark prob
lem used is the floorplanning of very large scale integrated (VLSI) circuit
s. This is a hard multi-criteria optimization problem. Fuzzy logic is used
to combine all objective criteria into a single fuzzy evaluation (cost) fun
ction, which is then used to rate competing solutions. (C) 2001 Elsevier Sc
ience Ltd. All rights reserved.