Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

Technische Samenvatting: Landschapsbewuste Bandit Hyper-Heuristieken voor Online Operatorselectie bij UAV-Inspectieroutes

1. Probleemdefinitie

Het artikel behandelt het UAV-meerdere-locaties inspectierouteprobleem, geabstraheerd als een Euclidisch Reizende Verkoper Probleem (TSP). In deze context moet een UAV een reeks toegewezen locaties bezoeken en binnen een beperkt vliegfenster terugkeren naar een depot. De centrale beslissingsvariabele is de bezoekvolgorde van deze locaties, ervan uitgaande dat lagere niveaus van zorg (zoals hoogtecontrole, botsingsvermijding en servicetijden) afzonderlijk door andere planners worden afgehandeld.

De uitdaging ligt in het feit dat verschillende routelandschappen (bijvoorbeeld uniform, geclusterd, corridor-achtig, rooster-achtig, gemengde dichtheid) en verschillende stadia van het zoekproces verschillende optimalisatiestrategieën vereisen. Klassieke heuristieken vertrouwen vaak op vaste schema's of willekeurige operatorselectie, wat kan leiden tot inefficiënties zoals het overmatig gebruiken van een operator die niet langer verbeteringen oplevert, of het verspillen van evaluaties aan moves die niet geschikt zijn voor de huidige zoektoestand.

2. Methodologie: LA-BHH

De auteurs stellen LA-BHH (Landschapsbewuste Bandit Hyper-Heuristiek) voor, een compacte online controller die is ontworpen om een operatorselectiebeleid te leren tijdens één optimalisatie-loop zonder offline training.

• Hyper-Heuristisch Kader: LA-BHH opereert op een hoog niveau en selecteert uit een portfolio van vier lage-niveau operators (armen):
  1. 2-opt: Keert een toursegment om om randkruisingen te verwijderen.
  2. Swap: Wisselt twee inspectielocaties uit.
  3. Relocate: Verplaatst één locatie naar een andere positie.
  4. Or-opt-2: Verplaatst een blok van twee locaties.
• Contextuele Bandit Controller: Het selectiemechanisme maakt gebruik van een LinUCB (Linear Upper Confidence Bound) algoritme.
  • Contextvector ($z_t$): De controller baseert zijn beslissingen op een kenmerkvector bestaande uit:
    • Statische Landschapsbeschrijvers: Genormaliseerde probleemgrootte, gemiddelde afstand tot de dichtstbijzijnde buur, dispersie, coördinaatanisotropie, radiale dispersie en MST-gewicht per knooppunt.
    • Dynamische Zoektoestand-kenmerken: Vooruitgang in het budget, huidige/beste tourlengte ten opzichte van de start, recente verbetering, acceptatiepercentage en stagnatie-indicatoren.
  • Leersignaal: De beloning ($r_t$) is de afgeknipte relatieve verbetering in tourlengte die wordt geproduceerd door de geselecteerde operator. Deze beloning update de ridge-regressiestatistieken ($A_a, b_a$) voor de gekozen arm, waardoor de controller zijn credittoewijzing in real-time kan aanpassen.
• Stagnatiebewuste Reparatie: Een specifiek ontwerpelement bevoordeelt de selectie van 2-opt-moves wanneer de zoektocht stagnatie detecteert (een gebrek aan verbetering over een kort venster). Dit maakt gebruik van de bekende effectiviteit van 2-opt voor Euclidische reparatie zonder nieuwe move-types in te voeren.
• Acceptatiestrategie: De methode hanteert een gierige beste-improvement-regel. Hoewel acceptatie in de stijl van temperen (annealing) is getest als een ablatie, bleek dit de prestaties op deze specifieke Euclidische instanties te verslechteren door sterke dichtstbijzijnde-buurstructuren te verstoren.

3. Belangrijkste Bijdragen

