Uppskattning av distributionsalgoritm - Estimation of distribution algorithm

Uppskattning av distributionsalgoritm. För varje iteration i utförs en slumpmässig dragning för en population P i en PDu med fördelning . Distributionsparametrarna PDe uppskattas sedan med användning av de valda punkterna PS . Det illustrerade exemplet optimerar en kontinuerlig målfunktionen f (X) med en unik optimal O . Provtagningen (efter en normalfördelning N ) koncentreras kring det optimala när man går längs med avvecklingsalgoritmen.

Uppskattning av distributionsalgoritmer ( EDA ), ibland kallade probabilistiska modellbyggande genetiska algoritmer (PMBGA), är stokastiska optimeringsmetoder som styr sökandet efter det optimala genom att bygga och ta prov på tydliga probabilistiska modeller av lovande kandidatlösningar. Optimering ses som en serie inkrementella uppdateringar av en sannolikhetsmodell, som börjar med att modellen kodar ett oinformativt tidigare än tillåtna lösningar och slutar med modellen som endast genererar den globala optiman.

EDA hör till klassen av evolutionära algoritmer . Huvudskillnaden mellan EDA och de mest konventionella evolutionära algoritmerna är att evolutionära algoritmer genererar nya kandidatlösningar med hjälp av en implicit distribution definierad av en eller flera variationoperatörer, medan EDA använder en uttrycklig sannolikhetsfördelning som kodas av ett Bayesianskt nätverk , en multivariat normalfördelning eller en annan modellklass. På samma sätt som andra evolutionära algoritmer kan EDA användas för att lösa optimeringsproblem definierade över ett antal representationer från vektorer till LISP -stil S -uttryck, och kvaliteten på kandidatlösningar utvärderas ofta med hjälp av en eller flera objektiva funktioner.

Det allmänna förfarandet för ett EDA beskrivs i följande:

t := 0
initialize model M(0) to represent uniform distribution over admissible solutions
while (termination criteria not met) do
    P := generate N>0 candidate solutions by sampling M(t)
    F := evaluate all candidate solutions in P
    M(t + 1) := adjust_model(P, F, M(t))
    t := t + 1

Genom att använda tydliga probabilistiska modeller för optimering fick EDA: er att lösa optimeringsproblem som var notoriskt svåra för de flesta konventionella evolutionära algoritmer och traditionella optimeringstekniker, till exempel problem med höga epistaser . Fördelen med EDA är dock också att dessa algoritmer ger en optimeringsutövare en rad probabilistiska modeller som avslöjar mycket information om problemet som ska lösas. Denna information kan i sin tur användas för att designa problemspecifika grannskapsoperatörer för lokal sökning, förspänna framtida körningar av EDA på ett liknande problem eller för att skapa en effektiv beräkningsmodell av problemet.

Till exempel, om populationen representeras av bitsträngar med längd 4, kan EDA representera populationen av lovande lösning med hjälp av en enda vektor med fyra sannolikheter (p1, p2, p3, p4) där varje komponent av p definierar sannolikheten för det positionen är en 1. Med denna sannolikhetsvektor är det möjligt att skapa ett godtyckligt antal kandidatlösningar.

Uppskattning av distributionsalgoritmer (EDA)

Detta avsnitt beskriver de modeller som byggts av några välkända EDA: er med olika komplexitetsnivåer. Det antas alltid en befolkning vid generationen , en urvalsoperatör , en modellbyggande operatör och en provtagningsoperatör . ${\ displaystyle P (t)}$ ${\ displaystyle t}$ ${\ displaystyle S}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ beta}$

Univariata faktoriseringar

De mest enkla EDAS antar att beslutsvariabler är oberoende, det vill säga . Därför förlitar sig univariata EDA bara på univariat statistik och multivariata fördelningar måste faktoriseras som en produkt av univariata sannolikhetsfördelningar, ${\ displaystyle p (X_ {1}, X_ {2}) = p (X_ {1}) \ cdot p (X_ {2})}$ ${\ displaystyle N}$

${\ displaystyle D _ {\ text {Univariate}}: = p (X_ {1}, \ dots, X_ {N}) = \ prod _ {i = 1}^{N} p (X_ {i}).}$

Sådana faktoriseringar används i många olika EDA: er, därefter beskriver vi några av dem.

