2.2 Metóda spätného šírenia chyby (BP) na RC NN
2.1 Hopfieldove siete
2.1 Hopfieldove siete

Obsah

2.1.1 Problém obchodného cestujúceho (TSP)

Majme danú mno¾inu $n$ miest a vzdialenosť $d_{i,j}$ pre v¹etky dvojice miest $i,j$. Potrebujeme zistiť, v akom poradí má obchodný cestujúci prechádzať mestá tak, aby sa vrátil do mesta, z ktorého vyrazil a zároveò ka¾dé mesto na trase nav¹tívil práve jedenkrát. Podmienkou v¹ak je, ¾e vzdialenosť, ktorú precestoval, je najkrat¹ia mo¾ná. Rie¹enie tohto problému je prípustné, ak sú splnené nasledujúce obmedzenia :

• obchodný cestujúci prechádza ka¾dým mestom práve jedenkrát,
• jeho cesta v grafe tvorí cyklus.

Prípustnosť rie¹enia je teda daná nájdením hamiltonovskej kru¾nice a mieru optimality rie¹enia popisuje súèet vzdialeností medzi mestami na hamiltonovskej kru¾nici. Neurónová sieť, ktorá tento problém rie¹i, musí vyjadriť pre dané mesto, ktoré mesto mu predchádza a ktoré mesto za ním nasleduje. Toto je vyjadriteľné v sieti s $n^2$ neurónmi pri maticovom usporiadaní uvedenom na obr. 2.2

Obrázok 2.2: Návrh neurónovej siete pre TSP pri $n=4$. Kvôli prehľadnosti nie sú zakreslené prepojenia neurónov. Rie¹enie je zobrazené pomocou èiar. Rie¹ením je postupnosť miest 4-2-1-3, prípadne jej cyklická premutácia.

Je zrejmé, ¾e usporiadanie v tomto tvare pomáha pri pochopení rie¹enia, inak je nepodstatné. Vzťah pre energiu siete je mo¾né upraviť pomocou zavedenia dvoch indexov pre jeden neurón. Jedná sa len o technickú úpravu vzťahu, význam zostane nezmenený. Teraz sformulujeme túto úlohu pomocou novej sústavy dvojstavových premenných tak, aby hľadanie prípustného rie¹enia mohlo byť vyjadrené ako minimalizácia funkcie týchto nových premenných. Zadefinujme maticu ${\bf M}$ typu $n~ x~ n$ s prvkami ${\bf M}_{ij}$, ktoré nadobúdajú hodnoty $0$ alebo $1$, pre $i,j \in <1,n>$. ${\bf M}_{ij}= 1$ vtedy, keď obchodný cestujúci prechádza mestom $i$ v $j$-tom kroku. V opaènom prípade ${\bf M}_{ij} = 0$. V podstate hodnoty ${\bf M}_{ij}$ sú ekvivalentom hodnotám neurónov $x_{ij}$. Prípustnému rie¹eniu pôvodnej úlohy teraz zodpovedá stav matice, ktorý sa dá popísať nasledovne :

• v ka¾dom riadku je najviac jedna jednièka, tj. pre x-te mesto platí ${\bf M}_{xj}{\bf M}_{xl}=0$, ak $j \ne l$,
• v ka¾dom ståpci je najviac jedna jednièka, tj. pre x-ty krok obchodného cestujúceho platí ${\bf M}_{ix}{\bf M}_{kx}=0$, ak $i \ne k$,
• v matici je práve $n$ jednièiek, tj. $\sum_i ^n \sum_j ^n {\bf M}_{ij}=n$,
• súèet vzdialeností medzi mestami je urèený maticou vzdialeností, prièom celková då¾ka cesty je $\frac{1}{2} \sum_i ^n \sum_{k\ne i} ^n \sum_{y}^n d_{ki}{\bf M}_{ky}({\bf M}_{i,y-1}+{\bf M}_{i,y+1})$

Teraz vytvoríme funkcie $E_a, E_b, E_c$ a $E_d$, ktoré nadobúdajú minimálne hodnoty pri splnení predchádzajúcich podmienok. Funkcie sú vytvárané na základe vzťahov uvedených v týchto podmienkách.

