Fitnessfunktion

Eine Fitnessfunktion ist die Zielfunktion eines evolutionären (Optimierungs-)Algorithmus (EA).[1][2] Gelegentlich wird eine Fitnessfunktion auch als Teil einer Zielfunktion beschrieben[3] 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[4], wie z. B. bei der Turnierselektion oder der Pareto-Optimierung.

Anforderungen an Bewertung und Fitnessfunktion

Die Qualität 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 und sollen die EA-Suche zum globalen Optimums leiten. 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 (siehe auch Abschnitt Hilfskriterien), sofern und insoweit dies nicht bereits von der Fitnessfunktion alleine geleistet wird. Die auf der Fitness basierenden Selektionsmechanismen für die Partnerwahl und für die Akzeptanz der Nachkommen stellen ein wichtiges Unterscheidungsmerkmal der EA zur Abgrenzung von den Monte-Carlo-Verfahren dar.

Die Definition einer im obigen Sinn geeigneten Fitnessfunktion ist in vielen Fällen nicht einfach und wird oft iterativ durchgeführt, wenn die von einem EA erzeugten besten Lösungen nicht den Vorstellungen entsprechen.

Eine weitere wichtige Anforderung an die Fitnessfunktion eines Individuums ist die effiziente und schnelle Berechenbarkeit, da ein EA-Lauf in der Regel auf einer Vielzahl von Bewertungen beruht. Je nach Aufgabenstellung muss mit einigen Tausend bis Zehntausend oder mehr Evaluationen gerechnet werden. Eine Approximation der Fitnessfunktion[5] kann insbesondere in den folgenden Fällen sinnvoll sein:

• Die Fitnessberechnungszeit einer einzelnen Lösung ist extrem hoch.
• Es fehlt ein genaues Modell für die Fitnessberechnung.
• Die Fitnessfunktion ist unsicher oder verrauscht.[6]

Die Fitness-Approximation basiert auf maschinellen Lernmodellen, die auf der Grundlage von Daten aus numerischen Simulationen oder physikalischen Experimenten erstellt werden. Diese Lernmodelle sind auch als Metamodelle oder Surrogate bekannt, und die evolutionäre Optimierung auf der Grundlage approximierter Fitness-Bewertungen wird auch als Surrogat-gestützte evolutionäre Approximation bezeichnet.[7] Die Fitness-Approximation in der evolutionären Optimierung kann als Teilbereich der datengesteuerten evolutionären Optimierung angesehen werden.[8]

Alternativ oder auch ergänzend zur Fitnessapproximation können die Fitnessberechnungen auch auf einem Parallelrechner verteilt werden, um die Ausführungszeiten zu reduzieren. Je nach verwendetem Populationsmodell des EAs können sowohl der EA selbst als auch die Fitnessberechnungen aller Nachkommen einer Generation parallel ausgeführt werden.[9][10][11]

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 an den zugänglichen Stellen 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 Kriteriums 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 a-posteriori Pareto-Optimierung und die Optimierung mit der gewichteten Summe, einer a-priori Methode.[12]

A-priori Mehrzieloptimierung: 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 der ${\displaystyle K}$ normierten Kriterien ${\displaystyle k_{i}}$ wird ein Gewicht ${\displaystyle w_{i}}$ zugeordnet, sodass die Gesamtrohfitness ${\displaystyle f_{roh}}$ als gewichtete Summe berechnet werden kann:

${\displaystyle f_{roh}=\sum _{i=1}^{K}{k_{i}\cdot w_{i}}\quad {\mathsf {mit}}\quad \sum _{i=1}^{K}{w_{i}}=1\quad {\mathsf {und}}\quad w_{i}>0}$