Univariat marginalfördelningsalgoritm (UMDA)

UMDA är en enkel EDA som använder en operatör för att uppskatta marginella sannolikheter från en vald befolkning . Genom att anta innehålla element producerar sannolikheter: ${\ displaystyle \ alpha _ {UMDA}}$ ${\ displaystyle S (P (t))}$ ${\ displaystyle S (P (t))}$ ${\ displaystyle \ lambda}$ ${\ displaystyle \ alpha _ {UMDA}}$

${\ displaystyle p_ {t+1} (X_ {i}) = {\ dfrac {1} {\ lambda}} \ sum _ {x \ i S (P (t))} x_ {i}, ~ \ forall i \ i 1,2, \ dots, N.}$

Varje UMDA -steg kan beskrivas enligt följande

${\ displaystyle D (t+1) = \ alfa _ {\ text {UMDA}} \ circ S \ circ \ beta _ {\ lambda} (D (t)).}$

Befolkningsbaserat inkrementellt lärande (PBIL)

PBIL, representerar befolkningen implicit genom sin modell, från vilken den provar nya lösningar och uppdaterar modellen. Vid varje generation urvals individer och väljs ut. Sådana individer används sedan för att uppdatera modellen enligt följande ${\ displaystyle \ mu}$ ${\ displaystyle \ lambda \ leq \ mu}$

${\ displaystyle p_ {t+1} (X_ {i}) = (1- \ gamma) p_ {t} (X_ {i})+(\ gamma /\ lambda) \ sum _ {x \ i S (P (t))} x_ {i}, ~ \ forall i \ i 1,2, \ dots, N,}$

var är en parameter som definierar inlärningshastigheten , bestämmer ett litet värde att den föregående modellen endast ska modifieras något av de nya lösningarna som samplats. PBIL kan beskrivas som ${\ displaystyle \ gamma \ in (0,1]}$ ${\ displaystyle p_ {t} (X_ {i})}$

${\ displaystyle D (t+1) = \ alfa _ {\ text {PIBIL}} \ circ S \ circ \ beta _ {\ mu} (D (t))}$

Kompakt genetisk algoritm (cGA)

CGA förlitar sig också på de implicita populationer som definieras av univariata fördelningar. Vid varje generation , två individer samplas, . Befolkningen sorteras sedan i minskande kondition, med att vara den bästa och den sämsta lösningen. CGA uppskattar univariata sannolikheter enligt följande ${\ displaystyle t}$ ${\ displaystyle x, y}$ ${\ displaystyle P (t) = \ beta _ {2} (D (t))}$ ${\ displaystyle P (t)}$ ${\ displaystyle S _ {{\ text {Sort}} (f)} (P (t))}$ ${\ displaystyle u}$ ${\ displaystyle v}$

${\ displaystyle p_ {t+1} (X_ {i}) = p_ {t} (X_ {i})+\ gamma (u_ {i} -v_ {i}), \ quad \ forall i \ i 1, 2, \ dots, N,}$

där, är en konstant som definierar inlärningshastigheten , vanligtvis inställd på . CGA kan definieras som ${\ displaystyle \ gamma \ in (0,1]}$ ${\ displaystyle \ gamma = 1/N}$

${\ displaystyle D (t+1) = \ alfa _ {\ text {CGA}} \ circ S _ {{\ text {Sort}} (f)} \ circ \ beta _ {2} (D (t))}$

Bivariata faktoriseringar

Även om univariata modeller kan beräknas effektivt, är de i många fall inte tillräckligt representativa för att ge bättre prestanda än GA. För att övervinna en sådan nackdel föreslogs användningen av bivariata faktoriseringar i EDA -gemenskapen, där beroenden mellan par av variabler kunde modelleras. En bivariat faktorisering kan definieras enligt följande, där innehåller en möjlig variabel som beror på , dvs . ${\ displaystyle \ pi _ {i}}$ ${\ displaystyle X_ {i}}$ ${\ displaystyle | \ pi _ {i} | = 1}$

${\ displaystyle D _ {\ text {Bivariate}}: = p (X_ {1}, \ dots, X_ {N}) = \ prod _ {i = 1}^{N} p (X_ {i} | \ pi _ {i}).}$

