11.4. Hopfield típusú hálózatok alkalmazása optimalizációs problémákra

Kombinatorikai optimalizációs feladatok megoldása nem jelent mást, mint megkeresni az optimálist a számos lehetséges megoldás közül. Rengeteg ilyen feladatra visszavezethető gyakorlati probléma ismert a számítástechnika, a VLSI tervezés, a közlekedésirányítás, az üzleti élet és számos egyéb területről.

Az utóbbi egy-két évtizedben ezek a feladatok előtérbe kerültek, mivel sok korábban kezelhetetlennek tűnő probléma részben vagy teljesen megoldhatóvá vált. Ennek oka a technika fejlődésén kívül, a problémák nehézségének meghatározásában elért eredmények és az egyre hatékonyabb megoldási algoritmusok megjelenése. A legjelentősebb felismerés a 60-as évek végén született, annak a máig nem bizonyított, de nem is cáfolt hipotézisnek a felállításával, amely azt mondja ki, hogy létezik a problémák egy osztálya, amelyre az jellemző, hogy nem lehet konstruálni olyan algoritmust, ami a probléma méret hatványával arányos lépésszámmal biztosan képes a megoldást megtalálni. Ezek a problémák az NP-teljes problémák körébe tartoznak. Az optimalizáció témakörébe tartozó feladatok jelentős része ebbe a kategóriába sorolható.

Az NP-teljes problémák megoldásánál kétféle stratégiát lehet követni. Ragaszkodhatunk az optimális megoldás megtalálásához, és ilyenkor kockáztatjuk egy nagyon hosszú, sok esetben kivárhatatlan eljárás esélyét, vagy pedig egy viszonylag gyorsan megkapható megoldást választunk tudomásul véve, hogy esetleg az optimálisnál rosszabb minőségű megoldást találunk. Az első lehetőséghez tartoznak azok az optimalizációs eljárások, amelyek előzetes információk felhasználásával megállapított, hatékonynak ígérkező sorrendben megvizsgálják az összes lehetséges variációt. Ilyenek például a különböző kimerítő kereső eljárások. A másik csoportba sorolhatók a heurisztikát, véletlen elemeket használó módszerek. Ezek közös jellemzője, hogy valamilyen ismeret vagy elv szerint a lehetőségek egy részét figyelmen kívül hagyják. Ide tartoznak a különböző neurális hálózatokat alkalmazó módszerek is.

Először megmutatjuk, hogyan lehet neurális hálózatokat optimalizációs problémák megoldására használni, majd néhány jellegzetes feladat Hopfield hálózattal, illetve Boltzmann géppel történő megoldását vázoljuk fel.

Neurális hálózatokat egy optimalizációs probléma megoldására a következő két előfeltétel esetén tudunk használni:

  1. A lehetséges megoldások száma legyen véges.

  2. A megoldások minősége számszerűleg kifejezhető és bármely más megoldás minőségével összehasonlítható legyen.

A feltételeknek megfelelő optimalizációs problémákat formálisan egy (S, C) kettőssel lehet leírni, ahol a megoldási tér, S egy véges halmaz, amely tartalmazza az összes lehetséges megoldást, míg C a költségfüggvény vagy kritériumfüggvény egy leképzés:

C:  SRMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qaiaacQdacaqGGaGaaeiiaiaadofacqGHsgIRcaWGsbaaaa@3BD1@ , (11.31)

Tehát C minden megoldáshoz egy valós értéket, egy költséget rendel. Ezek után a feladat egy optimális ioptSMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyAamaaBaaaleaacaqGVbGaaeiCaiaabshaaeqaaOGaeyicI4Saam4uaaaa@3BC5@ megoldásnak a megkeresése, amelyre a minimalizációs probléma esetén igaz, hogy:

C(iopt)C(i),            iS-reMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qaiaabIcacaWGPbWaaSbaaSqaaiaab+gacaqGWbGaaeiDaaqabaGccaqGPaGaeyizImQaam4qaiaabIcacaWGPbGaaeykaiaabYcacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacqGHaiIicaWGPbGaeyicI4Saam4uaiaab2cacaqGYbGaaeyzaaaa@4F44@ (11.32)

