Estymacja algorytmu rozkładu - Estimation of distribution algorithm

Estymacja algorytmu rozkładu. Dla każdej iteracji i losowane jest losowanie populacji P w rozkładzie PDu . Parametry rozkładu PDe są następnie szacowane za pomocą wybranych punktów PS . Zilustrowany przykład optymalizuje ciągłą funkcję celu f(X) z unikalnym optimum O . Próbkowanie (zgodnie z rozkładem normalnym N ) koncentruje się wokół optimum w miarę rozwijania algorytmu.

Estymacja algorytmów dystrybucji ( EDA ), czasami nazywanych genetycznymi algorytmami budowania modeli probabilistycznych (PMBGA), to stochastyczne metody optymalizacji , które kierują poszukiwaniem optimum poprzez budowanie i próbkowanie jawnych modeli probabilistycznych obiecujących rozwiązań. Optymalizacja jest postrzegana jako seria przyrostowych aktualizacji modelu probabilistycznego, zaczynając od modelu kodującego nieinformacyjne wyprzedzenie dopuszczalnych rozwiązań, a kończąc na modelu generującym tylko globalne optima.

EDA należą do klasy algorytmów ewolucyjnych . Główna różnica między EDA a większością konwencjonalnych algorytmów ewolucyjnych polega na tym, że algorytmy ewolucyjne generują nowe rozwiązania kandydujące przy użyciu niejawnego rozkładu zdefiniowanego przez jeden lub więcej operatorów wariacji, podczas gdy EDA używają jawnego rozkładu prawdopodobieństwa zakodowanego przez sieć bayesowską , wielowymiarowy rozkład normalny lub inny klasa modelu. Podobnie jak inne algorytmy ewolucyjne, EDA mogą być używane do rozwiązywania problemów optymalizacyjnych zdefiniowanych na podstawie wielu reprezentacji, od wektorów do wyrażeń w stylu LISP- a, a jakość proponowanych rozwiązań jest często oceniana przy użyciu jednej lub więcej funkcji celu.

Ogólna procedura EDA jest przedstawiona w następujący sposób:

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

Wykorzystanie jawnych modeli probabilistycznych w optymalizacji pozwoliło EDA na wykonalne rozwiązywanie problemów optymalizacyjnych, które były notorycznie trudne dla większości konwencjonalnych algorytmów ewolucyjnych i tradycyjnych technik optymalizacji, takich jak problemy z wysokim poziomem epistazy . Niemniej jednak zaletą EDA jest również to, że algorytmy te dostarczają praktykowi optymalizacji serii modeli probabilistycznych, które ujawniają wiele informacji o rozwiązywanym problemie. Informacje te można z kolei wykorzystać do zaprojektowania operatorów sąsiedztwa specyficznych dla danego problemu do wyszukiwania lokalnego, do skłaniania przyszłych serii EDA do podobnego problemu lub do stworzenia wydajnego modelu obliczeniowego problemu.

Na przykład, jeśli populacja jest reprezentowana przez ciągi bitów o długości 4, EDA może reprezentować populację obiecującego rozwiązania za pomocą pojedynczego wektora czterech prawdopodobieństw (p1, p2, p3, p4), gdzie każdy składnik p określa prawdopodobieństwo tego pozycja będąca 1. Wykorzystując ten wektor prawdopodobieństwa można utworzyć dowolną liczbę rozwiązań kandydujących.

Estymacja algorytmów dystrybucji (EDA)

Ta sekcja opisuje modele zbudowane przez niektóre dobrze znane EDA o różnych poziomach złożoności. Zawsze zakłada się populację w pokoleniu , operator selekcji , operator budowy modelu i operator próbkowania . ${\ Displaystyle P (t)}$${\displaystyle t}$${\displaystyle S}$${\ Displaystyle \ alfa}$${\ Displaystyle \ beta}$

Faktoryzacja jednowymiarowa

Najprostsze EDA zakładają, że zmienne decyzyjne są niezależne, tj . . Dlatego jednowymiarowe EDA opierają się tylko na jednowymiarowych statystykach, a wielowymiarowe rozkłady muszą być faktoryzowane jako iloczyn jednowymiarowych rozkładów prawdopodobieństwa, ${\ Displaystyle p (X_ {1}, X_ {2}) = p (X_ {1}) \ cdot p (X_ {2})}$${\ Displaystyle N}$

