„Fitnessfunktion“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][gesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
+Beispiel
Grundlegende Überarbeitung und Erweiterung des Artikels, siehe auch Diskussionsseite.
Zeile 1: Zeile 1:
Eine '''Fitnessfunktion''' ist die [[Zielfunktion]] eines [[evolutionärer Algorithmus|evolutionären (Optimierungs-)Algorithmus]] (EA). Gelegentlich wird eine Fitnessfunktion auch als Teil einer Zielfunktion beschrieben<ref>Thomas Jansen: ''Analyzing Evolutionary Algorithms: The Computer Science Perspective'', Seite 7.</ref> oder andersherum. Wie auch evolutionäre Algorithmen haben Fitnessfunktionen ein biologisches Vorbild, die [[biologische Fitness]], die den Grad der Anpassung eines [[Organismus]] an seine Umgebung angibt. Bei evolutionären Algorithmen beschreibt die Fitness eines Lösungskandidaten, wie gut er das zugrunde liegende Optimierungsproblem löst. Die Fitnessfunktion berechnet aus den Eigenschaften eines Lösungsversuchs, wie gut sich dieses „Individuum“ bzgl. des gestellten Problems als Lösung eignet.
Eine '''Fitnessfunktion''' ist die [[Zielfunktion]] eines [[evolutionärer Algorithmus|evolutionären (Optimierungs-)Algorithmus]] (EA). Gelegentlich wird eine Fitnessfunktion auch als Teil einer Zielfunktion beschrieben<ref>{{Literatur |Autor=Thomas Jansen |Titel=Analyzing Evolutionary Algorithms - The Computer Science Perspective |Band= |Nummer= |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2013 |Reihe= |ISBN=978-3-642-17338-7 |DOI=10.1007/978-3-642-17339-4 |Seiten= |Fundstelle=Seite 7 |Online=http://link.springer.com/10.1007/978-3-642-17339-4 |Abruf=2022-03-07}}</ref> oder umgekehrt. Wie auch evolutionäre Algorithmen haben Fitnessfunktionen ein biologisches Vorbild, die [[biologische Fitness]], die den Grad der Anpassung eines [[Organismus]] an seine Umgebung angibt und einen wesentlichen Faktor für seine Reproduktionswahrscheinlichkeit darstellt. Bei evolutionären Algorithmen beschreibt die Fitness eines Lösungskandidaten, wie gut er das zugrunde liegende Optimierungsproblem löst. Die Fitnessfunktion berechnet aus den Eigenschaften eines Lösungsversuchs, wie gut sich dieses „Individuum“ bzgl. des gestellten Problems als Lösung eignet.


Eine Fitnessfunktion muss nicht zwangsläufig einen absoluten Wert berechnen können, da es oft reicht, Kandidaten zu vergleichen, um den besseren auszuwählen. Eine relative Angabe der Fitness (Kandidat ''a'' ist besser als ''b'') genügt in manchen Fällen<ref>Thomas Baeck, D.B. Fogel, Z. Michalewicz: ''Evolutionary Computation 2: Advanced Algorithms and Operators'', Seite 2.</ref>, wie z.&nbsp;B. bei der [[Selektion (evolutionärer Algorithmus)#Turnierselektion|Turnierselektion]].
Eine Fitnessfunktion muss nicht zwangsläufig einen absoluten Wert berechnen können, da es oft reicht, Kandidaten zu vergleichen, um den besseren auszuwählen. Eine relative Angabe der Fitness (Kandidat ''a'' ist besser als ''b'') genügt in manchen Fällen<ref>{{Literatur |Autor= |Titel=Evolutionary Computation. Vol. 2, Advanced Algorithms and Operators |Hrsg=Thomas Bäck, David B. Fogel, Zbigniew Michalewicz |Verlag=CRC Press |Ort=Boca Raton |Datum=2000 |ISBN=0-585-30363-0 |DOI=10.1201/9781420034349 |Fundstelle=Seite 2 |Online= |Abruf=}}</ref>, wie z.&nbsp;B. bei der [[Selektion (evolutionärer Algorithmus)#Turnierselektion|Turnierselektion]] oder der [[Pareto-Optimierung]].


== Anforderungen an Bewertung und Fitnessfunktion ==
Wird eine Lösung zu mehreren Problemen gleichzeitig gesucht ([[Mehrzieloptimierung]]) und können diese nicht zusammengefasst werden, dann gibt die Fitnessfunktion keinen [[Skalar|einzelnen Wert]] zurück, sondern ein [[Tupel]].
Die Bedeutung der Bewertung und der Berechnung einer Fitnessfunktion ist für den Erfolg einer EA-Optimierung von grundlegender Bedeutung. Sie setzt [[Charles Darwin|Darwins]] Prinzip des "survival of the fittest" um. Ohne die auf der Fitness basierenden Selektionsmechanismen für die Partnerwahl und die Akzeptanz der Nachkommen wäre die EA-Suche blind und kaum vom [[Monte-Carlo-Algorithmus|Monte-Carlo-Verfahren]] zu unterscheiden. Bei der Aufstellung einer Fitnessfunktion muss man sich immer darüber im Klaren sein, dass es um mehr geht, als nur den gewünschten Zielzustand zu beschreiben. Vielmehr soll auch die evolutionäre Suche auf dem Weg zum Optimum möglichst unterstützt werden, sofern und insoweit dies nicht bereits von der Fitnessfunktion alleine geleistet wird.


== Beispiele ==
== Mehrzieloptimierung ==
Es soll ein Passagiersitz für Flugzeuge optimiert werden, dafür gebe es verschiedene Zielsetzungen:
Praktische Anwendungen haben in der Regel die Optimierung mehrerer und sich zumindest teilweise widersprechender Kriterien zum Ziel. Dazu ein Beispiel aus dem Gebiet der Designoptimierung. Es soll ein Passagiersitz für Flugzeuge optimiert werden und dafür gebe es verschiedene Zielsetzungen:
# er soll möglichst leicht sein;
# er soll möglichst leicht sein;
# er soll möglichst rund und nicht kantig sein;
# er soll möglichst stabil sein, wobei ein Mindestmaß an Stabilität nicht unterschritten werden darf;
# er soll kostengünstig herstellbar sein;
# er soll kostengünstig in Herstellung und Material sein;
# er soll möglichst wenig Material verwenden, das schwer zu recyceln ist.
# er soll möglichst wenig Material verwenden, das schwer zu recyceln ist;
# er soll möglichst rund und nicht kantig sein.
Die Fitnessfunktion berechne aus den Geometrieparametern dann einen Tupel mit vier Zahlen („je kleiner die Zahl, desto besser“):


Man kann davon ausgehen, dass sich die ersten drei Kriterien widersprechen und auch eine gute Erfüllung des vierten Kriteriums kann z.B. die Kosten erhöhen. Lediglich die Erfüllung des fünften Kriterium ist wahrscheinlich vom Grad der Erfüllung der anderen weitgehend unabhängig.
{ Gewicht ; Summe_der_Kantenlängen ; Herstellungskosten ; Masse_schlechtesMaterial }


Die Bewertung eines Designs des Passagiersitzes erfordert unterschiedliche Werkzeuge und Verfahren wie z. B. Simulatoren zur Ermittlung von Stabilität und Belastbarkeit, Kalkulationen zur Ermittlung von Produktions-, Einkaufs- und Entsorgungskosten sowie zur Berechnung des Produktgewichts. Diese Komponenten liefern jeweils Werte für die genannten Kriterien, die weiter verarbeitet werden müssen. Dazu werden häufig zwei grundsätzlich unterschiedliche Herangehensweisen benutzt, die [[Pareto-Optimierung]] und die Optimierung mit der [[Summe#Gewichtete Summe|gewichteten Summe]].<ref name=":0">{{Literatur |Autor= Kaisa Miettinen|Titel=Introduction to Multiobjective Optimization: Noninteractive Approaches |Hrsg=Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński |Sammelwerk=Multiobjective Optimization: Interactive and Evolutionary Approaches |Band=LNCS |Nummer=5252 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2008 |ISBN=978-3-540-88907-6 |DOI=10.1007/978-3-540-88908-3 |Seiten=1-26 }}</ref>
Verschiedene Sitzgeometrien können dann anhand ihrer zugehörigen Tupel eingestuft werden: Welche Variante ist am leichtesten, welche kostet am wenigsten?

=== Gewichtete Summe und Straffunktionen ===
Bei der Optimierung mit der gewichteten Summe erfolgt zunächst eine Normierung der einzelnen Werte, damit sie vergleichbar werden. Dies kann mit Hilfe von Kosten erfolgen oder dadurch, dass man jeweils Zielwerte vorgibt und den aktuellen Wert als Erfüllungsgrad ermittelt. Kosten bzw. Erfüllungsgrade sind dann miteinander vergleichbar und können bei Bedarf auch noch auf eine einheitliche Fitnessskala abgebildet werden. Jedem Kriterium wird ein Gewicht in Form eines Prozentwertes zugeordnet, sodass die Gesamtfitness als gewichtete Summe berechnet werden kann.

Die Verletzung von Restriktionen kann in Form von Straffunktionen in die so ermittelte Fitness einfließen. Dazu kann beispielsweise pro Restriktion eine Funktion definiert werden, die abhängig vom Grad der Verletzung einen Wert zwischen null und eins liefert, wobei das Resultat eins ist, wenn keine Restriktionsverletzung vorliegt. Die Straffunktionen werden mit der zuvor ermittelten Fitness multipliziert und das Resultat ist dann die Endfitness.

Diese Vorgehensweise ist einfach und hat den Vorteil, beliebig viele Kriterien und Straffunktionen zusammenfassen zu können. Nachteilig ist unter anderem, dass sich unterschiedliche Kriterien wechselseitig ausgleichen können und dass man die Gewichtungen vor der Optimierung festlegen muss.<ref>{{Literatur |Autor=Christian Blume, Wilfried Jakob |Titel=GLEAM - General Learning Evolutionary Algorithm and Method : ein Evolutionärer Algorithmus und seine Anwendungen |Verlag=KIT Scientific Publishing |Datum=2009 |DOI=10.5445/ksp/1000013553 |Online=http://digbib.ubka.uni-karlsruhe.de/volltexte/1000013553 |Abruf=2022-03-07}}</ref>

Obiges Beispiel könnte man z. B. so umsetzen, dass man entweder alle fünf Ziele zu Bewertungskriterien für die gewichtete Summe macht, oder aber einen Teil als Restriktionsverletzung begreift. Dies bietet sich beispielsweise bei der Stabilität an, bei der die Unterschreitung eines Mindestmaßes als Straffunktion behandelt wird. Oberhalb dieses Mindestwertes gibt es dann Fitnessanteile. Man kann das auch als Umsetzung des Prinzips ''Zuckerbrot und Peitsche'' ansehen. Es ist auch möglich, das fünfte Ziel als Straffunktion für die Anzahl zugänglicher Ecken und Kanten umzusetzen. Eine geschickte Ausnutzung dieser Freiheitsgrade kann die evolutionäre Suche unterstützen und so schneller zu besseren Lösungen führen.

=== Pareto-Optimierung ===
[[Datei:Transformationskurve - Effizienzbereiche und Realisierungsmöglichkeiten im Modell.jpg|mini|Pareto-Front zweier zu maximierender Kriterien.]]
Eine Lösung heißt ''[[Pareto-Optimum|Pareto-optimal]]'', wenn die Verbesserung eines Kriteriums nur bei einer Verschlechterung anderer Kriterien möglich ist. Die Menge aller Pareto-optimalen Lösungen, auch ''Pareto-Menge'' genannt, stellt die Menge aller optimalen Kompromisse zwischen den Kriterien dar. Nebenstehendes Bild zeigt beispielhaft die ''Pareto-Menge'' zweier zu maximierender Kriterien. Die Elemente der Menge bilden die ''Pareto-Front''. Aus dieser Menge muss nachträglich ein menschlicher Entscheider die beste Kompromisslösung auswählen.<ref name=":0" />

Schon früh wurde erkannt, dass EAs mit ihrer gleichzeitig betrachteten Lösungsmenge gut dazu geeignet sind, in einem Lauf Lösungen zu finden, die die Pareto-Front hinreichend gut abdecken.<ref>{{Literatur |Autor=Carlos M. Fonseca, Peter J. Fleming |Titel=An Overview of Evolutionary Algorithms in Multiobjective Optimization |Sammelwerk=Evolutionary Computation |Band=3 |Nummer=1 |Datum=1995-03 |ISSN=1063-6560 |DOI=10.1162/evco.1995.3.1.1 |Seiten=1–16 |Online=https://direct.mit.edu/evco/article/3/1/1-16/733 |Abruf=2022-03-07}}</ref><ref name=":1">{{Literatur |Autor=Kalyanmoy Deb |Titel=Introduction to Evolutionary Multiobjective Optimization |Hrsg=Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński |Sammelwerk=Multiobjective Optimization: Interactive and Evolutionary Approaches |Band=LNCS |Nummer=5252 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2008 |ISBN=978-3-540-88907-6 |DOI=10.1007/978-3-540-88908-3 |Seiten=58-96}}</ref> Neben dem SPEA2<ref>{{Literatur |Autor=Eckart Zitzler, Marco Laumanns, Lothar Thiele |Titel=SPEA2: Improving the strength pareto evolutionary algorithm |Band=Technical Report |Nummer=103 |Verlag=Computer Engineering and Networks Laboratory (TIK) |Ort=ETH Zürich |Datum=2001 |DOI=10.3929/ETHZ-A-004284029 |Online=http://hdl.handle.net/20.500.11850/145755 |Abruf=2022-03-04}}</ref> haben sich der NSGA-II<ref>{{Literatur |Autor=Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, T. Meyarivan |Titel=A fast and elitist multiobjective genetic algorithm: NSGA-II |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=6 |Nummer=2 |Datum=2002-04 |DOI=10.1109/4235.996017 |Seiten=182–197 |Online=http://ieeexplore.ieee.org/document/996017/ |Abruf=2022-03-04}}</ref> und NSGA-III<ref>{{Literatur |Autor=Kalyanmoy Deb, Himanshu Jain |Titel=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=18 |Nummer=4 |Datum=2014-08 |ISSN=1089-778X |DOI=10.1109/TEVC.2013.2281535 |Seiten=577–601 |Online=http://ieeexplore.ieee.org/document/6600851/ |Abruf=2022-03-04}}</ref><ref>{{Literatur |Autor=Himanshu Jain, Kalyanmoy Deb |Titel=An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach |Sammelwerk=IEEE Transactions on Evolutionary Computation |Band=18 |Nummer=4 |Datum=2014-08 |ISSN=1089-778X |DOI=10.1109/TEVC.2013.2281534 |Seiten=602–622 |Online=http://ieeexplore.ieee.org/document/6595567/ |Abruf=2022-03-04}}</ref> als Standardverfahren etabliert.

Beschränkungen werden bei der Pareto-Optimierung dadurch mit einbezogen, dass Lösungen ohne Verletzung von Beschränkungen per se besser sind als solche, die Verletzungen aufweisen. Haben zwei zu vergleichende Lösungen Beschränkungsverletzungen, so entscheidet das jeweilige Ausmaß der Verletzungen.<ref name=":1" />

Der Vorteil der Pareto-Optimierung besteht darin, dass sie im Gegensatz zur gewichteten Summe alle im Sinne der Kriterien gleichwertigen Alternativen als Gesamtlösung liefert. Der Nachteil besteht darin, dass eine [[Pareto-Optimierung#Dimension und Visualisierung|Visualisierung der Alternativen]] ab vier Kriterien problematisch bis unmöglich wird. Außerdem steigt der Aufwand mit der Anzahl der Kriterien exponentiell.<ref name=":2">{{Literatur |Autor=Wilfried Jakob, Christian Blume |Titel=Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. |Sammelwerk=Algorithms |Band=7 |Nummer=2 |Datum=2014-04-02 |ISSN=1999-4893 |DOI=10.3390/a7010166 |Seiten=166–185 }}</ref> Bei mehr als drei oder vier Kriterien müssen einige mit der gewichteten Summe oder anderen Aggregationsmethoden<ref name=":0" /> zusammengefasst werden.

Beim obigen Beispiel des Designs eines Passagiersitzes steht man angesichts der fünf Kriterien bei der Pareto-Optimierung bereits vor dem Problem, die Anzahl geeignet reduzieren zu müssen. Da die drei ersten Kriterien sich zumindest größtenteils widersprechen, bietet es sich an, sie zu drei Zielen einer Pareto-Optimierung zu machen. Wenn man die Unterschreitung der Stabilitätsuntergrenze (Ziel 2) und die Ziele 4 und 5 nicht mit Hilfe der gewichteten Summe zusammenfassen und zu einem vierten Kriterium machen will, könnte man sie noch einzeln als Restriktionen behandeln.

=== Vergleich beider Optimierungsarten ===
[[Datei:ParetoFront und Gewichtete Summe.png|links|mini|Zusammenhang zwischen der Pareto-Front und der gewichteten Summe.<ref name=":2" />]]
[[Datei:ParetoFront nicht konvex.png|mini|Beispiel einer nicht-konvexen Pareto-Front.<ref name=":2" />]]
Mit Hilfe der gewichteten Summe kann durch eine geeignete Wahl der Gewichte die gesamte Pareto-Front erreicht werden, sofern diese [[Konvexe Menge|konvex]] ist. Dies wird durch das nebenstehende Bild rechts illustriert. Der Punkt '''P''' auf der grünen Pareto-Front wird durch die Gewichte <math>w_1</math> und <math>w_2</math> erreicht, sofern der EA zum Optimum konvergiert. Die Richtung mit dem größten Fitnessgewinn in der Lösungsmenge <math>Z</math> ist durch die eingezeichneten Pfeile dargestellt.

Im Falle einer nicht-konvexen Front sind allerdings nicht-konvexe Frontabschnitte durch die gewichtete Summe nicht erreichbar. Im nebenstehenden Bild rechts ist das der Abschnitt zwischen den Punkten '''A''' und '''B'''. Dem kann durch die Verwendung der ''kaskadierten gewichteten Summe'' in begrenztem Maße abgeholfen werden.<ref name=":2" />

Vergleicht man beide Optimierungsansätze, so ist der Einsatz der Pareto-Optimierung sicher dann von Vorteil, wenn über die möglichen Lösungen einer Aufgabenstellung noch wenig bekannt ist und wenn die Anzahl der Optimierungsziele auf drei, maximal vier eingegrenzt werden kann. Bei wiederholter Optimierung von Variationen ein und derselben Aufgabenstellung sind jedoch die gewünschten Kompromisslinien bekannt und der Aufwand zur Ermittlung der gesamten Pareto-Front ist nicht mehr gerechtfertigt. Dies gilt auch dann, wenn keine menschliche Entscheidung nach der Optimierung erwünscht ist, wie z. B. in automatisierten Entscheidungsprozessen.<ref name=":2" />

== Hilfskriterien ==
[[Datei:Hilfskriterium-Beispiel.png|mini|300x300px|Beispiel zweier Schedules eines Auftrags, der eine späteste Fertigstellungszeit einhalten soll.<ref name=":3" />]]
Neben den sich aus der Aufgabenstellung ergebenden primären Zielen oder Kriterien, kann es erforderlich sein, Hilfskriterien mit in die Bewertung aufzunehmen, um die Erreichung von einem oder mehreren primären Zielen zu unterstützen. Zur Illustration wird das [[Genom (evolutionärer Algorithmus)#Genom für komplexe Gene|Schedulingbeispiel]] aus dem Artikel über die [[Genom (evolutionärer Algorithmus)|Genome von EAs]] herangezogen. Zu den Optimierungszielen zählt neben einer allgemeinen schnellen Bearbeitung aller Aufträge bei neu eingeführten Option eines Eilauftrags noch zusätzlich die Einhaltung einer spätesten Fertigstellungszeit. Diese wird durch den beispielhaften Ausgangsschedule verletzt, wie in nebenstehendem Bild dargestellt ist. Die nachfolgende Mutation ändert daran zwar nichts, plant aber den Arbeitsschritt '''d''' früher ein, was einen notwendigen Zwischenschritt für einen früheren Beginn vom letzten Arbeitsschritt '''e''' des Auftrags darstellt. Solange lediglich die späteste Fertigstellungszeit bewertet wird, bleibt die Fitness des mutierten Schedules aber unverändert, obwohl er einen relevanten Schritt zum Ziel einer rechtzeitigen Fertigstellung des Auftrags darstellt. Dem kann z.B. durch eine zusätzliche Bewertung der Verzögerung von Arbeitsschritten von Eilaufträgen abgeholfen werden. Das neue Kriterium ist ein Hilfskriterium, da es zusätzlich zu den eigentlichen Optimierungszielen eingeführt wurde, um deren Erreichung zu unterstützen. Eine ausführlichere Beschreibung und ein weiteres Beispiel können in <ref name=":3">{{Literatur |Autor=Wilfried Jakob |Titel=Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications |Verlag=Karlsruher Institut für Technologie (KIT) |Datum=2021 |arXiv=2107.11300 |DOI=10.5445/ir/1000135763 |Online=https://publikationen.bibliothek.kit.edu/1000135763 |Abruf=2022-03-02}}</ref> gefunden werden.

== Literatur ==
* {{Literatur|Herausgeber=Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński |Titel=Multiobjective Optimization: Interactive and Evolutionary Approaches| Verlag=Springer |Ort=Berlin, Heidelberg |Band=LNCS | Nummer=5252 |Jahr=2008|ISBN=978-3-540-88907-6 |DOI=10.1007/978-3-540-88908-3}}
* {{Literatur|Herausgeber=Thomas Baeck, David B. Fogel, Zbigniew Michalewicz |Titel=Handbook of Evolutionary Computation |Verlag=CRC Press |Ort=Boca Raton, USA |Jahr=1997 |ISBN=978-0-7503-0895-3 }}
* {{Literatur|Autor=Hartmut Pohlheim |Titel=Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis |Verlag=Springer |Ort=Berlin, Heidelberg |Jahr=1999 |ISBN=3-540-66413-0 }}
* {{Literatur|Autor=Volker Nissen |Titel=Einführung in evolutionäre Algorithmen: Optimierung nach dem Vorbild der Evolution |Verlag=Vieweg |Ort=Braunschweig |Jahr=1997 |ISBN=978-3-528-05499-1 |DOI=10.1007/978-3-322-93861-9}}
* {{Literatur|Autor=Karsten Weicker |Titel=Evolutionäre Algorithmen |Verlag=Springer Vieweg |Ort=Wiesbaden |Auflage=3 |Jahr=2015 |ISBN=978-3-658-09957-2 |DOI=10.1007/978-3-658-09958-9}}


== Einzelnachweise ==
== Einzelnachweise ==

Version vom 7. März 2022, 17:34 Uhr

Eine Fitnessfunktion ist die Zielfunktion eines evolutionären (Optimierungs-)Algorithmus (EA). Gelegentlich wird eine Fitnessfunktion auch als Teil einer Zielfunktion beschrieben[1] oder umgekehrt. Wie auch evolutionäre Algorithmen haben Fitnessfunktionen ein biologisches Vorbild, die biologische Fitness, die den Grad der Anpassung eines Organismus an seine Umgebung angibt und einen wesentlichen Faktor für seine Reproduktionswahrscheinlichkeit darstellt. Bei evolutionären Algorithmen beschreibt die Fitness eines Lösungskandidaten, wie gut er das zugrunde liegende Optimierungsproblem löst. Die Fitnessfunktion berechnet aus den Eigenschaften eines Lösungsversuchs, wie gut sich dieses „Individuum“ bzgl. des gestellten Problems als Lösung eignet.

Eine Fitnessfunktion muss nicht zwangsläufig einen absoluten Wert berechnen können, da es oft reicht, Kandidaten zu vergleichen, um den besseren auszuwählen. Eine relative Angabe der Fitness (Kandidat a ist besser als b) genügt in manchen Fällen[2], wie z. B. bei der Turnierselektion oder der Pareto-Optimierung.

Anforderungen an Bewertung und Fitnessfunktion

Die Bedeutung der Bewertung und der Berechnung einer Fitnessfunktion ist für den Erfolg einer EA-Optimierung von grundlegender Bedeutung. Sie setzt Darwins Prinzip des "survival of the fittest" um. Ohne die auf der Fitness basierenden Selektionsmechanismen für die Partnerwahl und die Akzeptanz der Nachkommen wäre die EA-Suche blind und kaum vom Monte-Carlo-Verfahren zu unterscheiden. Bei der Aufstellung einer Fitnessfunktion muss man sich immer darüber im Klaren sein, dass es um mehr geht, als nur den gewünschten Zielzustand zu beschreiben. Vielmehr soll auch die evolutionäre Suche auf dem Weg zum Optimum möglichst unterstützt werden, sofern und insoweit dies nicht bereits von der Fitnessfunktion alleine geleistet wird.

Mehrzieloptimierung

Praktische Anwendungen haben in der Regel die Optimierung mehrerer und sich zumindest teilweise widersprechender Kriterien zum Ziel. Dazu ein Beispiel aus dem Gebiet der Designoptimierung. Es soll ein Passagiersitz für Flugzeuge optimiert werden und dafür gebe es verschiedene Zielsetzungen:

  1. er soll möglichst leicht sein;
  2. er soll möglichst stabil sein, wobei ein Mindestmaß an Stabilität nicht unterschritten werden darf;
  3. er soll kostengünstig in Herstellung und Material sein;
  4. er soll möglichst wenig Material verwenden, das schwer zu recyceln ist;
  5. er soll möglichst rund und nicht kantig sein.

Man kann davon ausgehen, dass sich die ersten drei Kriterien widersprechen und auch eine gute Erfüllung des vierten Kriteriums kann z.B. die Kosten erhöhen. Lediglich die Erfüllung des fünften Kriterium ist wahrscheinlich vom Grad der Erfüllung der anderen weitgehend unabhängig.

Die Bewertung eines Designs des Passagiersitzes erfordert unterschiedliche Werkzeuge und Verfahren wie z. B. Simulatoren zur Ermittlung von Stabilität und Belastbarkeit, Kalkulationen zur Ermittlung von Produktions-, Einkaufs- und Entsorgungskosten sowie zur Berechnung des Produktgewichts. Diese Komponenten liefern jeweils Werte für die genannten Kriterien, die weiter verarbeitet werden müssen. Dazu werden häufig zwei grundsätzlich unterschiedliche Herangehensweisen benutzt, die Pareto-Optimierung und die Optimierung mit der gewichteten Summe.[3]

Gewichtete Summe und Straffunktionen

Bei der Optimierung mit der gewichteten Summe erfolgt zunächst eine Normierung der einzelnen Werte, damit sie vergleichbar werden. Dies kann mit Hilfe von Kosten erfolgen oder dadurch, dass man jeweils Zielwerte vorgibt und den aktuellen Wert als Erfüllungsgrad ermittelt. Kosten bzw. Erfüllungsgrade sind dann miteinander vergleichbar und können bei Bedarf auch noch auf eine einheitliche Fitnessskala abgebildet werden. Jedem Kriterium wird ein Gewicht in Form eines Prozentwertes zugeordnet, sodass die Gesamtfitness als gewichtete Summe berechnet werden kann.

Die Verletzung von Restriktionen kann in Form von Straffunktionen in die so ermittelte Fitness einfließen. Dazu kann beispielsweise pro Restriktion eine Funktion definiert werden, die abhängig vom Grad der Verletzung einen Wert zwischen null und eins liefert, wobei das Resultat eins ist, wenn keine Restriktionsverletzung vorliegt. Die Straffunktionen werden mit der zuvor ermittelten Fitness multipliziert und das Resultat ist dann die Endfitness.

Diese Vorgehensweise ist einfach und hat den Vorteil, beliebig viele Kriterien und Straffunktionen zusammenfassen zu können. Nachteilig ist unter anderem, dass sich unterschiedliche Kriterien wechselseitig ausgleichen können und dass man die Gewichtungen vor der Optimierung festlegen muss.[4]

Obiges Beispiel könnte man z. B. so umsetzen, dass man entweder alle fünf Ziele zu Bewertungskriterien für die gewichtete Summe macht, oder aber einen Teil als Restriktionsverletzung begreift. Dies bietet sich beispielsweise bei der Stabilität an, bei der die Unterschreitung eines Mindestmaßes als Straffunktion behandelt wird. Oberhalb dieses Mindestwertes gibt es dann Fitnessanteile. Man kann das auch als Umsetzung des Prinzips Zuckerbrot und Peitsche ansehen. Es ist auch möglich, das fünfte Ziel als Straffunktion für die Anzahl zugänglicher Ecken und Kanten umzusetzen. Eine geschickte Ausnutzung dieser Freiheitsgrade kann die evolutionäre Suche unterstützen und so schneller zu besseren Lösungen führen.

Pareto-Optimierung

Pareto-Front zweier zu maximierender Kriterien.

Eine Lösung heißt Pareto-optimal, wenn die Verbesserung eines Kriteriums nur bei einer Verschlechterung anderer Kriterien möglich ist. Die Menge aller Pareto-optimalen Lösungen, auch Pareto-Menge genannt, stellt die Menge aller optimalen Kompromisse zwischen den Kriterien dar. Nebenstehendes Bild zeigt beispielhaft die Pareto-Menge zweier zu maximierender Kriterien. Die Elemente der Menge bilden die Pareto-Front. Aus dieser Menge muss nachträglich ein menschlicher Entscheider die beste Kompromisslösung auswählen.[3]

Schon früh wurde erkannt, dass EAs mit ihrer gleichzeitig betrachteten Lösungsmenge gut dazu geeignet sind, in einem Lauf Lösungen zu finden, die die Pareto-Front hinreichend gut abdecken.[5][6] Neben dem SPEA2[7] haben sich der NSGA-II[8] und NSGA-III[9][10] als Standardverfahren etabliert.

Beschränkungen werden bei der Pareto-Optimierung dadurch mit einbezogen, dass Lösungen ohne Verletzung von Beschränkungen per se besser sind als solche, die Verletzungen aufweisen. Haben zwei zu vergleichende Lösungen Beschränkungsverletzungen, so entscheidet das jeweilige Ausmaß der Verletzungen.[6]

Der Vorteil der Pareto-Optimierung besteht darin, dass sie im Gegensatz zur gewichteten Summe alle im Sinne der Kriterien gleichwertigen Alternativen als Gesamtlösung liefert. Der Nachteil besteht darin, dass eine Visualisierung der Alternativen ab vier Kriterien problematisch bis unmöglich wird. Außerdem steigt der Aufwand mit der Anzahl der Kriterien exponentiell.[11] Bei mehr als drei oder vier Kriterien müssen einige mit der gewichteten Summe oder anderen Aggregationsmethoden[3] zusammengefasst werden.

Beim obigen Beispiel des Designs eines Passagiersitzes steht man angesichts der fünf Kriterien bei der Pareto-Optimierung bereits vor dem Problem, die Anzahl geeignet reduzieren zu müssen. Da die drei ersten Kriterien sich zumindest größtenteils widersprechen, bietet es sich an, sie zu drei Zielen einer Pareto-Optimierung zu machen. Wenn man die Unterschreitung der Stabilitätsuntergrenze (Ziel 2) und die Ziele 4 und 5 nicht mit Hilfe der gewichteten Summe zusammenfassen und zu einem vierten Kriterium machen will, könnte man sie noch einzeln als Restriktionen behandeln.

Vergleich beider Optimierungsarten

Zusammenhang zwischen der Pareto-Front und der gewichteten Summe.[11]
Beispiel einer nicht-konvexen Pareto-Front.[11]

Mit Hilfe der gewichteten Summe kann durch eine geeignete Wahl der Gewichte die gesamte Pareto-Front erreicht werden, sofern diese konvex ist. Dies wird durch das nebenstehende Bild rechts illustriert. Der Punkt P auf der grünen Pareto-Front wird durch die Gewichte und erreicht, sofern der EA zum Optimum konvergiert. Die Richtung mit dem größten Fitnessgewinn in der Lösungsmenge ist durch die eingezeichneten Pfeile dargestellt.

Im Falle einer nicht-konvexen Front sind allerdings nicht-konvexe Frontabschnitte durch die gewichtete Summe nicht erreichbar. Im nebenstehenden Bild rechts ist das der Abschnitt zwischen den Punkten A und B. Dem kann durch die Verwendung der kaskadierten gewichteten Summe in begrenztem Maße abgeholfen werden.[11]

Vergleicht man beide Optimierungsansätze, so ist der Einsatz der Pareto-Optimierung sicher dann von Vorteil, wenn über die möglichen Lösungen einer Aufgabenstellung noch wenig bekannt ist und wenn die Anzahl der Optimierungsziele auf drei, maximal vier eingegrenzt werden kann. Bei wiederholter Optimierung von Variationen ein und derselben Aufgabenstellung sind jedoch die gewünschten Kompromisslinien bekannt und der Aufwand zur Ermittlung der gesamten Pareto-Front ist nicht mehr gerechtfertigt. Dies gilt auch dann, wenn keine menschliche Entscheidung nach der Optimierung erwünscht ist, wie z. B. in automatisierten Entscheidungsprozessen.[11]

Hilfskriterien

Beispiel zweier Schedules eines Auftrags, der eine späteste Fertigstellungszeit einhalten soll.[12]

Neben den sich aus der Aufgabenstellung ergebenden primären Zielen oder Kriterien, kann es erforderlich sein, Hilfskriterien mit in die Bewertung aufzunehmen, um die Erreichung von einem oder mehreren primären Zielen zu unterstützen. Zur Illustration wird das Schedulingbeispiel aus dem Artikel über die Genome von EAs herangezogen. Zu den Optimierungszielen zählt neben einer allgemeinen schnellen Bearbeitung aller Aufträge bei neu eingeführten Option eines Eilauftrags noch zusätzlich die Einhaltung einer spätesten Fertigstellungszeit. Diese wird durch den beispielhaften Ausgangsschedule verletzt, wie in nebenstehendem Bild dargestellt ist. Die nachfolgende Mutation ändert daran zwar nichts, plant aber den Arbeitsschritt d früher ein, was einen notwendigen Zwischenschritt für einen früheren Beginn vom letzten Arbeitsschritt e des Auftrags darstellt. Solange lediglich die späteste Fertigstellungszeit bewertet wird, bleibt die Fitness des mutierten Schedules aber unverändert, obwohl er einen relevanten Schritt zum Ziel einer rechtzeitigen Fertigstellung des Auftrags darstellt. Dem kann z.B. durch eine zusätzliche Bewertung der Verzögerung von Arbeitsschritten von Eilaufträgen abgeholfen werden. Das neue Kriterium ist ein Hilfskriterium, da es zusätzlich zu den eigentlichen Optimierungszielen eingeführt wurde, um deren Erreichung zu unterstützen. Eine ausführlichere Beschreibung und ein weiteres Beispiel können in [12] gefunden werden.

Literatur

Einzelnachweise

  1. ↑ Thomas Jansen: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer, Berlin, Heidelberg 2013, ISBN 978-3-642-17338-7, Seite 7, doi:10.1007/978-3-642-17339-4 (springer.com [abgerufen am 7. März 2022]).
  2. ↑ Thomas Bäck, David B. Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation. Vol. 2, Advanced Algorithms and Operators. CRC Press, Boca Raton 2000, ISBN 0-585-30363-0, Seite 2, doi:10.1201/9781420034349.
  3. ↑ a b c Kaisa Miettinen: Introduction to Multiobjective Optimization: Noninteractive Approaches. In: Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński (Hrsg.): Multiobjective Optimization: Interactive and Evolutionary Approaches. LNCS, Nr. 5252. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-88907-6, S. 1–26, doi:10.1007/978-3-540-88908-3.
  4. ↑ Christian Blume, Wilfried Jakob: GLEAM - General Learning Evolutionary Algorithm and Method : ein Evolutionärer Algorithmus und seine Anwendungen. KIT Scientific Publishing, 2009, doi:10.5445/ksp/1000013553 (uni-karlsruhe.de [abgerufen am 7. März 2022]).
  5. ↑ Carlos M. Fonseca, Peter J. Fleming: An Overview of Evolutionary Algorithms in Multiobjective Optimization. In: Evolutionary Computation. Band 3, Nr. 1, März 1995, ISSN 1063-6560, S. 1–16, doi:10.1162/evco.1995.3.1.1 (mit.edu [abgerufen am 7. März 2022]).
  6. ↑ a b Kalyanmoy Deb: Introduction to Evolutionary Multiobjective Optimization. In: Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, Roman Słowiński (Hrsg.): Multiobjective Optimization: Interactive and Evolutionary Approaches. LNCS, Nr. 5252. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-88907-6, S. 58–96, doi:10.1007/978-3-540-88908-3.
  7. ↑ Eckart Zitzler, Marco Laumanns, Lothar Thiele: SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report, Nr. 103. Computer Engineering and Networks Laboratory (TIK), ETH Zürich 2001, doi:10.3929/ETHZ-A-004284029 (handle.net [abgerufen am 4. März 2022]).
  8. ↑ Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, T. Meyarivan: A fast and elitist multiobjective genetic algorithm: NSGA-II. In: IEEE Transactions on Evolutionary Computation. Band 6, Nr. 2, April 2002, S. 182–197, doi:10.1109/4235.996017 (ieee.org [abgerufen am 4. März 2022]).
  9. ↑ Kalyanmoy Deb, Himanshu Jain: An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. In: IEEE Transactions on Evolutionary Computation. Band 18, Nr. 4, August 2014, ISSN 1089-778X, S. 577–601, doi:10.1109/TEVC.2013.2281535 (ieee.org [abgerufen am 4. März 2022]).
  10. ↑ Himanshu Jain, Kalyanmoy Deb: An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach. In: IEEE Transactions on Evolutionary Computation. Band 18, Nr. 4, August 2014, ISSN 1089-778X, S. 602–622, doi:10.1109/TEVC.2013.2281534 (ieee.org [abgerufen am 4. März 2022]).
  11. ↑ a b c d e Wilfried Jakob, Christian Blume: Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. In: Algorithms. Band 7, Nr. 2, 2. April 2014, ISSN 1999-4893, S. 166–185, doi:10.3390/a7010166.
  12. ↑ a b Wilfried Jakob: Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications. Karlsruher Institut für Technologie (KIT), 2021, doi:10.5445/ir/1000135763, arxiv:2107.11300 (kit.edu [abgerufen am 2. März 2022]).
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Fitnessfunktion&oldid=220877617“