GA-Framework

Entwicklung eines Optimierungsframework auf der Basis von Genetischen Algorithmen (GA).

Ausgangslage

Das i4Ds beschäftigt sich mit der Ermittlung von diversen, nicht analytisch lösbaren Optimierungsproblemen. Solche Probleme haben eine Komplexität, welche die Suche nach einer exakten Lösung innerhalb akzeptabler Zeiten nicht zulässt.
Für praktische Anwendungen ist es allerdings oft genügend, eine hinreichend gute Annäherungslösung zu bestimmen. Dazu eignen sich heuristische Optimierungsverfahren zu denen auch GA gehören. GA wurden bereits erfolgreich für unterschiedlichste praktische Optimierungsprobleme in Feldern wie Chemie, Biologie, Unternehmensforschung und in diversen Ingenieurdisziplinen eingesetzt.

Projektziele

Bereitstellung eines Optimierungsframeworks, welches für unterschiedliche Optimierungsprobleme verwendet werden kann.

Lösungsansatz

GA basieren auf Darwins Prinzipien der biologischen Evolution. Zu Beginn wird eine Ausgangspopulation von Lösungskandidaten (Individuen) zufällig erzeugt. Diese Population wird anschliessend einer simulierten Evolution (Mutation/Rekombination) unterzogen, bei welcher Individuen, welche bestimmten Gütekriterien besser entsprechen, eine grössere Chance haben, ihr Erbgut in die nächste Population weiterzugeben. So pflanzen sich Lösungskandidaten fort und unterliegen einem Selektionsdruck, der dafür sorgt, dass die Qualität des geeignetsten Individuums von Generation zu Generation zunimmt. Schlechte Lösungen sterben aus, die besten überleben.

Ergebnisse

Das GA-Framework wurde ursprünglich in JAVA entwickelt und später wurden Teile davon in C++ portiert. In der Zwischenzeit wurde es bereits für diverse Probleme eingesetzt:

  • Routenplanung für Inspektionsfahrten
  • Optimierung von Projektplänen
  • Optimierung von Entscheidungsalternativen
  • Optimierung von Fussgängerströmen
  • Optimierung des Layouts von Stanzformen
  • Generator von graphischen Logos

Weitere Informationen

Weitere Informationen zu den einzelnen Anwendungen des GA-Frameworks finden Sie in den nachfolgenden Veröffentlichungen:

  • Märki, F.; Fischer, M; Kunz, J.; Haymaker, J. (2007): Decision Making for Schedule Optimization, Department of Civil Engineering, Stanford University. Stanford 2007, USA. Electronic version of the paper: http://cife.stanford.edu/online.publications/TR169.pdf  
  • Märki, F.; Vogel, M.; Fischer, M.; (2006): Process Plan Optimization using a Genetic Algorithm, published in the proceedings of “The 6th International Conference on the Practice and Theory of Automated Timetabling”, Brno, 30th August – 1st September 2006.
  • Märki, F.; Vogel, M.; Breit, M.; Fischer M. (2006): Interactive Toolbox for 4D-Modeling. Published at the Joint International Conference on Computing and Decision Making in Civil and Building Engineering 2006. Paper number IC-293, Montreal, Canada.
  • Märki, F.; Suter, M.A.; Vogel, M.; Breit, M.; (2004): Optimization of 4D Process Planning using Genetic Algorithms, published in the proceedings of the "Xth International Conference on Computing in Civil and Building Engineering", Weimar, 02-04 June 2004. Electronic version of the paper: http://www.i4ds.ch/forschung/4d/download/68.pdf
  • Märki F.; Suter M.A.; (2003): Projektplanoptimierung mit Genetischen Algorithmen, Windisch, 27. November 2003. Electronic version of the paper: http://www.i4ds.ch/forschung/4d/download/DES.pdf

 

Projektbeteiligte

Leitung

  • Prof. Dr. Manfred Vogel

Projektteam

  • Fabian Märki (JAVA)
  • Ruedi Müller (C++)