Stochastic evolution: a fast effective heuristic for some generic layout problems
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
There are two canonical optimization problems, network bisectioning (NB) and traveling salesman (TS), that emerge from the physical design and layout of integrated circuits. An analogy is used between iterative techniques for combinatorial optimization and the evolution of biological species to obtain the stochastic evolution (SE) heuristic for solving a wide range of combinatorial optimization problems. It is shown that SE can be specifically tailored to solve both NB and TS. Experimental results for the NB and TS problems show that the SE algorithm produces better quality solutions and is faster than the simulated annealing algorithm in all instances considered.Keywords
This publication has 13 references indexed in Scilit:
- Performance of a new annealing schedulePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Combinatorial optimization by stochastic evolutionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- ESp: Placement by simulated evolutionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- An evolution-based approach to partitioning ASIC systemsPublished by Association for Computing Machinery (ACM) ,1989
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- Genetic PlacementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Simulated annealing and combinatorial optimizationPublished by Association for Computing Machinery (ACM) ,1986
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- Design by natural selectionSynthese, 1963