Uni-Logo
English       Login
Rechnerarchitektur
        Startseite         |         Institut für Informatik         |         Technische Fakultät
 

Genetische Algorithmen

| Beteiligte Mitarbeiter | Projektbeschreibung | Struktur des Projekts | Publikationen |


Beteiligte Mitarbeiter

Lehrstuhl für Rechnerarchitektur
Frank Schmiedle, Dr.-Ing.
Nicole Drechsler, Dr.
Rolf Drechsler, Prof. 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