• Online Leren voor Routing: Het artikel toont aan dat een compacte online controller effectief kan leren operators te selecteren op basis van zowel statische instantiekenmerken als dynamische zoekvoortgang, waardoor de behoefte aan grote offline datasets of complexe neurale architecturen wordt geëlimineerd.
• Contextuele Credittoewijzing: Het combineert expliciet statische landschapsbeschrijvers met online zoektoestand-kenmerken om operatorselectie te sturen, en toont aan dat deze context superieur is aan niet-contextuele banditselectie (UCB-HH) of willekeurige selectie.
• Stagnatiebeheer: De integratie van een stagnatiebewuste poort die de controller dynamisch bevoordeelt naar 2-opt-reparatiemoves, wordt geïdentificeerd als een kritiek onderdeel voor het handhaven van zoekvoortgang.
• Ablatie-analyse: De studie isoleert systematisch de bijdragen van specifieke componenten (context, statische kenmerken, dynamische kenmerken, specifieke operators), en verduidelijkt dat de prestatiewinsten voortkomen uit de interactie tussen 2-opt-reparatie, contextuele credittoewijzing en het gebruik van stagnatiebewuste toestanden.

4. Experimentele Resultaten

De methode werd geëvalueerd op 45 gegenereerde Euclidische TSP-instanties verspreid over vijf landschapsfamilies (uniform, geclusterd, corridor, rooster-jitter, gemengde dichtheid) en drie instantiegroottes (50, 100, 200 locaties).

• Prestatiemetingen: LA-BHH behaalde de beste gemiddelde finale gap (0,0223) en convergentie AUC (0,0389) onder alle vergeleken methoden.
• Vergelijkende Winsten:
  • De finale gap werd met 17,6% verlaagd in vergelijking met niet-contextuele UCB-HH.
  • De finale gap werd met 22,6% verlaagd in vergelijking met Random-HH.
  • De finale gap werd met 68,2% verlaagd in vergelijking met Nearest-Neighbor (NN) constructie.
• Robuustheid: LA-BHH presteerde consequent beter dan klassieke baselines (waaronder Gesimuleerde Temperen, Genetische Algoritmen en Iterated Local Search) over alle landschapsfamilies heen, en toonde stabiliteit in diverse inzetscenario's.
• Operatorgebruik: Analyse toonde aan dat hoewel 2-opt de dominante operator was (vooral tijdens stagnatie), de geleerde controller effectief gebruikmaakte van swap, relocate en Or-opt-2 om lokale volgordefouten te corrigeren die door 2-opt alleen niet konden worden aangepakt.

5. Betekenis en Claims

Het artikel positioneert LA-BHH als een praktische casestudie voor Leerondersteund Algoritmeontwerp (LEAD) op het gebied van routing. De betekenis wordt omlijst rond enkele bescheiden maar praktische claims:

• Interpreteerbaarheid en Efficiëntie: In tegenstelling tot grote offline modellen, is LA-BHH een lichtgewicht, inspecteerbare controller die leert tijdens één enkele loop, waardoor het geschikt is voor scenario's waarin slechts een klein aantal gerelateerde instanties beschikbaar is.
• Complementaire Rol: De auteurs stellen expliciet dat LA-BHH niet bedoeld is om state-of-the-art TSP-oplossers (zoals LKH) te vervangen. In plaats daarvan dient het als een laag voor routeordening die beslist welke herbruikbare zoekoperator onder een vast budget moet worden toegepast.
• Schaalbaarheid: De methode is computerefficiënt (alleen CPU, $O(Tn)$ complexiteit) en schaalt goed van 50 tot 200 locaties, waarbij het concurrerend blijft waar klassieke local-search baselines minder betrouwbaar worden.
• Toekomstige Toepasbaarheid: De auteurs suggereren dat het kader kan worden uitgebreid naar real-world UAV-inspectie door Euclidische afstanden te vervangen door kortste-pad-afstanden op traverseerbaarheidsgrafieken en obstakels af te handelen via lagere-niveau planners, hoewel zij opmerken dat de huidige experimenten vertrouwen op gecontroleerde gegenereerde instanties in plaats van veldverzamelde data.