Ekstrem optimering - Extremal optimization

Extremal optimering (EO) er en optimering heuristisk inspireret af Bak-Sneppen model af selv-organiserede kritikalitet fra området for statistisk fysik. Denne heuristik blev oprindeligt designet til at tackle kombinatoriske optimeringsproblemer såsom det rejsende sælgerproblem og spinbriller , selvom teknikken er blevet demonstreret til at fungere i optimeringsdomæner.

Forhold til selvorganiseret kritik

Selvorganiseret kritik (SOC) er et statistisk fysikbegreb, der beskriver en klasse af dynamiske systemer, der har et kritisk punkt som tiltrækningskraft. Specifikt er disse ikke-ligevægtssystemer, der udvikler sig gennem laviner af ændringer og spredninger, der når op til systemets højeste skalaer. SOC siges at styre dynamikken bag nogle naturlige systemer, der har disse burst-lignende fænomener, herunder landskabsdannelse, jordskælv, evolution og den granulære dynamik af ris og sandbunker. Af særlig interesse her er Bak-Sneppen-modellen af SOC, som er i stand til at beskrive evolution via punktueret ligevægt (udryddelsesbegivenheder) - og dermed modellere evolution som en selvorganiseret kritisk proces.

Forhold til beregningskompleksitet

Et andet stykke i puslespillet er arbejde med beregningskompleksitet, specifikt at der er vist, at der er kritiske punkter i NP-komplette problemer, hvor næsten optimale løsninger er spredt vidt og adskilt af barrierer i søgerummet, der får lokale søgealgoritmer til at sidde fast eller alvorligt hæmmet. Det var den evolutionære selvorganiserede kriticitetsmodel af Bak og Sneppen og observationen af ​​kritiske punkter i kombinatoriske optimeringsproblemer, der førte til udviklingen af ​​ekstrem optimering af Stefan Boettcher og Allon Percus.

Teknikken

EO blev designet som en lokal søgealgoritme til kombinatoriske optimeringsproblemer . I modsætning til genetiske algoritmer , der arbejder med en population af kandidatløsninger, udvikler EO en enkelt løsning og foretager lokale ændringer til de værste komponenter. Dette kræver, at der vælges en passende repræsentation, der gør det muligt at tildele individuelle løsningskomponenter et kvalitetsmål ("fitness"). Dette adskiller sig fra holistiske tilgange som optimering af maurekoloni og evolutionær beregning, der tildeler alle egnethedskomponenter af en løsning baseret på deres kollektive vurdering mod en objektiv funktion. Algoritmen initialiseres med en indledende løsning, som kan konstrueres tilfældigt eller afledes fra en anden søgningsproces.

Teknikken er en finkornet søgning og ligner overfladisk en bjergbestigningsteknik (lokal søgning). En mere detaljeret undersøgelse afslører nogle interessante principper, som kan have anvendelighed og endda nogen lighed med bredere befolkningsbaserede tilgange ( evolutionær beregning og kunstigt immunsystem ). Det styrende princip bag denne algoritme er forbedring gennem selektiv fjernelse af komponenter af lav kvalitet og erstatning med en tilfældigt valgt komponent. Dette er naturligvis i strid med genetiske algoritmer , den kvintessente evolutionære beregningsalgoritme, der vælger gode løsninger i et forsøg på at skabe bedre løsninger.

Den resulterende dynamik i dette enkle princip er for det første en robust bjergbestigning-søgeadfærd og for det andet en mangfoldighedsmekanisme, der ligner den ved flere-genstart-søgning. Tegning af holistisk løsningskvalitet over tid (algoritme-iterationer) viser perioder med forbedring efterfulgt af kvalitetsnedbrud (lavine) meget på den måde som beskrevet af punktueret ligevægt . Det er disse nedbrud eller dramatiske spring i søgerummet, der gør det muligt for algoritmen at undslippe lokal optima og skelne denne tilgang fra andre lokale søgningsprocedurer. Selvom sådan adskilt-ligevægtsadfærd kan "designes" eller "hårdkodes", skal det understreges, at dette er en fremvoksende effekt af princippet om valg af negativ komponent, der er grundlæggende for algoritmen.

EO er primært blevet anvendt på kombinatoriske problemer som grafpartitionering og det rejsende sælgerproblem samt problemer fra statistisk fysik såsom spinbriller .

Variationer på tema og applikationer

Generaliseret ekstrem optimering (GEO) blev udviklet til at fungere på bitstrenge, hvor komponentkvalitet bestemmes af bitens absolutte hastighed eller bitens bidrag til en holistisk løsningskvalitet. Dette arbejde inkluderer anvendelse på standardfunktioner til optimering af funktioner samt tekniske problemdomæner. En anden lignende udvidelse til EO er Continuous Extremal Optimization (CEO).

EO er blevet anvendt til billedrasterisering såvel som brugt som en lokal søgning efter brug af optimering af myrkoloni . EO er blevet brugt til at identificere strukturer i komplekse netværk. EO er blevet brugt på et problem med flere målsporing. Endelig er der gjort noget arbejde med at undersøge sandsynlighedsfordelingen, der bruges til at kontrollere udvælgelsen.

Se også

Referencer

eksterne links