Bivariata och multivariata distributioner representeras vanligtvis som probabilistiska grafiska modeller (grafer), där kanter betecknar statistiska beroenden (eller villkorliga sannolikheter) och hörn betecknar variabler. För att lära sig strukturen för en PGM från datalänkande-lärande används.

Ömsesidig information som maximerar input clustering (MIMIC)

MIMIC faktoriserar den gemensamma sannolikhetsfördelningen i en kedjeliknande modell som representerar successiva beroenden mellan variabler. Den finner en permutation av beslutsvariabler, så att Minimerar Kullback-Leibler divergens i förhållande till den verkliga sannolikhetsfördelning, det vill säga . MIMIC modellerar en distribution ${\ displaystyle r: i \ mapsto j}$ ${\ displaystyle x_ {r (1)} x_ {r (2)}, \ dots, x_ {r (N)}}$ ${\ displaystyle \ pi _ {r (i+1)} = \ {X_ {r (i)} \}}$

${\ displaystyle p_ {t+1} (X_ {1}, \ dots, X_ {N}) = p_ {t} (X_ {r (N)}) \ prod _ {i = 1}^{N-1 } p_ {t} (X_ {r (i)} | X_ {r (i+1)}).}$

Nya lösningar samplas från variabeln längst till vänster till höger, den första genereras oberoende och de andra enligt villkorade sannolikheter. Eftersom den uppskattade distributionen måste beräknas varje generation använder MIMIC konkreta populationer på följande sätt

${\ displaystyle P (t+1) = \ beta _ {\ mu} \ circ \ alpha _ {\ text {MIMIC}} \ circ S (P (t)).}$

Bivariat marginalfördelningsalgoritm (BMDA)

BMDA faktoriserar den gemensamma sannolikhetsfördelningen i bivariata fördelningar. Först läggs en slumpmässigt vald variabel till som en nod i en graf, den mest beroende variabeln till en av dem i grafen väljs bland dem som ännu inte finns i grafen, denna procedur upprepas tills ingen kvarvarande variabel beror på någon variabel i diagram (verifierat enligt ett tröskelvärde).

Den resulterande modellen är en skog med flera träd rotade vid noder . Med tanke på de icke-rotvariablerna uppskattar BMDA en faktoriserad fördelning där rotvariablerna kan samplas oberoende, medan alla andra måste konditioneras till den överordnade variabeln . ${\ displaystyle \ Upsilon _ {t}}$ ${\ displaystyle I_ {t}}$ ${\ displaystyle \ pi _ {i}}$

${\ displaystyle p_ {t+1} (X_ {1}, \ dots, X_ {N}) = \ prod _ {X_ {i} \ in \ Upsilon _ {t}} p_ {t} (X_ {i} ) \ cdot \ prod _ {X_ {i} \ i I_ {t}} p_ {t} (X_ {i} | \ pi _ {i}).}$

Varje steg i BMDA definieras enligt följande

${\ displaystyle P (t+1) = \ beta _ {\ mu} \ circ \ alpha _ {\ text {BMDA}} \ circ S (P (t)).}$

Multivariata faktoriseringar

Nästa steg i utvecklingen av EDA var användningen av multivariata faktoriseringar. I detta fall är den gemensamma sannolikhetsfördelningen vanligtvis faktoriserad i ett antal komponenter av begränsad storlek . ${\ displaystyle | \ pi _ {i} | \ leq K, ~ \ forall i \ i 1,2, \ dots, N}$

${\ displaystyle p (X_ {1}, \ dots, X_ {N}) = \ prod _ {i = 1}^{N} p (X_ {i} | \ pi _ {i})}$

Inlärning av PGM som kodar för multivariata distributioner är en beräkningsmässigt dyr uppgift. Därför är det vanligt att EDA uppskattar multivariat statistik från bivariat statistik. Sådan avslappning gör att PGM kan byggas in på polynomtid i ; det begränsar emellertid också allmänheten i sådana EDA. ${\ displaystyle N}$

Utökad kompakt genetisk algoritm (eCGA)