$$E_a = \frac{A}{2} \sum_x ^n \sum_j ^n \sum_{l \ne j}^n {\bf M}_{xj}{\bf M}_{xl}$$ (2.7)

$$E_b = \frac{B}{2} \sum_i ^n \sum_x ^n \sum_{i \ne k}^n {\bf M}_{ix}{\bf M}_{kx}$$ (2.8)

$$E_c = \frac{C}{2} (\sum_i ^n \sum_j ^n {\bf M}_{ij} -n )^2$$ (2.9)

$$E_d = \frac{D}{2} \sum_i ^n \sum_{k\ne i} ^n \sum_{y}^n d_{ki}{\bf M}_{ky}({\bf M}_{i,y-1}+{\bf M}_{i,y+1})$$ (2.10)

Vo vzťahoch (2.7) - (2.10) A, B, C a D sú voliteľné parametre. Tak¾e rie¹enie je optimálne, ak $E = E_a + E_b + E_c + E_d$ nadobúda svoje minimum. Na tomto mieste je vhodné pripomenúť si, ako vyzerá energetická funkcia pre diskrétny model Hopfieldovej siete pri maticovom oèíslovaní neurónov:

$$E_{hop}=-\frac{1}{2} \sum_i ^n \sum_j ^n \sum_k^n \sum_l^... ...}{\bf M}_{kl}+ +\sum_i ^n \sum_j ^n \Theta_{ij}{\bf M}_{ij}$$ (2.11)

Prepísaním (2.7),(2.8),(2.9) a (2.10) na tvar energetickej funkcie (2.11) dosiahneme to, ¾e tvar "na¹ej" funkcie $E$ bude ekvivalentný tvaru funkcie $E_{hop}$, ktorá sa poèas konvergencie siete minimalizuje (základná vlastnosť Hopfieldovej siete). Po tomto prepísaní nám teda bude staèiť porovnať výsledky s (2.11) a ľahko vypoèítame nastavenie váh a prahov. Nasledujúce úpravy spoèívajú v zavedení symbolu Croneckerovo delta, tj. $\delta_{ij}=1$, ak $i=j$, inak $\delta_{ij}=0$, èo nám umo¾ní doplniť do niektorých výrazov ďal¹ie sumy. Z (2.7) vyplýva

$$E_a=\frac{A}{2} \sum_i ^n \sum_j ^n \sum_k^n \sum_l^n \delta_{ik}(1-\delta_{jl}) {\bf M}_{ij}{\bf M}_{kl}$$ (2.12)

Výraz $\delta_{ik}(1-\delta_{jl})$ je rovný $0$, ak $i \ne k$ alebo $j=l$.

$$E_a=-\frac{1}{2} \sum_i ^n \sum_j ^n \sum_k^n \sum_l^n -A \delta_{ik}(1-\delta_{jl}) {\bf M}_{ij}{\bf M}_{kl}$$ (2.13)

Tento výraz je vlastne výraz (2.11), kde

$$T_{ij,kl}^a = -A \delta_{ik} (1-\delta_{jl})$$ (2.14)

Analogicky z (2.8) dostaneme

$$T_{ij,kl}^b = -B \delta_{jl} (1-\delta_{ik})$$ (2.15)

Z (2.9) dostaneme