Eine Verletzung von ${\displaystyle R}$ Restriktionen kann in Form von Straffunktionen in die so ermittelte Fitness einfließen. Dazu kann beispielsweise pro Restriktion ${\displaystyle r_{j}}$ eine Funktion ${\displaystyle sf_{j}(r_{j})}$ 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 ${\displaystyle sf_{j}(r_{j})}$ werden mit der zuvor ermittelten Rohfitness ${\displaystyle f_{roh}}$ multipliziert und das Resultat ist dann die Endfitness ${\displaystyle f_{end}}$:

${\displaystyle f_{end}=f_{roh}\cdot \prod _{j=1}^{R}{sf_{j}(r_{j})}=\sum _{i=1}^{K}{(k_{i}\cdot w_{i})}\cdot \prod _{j=1}^{R}{sf_{j}(r_{j})}}$

Diese Vorgehensweise ist einfach und hat den Vorteil, beliebig viele Kriterien und Straffunktionen zusammenfassen zu können.[13] Nachteilig ist unter anderem, dass sich unterschiedliche Kriterien wechselseitig ausgleichen können und dass man die Gewichtungen vor der Optimierung festlegen muss,[12] daher auch die Zuordnung zu den a-priori-Methoden der Mehrzieloptimierung.

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.

A-posteriori Mehrzieloptimierung: Finden der Pareto-Menge

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.[12]

Schon früh wurde erkannt, dass EAs mit ihrer gleichzeitig betrachteten Lösungsmenge gut dazu geeignet sind, in einem Lauf viele Lösungen zu finden, die die Pareto-Front hinreichend gut abdecken.[14][15] Daher eignen sie sich gut als a-posteriori Methoden zur Mehrzieloptimierung, bei der die finale Entscheidung nach der Optimierung und der Ermittlung der Paretofront erfolgt.[12] Neben dem SPEA2[16] haben sich der NSGA-II[17] und NSGA-III[18][19] 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 jeweils Beschränkungsverletzungen, so entscheidet das jeweilige Ausmaß der Verletzungen.[15]

Der Vorteil der a-posteriori 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 a-posteriori Visualisierung der Alternativen ab vier Kriterien problematisch bis unmöglich wird. Außerdem steigt der Aufwand mit der Anzahl der Kriterien exponentiell.[13] Bei mehr als drei oder vier Kriterien müssen einige mit der gewichteten Summe oder anderen Aggregationsmethoden[12] 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 a-posteriori 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 auch einzeln als Restriktionen behandeln.

Vergleich beider Optimierungsarten

Zusammenhang zwischen der Pareto-Front und der gewichteten Summe.[13]

Beispiel einer nicht-konvexen Pareto-Front.[13]

Mit Hilfe der gewichteten Summe kann durch eine geeignete Wahl der Gewichte die gesamte Pareto-Front erreicht werden, sofern diese konvex ist.[20] Dies wird durch das nebenstehende Bild links illustriert. Der Punkt P auf der grünen Pareto-Front wird durch die Gewichte ${\displaystyle w_{1}}$ und ${\displaystyle w_{2}}$ erreicht, sofern der EA zum Optimum konvergiert. Die Richtung mit dem größten Fitnessgewinn in der Lösungsmenge ${\displaystyle Z}$ 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.[13]

Vergleicht man beide Optimierungsansätze, so ist der Einsatz der a-posteriori Pareto-Optimierung 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.[13]

Hilfskriterien

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

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 der 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 dieser Herangehensweise und ein weiteres Beispiel können in [21] gefunden werden.

Siehe auch

• Verlustfunktion (Statistik)
• Empirische Risikominimierung
• Akquisitionsfunktion

Literatur