ECGA var en av de första EDA som använde multivariata faktoriseringar, där beroendeordningar mellan beslutsvariabler kan modelleras. Dess tillvägagångssätt faktoriserar den gemensamma sannolikhetsfördelningen i produkten av multivariata marginalfördelningar. Antag är en uppsättning delmängder, där alla är en kopplingsuppsättning, som innehåller variabler. Den faktoriserade gemensamma sannolikhetsfördelningen representeras enligt följande ${\ displaystyle T _ {\ text {eCGA}} = \ {\ tau _ {1}, \ dots, \ tau _ {\ Psi} \}}$ ${\ displaystyle \ tau \ i T _ {\ text {eCGA}}}$ ${\ displaystyle | \ tau | \ leq K}$

${\ displaystyle p (X_ {1}, \ dots, X_ {N}) = \ prod _ {\ tau \ i T _ {\ text {eCGA}}} p (\ tau).}$

ECGA populariserade termen "kopplingsinlärning" som betecknande förfaranden som identifierar kopplingsuppsättningar. Dess kopplingsinlärningsprocedur bygger på två åtgärder: (1) Model Complexity (MC) och (2) the Compressed Population Complexity (CPC). MC kvantifierar modellrepresentationens storlek i termer av antalet bitar som krävs för att lagra alla marginella sannolikheter

${\ displaystyle MC = \ log _ {2} (\ lambda +1) \ sum _ {\ tau \ i T _ {\ text {eCGA}}} (2^{| \ tau | -1}),}$

CPC, å andra sidan, kvantifierar datakomprimeringen i termer av entropi av marginalfördelningen över alla partitioner, där är den valda befolkningsstorleken, är antalet beslutsvariabler i kopplingsuppsättningen och är den gemensamma entropin för variablerna i ${\ displaystyle \ lambda}$ ${\ displaystyle | \ tau |}$ ${\ displaystyle \ tau}$ ${\ displaystyle H (\ tau)}$ ${\ displaystyle \ tau}$

${\ displaystyle CPC = \ lambda \ sum _ {\ tau \ i T _ {\ text {eCGA}}} H (\ tau).}$

Kopplingsinlärningen i ECGA fungerar enligt följande: (1) Infoga varje variabel i ett kluster, (2) beräkna CCC = MC + CPC för de nuvarande kopplingsuppsättningarna, (3) verifiera ökningen på CCC genom att koppla ihop par med kluster, (4) sammanfogar effektivt de kluster med högsta CCC -förbättring. Denna procedur upprepas tills inga CCC -förbättringar är möjliga och ger en kopplingsmodell . ECGA arbetar med konkreta populationer, därför kan den med hjälp av den faktoriserade fördelningen som modelleras av ECGA beskrivas som ${\ displaystyle T _ {\ text {eCGA}}}$

${\ displaystyle P (t+1) = \ beta _ {\ mu} \ circ \ alpha _ {\ text {eCGA}} \ circ S (P (t))}$

Bayesiansk optimeringsalgoritm (BOA)

BOA använder Bayesianska nätverk för att modellera och prova lovande lösningar. Bayesiska nätverk är riktade acykliska grafer, med noder som representerar variabler och kanter som representerar villkorliga sannolikheter mellan par av variabler. Värdet på en variabel kan betingas av maximalt andra variabler, definierade i . BOA bygger en PGM som kodar en faktoriserad gemensam fördelning, där parametrarna i nätet, det vill säga villkorliga sannolikheter, uppskattas från den utvalda populationen med hjälp av den maximala sannolikhetsestimatorn. ${\ displaystyle x_ {i}}$ ${\ displaystyle K}$ ${\ displaystyle \ pi _ {i}}$

${\ displaystyle p (X_ {1}, X_ {2}, \ dots, X_ {N}) = \ prod _ {i = 1}^{N} p (X_ {i} | \ pi _ {i}) .}$

Den Bayesianska nätverksstrukturen måste å andra sidan byggas iterativt (kopplingsinlärning). Det börjar med ett nätverk utan kanter och lägger i varje steg till kanten som bättre förbättrar vissa poängmätningar (t.ex. Bayesiansk informationskriterium (BIC) eller Bayesian-Dirichlet-mätvärde med sannolikhetsekvivalens (BDe)). Poängvärdet utvärderar nätverksstrukturen enligt dess noggrannhet vid modellering av den utvalda befolkningen. Från det inbyggda nätverket samplar BOA nya lovande lösningar enligt följande: (1) den beräknar förfädernas ordning för varje variabel, varje nod föregås av sina föräldrar; (2) varje variabel samplas villkorligt till sina föräldrar. Med tanke på ett sådant scenario kan varje BOA -steg definieras som

