Genetische Algorithmen

Beteiligte Mitarbeiter
Lehrstuhl für Rechnerarchitektur
Frank Schmiedle, Dr.-Ing.
Rolf Drechsler, Prof. Dr.
Nicole Drechsler, Dr.

Projektbeschreibung

In VLSI CAD sind häufig schwierige Optimierungsprobleme zu lösen. Eine Methode, die in den zurückliegenden Jahren mit wachsendem Interesse untersucht und eingesetzt wurde, sind genetische Algorithmen(GA). Diese Optimierungsmethode ist an die Evolutionstheorie angelehnt: charakteristische Beschreibungen von Problemlösungen werden codiert und bilden sogenannte Individuen, die mit Hilfe einer Fitnessfunktion bewertet werden. Durch wiederholte Auswahl, Rekombination und Eliminierung werden immer neue Individuen, also Lösungen erzeugt, und Ziel ist, daß diese im Laufe der Generationen bzgl. ihrer Fitness immer besser werden. Genetische Algorithmen bzw. evolutionäre Strategien sind oft in der Lage, bessere Lösungen zu finden als dies bei anderen Optimierungsmethoden der Fall ist. Ein Nachteil dieses Verfahrens sind die teilweise sehr hohen Laufzeiten.

Struktur des Projekts

Genetic Algorithm Managing Environment

GAME ist ein C++-Softwarepaket, das einerseits den Rahmen für den Ablauf genetischer Algorithmen inklusive aller notwendigen Module wie z.B. Selektion oder Rekombination zur Verfügung stellt, andererseits aber auch eine einheitliche Schnittstelle und die Möglichkeit, benutzerdefinierte Module einzubinden, bietet. Durch dieses Konzept kann GAME komfortabel an die jeweilige Anwendung angepaßt werden und ist so im Bereich der genetischen Algorithmen sehr vielseitig anwendbar.

Anwendungen in CAD

Am Lehrstuhl für Rechnerarchitektur wurden und werden genetische Algorithmen in mehreren Teilbereichen des VLSI CAD, genauer in der Logiksynthese, der physikalischen Synthese sowie auch im Bereich des Testens mit Erfolg eingesetzt. In der Logiksynthese wurden auf diese Art beispielsweise AND/EXOR-Minimierung und mehrschichtige Schaltungsminimierung untersucht. Bei der physikalischen Synthese wurden GAs in den Bereichen Floorplanning und Routing angewendet. Beim Testen schließlich bediente man sich bei der Testmengengenerierung und integrierten Selbsttests evolutionärer Verfahren.

Publikationen

Christian Matuszweski, Frank Schmiedle, Dr.-Ing., Robby Schönfeld
Routing with Genetic Algorithms
Albert-Ludwigs-University Freiburg, Technical Report 125, 1999

Nicole Drechsler, Dr., Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
A New Model for Multi-Objective Optimization in Evolutionary Algorithms
International Conference on Computational Intelligence (Fuzzy Days), 1999

Martin Keim, Dr., Nicole Drechsler, Dr., Bernd Becker, Prof. Dr.
Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits
ASP Design Automation Conference, 1999

Nicole Drechsler, Dr., Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
GAME: A Software Environment for Using Genetic Algorithms in Circuit Design
International Conference on Applied Computer Systems, 1997

C. Ökmen, Martin Keim, Dr., R. Krieger, Bernd Becker, Prof. Dr.
On Optimizing BIST Architecture by Using OBDD-based Approaches and Genetic Algorithms
VLSI Test Symposium, 1997

Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
Learning Heuristics by Genetic Algorithms
ASP Design Automation Conference, 1995

Bernd Becker, Prof. Dr., Rolf Drechsler, Prof. Dr.
OFDD based Minimization of Fixed Polarity Reed-Muller Expressions Using Hybrid Genetic Algorithms
International Conference on Computer Design, 1994

Rolf Drechsler, Prof. Dr.
Evolutionary Algorithms for VLSI CAD
Kluwer Academic Publishers, 1998

Nicole Drechsler, Dr., Frank Schmiedle, Dr.-Ing., Daniel Große, Dipl.-Inf., Rolf Drechsler, Prof. Dr.
Heuristic Learning based on Genetic Programming
EuroGP, volume 2038 of LNCS, pp.1-10, Springer Verlag, 2001

Frank Schmiedle, Dr.-Ing., Nicole Drechsler, Dr., Daniel Große, Dipl.-Inf., Rolf Drechsler, Prof. Dr.
Priorities in Multi-Objective Optimization for Genetic Programming
Genetic and Evolutionary Computation Conference, pp.129-136, 2001

Frank Schmiedle, Dr.-Ing., Daniel Große, Dipl.-Inf., Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
Too Much Knowledge Hurts: Acceleration of Genetic Programs for Learning Heuristics
Int'l Conference on Computational Intelligence (Fuzzy Days), volume 2206 of LNCS, pp.479-491

Frank Schmiedle, Dr.-Ing., Nicole Drechsler, Dr., Daniel Große, Dipl.-Inf., Rolf Drechsler, Prof. Dr.
Heuristic Learning based on Genetic Programming
Genetic Programming and Evolvable Machines, 3(4):363-388

Frank Schmiedle, Dr.-Ing.
Exakte Verdrahtung mit symbolischen Methoden
Dissertation, Logos Verlag, 2003