$$E_c=\frac{C}{2} (\sum_i ^n \sum_j ^n \sum_k^n \sum_l^n {\bf... ...{ij}{\bf M}_{kl} -2n \sum_i ^n \sum_j ^n {\bf M}_{ij} +n^2)$$ (2.16)

Po prenásobení výrazu v zátvorke výrazom $\frac{C}{2}$ dostaneme

$$E_c=-\frac{1}{2} \sum_i ^n \sum_j ^n \sum_k^n \sum_l^n -C {... ...} + \sum_i ^n \sum_j ^n -C n {\bf M}_{ij} + \frac{C}{2} n^2$$ (2.17)

Preto¾e posledný èlen $\frac{C}{2} n^2$ nezmení polohu minima vy¹¹ie uvedenej funkcie $E_c$, zanedbáme ho a dostávame

$$T_{ij,kl}^c = -C, \qquad \Theta_{ij}=-C n.$$ (2.18)

Zo (2.10) vyplýva

$$E_d = \frac{D}{2} \sum_i ^n \sum_{k} ^n \sum_{y}^n d_{ki}{\... ... ^n \sum_{k} ^n \sum_{y}^n d_{ki}{\bf M}_{ky}{\bf M}_{i,y+1})$$ (2.19)

prièom platí, ¾e $d_{ik}=0$, ak $i=k$. Zavedením Croneckerovho symbolu $\delta_{lx}$ a nahradením indexu $y$ indexom $l$ vo výraze pre $E_d$ dostávame

$$E_d = \frac{D}{2} \sum_i ^n \sum_{x} ^n \sum_{k}^n \sum_{l}... ...k}^n \sum_{l}^n d_{ki} \delta_{lx}{\bf M}_{kl}{\bf M}_{i,x+1}$$ (2.20)

$E_d = 0$, ak $l \ne x$. Polo¾íme $j=x-1$ v prvej èasti výrazu a $j=x+1$ v druhej èasti a dostaneme

$$= \frac{D}{2} \sum_i ^n \sum_{j} ^n \sum_{k}^n \sum_{l}^n ... ...{\bf M}_{ij} + d_{ki} \delta_{l,j-1}{\bf M}_{kl}{\bf M}_{ij})$$ (2.21)

$$= -\frac{1}{2} \sum_i ^n \sum_{j} ^n \sum_{k}^n \sum_{l}^n... ...ta_{l,j+1} + d_{ki} \delta_{l,j-1}) {\bf M}_{kl} {\bf M}_{ij}$$ (2.22)

$$T_{ij,kl}^d = -D d_{ki} (\delta_{l,j+1} + \delta_{l,j-1})$$ (2.23)

Tak¾e nakoniec pre nastavenie váh prepojení v sieti medzi neurónmi $x_{ij}$ a $x_{kl}$ bude platiť

$$T_{ij,kl}=T_{ij,kl}^a+T_{ij,kl}^b+T_{ij,kl}^c+T_{ij,kl}^d$$ (2.24)

$$T_{ij,kl}^d = -A \delta_{ik}(1-\delta{jl}) -B \delta_{jl}(1-\delta_{ik}) -C-D d_{ki} (\delta_{l,j+1} \delta_{l,j-1})$$ (2.25)

Po odvodení vy¹¹ie uvedených vzťahov mo¾eme uviesť nasledujúci algoritmus:

ALGORITMUS pre TSP:

Krok 1. Priradenie váh prepojeniam $T_{ij,kl} = -A \delta_{ik} (1 - \delta_{jl}) -B \delta_{jl} (1 - \delta_{ik}) - C -D d_{ki}( \delta_{l,j+1} + \delta_{l,j-1})$ pre $1 \le i,j,k,l \le n$, - A,B,C,D sú zvolené parametre siete (sú meniteľné),

Krok 2. Inicializácia ${\bf M}_{ij}(0) = x_{ij}$, pre $1\le i,j \le n$, V tejto formule ${\bf M}_{ij}(t)$ je výstup vrcholu ,,ij'' v èase $t=0$ a $x_{ij}$ je náhodná premenná, ktorá nadobúda hodnotu 0 alebo 1.

Krok 3. Iterácia pokiaľ sieť neskovergovala ${\bf M}_{ij}(t+1) = g_h [\sum_{k=1}^n \sum_{i=1}^n T_{ij,kl}. {\bf M}_{kl}(t) ]$ pre $1\le i,j \le n$. Krok konèí, ak sieť skonvergovala, tj. jej stav sa u¾ nemení. Tu mô¾e dôjsť k zacykleniu siete.

Krok 4. Opakovanie od kroku 2. Ak do¹lo k zacykleniu siete, je potrebný nový výpoèet zaèínajúci nastavením nových poèiatoèných hodnôt siete. Tie¾ je mo¾né zmeniť parametre siete a nastaviť nové váhy, tj. zaèať krokom 1.

CIG Homepage(E-mail us!)