${\ displaystyle P (t+1) = \ beta _ {\ mu} \ circ \ alpha _ {\ text {BOA}} \ circ S (P (t))}$

Linkage-tree Genetic Algorithm (LTGA)

LTGA skiljer sig från de flesta EDA i den meningen att den inte uttryckligen modellerar en sannolikhetsfördelning utan bara en kopplingsmodell, kallad länkträd. En koppling är en uppsättning kopplingsuppsättningar utan sannolikhetsfördelning associerad, därför finns det inget sätt att prova nya lösningar direkt från . Kopplingsmodellen är ett kopplingsträd som produceras lagrat som en familj av uppsättningar (FOS). ${\ displaystyle T}$ ${\ displaystyle T}$

${\ displaystyle T _ {\ text {LT}} = \ {\ {x_ {1} \}, \ {x_ {2} \}, \ {x_ {3} \}, \ {x_ {4} \}, \ {x_ {1}, x_ {2} \}, \ {x_ {3}, x_ {4} \} \}.}$

Inlärningsproceduren för kopplingsträd är en hierarkisk klusteralgoritm som fungerar enligt följande. Vid varje steg de två närmaste klustren och slås samman, upprepas denna procedur tills endast ett kluster återstår, varje delträd lagras som en delmängd . ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle \ tau \ i T _ {\ text {LT}}}$

LTGA använder för att styra en "optimal blandning" -procedur som liknar en rekombinationsoperatör men bara accepterar förbättrade drag. Vi betecknar det som där notationen indikerar överföringen av det genetiska materialet som indexeras av från till . ${\ displaystyle T _ {\ text {LT}}}$ ${\ displaystyle R _ {\ text {LTGA}}}$ ${\ displaystyle x [\ tau] \ får y [\ tau]}$ ${\ displaystyle \ tau}$ ${\ displaystyle y}$ ${\ displaystyle x}$

Algorithm Gene-pool optimal mixing
   Input: A family of subsets  $T_{\text{LT}}$  and a population  $P(t)$ 
   Output: A population  $P(t+1)$ .
   for each  $x_{i}$  in  $P(t)$  do
       for each  $\tau$  in  $T_{\text{LT}}$  do
           choose a random  $x_{j}\in P(t):x_{i}\neq x_{j}$ 
            $f_{x_{i}}$  :=  $f(x_{i})$ 
            $x_{i}[\tau ]$ :=  $x_{j}[\tau ]$ 
           if  $f(x_{i})\leq f_{x_{i}}$  then
                $x_{i}[\tau ]:=x_{j}[\tau ]$  
   return  $P(t)$

"←" betecknar uppgift . Till exempel betyder " största ← artikel " att värdet av största ändras till objektets värde .
" retur " avslutar algoritmen och matar ut följande värde.

LTGA implementerar inte typiska urvalsoperatörer, istället utförs urval under rekombination. Liknande idéer har vanligtvis tillämpats på heuristik för lokal sökning och i denna mening kan LTGA ses som en hybridmetod. Sammanfattningsvis definieras ett steg i LTGA som

${\ displaystyle P (t+1) = R _ {\ text {LTGA}} (P (t)) \ circ \ alpha _ {\ text {LTGA}} (P (t))}$

Övrig

Sannolikhetskollektiv (PC)
Bergsklättring med lärande (HCwL)
Uppskattning av multivariat normal algoritm (EMNA)
Uppskattning av Bayesiansk nätverksalgoritm (EBNA)
Stokastisk backklättring med inlärning av vektorer av normalfördelningar (SHCLVND)
Riktigt kodad PBIL
Egoistisk genalgoritm (SG)
Compact Differential Evolution (cDE) och dess varianter
Kompakt partikelvärmoptimering (cPSO)
Kompakt bakteriell foderoptimering (cBFO)
Probabilistisk inkrementell programutveckling (PIPE)
Uppskattning av Gaussian -nätverksalgoritm (EGNA)
Estimering multivariat normal algoritm med tröskelkonvergens
Beroendestrukturmatris Genetisk algoritm (DSMGA)

Languages

In other projects