(Maximalizációs probléma esetén az egyenlőtlenség természetesen fordítva áll.)

Például, a talán legismertebb, bár közvetlen gyakorlati jelentőséggel nem bíró, de tipikus optimalizációs feladat, az utazó ügynök probléma (Traveling Salesman Problem, TSP) a következőképpen írható le. A problémában egy ügynöknek adott városokat kell végiglátogatnia úgy, hogy minden városban csak egyszer járjon és a lehető legrövidebb utat megtéve érkezzen vissza a kiindulási pontba.

Legyen adott az n város közti távolságokat leíró n×n-es [dpq]MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaae4waiaadsgadaWgaaWcbaGaamiCaiaadghaaeqaaOGaaeyxaaaa@3A31@ mátrix. Egy, az ügynök által bejárandó, lehetséges útvonalat jelöljön a P=(P(1),...,P(n)) ciklikus permutáció, ahol P(k) jelenti azt a várost, amelyik a k-adik után következik az úton (P(k)≠k).

Így a lehetséges megoldások: S ={az n város összes P ciklikus permutációja}

11.7. ábra - Egy jó és egy rossz megoldás az utazó ügynök problémára
Egy jó és egy rossz megoldás az utazó ügynök problémára

A megoldási tér mérete: |S|=(n-1)!, és ismert, hogy ez is egy NP-teljes probléma. A feladathoz tartozó költségfüggvény, azaz az út hossza:

C(P)=p=1ndp,P(p)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qaiaabIcacaWGqbGaaeykaiabg2da9maaqahabaGaamizamaaBaaaleaacaWGWbGaaeilaiaadcfacaqGOaGaamiCaiaabMcaaeqaaaqaaiaadchacqGH9aqpcaaIXaaabaGaamOBaaqdcqGHris5aaaa@451D@ (11.33)

Optimalizációs feladatok neurális hálózattal történő megoldásához a problémát le kell képeznünk a neurális struktúrára. Ennek lényege, hogy a hálózat minden konfigurációjához hozzárendelünk egy megoldást. Ha egy Boltzmann gép formális leírását egy B(x,W) kettőssel határozzuk meg, ahol x a neuronok állapotvektora és W a súlymátrix, akkor a probléma leképzését jelölhetjük az mxSMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyBaiaabQdacaqGGaGaaCiEaiabgkziUkaadofaaaa@3B81@ függvénnyel.

Ezek alapján az optimalizációs problémák implementációjának stratégiája a következő 3 lépésben foglalható össze.

  1. Alakítsuk át az optimalizációs feladatot 0-1 programozási feladattá. Ehhez az eredeti diszkrét változók helyett megfelelő számú új bináris változót kell bevezetni.

  2. Definiáljunk egy Boltzmann gépet úgy, hogy minden egyes neuron a probléma egy változójának feleljen meg.

  3. Határozzuk meg a hálózat súlyait úgy, hogy a hálózathoz tartozó energiafüggvényre igaz legyen a következő két feltétel:

I. Az energiafüggvény minimumpontjaihoz tartozó konfigurációknak a probléma változóinak olyan értékei feleljenek meg, amelyekhez optimális megoldások tartoznak (a költségfüggvény minimumpontjai)

m(x(Emin))=SoptMathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaad2gacaGGOaGaaCiEamaaBaaaleaacaGGOaGaamyramaaBaaameaaciGGTbGaaiyAaiaac6gaaeqaaSGaaiykaaqabaGccaGGPaGaeyypa0Jaam4uamaaBaaaleaacaWGVbGaamiCaiaadshaaeqaaaaa@4385@ (11.34)

II. Az energiafüggvény és a költségfüggvény legyen nagyságrendtartó:

C(m(x1)) C(m(x2))E(x1E(x2)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qaiaabIcacaWGTbGaaeikaiaadIhadaWgaaWcbaGaaGymaaqabaGccaqGPaGaaeykaiaabccacqGHPms4caWGdbGaaeikaiaad2gacaqGOaGaamiEamaaBaaaleaacaaIYaaabeaakiaabMcacaqGPaGaamiiaiabgkDiElaadccacaWGfbGaaeikaiaadIhadaWgaaWcbaGaaGymaaqabaGccaqGPaGaaeiiaiabgMYiHlaadweacaqGOaGaamiEamaaBaaaleaacaaIYaaabeaakiaabMcaaaa@5294@ (11.35)

Ha az előzőekben leírtak szerint hozunk létre egy Boltzmann gépet optimalizációs probléma megoldására, akkor a hálózat egy véletlen kiindulási konfigurációból elindítva olyan állapotban stabilizálódik, amely a probléma egy jó megoldását adja. Az utolsó pontban szereplő feltételek biztosítják, hogy ha a hálózat globális minimumpontban stabilizálódik, akkor optimális megoldást kapunk, de ha egy alacsony energiájú lokális minimum lesz a stabil állapot, akkor is jó minőségű, alacsony költségű megoldáshoz jutunk.

11.4.1. Az utazó ügynök probléma

A már bemutatott utazó ügynök problémát a fentiek alapján könnyen lehet Boltzmann típusú neurális hálózatra implementálni. Először új bináris változókat vezetünk be a probléma leírására:

uip={1      ha az út során az i-edik város a p-edik lépésben   kerül meglátogatásra0     egyébkéntMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyDamaaBaaaleaacaWGPbGaamiCaaqabaGccqGH9aqpdaGabaqaauaabaqaceaaaeaacaqGXaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiAaiaabggacaqGGaGaaeyyaiaabQhacaqGGaGaaeO+aiaabshacaqGGaGaae4Caiaab+gacaqGYbGaaey4aiaab6gacaqGGaGaaeyyaiaabQhacaqGGaGaamyAaiaab2cacaqGLbGaaeizaiaabMgacaqGRbGaaeiiaiaabAhacaqGHdGaaeOCaiaab+gacaqGZbGaaeiiaiaabggacaqGGaGaamiCaiaab2cacaqGLbGaaeizaiaabMgacaqGRbGaaeiiaiaabYgacaqGPdGaaeiCaiaabMoacaqGZbGaaeOyaiaabwgacaqGUbGaaeiiaiaabccacaqGGaGaae4AaiaabwgacaqGYbGaaei=aiaabYgacaqGGaGaaeyBaiaabwgacaqGNbGaaeiBaiaabgoacaqG0bGaae4BaiaabEgacaqGHbGaaeiDaiaabgoacaqGZbGaaeOCaiaabggaaeaacaaIWaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGLbGaae4zaiaabMhacaqGPdGaaeOyaiaabUgacaqGPdGaaeOBaiaabshaaaaacaGL7baaaaa@8E46@

A bevezetett változókkal a feladat költségfüggvénye, az út hossza így írható le:

C(P)=i,j,p,q=0n1aijpquipujqMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaabmaabaGaamiuaaGaayjkaiaawMcaaiabg2da9maaqahabaGaamyyamaaBaaaleaacaWGPbGaamOAaiaadchacaWGXbaabeaakiaadwhadaWgaaWcbaGaamyAaiaadchaaeqaaOGaamyDamaaBaaaleaacaWGQbGaamyCaaqabaaabaGaamyAaiaacYcacaWGQbGaaiilaiaadchacaGGSaGaamyCaiabg2da9iaaicdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aaaa@5101@ , (11.36)

ahol az aijpqMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyaSWaaSbaaeaacaWGPbGaamOAaiaadchacaWGXbaabeaaaaa@3A43@ együtthatókat a távolságok alapján a következőképpen definiáljuk:

aijpq={dij       ha   q=(p+1)mod n0         egyébkéntMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyyamaaBaaaleaacaWGPbGaamOAaiaadchacaWGXbaabeaakiabg2da9maaceaabaqbaeaabiqaaaqaaiaadsgadaWgaaWcbaGaamyAaiaadQgaaeqaaOGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabIgacaqGHbGaaeiiaiaabccacaqGGaGaamyCaiaab2dacaqGOaGaamiCaiaabUcacaaIXaGaaeykaiaab2gacaqGVbGaaeizaiaabccacaWGUbaabaGaaGimaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabwgacaqGNbGaaeyEaiaabMoacaqGIbGaae4AaiaabMoacaqGUbGaaeiDaaaaaiaawUhaaaaa@6142@ (11.37)

A költségfüggvény minimalizálásán kívül ügyelni kell, hogy a megoldás valódi utat írjon le, ezért be kell tartani a következő két kényszert:

p-re   i=0n1uip=1   (egy időpontban csak egy városban lehet az ügynök),i-re    p=0n1uip=1  (minden várost pontosan egyszer látogasson meg az ügynök).MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacqGHaiIicaWGWbGaaeylaiaabkhacaqGLbGaaeiiaiaabccacaqGGaWaaabCaeaacaWG1bWaaSbaaSqaaiaadMgacaWGWbaabeaakiabg2da9iaabgdaaSqaaiaadMgacaqG9aGaaeimaaqaaiaad6gacqGHsislcaaIXaaaniabggHiLdGccaqGGaGaaeiiaiaabccacaqGOaGaaeyzaiaabEgacaqG5bGaaeiiaiaabMgacaqGKbGaaeyubiaabchacaqGVbGaaeOBaiaabshacaqGIbGaaeyyaiaab6gacaqGGaGaae4yaiaabohacaqGHbGaae4AaiaabccacaqGLbGaae4zaiaabMhacaqGGaGaaeODaiaabgoacaqGYbGaae4BaiaabohacaqGIbGaaeyyaiaab6gacaqGGaGaaeiBaiaabwgacaqGObGaaeyzaiaabshacaqGGaGaaeyyaiaabQhacaqGGaGaaei=aiaabEgacaqG5bGaaeOBaiaabApacaqGRbGaaeykaiaabYcaaeaacqGHaiIicaWGPbGaaeylaiaabkhacaqGLbGaaeiiaiaabccacaqGGaGaaeiiamaaqahabaGaamyDamaaBaaaleaacaWGPbGaamiCaaqabaGccqGH9aqpcaqGXaaaleaacaWGWbGaaeypaiaabcdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aOGaaeiiaiaabccacaqGOaGaaeyBaiaabMgacaqGUbGaaeizaiaabwgacaqGUbGaaeiiaiaabAhacaqGHdGaaeOCaiaab+gacaqGZbGaaeiDaiaabccacaqGWbGaae4Baiaab6gacaqG0bGaae4BaiaabohacaqGHbGaaeOBaiaabccacaqGLbGaae4zaiaabMhacaqGZbGaaeOEaiaabwgacaqGYbGaaeiiaiaabYgacaqGHdGaaeiDaiaab+gacaqGNbGaaeyyaiaabohacaqGZbGaae4Baiaab6gacaqGGaGaaeyBaiaabwgacaqGNbGaaeiiaiaabggacaqG6bGaaeiiaiaabYpacaqGNbGaaeyEaiaab6gacaqG2dGaae4AaiaabMcacaqGUaaaaaa@C1A5@ (11.38)

A problémában szereplő minden bináris uip változónak a hálózat egy xip neuronja fog megfelelni, így a hálózat n2 neuront fog tartalmazni. A Hopfield modellről szóló fejezetben leírtak alapján a hálózat súlyait az energiafüggvény megadásával definiáljuk. Az utazó ügynök probléma megoldásához definiált függvény három tagból áll, melyekből az első a költségfüggvény minimalizálásáért felelős, a másik kettő pedig a problémában szereplő két kényszert realizálja:

E=i,j,p,q=0n1aijpqxipxjq+c[i=0n1(1p=0n1xip)2+p=0n1(1i=0n1xip)2]MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyraiabg2da9maaqahabaGaamyyamaaBaaaleaacaWGPbGaamOAaiaadchacaWGXbaabeaakiaadIhadaWgaaWcbaGaamyAaiaadchaaeqaaOGaamiEamaaBaaaleaacaWGQbGaamyCaaqabaGccqGHRaWkcaWGJbWaamWaaeaadaaeWbqaamaabmaabaGaaGymaiabgkHiTmaaqahabaGaamiEamaaBaaaleaacaWGPbGaamiCaaqabaaabaGaamiCaiabg2da9iaaicdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aaGccaGLOaGaayzkaaWaa0baaSqaaaqaaiaaikdaaaGccqGHRaWkdaaeWbqaamaabmaabaGaaGymaiabgkHiTmaaqahabaGaamiEamaaBaaaleaacaWGPbGaamiCaaqabaaabaGaamyAaiabg2da9iaaicdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aaGccaGLOaGaayzkaaWaa0baaSqaaaqaaiaaikdaaaaabaGaamiCaiabg2da9iaaicdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aaWcbaGaamyAaiabg2da9iaaicdaaeaacaWGUbGaeyOeI0IaaGymaaqdcqGHris5aaGccaGLBbGaayzxaaaaleaacaWGPbGaaiilaiaadQgacaGGSaGaamiCaiaacYcacaWGXbGaeyypa0JaaGimaaqaaiaad6gacqGHsislcaaIXaaaniabggHiLdaaaa@7FEB@ (11.39)

A hálózat súlyait az energiafüggvény tagjainak kiszorzása után közvetlenül megkapjuk, mivel nem szerepel benne xipnégyzeténél magasabb hatványfokú tag. Könnyű belátni, hogy a függvény minimumpontjai ott vannak, ahol az út minimális és a megoldás megfelel mind a két kényszernek, ezenkívül teljesíti a függvénnyel kapcsolatban korábban leírt feltételeket.

Az eredmények azt mutatják, hogy az utolsó két tagot súlyozó c paramétert helyesen megválasztva igen jó megoldást talál a hálózat a problémára. Hozzá kell tenni azonban, hogy a tapasztalatok szerint a megoldás minősége jelentősen függ c értékétől.

11.8. ábra - Egy 4 várost tartalmazó utazó ügynök probléma.
Egy 4 várost tartalmazó utazó ügynök probléma.

Az ábrán látható 16 neuronból a 4 aktív (fekete) processzáló elem egy lehetséges megoldást mutat. Az ábrán jelöltük még az n22 neuron súlyozott összeköttetéseit (a szaggatott vonalak a c súlyú kapcsolatokat jelölik).

A módszert hagyományos kombinatorikai algoritmusokkal összehasonlítva, a talált út hosszát vizsgálva a neurális hálózat a hagyományos algoritmusok megoldásainál valamivel gyengébb eredményt ad. Ennek alapvető oka, hogy a hálózat a véletlenszerű állapotból kiindulva részben olyan állapotokon keresztül jut el a stabil állapotig, amelyek nem valódi utaknak felelnek meg, míg a hagyományos eljárások közül a legjobbak csak ilyet vesznek figyelembe. Így a hálózat számára a problématér, melyben az optimális megoldást keresi, lényegesen nagyobb. Ennek a gondnak a kiküszöbölésére javasolták a hálózat struktúrájának olyan módosítását, hogy a neuronokat csoportba szervezve ún. "k-ból 1 neuron"-okat alakítottak ki, ahol garantált, hogy a hálózat minden neuron csoportjában mindig pontosan egy aktív van. Ilyenkor az energiafüggvény első tagjának módosítása után az utolsó két tag elhagyható. Ezzel a módszerrel a Boltzmann gépek mind minőség, mind sebesség tekintetében lényegesen jobb eredményeket értek el.

11.4.2. Rádiófrekvenciák kiosztása neurális hálózattal

Hasonló problémára vezet a haditechnikában és a polgári távközlésben is felmerülő feladat, a nagyszámú rádiókapcsolatok létesítésének feladata. Igen bonyolult probléma több száz, esetleg néhány ezer rádiókapcsolathoz frekvenciát rendelni úgy, hogy azok ne zavarják egymást. A gyakorlatban a frekvencia értékeket a használt eszközöktől függő véges halmazból kell választani, és ki kell elégíteni a rádiókapcsolatok földrajzi elhelyezkedésétől függő kényszereket. Az alapproblémában a kapcsolatokhoz l1,...,ln frekvencia értékeket rendelünk az f1,...,fp lehetséges értékek közül. A kapcsolatokhoz rendelt frekvenciaértékekre a kényszerek a következő alakban írhatók fel:

|lilj|dijMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaqWaaeaacaWGSbWaaSbaaSqaaiaadMgaaeqaaOGaeyOeI0IaamiBamaaBaaaleaacaWGQbaabeaaaOGaay5bSlaawIa7aiabgwMiZkaadsgadaWgaaWcbaGaamyAaiaadQgaaeqaaaaa@425B@ (11.40)

Minden lehetséges (li,fk) kettőshöz rendeljünk hozzá egy bináris vik változót:

vik=1ha li=fkvik=0ha lifkMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWG2bWaaSbaaSqaaiaadMgacaWGRbaabeaakiabg2da9iaaigdacaaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caqGObGaaeyyaiaabccacaWGSbWaaSbaaSqaaiaadMgaaeqaaOGaeyypa0JaamOzamaaBaaaleaacaWGRbaabeaaaOqaaiaadAhadaWgaaWcbaGaamyAaiaadUgaaeqaaOGaeyypa0JaaGimaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaabIgacaqGHbGaaeiiaiaadYgadaWgaaWcbaGaamyAaaqabaGccqGHGjsUcaWGMbWaaSbaaSqaaiaadUgaaeqaaaaaaa@61CE@ (11.41)

A vik változóknak feleltessük meg a neurális hálózat xik neuronjait, majd a neuronok közti kapcsolatok súlyait kell meghatározni. Itt is az energiafüggvény meghatározásával jutunk eredményre. A probléma költségfüggvénye legyen a ki nem elégített feltételek száma. Az ezt reprezentáló energiafüggvény tag a következő alakú:

E1=i,p,j,q(1wipjq)xipxjqMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyramaaBaaaleaacaaIXaaabeaakiabg2da9maaqafabaWaaeWaaeaacaaIXaGaeyOeI0Iaam4DamaaBaaaleaacaWGPbGaamiCaiaadQgacaWGXbaabeaaaOGaayjkaiaawMcaaiaadIhadaWgaaWcbaGaamyAaiaadchaaeqaaOGaamiEamaaBaaaleaacaWGQbGaamyCaaqabaaabaGaamyAaiaacYcacaWGWbGaaiilaiaadQgacaGGSaGaamyCaaqab0GaeyyeIuoaaaa@4E69@ , (11.42)

ahol

wipjq=1ha |fpfq|<dijwipjq=0egyébkéntMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWG3bWaaSbaaSqaaiaadMgacaWGWbGaamOAaiaadghaaeqaaOGaeyypa0JaaGymaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caqGObGaaeyyaiaabccadaabdaqaaiaadAgadaWgaaWcbaGaamiCaaqabaGccqGHsislcaWGMbWaaSbaaSqaaiaadghaaeqaaaGccaGLhWUaayjcSdGaeyipaWJaamizamaaBaaaleaacaWGPbGaamOAaaqabaaakeaacaWG3bWaaSbaaSqaaiaadMgacaWGWbGaamOAaiaadghaaeqaaOGaeyypa0JaaGimaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caqGLbGaae4zaiaabMhacaqGPdGaaeOyaiaabUgacaqGPdGaaeOBaiaabshaaaaa@83AE@ (11.43)

Az energiafüggvényt, az utazó ügynök problémával bemutatottakhoz hasonlóan, ki kell még egészíteni egy taggal, amely minimumpontjában azt garantálja, hogy egy rádiókapcsolathoz pontosan egy frekvenciát rendelünk, illetve itt is alkalmazható a neuronok csoportba rendezésével (k-ból 1 neuronok) az utóbbi feltételt automatikusan teljesítő módszer.

11.4.3. A/D konverter megvalósítása Hopfield hálózattal

A/D konverterek érdekes megvalósítását mutatta be az alkalmazott hálózat névadója, John Hopfield. Mivel az eddigiekben csak kétértékű neuronokkal foglalkoztunk ezért itt a szerző által leírt folytonos értékű neuronokat alkalmazó A/D konverter megoldás digitális neurális hálózattal megvalósított változatát mutatjuk be [Hop86]. A hálózat modell itt kiegészül egy analóg bemenettel (a digitalizálandó jel − u), amelyet − hasonlóan a többi neuron kimenetének visszacsatolásához − súlyozott kapcsolatokon keresztül vezetünk a neuronok bemenetére. Az A/D átalakító költségfüggvénye legyen az átalakítás hibájának a négyzete, és a neuronok bináris kimenetei a digitalizált jel bitjei.

Így a hálózat energiafüggvénye:

E=(uixi2i)2MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyraiabg2da9maabmaabaGaamyDaiabgkHiTmaaqafabaGaamiEamaaBaaaleaacaWGPbaabeaakiaaikdadaqhaaWcbaaabaGaamyAaaaaaeaacaWGPbaabeqdcqGHris5aaGccaGLOaGaayzkaaWaa0baaSqaaaqaaiaaikdaaaaaaa@429A@ (11.44)

Ebből a hálózat súlyaira a következőket kapjuk:

wij=2i+jMathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadEhadaWgaaWcbaGaamyAaiaadQgaaeqaaOGaeyypa0JaaGOmamaaCaaaleqabaGaamyAaiabgUcaRiaadQgaaaaaaa@3DA7@(11.45)

Az analóg bemenetet súlyozó tagokra:

ti=2iMathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadshadaWgaaWcbaGaamyAaaqabaGccqGH9aqpcqGHsislcaaIYaWaaWbaaSqabeaacaWGPbaaaaaa@3BD1@(11.46)

Egy 4-bites A/D konverter látható a 11.9 ábrán. Bár a megoldás nem hódított teret más A/D megvalósítások mellett, jól mutatja, hogy a feladatok milyen széles köre értelmezhető optimalizációs problémaként és oldható meg Hopfield típusú hálózattal.

11.9. ábra - 4 bites A/D konverter megvalósítása Hopfield hálózattal
4 bites A/D konverter megvalósítása Hopfield hálózattal

Feladatok

11.1 Tervezzen Hopfield neurális hálózatot, amely megoldja az N-királynő problémát. A logikai feladvány lényege, hogy egy N×N-es sakktáblán kell elhelyezni N királynőt úgy, hogy egyik se álljon másik által ütésben. Bizonyított, hogy minden N>3 esetre létezik megoldás. Határozza meg egy N2MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqi=G0dg9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOtamaaCaaaleqabaGaaGOmaaaaaaa@3725@ neuront tartalmazó hálózat súlyait úgy, hogy a hálózat minden neuronja a sakktábla egy-egy mezőjének felel meg és egy neuron a hálózat stabil állapotában akkor vesz fel aktív értéket, ha rajta egy királynő található.

11.2 Adja meg annak a Hopfield neurális hálózatnak az energiafüggvényét, amely képes megoldani a következő gráf partícionálási problémát. Válasszunk szét egy gráfot két egyenlő méretű részgráfra úgy, hogy a köztük található élek száma minimális legyen. A hálózat neuronjai reprezentálják a gráf csomópontjait úgy, hogy az energiafüggvény által meghatározott súlyokkal rendelkező hálózat stabil állapotában a neuronok aktív értéke jelölje az egyik, míg az inaktív érték a másik részgráfhoz való tartozást.

11.3 Mutassa meg, hogy az aszinkron Hopfield hálózatnak új hamis stabil állapotai jöhetnek létre, ha az önvisszacsatoló súlyok értékét növeljük.

11.4 Mutassa meg, hogy a szimmetrikus súlyokkal rendelkező szinkron Hopfield hálózatnál lehetséges, hogy két állapotváltozás után ugyanabba az állapotba kerül a hálózat (2 hosszúságú határciklus).