Related Experiment Videos
Effective Memetic Algorithms for VLSI design = Genetic Algorithms + local search + multi-level clustering.
1School of Engineering, University of Guelph, Guelph, Ontario, N1G 2W1, Canada. sareibi@uoguelph.ca
Evolutionary Computation
|September 10, 2004
Summary
Memetic Algorithms (MAs), a type of Evolutionary Algorithm (EA), enhance optimization by combining global and local search. This study shows MAs significantly improve VLSI circuit layout solutions, boosting quality by 35% for partitioning and 54% for placement.
Area of Science:
- Computer Science
- Artificial Intelligence
- Optimization Techniques
Background:
- Hybrid optimization strategies often integrate global and local search methods.
- Memetic Algorithms (MAs), a subset of Evolutionary Algorithms (EAs), are recognized for their effectiveness in solving complex combinatorial optimization problems by incorporating local search to refine individual solutions.
- The design and application of MAs involve critical considerations for optimal performance.
Purpose of the Study:
- To identify and explore key issues influencing the design and application of Memetic Algorithms.
- To present a hybrid approach combining hierarchical design, Genetic Algorithms, constructive techniques, and advanced local search for VLSI circuit layout.
- To evaluate the effectiveness of this MA-based approach for VLSI circuit partitioning and placement.
Main Methods:
- A hybrid optimization strategy was developed, integrating hierarchical design, Genetic Algorithms, constructive techniques, and advanced local search.
- The proposed method was applied to solve the VLSI circuit layout problem, specifically addressing circuit partitioning and placement.
- Memetic Algorithms were employed, leveraging local search, clustering, and the generation of good initial solutions.
Main Results:
- The Memetic Algorithm approach demonstrated significant improvements in solution quality for VLSI circuit layout tasks.
- Specifically, solution quality improved by an average of 35% for the VLSI circuit partitioning problem.
- Furthermore, solution quality improved by an average of 54% for the VLSI standard cell placement problem.
Conclusions:
- Memetic Algorithms, particularly when enhanced with local search, clustering, and effective initial solutions, offer substantial benefits for complex optimization problems.
- The developed hybrid approach effectively addresses challenging VLSI circuit layout problems, yielding superior results compared to existing methods.
- The findings underscore the potential of Memetic Algorithms as a powerful tool for improving efficiency and quality in VLSI design and other combinatorial optimization domains.