${\ Displaystyle D_ {\ tekst {jednowymiarowy}}: = p (X_ {1}, \ kropki, X_ {N}) = \ prod _ {i = 1} ^ {N} p (X_ {i}).}$

Takie faktoryzacje są używane w wielu różnych EDA, następnie opiszemy niektóre z nich.

Algorytm jednowymiarowego rozkładu marginalnego (UMDA)

UMDA to prosta EDA, która używa operatora do oszacowania marginalnych prawdopodobieństw z wybranej populacji . Zakładając zawiera elementy, daje prawdopodobieństwa: ${\ Displaystyle \ alfa _ {UMDA}}$${\displaystyle S(P(t))}$${\displaystyle S(P(t))}$${\ Displaystyle \ lambda}$${\ Displaystyle \ alfa _ {UMDA}}$

${\ Displaystyle p_ {t + 1} (X_ {i}) = {\ dfrac {1} {\ lambda}} \ suma _ {x \ w S (P (t))} x_ {i} ~ \ dla wszystkich ja\w 1,2,\kropki ,N.}$

Każdy krok UMDA można opisać w następujący sposób

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

Przyrostowe uczenie się oparte na populacji (PBIL)

PBIL reprezentuje populację niejawnie przez swój model, z którego pobiera nowe rozwiązania i aktualizuje model. W każdym pokoleniu pobierane są próbki i selekcjonowane są osobniki . Takie osoby są następnie wykorzystywane do aktualizacji modelu w następujący sposób ${\ Displaystyle \ mu}$${\ Displaystyle \ lambda \ leq \ mu}$

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

gdzie jest parametrem określającym szybkość uczenia się , mała wartość oznacza, że ​​poprzedni model powinien być tylko nieznacznie zmodyfikowany przez nowe próbkowane rozwiązania. PBIL można opisać jako ${\ Displaystyle \ gamma \ w (0,1]}$${\ Displaystyle p_ {t} (X_ {i})}$

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

Kompaktowy algorytm genetyczny (cGA)

CGA opiera się również na niejawnych populacjach zdefiniowanych przez rozkłady jednowymiarowe. W każdym pokoleniu pobierane są próbki od dwóch osobników . Populacja jest następnie sortowana w porządku malejącym według przydatności, , przy czym jest to najlepsze i najgorsze rozwiązanie. CGA szacuje jednowymiarowe prawdopodobieństwa w następujący sposób: ${\displaystyle t}$${\displaystyle x,y}$${\ Displaystyle P (t) = \ beta _ {2} (D (t))}$${\ Displaystyle P (t)}$${\ Displaystyle S_ {{\ tekst {Sortuj}} (f)} (P (t))}$${\ Displaystyle u}$${\displaystyle v}$

${\ Displaystyle p_ {t + 1} (X_ {i}) = p_ {t} (X_ {i}) + \ gamma (u_ {i}-v_ {i}}), \ quad \ dla wszystkich i \ w 1, 2,\kropki ,N,}$

gdzie jest stałą określającą szybkość uczenia się , zwykle ustawianą na . CGA można zdefiniować jako ${\ Displaystyle \ gamma \ w (0,1]}$${\ Displaystyle \ gamma = 1 / N}$

${\ Displaystyle D (t + 1) = \ alfa _ {\ tekst {CGA}} \ circ S_ {{\ tekst {sortuj}} (f)} \ circ \ beta _ {2} (D (t))}$

Faktoryzacja dwuwymiarowa

Chociaż modele jednowymiarowe można obliczyć wydajnie, w wielu przypadkach nie są one wystarczająco reprezentatywne, aby zapewnić lepszą wydajność niż modele GA. Aby przezwyciężyć tę wadę, w środowisku EDA zaproponowano zastosowanie dwuwymiarowych faktoryzacji, w których można modelować zależności między parami zmiennych. Rozkład na czynniki dwuwymiarowe można zdefiniować w następujący sposób, gdzie zawiera możliwą zmienną zależną od , tj . . ${\ Displaystyle \ pi _ {i}}$${\ Displaystyle X_ {i}}$${\ Displaystyle | \ pi _ {i} | = 1}$

