Maximum Dispersion, Maximum Concentration: Enhancing the Quality of MOP Solutions

Technische Samenvatting: Maximale Dispersie, Maximale Concentratie

Probleemdefinitie
Multi-objectieve optimalisatieproblemen (MOP's) vereisen een balans tussen conflicterende doelstellingen, waarbij doorgaans wordt gestreefd naar het benaderen van de Pareto-front (PF) in de objectruimte. Hoewel traditionele Multi-Objective Evolutionary Algorithms (MOEA's) effectief convergeren naar de PF, lijden ze vaak aan een kritieke beperking: oplossingen hebben de neiging om te clusteren in specifieke regio's van de beslissingsruimte. Dit gebrek aan diversiteit in de beslissingsruimte ($\Omega$) creëert implementatiebias, waarbij besluitvormers worden gepresenteerd aan een smalle set opties die onhaalbaar kunnen worden als de initiële condities veranderen. Daarentegen, hoewel er preferentie-gebaseerde methoden bestaan om de zoekinspanningen te richten op een specifieke Region of Interest (ROI) in de objectruimte om convergentie te verbeteren, adresseren deze zelden de gelijktijdige behoefte aan maximale dispersie in de beslissingsruimte. Het artikel identificeert een gat in de literatuur met betrekking tot de gelijktijdige optimalisatie van oplossingconcentratie in de objectruimte en dispersie in de beslissingsruimte.

Methodologie: Het C-DWU Algoritme
De auteurs stellen het C-DWU (Cone-Dominance Weighted Uniformity) algoritme voor, een adaptatie van de bestaande Dominance-Weighted Uniformity (DWU) benadering. De methodologie integreert de voorkeuren van een besluitvormer, gedefinieerd door een voorkeurskegel $C$ (gekarakteriseerd door een asvector $v$ en een openingshoek $\theta$), in het evolutionaire proces via twee specifieke modificaties:

1. Gepenaliseerde Niet-Gedomineerde Sorting: Tijdens de sorteerfase worden oplossingen die buiten de voorkeurskegel $C$ liggen, gepenaliseerd. De straf is evenredig aan de hoekafstand ($\phi$) tussen de objectvector van de oplossing en de kegelas $v$. Dit wordt berekend met een straffunctie $P_{\alpha,\theta}(\phi) = \lfloor e^{\alpha(\phi-\theta)} \rfloor$, die het niet-gedomineerde frontniveau van uitliggende oplossingen verhoogt, wat de zoektocht effectief richting de ROI duwt.
2. Gemodificeerde Selectie Heuristiek (C-wd): De standaard DWU-selectieheuristiek, die de uniformiteit in de beslissingsruimte maximaliseert, is gewijzigd om de voorkeurskegel te incorporeren. Een nieuwe functie, C-wd, past een strafterm $P_{\beta,\theta}(\phi)$ toe op de dominantie-gewogen uniformiteitsberekening voor oplossingen buiten de kegel. Dit zorgt ervoor dat terwijl het algoritme streeft naar het maximaliseren van de afstand tussen oplossingen in de beslissingsruimte (dispersie), het prioriteit geeft aan oplossingen die ook voldoen aan de concentratiebeperkingen binnen de ROI in de objectruimte.

Het algoritme beoogt een subset van oplossingen te vinden die Pareto-optimaal zijn, geconcentreerd binnen de gedefinieerde ROI in de objectruimte, en maximaal gedispergeerd binnen de beslissingsruimte.

Experimentele Opzet en Resultaten
De auteurs evalueerden C-DWU tegenover een gemodificeerde versie van NSGA-II (aangeduid als C-NSGAII), die dezelfde kegel-gebaseerde penalizatie toepast op de standaard NSGA-II maar de mechanismen voor diversiteit in de beslissingsruimte mist. Experimenten werden uitgevoerd op bi-objectieve geconstraineerde optimalisatieproblemen met behulp van de WFG4, WFG9 (multimodaal) en DTLZ2 (unimodaal) testsuites met beslissingsruimte dimensies van 5, 7 en 9.

• Convergentie (Objectruimte): Gemeten door de Inverted Generational Distance (IGD) relatief ten opzichte van de ROI. Resultaten geven aan dat C-NSGAII in de meeste instanties een iets betere convergentie bereikte (lagere IGD-waarden).
• Dispersie (Beslissingsruimte): Gemeten door een uniformiteitsmetriek gebaseerd op de minimale afstand tussen oplossingen. C-DWU presteerde significant beter dan C-NSGAII, waarbij het veel hogere uniformiteitswaarden behaalde.
• Visualisatie: High-dimensional visualisatie (gebruikmakend van CAP-VIZ) van het WFG4-probleem toonde aan dat de oplossingen van C-NSGAII zwaar clusterden in een enkele sector van de beslissingsruimte (nabij as $e_9$), terwijl de oplossingen van C-DWU verdeeld waren over meerdere sectoren (7, 8 en 9) met grotere variabiliteit in zowel de hoekafstand als de Euclidische norm.

Belangrijkste Bijdragen

• Dual-Objective Optimalisatie: Het artikel introduceert een raamwerk dat gelijktijdig de concentratie van oplossingen in een specifieke ROI van de objectruimte maximaliseert en de dispersie van oplossingen in de beslissingsruimte maximaliseert.
• Algoritmische Adaptatie: De ontwikkeling van C-DWU, die de DWU-algoritme modificeert om voorkeurskegel-beperkingen te accepteren zonder de diversiteit in de beslissingsruimte op te offeren.
• Mitigatie van Bias: De aanpak adresseert het probleem van "gepolariseerde" oplossingen in de beslissingsruimte, waardoor besluitvormers een divers pakket aan implementatieopties krijgen die allemaal optimaal zijn binnen een geprefereerde regio van de objectruimte.

Betekenis en Claims
De auteurs beweren dat de voorgestelde methode de kwaliteit van MOP-oplossingen verbetert door een balans te vinden tussen diversiteit en nauwkeurigheid. Zij argumenteren dat hoewel het C-DWU algoritme een marginale reductie in convergentiesnelheden kan vertonen vergeleken met C-NSGAII, deze trade-off gerechtvaardigd is door de substantiële winst in oplossing-diversiteit. De primaire betekenis ligt in het bieden van een robuuste set opties aan besluitvormers; diverse oplossingen in de beslissingsruimte maken flexibiliteit mogelijk indien onvoorziene veranderingen optreden in de real-world scenario, wat de noodzaak voor kostbare her-optimalisatie voorkomt. Het artikel concludeert dat het definiëren van een ROI via een voorkeurskegel een effectieve en gemakkelijk aanpasbare methode is om de voorkeuren van besluitvormers te integreren in evolutionaire algoritmen, terwijl de representativiteit van de oplossingenset behouden blijft.