Algorytm PBIL

Algorytm Population-Based Incremental Learning (algorytm PBIL) jest prostym algorytmem ewolucyjnym (ang. Evolutionary Algorithm) z rodziny algorytmów estymowania rozkładu (ang. Estimation of Distribution Algorithms, EDA), które rozwiązują problem optymalizacji przez estymowanie rozkładu prawdopodobieństwa opisującego rozwiązanie optymalne.

Algorytm PBIL – model probabilistyczny

Algorytm PBIL służy do optymalizacji funkcji celu \(F:\Omega\to\mathbb{R}\) określonej na przestrzeni poszukiwań \(\Omega=\{0,1\}^d\) złożonej z ciągów binarnych ustalonej długości \(d\) i przyjmującej wartości rzeczywiste.

Algorytm PBIL optymalizuje funkcję celu \(F:\Omega\to\mathbb{R}\) przez iteracyjne konstruowanie modelu probabilistycznego opisującego rozwiązanie optymalne \(\mathbf{x}^* = (x^*_1, x^*_2, \ldots, x^*_d) \in \Omega\), czyli wyznaczanie ciągu rozkładów prawdopodobieństwa \(\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_T\), gdzie \(T\) jest liczbą iteracji algorytmu PBIL, przybliżających rozkład prawdopodobieństwa wektora losowego \(\mathbf{X} = (X_1, X_2, \ldots, X_d) \in \Omega\) opisującego rozwiązanie optymalne problemu optymalizacji. Model probabilistyczny używany w algorytmie PBIL zakłada niezależność zmiennych losowych \(X_1, X_2, \ldots, X_d \in \{0, 1\}\), a zatem rozkład prawdopodobieństwa \(\mathcal{P}_t\), dla każdego \(t=1,2,\ldots,T\) ma postać

$$
\mathcal{P}_t(\mathbf{X} = \mathbf{x}^*) =
\mathcal{P}_t(X_1 = x_1, X_2 = x_2, \ldots, X_d = x_d) =
\mathcal{P}_t(X_1 = x_1) \cdot \mathcal{P}_t(X_2 = x_2) \cdots \mathcal{P}_t(X_d = x_d).
$$

Jako że zmienne losowe \(X_1, X_2, \ldots, X_d\) przyjmują wartości binarne, rozkład prawdopodobieństwa \(\mathcal{P}_t\) można definiować przez określenie prawdopodobieństw \(\mathcal{P}_t(X_1 = 1), \mathcal{P}_t(X_2 = 1), \ldots, \mathcal{P}_d(X_i = 1)\), czyli przez określenie wektora prawdopodobieństw \(\mathbf{p}_t = (p^{(t)}_1, p^{(t)}_2, \ldots, p^{(t)}_d) \in [0, 1]^d\), gdzie \(p^{(t)}_i = \mathcal{P}_t(X_i = 1)\) oznacza prawdopodobieństwo wystąpienia jedynki na \(i\)-tej współrzędnej optymalnego wektora rozwiązania.

Algorytm PBIL – działanie

Schemat algorytmu PBIL przedstawia poniższy kod:

p[0] = [0.5, 0.5, …, 0.5]
FOR t = 1 TO T
populacja = Populacja_Losowa(p[t-1])
rozwiazanie = Najlepsze_Rozwiazanie(populacja)
p[t] = (1 – teta1) * p[t-1] + teta1 * rozwiazanie
FOR i = 1 TO d
z prawdopodobieństwem teta2
p[t][i] = (1 – teta3) * p[t][i] + teta3 * Binarna_Wartosc_Losowa()
[\code]

T oznacza liczbę iteracji algorytmu Population-Based Incremental Learning, d oznacza wymiar przestrzeni poszukiwań, zaś teta1, teta2 i teta3 są parametrami algorytmu PBIL.

Algorytm PBIL – implementacja

Przykładową implementację algorytmu PBIL w języku Python przedstawia poniższy kod:

import numpy as np

d = 10
N = 20
T = 50
theta_1 = 0.10
theta_2 = 0.05
theta_3 = 0.01

def objective_function(population):
    return population.sum(axis=1)

p = np.empty((T+1, d))

p[0, :] = 0.5

for t in xrange(T):
    population = (np.random.rand(N, d) < p[t, :]).astype(np.int)
    objective_values = objective_function(population)

    p[t+1, :] = (1 - theta_1) * p[t, :] + theta_1 * population[objective_values.argmax(), :]

    mutation = np.random.rand(d) < theta_2
    p[t+1, mutation] = (1 - theta_3) * p[t+1, mutation] + theta_3 * (np.random.rand(d)).astype(np.int)[mutation]

Algorytm PBIL – przykład

Poniższy przykład przedstawia działanie algorytmu PBIL na problemie optymalizacji OneMax, który często stosowany jest do testowania algorytmów ewolucyjnych i genetycznych. W problemie OneMax funkcja celu, określona na przestrzeni poszukiwań złożonej z ciągów binarnych ustalonej długości, zlicza liczbę jedynek w ciągu binarnym. Przyjmuje ona maksimum dla ciągu złożonego z samych jedynek i równe jest ono ustalonej długości ciągów.

Pierwszy rysunek przedstawia model probabilistyczny w kolejnych iteracjach algorytmu Population-Based Incremental Learning zastosowanego do rozwiązywania problemu OneMax z ciągami binarnymi długości 10. Każda krzywa na rysunku odpowiada jednej współrzędnej wektora prawdopodobieństw. Początkowo, w iteracji 0, wszystkie współrzędne wektora prawdopodobieństw miały wartość 0.5. Następnie, w kolejnych iteracjach algorytmu PBIL, wartości zmieniały się: w większości rosnąć, ale (prawdopodobnie na skutek mutacji) czasem malejąc. Ostatecznie, w iteracji 50, wszystkie współrzędne wektora prawdopodobieństw miały wartość bardzo bliską 1.

algorytm PBIL - model probabilistyczny

Drugi rysunek przedstawia wartość oczekiwaną funkcji celu, estymowaną przez średnią z wartości współrzędnych wektora prawdopodobieństw, w kolejnych iteracjach algorytmu PBIL. Początkowo, w iteracji 0, wartość oczekiwana wynosiła 0.5, bo wszystkie współrzędne wektora prawdopodobieństw miały wartość 0.5. Ostatecznie, w iteracji 50, wartość oczekiwaną funkcji celu była bardzo bliska 1, a zatem bardzo bliska optymalnemu rozwiązaniu.

algorytm PBIL - wartość oczekiwana funkcji celu

Trzeci rysunek przedstawia odchylenie standardowe funkcji celu w kolejnych iteracjach algorytmu Population-Based Incremental Learning.

algorytm PBIL - odchylenie standardowe funkcji celu