${\ Displaystyle D_ {\ tekst {Dwuzmienny}}: = p (X_ {1}, \ kropki, X_ {N}) = \ prod _ {i = 1} ^ {N} p (X_ {i} | \ pi _{i}).}$

Rozkłady dwuwymiarowe i wielowymiarowe są zwykle reprezentowane jako probabilistyczne modele graficzne (grafy), w których krawędzie oznaczają zależności statystyczne (lub prawdopodobieństwa warunkowe), a wierzchołki oznaczają zmienne. Do poznania struktury PGM na podstawie połączenia danych wykorzystuje się uczenie.

Wzajemne informacje maksymalizujące grupowanie danych wejściowych (MIMIC)

MIMIC dokonuje faktoryzacji łącznego rozkładu prawdopodobieństwa w modelu łańcuchowym reprezentującym kolejne zależności między zmiennymi. Znajduje permutację zmiennych decyzyjnych , taką, która minimalizuje rozbieżność Kullbacka-Leiblera w stosunku do prawdziwego rozkładu prawdopodobieństwa, tj . . MIMIC modeluje dystrybucję ${\displaystyle r:i\mapsto j}$${\ Displaystyle x_ {r (1)} x_ {r (2)}, \ kropki, x_ {r (N)}}$${\ Displaystyle \ pi _ {r (i + 1)} = \ {X_ {r (i)} \}}$

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

Nowe rozwiązania są próbkowane od skrajnie lewej do skrajnej prawej zmiennej, pierwsze generowane jest niezależnie, a pozostałe według prawdopodobieństw warunkowych. Ponieważ szacowany rozkład musi być przeliczany w każdym pokoleniu, MIMIC wykorzystuje konkretne populacje w następujący sposób:

${\ Displaystyle P (t + 1) = \ beta _ {\ mu } \ circ \ alfa _ {\ tekst {MIMIC}} \ circ S (P (t)).}$

Dwuwymiarowy algorytm rozkładu marginalnego (BMDA)

BMDA dokonuje faktoryzacji łącznego rozkładu prawdopodobieństwa w rozkładach dwuwymiarowych. Najpierw losowo wybrana zmienna jest dodawana jako węzeł na wykresie, najbardziej zależna zmienna do jednej z tych na wykresie jest wybierana spośród tych, których jeszcze nie ma na wykresie, ta procedura jest powtarzana, dopóki żadna pozostała zmienna nie będzie zależeć od żadnej zmiennej na wykresie wykres (zweryfikowany według wartości progowej).

Powstały model to las z wieloma drzewami zakorzenionymi w węzłach . Biorąc pod uwagę zmienne inne niż pierwotne, BMDA szacuje rozkład faktoryzowany, w którym zmienne źródłowe mogą być próbkowane niezależnie, podczas gdy wszystkie inne muszą być uwarunkowane zmienną rodzicielską . ${\ Displaystyle \ Upsilon _ {t}}$${\ Displaystyle I_ {t}}$${\ Displaystyle \ pi _ {i}}$

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

Każdy krok BMDA jest zdefiniowany w następujący sposób

${\ Displaystyle P (t + 1) = \ beta _ {\ mu} \ circ \ alfa _ {\ tekst {BMDA}} \ circ S (P (t)).}$

Faktoryzacja wielowymiarowa

Kolejnym etapem rozwoju EDA było wykorzystanie wielowymiarowych faktoryzacji. W takim przypadku łączny rozkład prawdopodobieństwa jest zwykle rozkładany na czynniki o kilku składnikach o ograniczonej wielkości . ${\ Displaystyle | \ pi _ {i} | \ równoważnik K ~ \ dla wszystkich i \ w 1,2 \ kropki, N}$

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

Uczenie się PGMs kodujących rozkłady wielowymiarowe jest zadaniem kosztownym obliczeniowo, dlatego też EDA zwykle oceniają statystyki wielowymiarowe na podstawie statystyk dwuwymiarowych. Taka relaksacja pozwala na budowanie PGM w czasie wielomianowym w ; jednak ogranicza to również ogólność takich EDA. ${\ Displaystyle N}$

Rozszerzony kompaktowy algorytm genetyczny (eCGA)