• 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, doi:10.1007/978-3-540-88908-3. 
• Thomas Baeck, David B. Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 1: Basic Algorithms and Operators. CRC Press, Boca Raton, USA 1999, ISBN 0-7503-0664-5. 
• Thomas Baeck, David B. Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 2: Advanced Algorithms and Operators. CRC Press, Boca Raton, USA 2000, ISBN 0-367-80637-1, doi:10.1201/9781420034349. 
• Hartmut Pohlheim: Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis. Springer, Berlin, Heidelberg 1999, ISBN 3-540-66413-0. 
• Volker Nissen: Einführung in evolutionäre Algorithmen: Optimierung nach dem Vorbild der Evolution. Vieweg, Braunschweig 1997, ISBN 3-528-05499-9, doi:10.1007/978-3-322-93861-9. 
• Karsten Weicker: Evolutionäre Algorithmen. 3. Auflage. Springer Vieweg, Wiesbaden 2015, ISBN 978-3-658-09957-2, doi:10.1007/978-3-658-09958-9. 

Einzelnachweise

1. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Evaluation Function (Fitness Function), S. 30, doi:10.1007/978-3-662-44874-8 (englisch). 
2. Hartmut Pohlheim: Evolutionäre Algorithmen. Springer, Berlin, Heidelberg 2000, ISBN 3-642-63052-9, Fitneßzuweisung, S. 16–23, doi:10.1007/978-3-642-57137-4. 
3. Thomas Jansen: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer, Berlin, Heidelberg 2013, ISBN 978-3-642-17338-7, S. 7, doi:10.1007/978-3-642-17339-4. 
4. 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, S. 2, doi:10.1201/9781420034349. 
5. Y. Jin: A comprehensive survey of fitness approximation in evolutionary computation. In: Soft Computing. Band 9, Nr. 1, 1. Januar 2005, ISSN 1433-7479, S. 3–12, doi:10.1007/s00500-003-0328-5. 
6. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Nonstationary and Noisy Function Optimisation, S. 185–194, doi:10.1007/978-3-662-44874-8. 
7. Yaochu Jin: Surrogate-assisted evolutionary computation: Recent advances and future challenges. In: Swarm and Evolutionary Computation. Band 1, Nr. 2, Juni 2011, S. 61–70, doi:10.1016/j.swevo.2011.05.001 (elsevier.com [abgerufen am 27. Februar 2023]). 
8. Yaochu Jin, Handing Wang, Tinkle Chugh, Dan Guo, Kaisa Miettinen: Data-Driven Evolutionary Optimization: An Overview and Case Studies. In: IEEE Transactions on Evolutionary Computation. Band 23, Nr. 3, Juni 2019, ISSN 1089-778X, S. 442–458, doi:10.1109/TEVC.2018.2869001 (ieee.org [abgerufen am 27. Februar 2023]). 
9. Dirk Sudholt: Parallel Evolutionary Algorithms. In: Springer Handbook of Computational Intelligence. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-43504-5, S. 929–959, doi:10.1007/978-3-662-43505-2_46. 
10. Hatem Khalloof, Mohammad Mohammad, Shadi Shahoud, Clemens Duepmeier, Veit Hagenmeyer: A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics. In: Proceedings of the 12th International Conference on Management of Digital EcoSystems. ACM, Virtual Event United Arab Emirates 2020, ISBN 978-1-4503-8115-4, S. 124–131, doi:10.1145/3415958.3433041. 
11. Paul Jähne: Overview of the current state of research on parallelisation of evolutionary algorithms on graphic cards. In: H.C. Mayr, M. Pinzger (Hrsg.): Informatik 2016 Tagung vom 26. - 30. September 2016. Gesellschaft für Informatik, Bonn 2016, ISBN 978-3-88579-653-4 (emis.de [PDF; abgerufen am 17. Februar 2023]). 
12. 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 (researchgate.net). 
13. 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, arxiv:2203.02697. 
14. 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]). 
15. 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 (researchgate.net). 
16. 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 (ethz.ch [abgerufen am 4. März 2022]). 
17. 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. 
18. 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]). 
19. 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]). 
20. Kaisa Miettinen: Nonlinear Multiobjective Optimization (= International Series in Operations Research & Management Science. Band 12). Springer US, Boston, MA 1998, ISBN 1-4613-7544-4, doi:10.1007/978-1-4615-5563-6. 
21. 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.