Fitnessfunktion

Eine Fitnessfunktion ist die Zielfunktion eines evolutionären (Optimierungs-)Algorithmus (EA). Gelegentlich wird eine Fitnessfunktion auch als Teil einer Zielfunktion beschrieben 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, 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. 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 (siehe auch Abschnitt Hilfskriterien), sofern und insoweit dies nicht bereits von der Fitnessfunktion alleine geleistet wird.

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 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.

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. Die Fitness-Approximation in der evolutionären Optimierung kann als Teilbereich der datengesteuerten evolutionären Optimierung angesehen werden.

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.

Mehrzieloptimierung

→ Hauptartikel: 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 (a-priori) gewichteten Summe.

A-Priori Mehrzieloptimierung: Gewichtete Summe und Straffunktionen

Siehe auch: Mehrzieloptimierung

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

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

$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. Nachteilig ist unter anderem, dass sich unterschiedliche Kriterien wechselseitig ausgleichen können und dass man die Gewichtungen vor der Optimierung festlegen muss.

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

Siehe auch: Mehrzieloptimierung und Pareto-Menge

Pareto-Front zweier zu maximierender Kriterien.

EA können zum Auffinden vieler Lösungen der Pareto-Menge genutzt werden - sie sind a-Posteriori-Methoden zur Mehrzieloptimierung.

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.

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. Neben dem SPEA2 haben sich der NSGA-II und NSGA-III als Standardverfahren etabliert.

Beschränkungen werden bei der a-posteriori 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.

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. Bei mehr als drei oder vier Kriterien müssen einige mit der gewichteten Summe oder anderen Aggregationsmethoden zusammengefasst werden.

Beim obigen Beispiel des Designs eines Passagiersitzes steht man angesichts der fünf Kriterien bei der a-posteriori 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.

Beispiel einer nicht-konvexen Pareto-Front.

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 links illustriert. Der Punkt P auf der grünen Pareto-Front wird durch die Gewichte $w_{1}$ und $w_{2}$ erreicht, sofern der EA zum Optimum konvergiert. Die Richtung mit dem größten Fitnessgewinn in der Lösungsmenge $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.

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.

Hilfskriterien

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

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 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.