ECGA była jedną z pierwszych EDA, w której zastosowano wielowymiarowe faktoryzacje, w których można modelować zależności wysokiego rzędu między zmiennymi decyzyjnymi. Jego podejście faktoryzuje łączny rozkład prawdopodobieństwa w iloczynie wielowymiarowych rozkładów krańcowych. Załóżmy, że jest zbiorem podzbiorów, w którym każdy jest zbiorem sprzężeń, zawierającym zmienne. Faktoryzowany łączny rozkład prawdopodobieństwa jest reprezentowany w następujący sposób: ${\ Displaystyle T_ {\ tekst {eCGA}} = \ {\ tau _ {1}, \ kropki, \ tau _ {\ psi} \}}$${\ Displaystyle \ tau \ w T_ {\ tekst {eCGA}}}$${\displaystyle |\tau |\leq K}$

${\ Displaystyle p (X_ {1}, \ kropki, X_ {N}) = \ prod _ {\ tau \ w T_ {\ tekst {eCGA}}} p (\ tau).}$

ECGA spopularyzowało termin „uczenie się powiązań” jako oznaczający procedury, które identyfikują zestawy powiązań. Jego procedura uczenia się powiązań opiera się na dwóch miarach: (1) złożoności modelu (MC) i (2) złożoności skompresowanej populacji (CPC). MC określa ilościowo rozmiar reprezentacji modelu pod względem liczby bitów wymaganych do przechowywania wszystkich marginalnych prawdopodobieństw

${\ Displaystyle MC = \ log _ {2} (\ lambda + 1) \ suma _ {\ tau \ w T_ {\ tekst {eCGA}}} (2 ^ {| \ tau | -1}}),}$

Z drugiej strony CPC określa ilościowo kompresję danych pod względem entropii rozkładu marginalnego na wszystkich partycjach, gdzie jest to wielkość wybranej populacji, jest liczbą zmiennych decyzyjnych w zestawie sprzężeń i jest łączną entropią zmiennych w${\ Displaystyle \ lambda}$${\displaystyle |\tau |}$${\ Displaystyle \ tau}$${\ Displaystyle H (\ tau )}$${\ Displaystyle \ tau}$

${\ Displaystyle CPC = \ lambda \ suma _ {\ tau \ w T_ {\ tekst {eCGA}}} H (\ tau).}$

Uczenie powiązań w ECGA działa w następujący sposób: (1) Wstaw każdą zmienną do klastra, (2) oblicz CCC = MC + CPC z bieżących zestawów powiązań, (3) zweryfikuj wzrost CCC zapewniony przez łączenie par klastrów, (4) skutecznie dołącza do klastrów o najwyższej poprawie CCC. Ta procedura jest powtarzana do momentu, gdy żadne ulepszenia CCC nie są możliwe i tworzy model powiązania . ECGA działa z konkretnymi populacjami, dlatego stosując rozkład czynnikowy modelowany przez ECGA, można go opisać jako ${\ Displaystyle T_ {\ tekst {eCGA}}}$

${\ Displaystyle P (t + 1) = \ beta _ {\ mu} \ circ \ alfa _ {\ tekst {eCGA}} \ circ S (P (t))}$

Bayesowski algorytm optymalizacji (BOA)

BOA wykorzystuje sieci bayesowskie do modelowania i próbkowania obiecujących rozwiązań. Sieci bayesowskie są skierowanymi grafami acyklicznymi, w których węzły reprezentują zmienne, a krawędzie reprezentują prawdopodobieństwa warunkowe pomiędzy parą zmiennych. Wartość zmiennej może być uwarunkowana maksymalnie innymi zmiennymi, zdefiniowanymi w . BOA buduje PGM kodujący łączny rozkład faktorów, w którym parametry sieci, czyli prawdopodobieństwa warunkowe, są szacowane z wybranej populacji za pomocą estymatora największej wiarygodności. ${\displaystyle x_{i}}$${\ Displaystyle K}$${\ Displaystyle \ pi _ {i}}$

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

