Řešení problému vektorové kvantizace

V kapitole 4 jsme popsali tří fázovou metodu učení RBF sítí. Toto učení sestává ze tří podúloh. Jednou z nich je řešení problému vektorové kvantizace.

Protože minimalizace chybové funkce (4.3) není triviální, metody řešení vektorové kvantizace bývají založené na různých heuristikách a většinou nabízejí pouze přibližné řešení.

Nabízí se tedy možnost, řešit problém vektorové kvantizace pomocí genetického algoritmu.

Způsob kódování
Řešení problému vektorové kvantizace je tvořeno množinou $h$ vektorů. Jedinec bude tvořen zřetězením souřadnich těchto vektorů.

$$J = \{ w_{11}, w_{12}, \cdots, w_{1n}, w_{21}, \cdots, w_{2n} , \cdots, w_{h1}, w_{h2}, \cdots, w_{hn} \}$$ (5.6)

Protože na pořadí vektorů nezáleží, můžeme použít kanonický algoritmus. V tomto případě musí platit

$$\vec{w}_1 \prec \vec{w}_2 \prec \cdots \prec \vec{w}_h,$$ (5.7)

kde $\prec$ je uspořádání v lexikografickém pořadí.

Počáteční populace
Počáteční populaci vytvoříme náhodně, v případě kanonického algoritmu vektory před zakódováním setřídíme.

Účelová funkce $\mathcal{F}$
Stejně jako u učení neuronových sití 5.4 budeme hodnotit jedince hodnotou chybové funkce

$$\mathcal{F}(J_i) = E_{VQ}( \vec{w}_1, \cdots , \vec{w}_h ) ,$$ (5.8)

kde $E_{VQ}$ je chybovová funkce z vektorové kvantizace (4.3). Čím menší ohodnocení, tím lepší řešení jedinec reprezentuje.

Selekce
Použijeme selekci popsanou v části 5.4.

Křížení
Použijeme jednobodové křížení. Křížením jedinců

$$\begin{eqnarray*} J_1 & = & \{ w_{11}, \cdots , w_{kl}, \cdots, w_{hn} \} \\ J_2 & = & \{ {w'}_{11}, \cdots , {w'}_{kl}, \cdots, {w'}_{hn} \} \end{eqnarray*}$$

získáme nové jedince

$$\begin{eqnarray*} {J'}_1 = \{ w_{11}, \cdots ,{w'}_{kl}, \cdots, {w'}_{hn} \} \\ {J'}_2 = \{ {w'}_{11}, \cdots ,w_{kl}, \cdots, w_{hn} \}, \end{eqnarray*}$$

kde souřadnice $k$ a $l$ jsou zvoleny náhodně.

V případě kanonického algoritmu budeme bod křížení $k$ volit pouze na hranici bloků odpovídajících jednotlivým vektorům

$$\begin{eqnarray*} J_1 & = & \{ \vec{w}_1, \cdots , \vec{w}_k \cdots , \vec{w}_h ... ... & = & \{ \vec{w'}_1, \cdots , \vec{w'}_k \cdots , \vec{w'}_h\} \end{eqnarray*}$$

a výsledkem budou pouze jeden jedinec

$${J'}_1 = \{ w_{1}, \cdots ,{w'}_{k}, \cdots, {w'}_{h} \} \qquad \vec{w}_{k-1} \prec \vec{w'}_{k}$$

nebo

$${J'}_2 = \{ {w'}_{1}, \cdots ,w_{k}, \cdots, w_{h} \} \qquad \vec{w'}_{k-1} \prec \vec{w}_{k}$$

Mutace
Náhodně vybereme jednu souřadnici a tu náhodně změníme. V případě kanonického algoritmu náhodně vybere blok, který změníme náhodně s ohledem na zachování uspořádání.

Výše uvedený algoritmus představuje alternativu metodám pro řešení vektorové kvantizace uvedených v části 4.1. V případě, že přesně neznáme počet reprezentantů, můžeme tyto genetické operátory upravit tak, aby pracovaly s jedinci různé délky reprezentujícími řešení lišící se počtem reprezentantů. Do ohodnocení takovýchto jedinců je pak třeba zahrnout penalizaci příliš dlouhých jedinců.