Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels

Titel: Snelle schattingen van ondergrenzen voor de 'hitting time' van elitistische evolutionaire algoritmen

Auteurs: Jun He, Siang Yew Chong, Xin Yao
Publicatie: arXiv:2311.10502v4 [cs.NE]

1. Probleemstelling

Het bepalen van de hitting time (de verwachte tijd tot een evolutionair algoritme een optimale oplossing vindt) is cruciaal voor het analyseren van de prestaties van Evolutionaire Algoritmen (EA's). Een veelgebruikte methode hiervoor is de fitness level methode. Deze methode verdeelt de zoekruimte in niveaus op basis van fitnesswaarden en schat de tijd op basis van overgangskansen tussen deze niveaus.

Het artikel identificeert een fundamentele beperking van de bestaande fitness level methode:

• Ongelijke overgangskansen: Voor veel realistische fitnessfuncties (zogenoemde non-level-based functions) zijn de minimale en maximale overgangskansen tussen twee niveaus niet gelijk.
• Losse ondergrenzen: Wanneer de hele zoekruimte wordt gepartitioneerd, levert de bestaande theorie voor het berekenen van ondergrenzen vaak zeer losse (triviale) resultaten op, zoals $O(n \log n)$. Dit is onvoldoende voor complexe problemen waar de werkelijke tijd veel hoger ligt (bijvoorbeeld exponentieel of factorial).
• Het doel: Er is behoefte aan een methode die snelle, maar strakke (tight) ondergrenzen kan berekenen voor fitnessfuncties die geen duidelijke niveau-structuur hebben.

2. Methodologie: De Subset Fitness Level Methode

De auteurs introduceren een nieuwe aanpak, de Subset Fitness Level Methode, om de beperkingen van de traditionele methode te overwinnen.

Kernconcepten:

1. Selectie van een Subset ($S'$): In plaats van de hele zoekruimte te partitioneren, selecteert de methode een subset van niet-optimale oplossingen ($S'$). Deze subset wordt vaak gekozen rondom lokale optima of specifieke paden waar het algoritme vastloopt.
2. Gefocuste Partitionering: Alleen deze subset $S'$ wordt verdeeld in fitnessniveaus ($S_1, \dots, S_K$). De rest van de ruimte wordt behandeld als een absorberende toestand ($S_0$).
3. Drift Analyse van Hitting Probability: De methode transformeert het probleem van het schatten van de hitting time naar het schatten van de hitting probability (de kans om van niveau $k$ naar niveau $\ell$ te komen).
4. Expliciete Formules via Paden en Segmenten:
   • De auteurs ontwikkelen nieuwe, niet-recursieve formules gebaseerd op het concept van paden (sequences van niveaus) en segmenten.
   • Ze gebruiken een drift-functie om een ondergrenscoëfficiënt ($c_{k,\ell}$) te berekenen die de minimale hitting probability benadert.
   • Door paden op te splitsen in segmenten (bijvoorbeeld bij meerdere paden naar een lokaal optimum), kunnen ze de cumulatieve kans berekenen zonder de factoriële complexiteit van het tellen van alle mogelijke subsequenties.

Wiskundige Basis:

De ondergrens voor de gemiddelde hitting time wordt afgeleid uit:
$$m_{min} \geq \frac{1}{p_{max}} + \sum \frac{h_{min}}{p_{max}}$$
Waarbij $h_{min}$ (de hitting probability) wordt geschat via de nieuwe coëfficiënten die zijn afgeleid uit de product van conditionele overgangskansen langs geselecteerde paden.

3. Belangrijkste Bijdragen

• Nieuwe Theorie: De introductie van de subset fitness level method, die toont dat het partitioneren van een subset van de zoekruimte leidt tot strakke ondergrenzen, zelfs voor niet-level-based functies.
• Snelle Berekening: Ontwikkeling van expliciete formules (Theorema 3, 4 en 5) die het berekenen van ondergrenscoëfficiënten mogelijk maken zonder complexe recursie, door gebruik te maken van paden en segmenten.
• Overbrugging van de Kloof: Het bewijzen dat de traditionele methode faalt bij functies met "shortcuts" of grote Hamming-afstanden tussen lokale en globale optima, terwijl de nieuwe methode dit succesvol adresseert.

4. Resultaten en Experimenten

De methode werd getest op zes knapsack-probleem实例 (P1 t/m P6) en het lineaire OneMax-probleem. De resultaten tonen een drastisch verschil tussen de traditionele methode (hele zoekruimte) en de nieuwe subset-methode:

• Observatie: Voor de complexe knapsack-varianten (P1-P5), waar lokale optima gescheiden zijn van het globale optimum door een grote "gap" (grote Hamming-afstand), gaf de traditionele methode een triviale ondergrens van $O(n \log n)$. De subset-methode leverde echter ondergrenzen op die overeenkomen met de verwachte moeilijke aard van deze problemen (factorieel of exponentieel).
• Validatie: Voor het lineaire OneMax-probleem (P6), dat wel een level-based structuur heeft, leverde de methode de bekende strakke ondergrens van $\Omega(n \log n)$ op, wat de geldigheid van de methode bevestigt.

5. Betekenis en Conclusie

Dit artikel is significant voor de theoretische analyse van evolutionaire algoritmen omdat het een oplossing biedt voor een langdurig probleem: het gebrek aan strakke ondergrenzen voor niet-ideale fitnesslandschappen.

• Praktische Toepassing: De methode maakt het mogelijk om te voorspellen dat bepaalde EA's op specifieke problemen (zoals de knapsack-problemen met lokale optima) extreem langzaam zullen presteren, iets wat met de oude methode niet zichtbaar was.
• Efficiëntie: Door het gebruik van paden en segmenten kunnen deze complexe ondergrenzen sneller worden berekend dan met eerdere recursieve benaderingen.
• Toekomst: De auteurs suggereren dat deze techniek kan worden uitgebreid naar andere combinatorische optimalisatieproblemen (zoals arc routing) en continue optimalisatie.

Kortom, de paper biedt een krachtig nieuw instrument voor theoretici om de ondergrenzen van de looptijd van elitistische EA's nauwkeuriger en realistischer te bepalen voor complexe, realistische probleemstructuren.