Z drugiej strony, struktura sieci bayesowskiej musi być budowana iteracyjnie (uczenie powiązania). Rozpoczyna się od sieci bez krawędzi i na każdym kroku dodaje krawędź, która lepiej poprawia pewną metrykę punktacji (np. Bayesowskie kryterium informacyjne (BIC) lub metryka Bayesowska-Dirichleta z równoważnością wiarygodności (BDe)). Miernik scoringowy ocenia strukturę sieci zgodnie z jej dokładnością w modelowaniu wybranej populacji. Z zbudowanej sieci BOA pobiera próbki nowych obiecujących rozwiązań w następujący sposób: (1) oblicza kolejność przodków dla każdej zmiennej, przy czym każdy węzeł jest poprzedzony jego rodzicami; (2) każda zmienna jest dobierana warunkowo do swoich rodziców. Przy takim scenariuszu każdy krok BOA można zdefiniować jako

${\ Displaystyle P (t + 1) = \ beta _ {\ mu} \ circ \ alfa _ {\ tekst {BOA}} \ circ S (P (t))}$

Algorytm genetyczny drzewa powiązania (LTGA)

LTGA różni się od większości EDA w tym sensie, że nie modeluje wprost rozkładu prawdopodobieństwa, a jedynie model sprzężenia, zwany drzewem sprzężeń. Powiązanie to zbiór zbiorów powiązań bez powiązanego rozkładu prawdopodobieństwa, dlatego nie ma możliwości bezpośredniego próbkowania nowych rozwiązań z . Model powiązania jest drzewem powiązań utworzonym i przechowywanym jako rodzina zbiorów (FOS). ${\displaystyle T}$${\displaystyle T}$

${\ Displaystyle T_ {\ tekst {LT}} = \ {\ {x_ {1} \}, \ {x_ {2} \}, \ {x_ {3} \}, \ {x_ {4} \}, \{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

Procedura uczenia się drzewa powiązań to hierarchiczny algorytm grupowania , który działa w następujący sposób. Na każdym kroku dwa najbliższe klastry i są łączone, ta procedura powtarza się, aż pozostanie tylko jeden klaster, każde poddrzewo jest przechowywane jako podzbiór . ${\displaystyle i}$${\displaystyle j}$${\ Displaystyle \ tau \ w T_ {\ tekst {LT}}}$

LTGA wykorzystuje do prowadzenia procedury „optymalnego mieszania”, która przypomina operatora rekombinacji, ale akceptuje tylko ruchy poprawiające. Oznaczamy to jako , gdzie notacja wskazuje na przeniesienie materiału genetycznego indeksowanego przez od do . ${\displaystyle T_{\tekst{LT}}}$${\ Displaystyle R_ {\ tekst {LTGA}}}$${\displaystyle x[\tau]\gets y[\tau]}$${\ Displaystyle \ tau}$${\displaystyle y}$${\displaystyle x}$

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

LTGA nie implementuje typowych operatorów selekcji, zamiast tego selekcja jest wykonywana podczas rekombinacji. Podobne pomysły były zwykle stosowane w heurystyce wyszukiwania lokalnego iw tym sensie LTGA można postrzegać jako metodę hybrydową. Podsumowując, jeden etap LTGA jest zdefiniowany jako

${\ Displaystyle P (t + 1) = R_ {\ tekst {LTGA}} (P (t)) \ circ \ alfa _ {\ tekst {LTGA}} (P (t))}$

Inne

• Kolektywy prawdopodobieństwa (PC)
• Wspinaczka górska z nauką (HCwL)
• Estymacja wielowymiarowego algorytmu normalnego (EMNA)
• Estymacja algorytmu sieci bayesowskich (EBNA)
• Stochastyczna wspinaczka górska z uczeniem się za pomocą wektorów rozkładów normalnych (SHCLVND)
• PBIL z kodowaniem rzeczywistym
• Algorytm samolubnego genu (SG)
• Compact Differential Evolution (cDE) i jego warianty
• Optymalizacja kompaktowego roju cząstek (cPSO)
• Kompaktowa optymalizacja żerowania bakteryjnego (cBFO)
• Probabilistyczna przyrostowa ewolucja programu (PIPE)
• Estymacja algorytmu sieci Gaussa (EGNA)
• Estymacja wielowymiarowego algorytmu normalnego z progową zbieżnością
• Algorytm genetyczny macierzy struktury zależności (DSMGA)

Związane z

• CMA-ES
• Metoda entropii krzyżowej

Bibliografia