MO Indicators
BlueM.Opt | Download | Usage | Development
BlueM.Opt.MO_Indicators ist eine Assembly zur Berechnung von Multi-Objective Indikatoren wie Hypervolumen und Solutionvolume.
Hypervolumen
The size of the objective value space covered by a set of nondominated solutions.
- — Zitzler & Thiele (1998)[1]
Implementierung in BlueM.Opt basiert auf dem PISA Performance Assessment Package.
Der Nadir-Punkt, der als Ausgangspunkt für die Hypervolumenberechnung dient, wird vor jeder Berechnung (i.d.R. bei jeder neuen Generation) automatisch so verschoben, dass keine negativen Abstände zwischen dem Nadir-Punkt und den nicht-dominierten Lösungen auftreten - dies kann zu Sprüngen im Hypervolumen führen.
Weitere Literatur:
- more detailed discussion: Zitzler et al. (2003)[2]
- generalization to arbitrary weight distribution functions: Zitzler et al. (2007)[3]
Solutionvolume
Solutionvolume ist ein Indikatorwert für eine Individuenmenge im Werteraum einer (multikriteriellen) Problemstellung[4].
Bestimmung
Für ein Individuen wird die quadrierte Summe eines jeden Zielwertfunktionswertes (in Differenz zu einem Offsetpunkt) bestimmt. Anschliessend wird dieser Vorgang für alle Individuen wiederholt, alle Werte der einzelnen Individuen ebenfalls summiert und durch die Anzahl der Individuen geteilt. Das Resultat ist also ein Indikatorwert einer Menge von Individuen, unabhängig von deren Anzahl.
Aussage
Das Solutionvolume bietet beim Vergleich einer Individuenmenge über mehrere Generationen die Möglichkeit festzustellen, in wie weit eine Entwicklung stattfindet. Bei der Anwendung auf den Genpool jeder neuen Generation sind folgende Schlüsse zu ziehen:
- Ist der neue Wert des Solutionvolumes niedriger als der vorherige, entwickelt sich die Paretofront in Richtung des Offsetpunktes.
- Ist der neue Wert höher als der vorherige, besitzt die neue Generation wahrscheinlich eine höhere Diversität. Dies gilt nur, wenn die Selektion zuverlässig keine schlechteren Individuen als die bestehenden in den Genpool übernimmt.
- Bleibt der Wert in etwa konstant, können die genutzten Algorithmen keine effiziente Verbesserung im Sinne des Dominanzkriteriums bewirken.
Solutionvolume2
Solutionvolume2 ist eine Weiterentwicklung von Solutionvolume. Das manuelle Setzen eines Basispunktes entfällt. Die Berechnung basiert auf dem Vergleich zweier Indikatorwerte über 'historylength' Generationen.
Der erste Wert stellt den Abstand zwischen zwei Durchschnittsindividuen zweier aufeinanderfolgender Generationen dar. Der zweite Wert stellt die Distanzsumme der Individuen einer Generation zum jeweiligen Durchschnittsindividuum dar.
Basierend auf diesen Werten über mehrere Generationen summiert kann eine gravierende und dauerhafte Änderung der Indikatorwerte leicht festgestellt werden. Der Wert faktor2switch definiert für jeden der beiden Indikatoren den Schwellenwert ab wann eine Umschaltung vom System vorgeschlagen wird. Dabei gilt
Umschaltung = (MaximalIndikator / faktor2switch > IndikatorAktuell)
Literaturangaben
- ↑ Zitzler, E., and Thiele, L. (1998): Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. In: Parallel Problem Solving from Nature (PPSN-V), 292-301, DOI:10.1007/BFb0056872
- ↑ Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C., and Grunert da Fonseca, V. (2003): Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, 7(2), 117-132, DOI:10.1109/TEVC.2003.810758
- ↑ Zitzler, E., Brockhoff, D., and Thiele, L. (2007): The Hypervolume Indicator Revisited: On the Design of Pareto-compliant Indicators Via Weighted Integration. Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), volume 4403 of LNCS, pages 862-876, Springer, DOI:10.1007/978-3-540-70928-2
- ↑ Kerber, D. (2009): Entwicklung eines multi-kriteriellen, hybriden Optimierungsalgorithmus für den Einsatz in der Kanalnetzsteuerung
, Diplomarbeit, TU Darmstadt