Az utazó ügynök probléma és megoldása genetikus algoritmussal

Készítette: Tersztenyák László
Témavezető: Fábián Csaba

Eötvös Loránd Tudományegyetem Természettudományi Kar

Budapest, 1996.

Tartalom

1. Bevezetés 3

2. Az utazó ügynök probléma 4

2.1 A problémáról . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Történet . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Megfogalmazás . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Megközelítési módok . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Feszítőfa-heurisztika . . . . . . . . . . . . . . . . . . . 6 2.2.2 Heurisztikus túraépítő módszerek . . . . . . . . . . . . 6 2.2.3 Túrajavító módszerek . . . . . . . . . . . . . . . . . . 7 2.2.4 Kombinált eljárások . . . . . . . . . . . . . . . . . . . 8 2.2.5 Lokális keresési eljárások . . . . . . . . . . . . . . . . . 9

2.3 A Lin-Kerninghan heurisztika . . . . . . . . . . . . . . . . . . 10 2.3.1 A módosított Lin-Kerninghan módszer . . . . . . . . . 11

3. A genetikus algoritmusokról 13 3.1 Evolúciós program . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Genetikus algoritmusok . . . . . . . . . . . . . . . . . . . . . . 14

3.2.1 Hogyan működnek? . . . . . . . . . . . . . . . . . . . . 14 3.2.2 Miért működnek? . . . . . . . . . . . . . . . . . . . . . 18

4. Az utazó ügynök probléma és a genetikus algoritmusok 21 4.1 A problémához illeszkedő kódolások . . . . . . . . . . . . . . . 21 4.2 Speciális keresztezési eljárások . . . . . . . . . . . . . . . . . . 23 4.3 Speciális mutációs eljárások . . . . . . . . . . . . . . . . . . . 27 4.4 Más megközelítés . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.5 Zárás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1. Fejezet

Bevezetés

A dolgozat az utazó ügynök problémának ismertetésére, és a megoldására kifejlesztett kombinatorikai jellegű algoritmusok bemutatására törekszik. Kitérünk az evolúciós elveket – kiválasztódás, keresztezés, mutáció – alkalmazó, napjainkban egyre inkább előtérbe kerülő módszerekre is.

A módszerek egy része kifejezetten az utazó ügynök probléma megoldására alkalmas, de többségük tartalmaz olyan elemeket is, amelyek más kombinatorikai problémák megoldásában is használhatóak. Különösen igaz ez az evolúciós alapú módszerekre, hiszen napjainkban a számítógép ideje sokkal olcsóbb, mint az ember ideje, így egyre nagyobb szerepük van az olyan eljárásoknak, melyeknél nagyobb emberi munka befektetés nélkül – valamilyen önmagát alakító rendszer segítségével – lehet jó eredményt elérni.

Az utazó ügynök probléma

2.1 A problémáról

Az utazó ügynök probléma (traveling salesman problem - TSP) talán a legismertebb NP-beli^{1} probléma.

2.1.1 Történet

Már Euler egy 1759-es munkájában előkerült (igaz nem ezen a néven); őt az érdekelte, bejárható-e sakktábla 64 mezője egy huszárral, úgy hogy mindegyiket csak egyszer érintjük és visszaérünk a kiindulási mezőre.

Az utazó ügynök elnevezés egy 1932-es német könyvből (The traveling salesman, how and what he should do to get commissions and be successful) származik. Bár nem a könyv fő témája, az utolsó fejezet tárgyalja a TSP-t és ütemezési problémákat is.

Közismertté a TSP 1948-ban vált a RAND Corporation által, majd a kombinatorikus optimalizálás – a gyakorlati igények miatti – előretörésével együtt egyre népszerűbb lett. Ebben nagy szerepe volt annak, hogy a gazdaságban is felmerül problémaként – például hirközlési hálózat kiépítésekor.

2.1.2 Megfogalmazás

A probléma egyszerűen megfogalmazható: adottak városok és köztük utak. Egy ügynöknek be kell járnia az összes várost, úgy hogy közben mindegyiket csak egyszer érinti és visszatér a kiindulási helyre. A városok közti utak különböző ideig tartanak és a cél az, hogy az út összideje a lehető legkisebb legyen.

1Olyan problémák tartoznak ide, melyekre jelenleg nem ismert polinom idejű megoldás, azaz olyan algoritmus, melynek lépésszáma a probléma méretének polinomja

A matematika nyelvén: adott egy G(V, E) irányított gráf és egy c : E ↦ R^{+} költségfüggvény. Keressünk a gráfban olyan Hamilton kört, melynek a c szerinti költsége a minimális. Azaz olyan H ⊂ E élhalmazt, melyre

ki_{H}(v)  =  1 (v ∈ V),  (2.1)
be_{H}(v)  =  1 (v ∈ V),  (2.2)
|H|  =  n,  (2.3)
∑_{e∈H} c(e) minimális,  (2.4)

ahol be_{H}(v) jelenti a v csúcsba a H részgráfban bemenő élek számát (és ki_{H}(v)) ugyanezt a kimenő élekre, n = |V |.

Szokásos egy másik megfogalmazás is: a Hamilton kör tulajdonképpen azt jelenti, hogy a gráf minden csúcsához hozzárendelünk egy másikat – nevezetesen azt, amelyikbe innét megy él a körben –, vagyis egy ϕ : {1, 2, …, n} ↦ {1, 2, …, n} egy-egy értelmű hozzárendelést, azaz egy permutációt adunk meg. A permutációt pedig leírhatjuk egy mátrixszal is melyre x_{ij} = 1, ha ϕ(i) = j, különben 0. Így megfogalmazva a feladat a következő: Keressük azt az X n × n mátrixot, melyre

∑_{i∈V} x_{ij} = 1 j ∈ V,  (2.5)
∑_{j∈V} x_{ij} = 1 i ∈ V,  (2.6)
x_{ij} ∈ {0, 1},  (2.7)
x túra^{2}  (2.8)

és

∑_{i∈V} ∑_{j∈V} x_{ij}c_{ij} minimális.  (2.9)

(Ha (i, j) ∈ E c_{ij} jelöli az (i, j) él költségét, (i, j) ∉ E esetén c_{ij} = ∞)

(2.8) helyettesíthető a következő egyenletekkel

∑_{i∈S} ∑_{j∈S} x_{ij} ≤ |S| − 1,  S ⊂ V, 1 < |S| < n.  (2.10)

2.2 Megközelítési módok

Az optimum felkutatásának egyik módja lehetne, hogy megkeressük az összes Hamilton kört az gráfban, és kiválasztjuk közülük a legkisebb költségűt. Mivel így a permutációkat nézzük végig, O(n!) kört kell megvizsgálnunk, ami már néhány tíz csúcs esetén is reménytelen feladat, a gyakorlatban pedig ennél sokkal nagyobb feladatok is előfordulnak.

Az előző részben láttuk, hogy a TSP megfogalmazható egy egészértékű programozási feladatként is, így az ott alkalmazott módszerekkel (relaxáció, branch-and-bound) megoldható. Persze itt is gondot jelent a nagy lépésszám, ezért a TSP szerkezetét kihasználó módszerek fejlődtek ki.

A gyakorlati alkalmazasok miatt – itt általában elég egy gyorsan megkapott nem túl rossz megoldás – előtérbe kerültek azok a módszerek, amelyek rövidebb idő alatt adnak közel optimális megoldást.

2.2.1 Feszítőfa-heurisztika

Legyen G′ = (V, E′) minimális költségű feszítőfa a G gráfban. Jelölje Q a G′ éleinek duplázásával adódó kört. Készítsük ebből a T túrát az ismétlődő csúcsok törlésével.

2.1. Tétel Ha a költségek nemnegatívak és teljesül rájuk a háromszög egyenlőtlenség, akkor a feszítőfa-heurisztikával kapott túra költsége nem nagyobb, mint az optimális költség kétszerese.

Bizonyítás. Legyen T^{∗} az optimális túra! Ekkor

∑_{e∈E(T)} c_{e} ≤ ∑_{e∈E(Q)} c_{e} = 2 ∑_{e∈E′} c_{e} ≤ ∑_{e∈E(T^{∗})} c_{e},

ahol az első egyenlőtlenség a háromszög-egyenlőtlenségből, a második a költségek nemnegativitásából következik, hiszen a túrából elhagyva egy élet feszítőfát kapunk.

2.2.2 Heurisztikus túraépítő módszerek

Ezeknél a módszereknél általában egy tetszőlegesen választott csúcsból indulunk és valamilyen egyszerű módszer szerint döntjük el, hogy melyik csúcsot vesszük hozzá a túrához következőnek.

• Nearest neighbor (legközelebbi szomszéd) ^{3} A túrát az utolsó csúcshoz legközelebbi, még nem érintett csúccsal bővítjük. Ha a gráf teljes, így is biztosan kapunk túrát, de az nagyon rossz is lehet.

3A nem kialakult magyar szóhasználat miatt az elfogadott angol elnevezést használom

• Greedy feasible (mohó)

Legyen E_{0} = ∅. Legyen E_{t}(t < n − 1) a kiválasztott élhalmaz a t. lépésben, úgy hogy (V, E_{t})

1. körmentes

2. minden csúcs foka legfeljebb kettő.

Ekkor adjuk hozzá azt a e ∈ E \ E_{t} élet, melynek a költsége minimális és (V, E_{t} ∪ {e})-re teljesül 1 és 2. Végül (V, E_{n−1})-et (ha lehetséges) a két elsőfokú csúcs összekötésével tegyük túrává.

A kapott megoldás itt is nagyon rossz is lehet.

Másik csoportba tartoznak azok a módszerek, amikor kiindulunk egy egyszerű (egy vagy két csúcsból álló) túrából és sorban hozzávéve alakítjuk ki a túrát.

• nearest insertion (legközelebbi csúcs hozzávétele)

Kiindulásnak valasszuk a két egymáshoz legközelebbi csúcsból álló kört. Az algoritmus minden lépésében válasszuk azt a csúcsot, amelyik az eddig kiválasztott csúcsoktól a legkisebb távolságra van, illesszük be oda, ahol a legkevésbé növeli az összhosszt.

• farest insertion (legtávolabbi csúcs hozzávétele)

Kiindulásul a két legtávolabbi csúcsot válasszuk, és mindig azt a csúcsot illesszük be a legkevésbé növelő helyre, amelyik a már kiválasztott csúcsoktól a legtávolabb van.

Sajnos ezekben az esetekben sem tudjuk biztosítani, hogy a kapott túra jó lesz.

2.2.3 Túrajavító módszerek

Léteznek olyan technikák, melyek segítségével egy már meglévő túrát javíthatunk, esetleg egészen egy lokális optimumig. Mivel nem lehet semmit mondani egy lokális optimumnak a globális optimumhoz való viszonyáról, nem tudunk semmit garantálni abban az esetben sem, ha egy túra már nem javítható tovább a leírt eljárásokkal. Azonban a gyakorlatban a kapott lokális optimum nincs túl messze a valódi optimumtól, tehát elfogadható kompromisszum.

• r-optimalizálás (r-opt)

A jelenlegi megoldás r élét kicseréljük r a másik élre, úgy hogy a kapott részgráf is túra legyen, és az összhossza kisebb legyen, mint a kiindulási hossz.

Mivel a megvizsgálandó cserelehetőségek száma r-rel exponenciálisan nő, a gyakorlatban csak r = 2 és r = 3 használatos.

• Or-optimalizálás A 3-opt eljárás módosítása [8], melyben a 3-opt esetén felmerülő cserelehetőségek jelentős részét eleve kizárjuk. Az olyan cserékre korlátozzuk a javítás vizsgálatát, amikor egy, kettő vagy három jelenleg szomszédos csúcsot illesztünk be két másik csúcs közé a túrában.

• Lin-Kerninghan optimalizálás Tulajdonképpen egy r-opt eljárás változó r mellett. Az alapgondolata a következő: A jelenlegi túrában van k rossz él, ezeket kell kicserélni. Mivel nem tudjuk, mekkora k értéke, megprobáljuk a rossz éleket egyenként azonosítani és kicserélni. Akkor hagyjuk abba az eljárást, ha úgy tűnik, hogy nem lesz több javulás. Részletesebb leírás talalható az eljárásról a 2.3 részben.

2.2.4 Kombinált eljárások

A gyakorlatban az előzőekben leírt – vagy hozzájuk hasonló, de nem említett – elemekből összeállított kombinált eljárások mutatkoztak megfelelőnek.

A tipikus heurisztikus eljárások a következőképpen épülnek fel:

1. lépés Valamilyen módon meghatározunk egy kiinduló résztúrát.

2. lépés További csúcsokat választunk hozzávételre és beillesztjük őket.

3. lépés Ha még van olyan csúcs, amelyet nem érintettünk, visszatérünk a 2. lépéshez.

4. lépés A kapott túrára alkalmazunk egy – esetleg több – túrajavító eljárást.

2.2.5 Lokális keresési eljárások

Igazából ezek nem különülnek el az előzőekben ismertetett módszerektől, hanem arról van szó, hogy az eljárásokat más módon használjuk fel.

Általánosan megfogalmazva az optimalizálás lényege az, hogy adott egy X tér, egy f : X ↦ R függvény, és keressük azt az x^{∗} ∈ X elemet, melyre

f(x^{∗}) ≤ f(x) ∀x ∈ X.

Szerkezetében a legegyszerűbb az olyan optimalizálás, amikor kiindulunk valamely x_{0} ∈ X pontból, és olyan x_{1}, …, x_{n} ∈ X pontokat határozunk meg, hogy

f(x_{i}) < f(x_{i−1}) ∀i = 1, …, n.

Az eljárást akkor hagyjuk abba, amikor már nem tudunk jobb pontot meghatározni. Ebben az esetben eljutottunk egy lokális optimumhoz.

Az új pontok meghatározása történhet intelligensen, figyelembe véve a feladat szerkezetét, például gradien irányban továbblépve vagy más módon garantálva, hogy megfelelő irányban keresünk, de lehet teljesen véletlenszerűen is.

Amennyiben valamilyen egyéb feltétel biztosítja, hogy a feladatnak nincs a globálistól különböző optimuma, akkor azt ezzel az eljárással megtaláljuk. Ha több lokális optimum is lehet, akkor a téren egyenletes eloszlással választva a kiinduló x_{0} pontokat, valószínűsíteni lehet, hogy a megtalált lokális optimumok között ott lesz a globális is.

Az utazóügynök problémára vonatkoztatva ez a következő algoritmussémát jelenti:

1. lépés Generálunk véletlenszerűen egy megengedett túrát.

2. lépés Túrajavító eljárás(ok) segítségével meghatározunk helyette egy jobb túrát.

3. lépés Ha nem teljesül a kilépési feltétel, visszatérünk a 1. lépéshez.

4. lépés A megtalált legjobb túra az eredmény.

A kilépési feltétel sokféle lehet, például elvégeztünk megadott számú vizsgálatot, lejárt a vizsgálatokra szánt összidő, vagy az elmúlt valahány ciklus alatt nem javítottunk ez eddigi legjobb értéken.

Egy másik lehetőség a lokális optimumokon való túllépésre az, hogy a keresés során megengedünk olyan lépést is, amikor a kapott hely nem jelent javítást az előzőhöz képest. A TSP megoldására szolgáló heurisztikus eljárások esetén ez általában azt jelenti, hogy olyan amennyiben nem tudunk javító élcserét végezni, akkor megengedünk rontó cserét is. (Valamiféle korlátozott visszalépéses keresést hajtunk végre.)

2.3 A Lin-Kerninghan heurisztika

A Lin-Kerninghan heurisztika jó – és hatékonysága miatt a gyakorlatban is használt – példája az előző részben leírt lokális keresési eljárásnak.

Legyen T ⊂ E egy nem optimális, de megengedett megoldás, azaz egy túra. Azt mondhatjuk, hogy T azért nem optimális, mert x_{1}, …, x_{k} ∈ T nem megfelelő élek, ki kellene őket cserélni a y_{1}, …, y_{k} ∈ E − T élekre. A nehézséget k meghatározása és az x-ek és y-ok azonosítása jelenti.

Mivel k rögzítése egy feltételezett értékre nem gazdaságos, keressük az x − y párokat egyenként. Azaz először meghatározzuk x_{1}-et és y_{1}-et, mint a leginkább kilógó párt. Aztán ezt a párt félretéve x_{2}-et és y_{2}-et a maradékból leginkább kilógó párt, és így tovább.

Kicsit pontosabban:

1. Legyen T_{0} a kiindulási túra!

2. Legyen m = 1, t_{1} a javítás kiinduló csúcsa, (t_{1}, t_{2}) a túra éle.

3. Az eljárás m-dik lépésében elhagyjuk a (t_{1}, t_{2m}) élet és bevesszük helyette a (t_{2m}, t_{2m+1})-et, ahol az új élet úgy választottuk, hogy a legnagyobb legyen a nyereség.

4. Legyen t_{2m+2} az a pont, melyre teljesül, hogy (t_{2m+1}, t_{2m+2}) törlése és (t_{2m+2}, t_{1}) hozzávétele után ismét túrát kapunk (T_{m}).

5. Ha – később részletezett kritérium alapján – úgy találjuk, hogy nem érdemes tovább keresni, megállunk, egyébként legyen m = m + 1 és folytatjuk a 3. lépéstől.

6. Legyen T_{0} = T_{k} az a túra, amelyik a javítás során a legjobb volt, válasszunk újabb kiinduló élet, és folytatjuk a 3. lépéstől. Ha már minden élet kipróbáltunk, akkor nem tudunk tovább javítani a túrán.

Nagy hiányossága ennek az eljárásnak, hogy léteznek olyan cserék, melyeket nem lehet egymásutáni cserékkel előállítani. Ezért szükség van rá, hogy megengedjünk olyan cserét is, amelyik nem túrát eredményez. Az algoritmus különböző megvalósításai az algoritmus más-más pontján és más-más módon engednek meg ilyen lépést, de a nem megengedett megoldás kezelése mindenképpen bonyolítja az algoritmust.

Más megoldást talált K-T. Mak és A. Morton [6]. Ők úgy módosították az algoritmus, hogy ne legyen szükség átmenetileg sem nem túrák kezelésére.

2.3.1 A módosított Lin-Kerninghan módszer

Hívjuk a m-dik lépésben törlendő (t_{1}, t_{2m}) élet a lépés alapélének! Az eredeti módszerben olyan élét veszünk hozzá a túrához, amelyik az alapél végéhez csatlakozik, és 2-optimalizálással választjuk meg a túra zárását. Teljesen szimmetrikusan választhatunk olyan élet is, amelyik az alapél kezdetéhez csatlakozik. Ha mindkét lehetőséget megengedjük a következő túrajavító eljárást nyerjük:

1. Legyen m = 1, x_{1} = (t_{1}, t_{2}) a lépés alapéle! Legyen a túra iránya olyan, hogy az alapél t_{1}-ből t_{2}-be menjen!

2. Ha nincs olyan y_{m} vagy z_{m}, melyre az alapélet nyereségesen le lehet cserélni, akkor megállunk, egyébként kiválasztjuk a legnyereségesebbet.

3. 2-optimalizáló cserével töröljük az alapélet és bevesszük y_{m}-t vagy z_{m}-t, attól függően, melyiket választottuk. A csere törli x_{m+1}-et is.

4. Ha y_{m}-t vettük hozzá, legyen az új alapél z_{m}, ha z_{m}-et vettük hozzá, akkor y_{m}.

5. Legyen m = m + 1 és folytassuk a 2. lépéstől.

Meg kell még pontosan fogalmazni az eljáráshoz a kiválasztási és megállási feltételeket.

Nyereség alatt értsük a túra hosszának csökkenését! Jelölje OsszNy(m) az összegzett nyereséget m 2-optimalizáló csere után. Az egyszerűség kedvéért az élet és a hosszát jelöljük ugyanúgy! Ha OsszNy(0) = 0 és c_{0} a kezdeti alapél, az összegzett nyereség:

OsszNy(m) = OsszNy(m−1)+(c_{m−1}−a_{m})+(x_{m−1}−c_{m}), m = 1, 2, …,

ahol a_{m} a hozzávett él – x_{m} vagy y_{m} –, c_{m} pedig az az él, amelyik zárja a túrát az m. lépésben. Természetesen a_{m} = y_{m} pontosan akkor, ha c_{m} = z_{m}, és a_{m} = z_{m} pontosan akkor, ha c_{m} = y_{m}.

Elvégezve m lépést az addigi legnagyobb nyereség:

MaxNy(m) = max{OsszNy(i)|i = 1, …, m}.

Annak eldöntésére, hogy érdemes-e további lépéseket tenni, MaxNy-t hasonlítjuk P robaNy-hez:

P robaNy = OsszNy(m) + P luszNy(m),

ahol P luszNy méri, hogy mekkora nyereség várható egy újabb lépéstől. P luszNy-t úgy kell meghatározni, hogy P robaNy(m) ≤ MaxNy(m) esetén kicsi legyen az esély rövidebb túra elérésére.

P luszNy megválasztására több lehetőség kínálkozik. Gyakorlati eredmények alapján

P luszNy(m) = max_{y_{m+1},z_{m+1}}{x_{m+2} − y_{m+1}, c_{m} − z_{m+1}}

és szimmetrikus megfelelője

P luszNy(m) = max_{y_{m+1},z_{m+1}}{c_{m} − y_{m+1}, x_{m+2} − z_{m+1}}

egyformán hatásosak és jobbak, mint más kritériumok.

Valamelyik változatot felhasználva a teljes heurisztika a következő:

1. Válasszunk egy véletlen túrát kiindulásnak.

2. Legyen az alapél az, amelyiknek a kiindulópontja a következő csúcs egy előre meghatározott véletlen sorren szerint.

3. Alkalmazzuk a módosított eljárást a túrák javítására, amíg P robaNy ≤ MaxNy vagy P robaNy ≤ 0 nem teljesül.

4. Tekintsük azt a túrát, amelyik MaxNy-hez tartozik! Ha rövidebb, mint az eredeti túra, válasszuk őt, egyebként térjünk vissza az eredetihez, és folytassuk a 2. lépéssel.

5. Az eljárásnak akkor van vége, ha a vizsgált túra minden élét választottuk már alapélnek.

A genetikus algoritmusokról

A genetikus algoritmusok, újabb szóhasználattal az evolúciós algoritmusok, a biológia evolúciót utánzó valószínőségi kereső eljárások. Lényegük, hogy egy populáció egyedei reprezentálnak pontokat a keresési térben. A kiindulási populációt úgy módosítjuk kiválasztó, keresztező és mutációs eljárásokkal, hogy az egyedek értékének átlaga növekedjen. Az érték felel meg a biológiai alkalmasság fogalmának, így az átlag növekedését hasonlóan érjük el, mint ahogy az evolúció működik: a nagyobb értékű (alkalmasabb) egyedeknek nagyobb esélyük van arra, hogy megjelenjenek a következő generációban is, illetve az utódok az alkalmasabb egyedek tulajdonságait próbálják egyesíteni.

Így kellő számú generáció múlva a populáció legjobb egyedei közel hasonlóak lesznek a lehetséges legjobb egyedekhez.

Az alkalmasság mérése általában a egyszerűen a célfüggvény értékével történik, tehát arra törekszünk, hogy az egyedek a célfüggvény optimumhelyei körül sűrűsödjenek.

3.1 Evolúciós program

Az evolúciós program elnevezést használjuk minden az evolúciós elven alapuló rendszerre. Az evolúciós program szerkezete a 3.1. ábrán látható.

Az evolúciós program egy olyan valószínűségi algoritmus, mely az egyedek egy P (t) = {x_{1}^{t}, …, x_{n}^{t}} populációját kezeli a t. iteráció során. Minden egyed a probléma egy lehetséges megoldását reprezentálja, és valamilyen (esetleg komplex) S adatszerkezet valósítja meg. Minden x_{i}^{t} megoldást értékelünk, hogy mérni tudjuk az alkalmasságát. Ezután egy új populációt (t + 1. iteráció vagy nemzedék) hozunk létre kiválasztva az alkalmasabb egyedeket (kiválasztási lépés). Az egyedek egy része átalakításon esik át: bizonyos operátorok segítségével új megoldásokat hozunk létre belőlük (rekombinációs t := 1 létrehoz P (t) értékel P (t) amíg nem befejezés t := t + 1 kiválaszt P (t)-t P (t − 1)-ből rekombinál P (t) mutál P (t)

3.1. Ábra: Az evolúciós program szerkezete

lépés). Vannak egyparaméteres átalakítások m_{i} (mutáció), melyek az új egyedet egyetlen egyed kis változtatásával hozzák létre (m_{i} : S → S), és magasabb rendű átalakítások c_{i} (keresztezés), melyek az új egyedet néhány (kettő vagy több) egyed részeinek kombinálásával állítják elő (c_{j} : S ×…×S → S). Néhány generáció után a programkonvergál – a legjobb egyedek remélhetőleg az optimális megoldást reprezentálják.

3.2 Genetikus algoritmusok

A genetikus algoritmusok jelentik az evoluciós programok legelső és legjobban vizsgált változatát. Ezeknél egyértelműen az egyes operátorok a meghatározóak a működés szempontjából, a különböző változatok abban különböznek, hogy hogyan valósítják meg az egyes operátorokat. A leglényegesebb a rekombináció, a mutáció csak másodlagos szerepet játszik. A továbbiakban HOL-LAND [4] eredeti GA fogalmait használjuk.

3.2.1 Hogyan működnek?

A genetikus algoritmusokban jelennek meg a legközvetlenebbül a biológiai fogalmak. Az algoritmus bitvektorokkal dolgozik, ezek felelnek meg a kromoszómáknak, illetve az egyes bitek a géneknek. A rekombináció megegyezik a kromoszómák keresztezésével: a szülő bitvektorok egy részletüket kicserélik egymás között. A mutáció pedig azt jelenti, hogy véletlenszerűen megváltozik egy gén – egy bit. A pontosabb megfogalmazáshoz vezessük be a következő jelöléseket:

I  az egyedek (individuumok tere)
a⃗  egy egyed
x⃗ ∈ R^{n}  a célfüggvény változóinak vektora
f(x⃗) → R  az optimalizálandó függvény, célfüggvény
Φ : I → R  az értékelő, alkalmassági függvény
μ ≥ 1  a szülők száma
λ ≥ 1  a gyermekek száma
t  a generáció száma
P (t) = {a⃗_{1}(t), …, a⃗_{μ}(t)} a t. generációban lévő egyedek

Kódolás és alkalmasság

Mivel genetikus algoritmusok állandó l hosszúságú bitvektorokkal dolgoznak, bináris számokon értelmezett célfüggvény esetén közvetlenül használhatjuk a kiértékelésben – az alkalmasság megállapításában. Ha az optimalizálási feladatban fellépő célfüggvény

f : ∏_{i=1}^{n}[u_{i}, v_{i}] ⊂ R^{n} → R, u, v ∈ R, (u_{i} < v_{i})

alakú, akkor szükséges az átalakítása, hogy az algoritmusban használható értékelőfüggvényt nyerjünk. Ehhez osszuk fel az l hosszú bitsorozatot l = l_{1} + … + l_{n} részekre és mindegyik rész legyen a megfelelő x_{i} ∈ [u_{i}, v_{i}] változó bináris kódja. Az ehhez a részhez tartozó Γ^{i} : {0, 1}^{l_{i}} → R dekódolófüggvényt definiáljuk a következőképpen:

Γ^{i}(a_{i1} … a_{il_{i}}) := u_{i} + \frac{v_{i} − u_{i}}{2^{l_{i}} − 1} (∑_{j=1}^{l_{i}} a_{ij}2^{j−1}),

ahol a_{i1} … a_{il_{i}} az a⃗ egyed i. szegmense, a⃗ = a_{11} … a_{nl_{n}} ∈ I.

Ezeket a függvényeket összefogva egyetlen Γ = Γ_{1} × ⋯ × Γ_{n} dekódolófüggvénnyé kapjuk a Φ(a⃗) = δ(f(Γ(a⃗))) értékelőfüggvényt, ahol δ egy skálázófüggvényt jelent, mely minden fitness értéket pozitívvá tesz, úgy, hogy a legjobb egyed kapja a legnagyobb értéket. A skálázás többnyire csak egy eltolást jelent, például az előző generáció legrosszabb egyedének értékével.

A fenti bináris kódolás a GA paraméteroptimalizálásban való felhasználásához lett kifejlesztve. A rajta alapuló más – vagy hozzá csak hasonló, például bináris vektorok helyett valós vektorokat alkalmazó – kódolások lehetővé teszik az alkalmazást további problémákra.

Mutáció

A genetikus algoritmusokban a mutáció csak alárendelt szerepet játszik, de nem szabad megfeledkezni róla. Mivel teljesen új egyedeket hoz létre, meggátolja, hogy az eljárás egy lokális optimumhoz konvergáljon. A kiválasztás bizonyos körülmények között azt eredményezheti, hogy a populáció csupa azonos egyedből áll, ilyen esetekben jelent továbblépést a mutáció.

A mutáció a bitsorozat szintjén dolgozik: az egyed bitjeit változtatja meg p_{m} – általában nagyon kicsi – valószínűséggel. Általában a paraméter nagysága függ a változók számától vagy l értékétől. Az egyes egyedekre a következő operátor hat: m_{p_{m}} : I → I, m_{p_{m}}(s_{1}, … s_{l}) = (s′_{1}, … s′_{l}),

s′_{i} = \{ \begin{matrix}s_{i}, & χ_{i} > p_{m} \\ 1 − s_{i}, & χ_{i} ≤ p_{m} \end{matrix}

Itt χ_{i} ∈ [0, 1] egyenletes eloszlású véletlenszám, minden bithez külön meghatározva.

Rekombináció

A genetikus algoritmusoknál a főszerep a rekombinációra hárul, a keresztező r_{p_{c}} : I^{μ} → I operátorra hárul, mely az egyedek különböző részeiből hoz létre új egyedet. Mivel a létrejövő egyed többnyire különbözik minden eddigitől, ez a művelet teszi lehetővé, hogy a vizsgálandó tér minden részét megvizsgáljuk. A keresztezés független az egyes változókhoz tartozó szegmensek l_{i} hosszától. Az operátor paramétere a p_{c} keresztezési valószínűség határozza meg, hogy mekkora eséllyel vesz részt egy egyed a keresztezésben. A szokásos értékek a [0,6 , 1,0] tartományba esnek.

Ha s⃗ = (s_{1}, …, s_{l}) és v⃗ = (v_{1}, …, v_{l}) lettek véletlenszerűen kiválasztva a keresztezésre, akkor az s′, v′ utódok a következőképpen fognak kinézni:

s′ = (s_{1}, s_{2}, …, s_{χ−1}, s_{χ}, v_{χ+1}, …, v_{l})
v′ = (s_{1}, s_{2}, …, v_{χ−1}, v_{χ}, s_{χ+1}, …, s_{l})

Mint az előző esetben is, χ ∈ {1, …, l} egyenletes eloszlású véletlenszám. Ez a séma az egy pontú keresztezés, újabb pontok bevezetésével értelmezhető a több pontú keresztezés is.

Kiválasztás

A kiválasztás során döntjük el, hogy a szülőpopuláció mely tagjai vesznek részt az utódok létrehozásában, illetve mely egyedek helyére kerülnek be az új egyedek. Az utódok létrehozása során általában két szülőnek két utódja lesz, de létezik mást megoldás is.

A kiválasztás úgy történik, hogy minden egyedhez hozzárendelünk egy – az egyed alkalmasságával arányos – túlélési valószínűséget és ezek szerint a valószínűségek szerint választjuk ki a szülőket. Ez a módszer biztosítja, hogy kellően egyensúlyban legyen az ígéretes megoldások kihasználása, és a megoldástér új területeinek felfedezése.

Az a⃗_{i} egyed részvételének valószínűségét új egyedek létrehozásában relatív alkalmassága adja meg:

p_{s}(a⃗_{i}) = \frac{Φ(a⃗_{i})}{∑_{j=1}^{μ} Φ(a⃗_{j})}, ∀j ∈ \{1, …, μ\}

Amennyiben minimalizálási feladatról van szó, vagy az alkalmasság értéke negatív is lehet, akkor skálázófüggvényt kell alkalmazni.

Miután kiválasztottuk az új generáció létrehozásában részt vevő μ szülőt és belőlük megalkottuk a λ utódot felmerül a kérdés, hogy hogyan illesszük be az utódokat a populációba, kikból álljon az új populáció. A legkézenfekvőbb lehetőség, hogy a következő populációt teljes egészében az új generáció fogja alkotni, de ekkor nagy esély áll fenn arra, hogy elvesztünk egy nagyon jó megoldást. Éppen ezért célszerű megtartani az előző generáció bizonyos tagjait is. Néhány egyszerű stratégia látható a 3.1. táblázatban.

generációcsere minden szülőt lecserélünk elitizmus

az n legjobb szülőt (elit) változatlanul megtartjuk

gyenge elitizmus az n legjobb szülőt mutáció utáni formájában

megtartjuk

utolsó n törlése az n legrosszabb szülőt cseréljük le n törlése

n véletlenszerűen kiválasztott szülőt cserélünk le

n törlése elitizmussal az n cserélendő szülőt az eliten kívüli részből választjuk

3.1. Táblázat: A populáció fiatalításának néhány változata

Alapalgoritmus

Az előzőleg leírt eljárások alkalmazásával az általános genetikus algoritmus a 3.2. ábrán látható módon áll össze:

• Initializáljuk a generációszámlálót.

• Egy μ egyedből álló populációt hozunk létre véletlenszerű bitsorozatokból. t := 0 létrehoz: P (0) := (a⃗_{1}(0), …, a⃗_{μ}(0)) ∈ I^{μ} (I = {0, 1}^{l}) értékel: P (0) : {Φ(a⃗_{1}(0)), …, Φ(a⃗_{μ}(0))}

ahol Φ(a⃗_{k}(0)) := δ(f(Γ(a⃗_{k}(0))))

amíg P (t) nem utolsó generáció rekombinál: a′_{k} := r_{p_{c}}(P (t)), ∀k ∈ {1, …, λ} mutál: a′′_{k} := m_{p_{m}}(a′_{k}), ∀k ∈ {1, …, λ} értékel: P′′(t) : {a′′_{1}(t), …, a′′_{λ}(t)} : {Φ(a′′_{1}(t)), …, Φ(a′′_{λ}(t))} kiválaszt P (t + 1) := s_{θ}(P′′(t) ∪ Q) t := t + 1

3.2. Ábra: Az általános genetikus algoritmus

• Az egyedekhez jóságot rendelünk a Φ alkalmassági függvény segítségével. Közben alkalmazzuk a δ skálázófüggvényt, hogy pozitív alkalmassági értékeket nyerjünk.

• A következő lépéseket ismételjük, amíg a befejezési kritérium nem teljesül:

– A különböző feltételek alapján rekombinációra kiválasztott egyedek közül kettőt kiválasztva, az egyedekben lévő információk keverésével két új egyedet hozunk létre, amíg nincs összesen λ utódunk.

– A λ új egyedet p_{m} mutációs valószínűséggel valamilyen formában megváltoztatjuk.

– A módosított utódokat a Φ alkalmassági függvény segítségével értékeljük – közben alkalmazzuk a δ skálázófüggvényt.

– A utódok közül és a szülőpopuláció valamilyen Q részhalmazából a kiválasztási séma szerint meghatározzuk az új populáció μ egyedét.

– Növeljük a generációszámláló értékét.

3.2.2 Miért működnek?

Annak a megértéséhez, hogy miért működik az előző részben leírt algoritmus, kicsit vissza kell térnünk a kódoláshoz. HOLLAND [4] vezetett be egy új fogalmat a sémát. A séma H ∈ {0, 1, ∗}^{l} segítségével a keresési tér egy alterét határozzuk meg. A ∗ szimbólum azt jelenti, hogy nem kötjük meg azon a helyen a bitsorozat értékét, az lehet 0 és 1 is. Ennek megfelelően a (01∗) séma tartalmazza a (010) és a (011) bitsorozatot is. Másként fogalmazva: akár a (010), akár a (011) bitsorozat megvalósítja a (01∗) sémát.

Egy P (t) populációban a H^{t} séma megjelenésének számát jelölje m(H^{t}), a H sémában szereplő rögzített pozíciók számát (rend) o(H), az első és utolsó rögzített pozíció távolságát (méret) pedig η(H). (Például o(0 ∗ 1 ∗ ∗∗) = 2, η(0 ∗ 1 ∗ ∗∗) = 2.) A séma átlagos alkalmasságát a P (t) populációban jelentse az őt megvalósító egyedek alkalmasságának átlaga:

Φ(H^{t}) = \frac{1}{m(H^{t})} ∑_{a_{i}∈H^{t}∩P (t)} Φ(a_{i}).

A populáció átlagos alkalmassága:

\overline{Φ^{t}} = \frac{∑_{i=1}^{μ} Φ(a⃗_{i})}{μ}.

Ezekkel a jelölésekkel egy séma megvalósulásainak száma a következő generációban várható értékben

m(H^{t+1}) = \frac{m(H^{t})Φ(H^{t})}{\overline{Φ^{t}}},

hiszen a kiválasztási szabályunk olyan, hogy – szemléletesen fogalmazva – egy egyed elterjedtsége a következő generációban közel megegyezik a egyed relatív alkalmasságával.

Így egy átlagon felüli alkalmasságú séma – melyre Φ(H^{t}) = \overline{Φ^{t}} +c\overline{Φ^{t}}, ahol c > 0 konstans – elterjedtsége t generáció után (t_{0} = 0):

m(H^{t}) = m(H^{0}) · (1 + c)^{t}.

Ez azt jelenti, hogy a kiválasztás egy átlagon felüli alkalmasságú sémának exponenciálisan növekvő számban biztosít lehetőséget a fennmaradásra, míg egy átlagon aluli alkalmasságú séma hasonló gyorsasággal kiszorul a populációból.

A mutáció és a keresztezés hatását is figyelembe véve, annak kiszámolásával, hogy mekkora egy séma fennmaradásának valószínűsége egyszerű keresztezés (1 − p_{c}η(H^{t})/(l − 1)) és egyszerű mutáció ((1 − p_{m})^{o(H)}) mellett, adódik HOLLAND [4] Séma-tétele:

m(H^{t+1}) ≥ m(H^{t}) · \frac{Φ(H^{t})}{\overline{Φ^{t}}} · (1 − p_{c} \frac{η(H^{t})}{l − 1}) · (1 − p_{m})^{o(H)}

Szavakkal megfogalmazva: egy séma melynek kicsi a mérete, alacsony a rendje és átlagon felüli az alkalmassága, exponenciálisan növekvő eséllyel rendelkezik, hogy a következő generációkban is jelen legyen.

Ebből következik a paraméterek kódolására vonatkozóan, hogy azokat a paramétereket, melyek összetartoznak, egymás melletti szegmensekbe tanácsos leképezni, ezenkívül jó, ha azok a jellemzők is egymás melletti szegmensekbe kerülnek, melyek nagy befolyással rendelkeznek az egyed alkalmasságára, mert így az átlagonfelüliség jobban fennmaradhat.

Az átlagon felüli alkalmasságú sémákat GOLDBERG[3] építőkőnek (Building-Block) nevezi, és az ő megfogalmazásában a GA fő mechanizmusa bitsorozatok létrehozása egyre nagyobb túlélési valószínűséggel építőkövek kombinálása által (Building-Block-Hyphotese).

Léteznek olyan feladatok is, amikor a Séma tétel, és az Építőkő sejtés nem működnek. Többnyire arról van szó, hogy építőkövek kombinálásakor viszonylag alacsony alkalmasságú sémák jönnek létre. Emögött többnyire az áll, hogy viszonylagos optimumok találhatóak nagyon rossz megoldások közelében. Azonban az ilyen feladatok esetében a hagyományos optimalizálási módszerek is rosszul működnek.

Az utazó ügynök probléma és a genetikus algoritmusok

Bár mint az első fejezetben láthattuk, az utazó ügynök problémára sok és viszonylag hatékony heurisztikus megoldási módszer létezik, mégis jelentős a genetikus algoritmusok alkalmazása is. Ennek oka egyrész az, hogy az evolúciós jellegű algoritmusok is közel optimális vagy optimális eredményt adnak, és közben kevésbé hajlamosak leragadni egy lokális optimumnál. Másik ok abban rejlik, hogy nagy méretű problémák esetén a megoldás időszükségletének csökkentésére természetesen adódik a megoldás keresése párhuzamos architechtúrán és míg a heurisztikus algoritmusok esetén ez külön átalakítást igényel, a genetikus algoritmusok már jellegükben párhuzamosak, nem igényel külön erőfeszítést párhuzamos implementálásuk.

4.1 A problémához illeszkedő kódolások

A genetikus algoritmusoknál általában bináris kódolást alkalmazunk. Az utazó ügynök probléma esetében azonban egy megoldás a városokon keresztül vezető körutat jelent. Ennek ábrázolása porzitív egészek megadását jelenti, melyekre speciális feltételeknek kell teljesülniük (például minden várost pontosan egyszer érinthetünk). Mivel a bitszintű genetikus operátorok ezeket a plusz feltételeket nem tartanák fenn, nem alkalmazhatóak a problémára.

Az elmúlt években három vektor-reprezentáció került kidolgozásra, a hozzájuk tartozó keresztezési eljárásokkal együtt. A reprezentációk jobb megértéséhez tekintsük az A, B, C, D, E, F városokat és az [F BACED] utat, a városok számozása abc sorrend szerint történik.

• Út ábrázolás Ez a legtermészetesebb leírása egy körútnak: egyszerűen felsoroljuk a városák sorszámát a bejárás sorrendjében. A példa kódolása eszerint {621354}.

A legismertebb keresztezési eljárások ezen kódolás mellett a Partially-Mapped-Crossover (PMX)^{1}, az Order-Crossover (OX), a Cycle-Cross-over (CX), valamint az Edge-Recombination-Crossover (ERX) / Enhanced-Edge-Recombination-Crossover (EERX).

• Szomszédsági ábrázolás Ebben a leírásban egy egészekből álló vektorban leírjuk, hogy melyik város után melyik másik város következik a bejárás során. Például az E város (abc sorrendben az ötös) után a D (négyes) város következik, tehát a vektor 5. eleme 4 szám. Az előző példánk kódolása: {315642}. Míg a többi kódolásnál egy útnak több kód is megfelel – attól függően, hogy hol kezdjük el a kört leírni –, ebben az esetben az út kódolása egyértelmű.

A megfelelő keresztezések az Alternating-Edges-Crossover és a Subtour-Chrunking-Crossover

• Sorrend szerinti ábrázolás Itt a városok listájából indulunk ki, melyben a városok a felsorolásuk szerint helyezkednek el (a példában ez egyszerűen az abc sorrend). Minden város a listában elfoglalt helyével kerül be a kódba, és utána eltávolítjuk a listából. A példánk kódolása: {6 2 1 1 2 1}.

Előnye ennek az ábrázolásnak, hogy a m-pontos keresztezés változtatás nélkül végrehajtható rajta, és a kapott kód is egy szabályos utat ír le. Ha más keresztezést akarunk alkalmazni, könnyen át lehet térni az út ábrázolásra, majd a keresztezés után visszatérni. Hátrány, hogy a mutációra külön oda kell figyelni. Ha megváltoztatunk egy elemet a kódban, akkor az összes utána szereplő város is megváltozik az úton. Azonkívül figyelni kell arra is, hogy a kód egy eleme nem lehet nagyobb, mint a még be nem sorolt városok száma. Ezért ezt a kódolást kevésbé használják.

1Itt a dolgozat egészétől eltérően nem próbálok magyar elnevezéseket használni. Főleg mert nem sikerült megfelelő kifejezéseket találni, másrészt általában csak a rövidítésükkel emlegetjük őket, azt pedig nem szerencsés magyarítani.

4.2 Speciális keresztezési eljárások

A következő keresztezésekben példaként a

\begin{matrix}A : \{7 4 9 3 5 8 2 1 6\} \\ B : \{4 2 7 1 8 3 9 6 5\} \end{matrix}

szülőket használjuk.

Partially-Mapped-Crossover (PMX)

• Először véletlenszerűen kiválasztjuk a keresztezés két pontját. Legyenek ezek például a 3. és 4. valamint a 6. és 7. pozíció között. A két pont közti részt hívjuk a keresztezési intervallumnak.

\begin{matrix}A : \{7 4 9 | 3 5 8 | 2 1 6\} \\ B : \{4 2 7 | 1 8 3 | 9 6 5\} \end{matrix}

• A gyermek a keresztezési intervallumon kívül az A szülő, azon belül a B szülő városait kapja.

1 : {7 4 9 | 1 8 3 | 2 1 6}

• Ezután megszüntetjük a város-ismétlődéseket: az s ismétlődő városnak meghatározzuk a p helyét a B szülőben, és lecseréljük az A szülő p-dik helyén álló városra. Ha ez a város is szerepelne már az utódban, akkor megismételjük az eljárást, amíg olyan város nem találunk, amelyik még nem szerepel.

K : {7 4 9 1 8 3 2 5 6}

Order-Crossover

• Először itt is meghatározzuk a keresztezési intervallumot.

\begin{matrix}A : \{7 4 9 | 3 5 8 | 2 1 6\} \\ B : \{4 2 7 | 1 8 3 | 9 6 5\} \end{matrix}

• Megjelöljük azokat a városokat, amelyikek a másik szülőnél a keresztezési intervallumban találhatóak.

\begin{matrix}A′ : \{7 4 9 | X 5 X | 2 X 6\} \\ B′ : \{4 2 7 | 1 X X | 9 6 X\} \end{matrix}

• A baloldali keresztezési ponttól kezdve átrendezzük a városokat úgy, hogy egymáshoz képest a sorrendjük ne változzon, és a megjelölt helyek kerüljenek a cserélendő közbe.

\begin{matrix}A′′ : \{7 4 9 | X X X | 5 2 6\} \\ B′′ : \{4 2 7 | X X X | 1 9 6\} \end{matrix}

• Ezután elvégezzük a cserét.

K : {7 4 9 | 1 8 3 | 5 2 6}

Cycle-Crossover

A CX operátor az eddigiektől eltérő módon dolgozik.

• Kiválasztunk egy helyet az A szülőben és az ott található kódot átvesszük az utódba. Legyen például a pozíció a 2.!

A : {7 4 9 3 5 8 2 1 6}
B : {4 2 7 1 8 3 9 6 5}
A′ : {? 4 ? ? ? ? ? ? ?}

• Ezután megkeressük az utoljára bevett város p helyét B-ben, és a p helyre vesszük át a várost A-ból. Ezt mindaddig folytatjuk, amíg el nem érünk a kiindulási helyre.

A′′ : {7 4 9 ? ? ? 2 ? ?}

• A még fennmaradó helyeket feltöltjük B-ből.

K : {7 4 9 1 8 3 2 6 5}

Edge-Recombination-Crossover (ERX) / Enhanced-Edge-Recom-bination-Crossover (EERX)

Az ERX/EERX operátor – az eddigiektől eltérően – élorientált, azaz nem azt használja fel, hogy a szülők kódja hogyan néz ki, hanem igyekszik a szülőkben lévő élekből minél többet átmenteni az utódba.

• Létrehozunk egy listát a szülőkben levő élekből, abban a formában, hogy minden városhoz megadjuk, belőle melyik másik városba vezet él a két szülő valamelyikében. Amennyiben így egy város a listán kétszer előfordulna, ERX esetén az ismétlődést elhagyjuk, EERX esetén elhagyás után a várost megjelöljük – negatív előjellel. A példa esetén a következő listát kapjuk (balra az ERX, jobbra az EERX esetén):

1: 2 6 7 8 1: 2 6 7 8 2: 1 4 7 8 2: 1 4 7 8 3: 5 8 9 3: 5 8 -9 4: 2 5 7 9 4: 2 5 7 9 5: 3 4 6 8 5: 3 4 6 8 6: 1 5 7 9 6: 1 5 7 9 7: 1 2 4 6 7: 1 2 4 6 8: 1 2 3 5 8: 1 2 3 5 9: 3 4 6 9: -3 4 6

• Az utód kiindulópontjaként kiválasztjuk valamelyik szülő kiindulópontját. Esetünkben ez az A szülő. Ezután ezt a várost töröljük az éllistából.

A : {7 4 9 3 5 8 2 1 6}
B : {4 2 7 1 8 3 9 6 5}
A′ : {7 ? ? ? ? ? ? ? ?}

1: 2 6 8 1: 2 6 8 2: 1 4 8 2: 1 4 8 3: 5 8 9 3: 5 8 -9 4: 2 5 9 4: 2 5 9 5: 3 4 6 8 5: 3 4 6 8 6: 1 5 9 6: 1 5 9 7: 1 2 4 6 7: 1 2 4 6 8: 1 2 3 5 8: 1 2 3 5 9: 3 4 6 9: -3 4 6

• A következő várost az utolsó város szomszédjai közül választjuk ki, méghozzá azt, amelyiknek a listáján a legkevesebb bejegyzés szerepel. Amennyiben ez nem egyértelmű, ERX esetén véletlenül választunk, EERX esetén a megjelöltet részesítjük előnyben. Ha még mindig két jelölt van, akkor véletlenszerűen választunk.

A példánkban a 7 város szomszédai az 1,2,4,6 és mindegyiknek a listája három elemű, így például a 2-t választjuk. Ezután a kiválasztott csúcsot is töröljük az éllistából.

A′′ : {7 2 ? ? ? ? ? ? ?}

1: 6 8 1: 6 8 2: 1 4 8 2: 1 4 8 3: 5 8 9 3: 5 8 -9 4: 5 9 4: 5 9 5: 3 4 6 8 5: 3 4 6 8 6: 1 5 9 6: 1 5 9 7: 1 4 6 7: 1 4 6 8: 1 3 5 8: 1 3 5 9: 3 4 6 9: -3 4 6

• Az utolsó lépés addig ismételjük, amíg minden helyet ki nem töltöttünk. Amennyiben egy lépésben szülőktől származó éllel nem folytatható az út, véletlenszerűen választunk egy még nem érintett csúcsot.

A példát folytatva – több lehetőség esetén mindig az elsőt választva –:

\begin{matrix}K : \{7 2 1 6 9 4 5 3 8\} (ERX) \\ K : \{7 2 8 1 6 5 3 9 4\} (EERX) \end{matrix}

Alternating-Edges-Crossover

• Az utód létrehozásához először kiválasztunk egy élet az egyik szülőből, legyen az például a 7-1 él B-ből! Ez lesz az új túra első éle.

A : {7 4 9 3 5 8 2 1 6}
B : {4 2 7 1 8 3 9 6 5}
1 : {7 1 ? ? ? ? ? ? ?}

• A kövekező él legyen az, amelyik az utolsó él végpontjából indul a másik szülőben. Amennyiben az az él idő előtt zárná a kört, tetszőleges, még nem érintett csúcsot választunk a következő csúcsnak.

2 : {7 1 6 ? ? ? ? ? ?}

• Az előző lépést ismételjük, amíg a túra teljes nem lesz.

3 : {7 1 6 5 ? ? ? ? ?} 4 : {7 1 6 5 8 ? ? ? ?} 5 : {7 1 6 5 8 3 ? ? ?} 6 : {7 1 6 5 8 3 2 ? ?} a 2-t véletlenül választottuk a 2,4,9 közül 7 : {7 1 6 5 8 3 2 4 ?} a 4-et véletlenül választottuk a 4,9 közül K : {7 1 6 5 8 3 2 4 9}

Hátránya ennek az operátornak, hogy jó részsorozatokat megszüntet. Ennek a kiküszöbölésére fejlesztették ki a következő keresztezést.

Subtour-Chrunking-Crossover

• Az első két lépés hasonló az előző módszerhez.

1 : {7 1 ? ? ? ? ? ? ?} 7-1 a B szülőből 2 : {7 1 6 ? ? ? ? ? ?} 6 az A-ból

• Ahelyett, hogy azonnal szülőt váltanánk, véletlen mennyiségű csúcsot másolunk ebből a szülőből.

A : {7 4 9 3 5 8 2 1 6} B : {4 2 7 1 8 3 9 6 5} 3 : {7 1 6 4 ? ? ? ? ?} 4 még mindig az A-ból

• Az utolsó két lépést ismételjük, amíg a túra teljes nem lesz.

4 : {7 1 6 4 2 ? ? ? ?} 2 a B-ből

5 : {7 1 6 4 2 8 ? ? ?} még mindig B-ből 6 : {7 1 6 4 2 8 3 ? ?} továbbra is B-ből 7 : {7 1 6 4 2 8 3 5 ?} az A-ból K : {7 1 6 4 2 8 3 5 9}

4.3 Speciális mutációs eljárások

A következőkben bemutatunk néhány – az utazó ügynök problémához illeszkedő – mutációt. A példákban I=(4 2 6 7 1 3 5) az egyed, és P_{1} = 2, P_{2} = 5 két véletlenszerűen választott pozíció.

2 pontú elcsúsztatás

• Kijelölünk az egyedben két pozíciót – P_{1}, P_{2}.

• A P_{1}-en levő elemet átírjuk P_{2}-re és a köztük lévő sorozatot eggyel balra csúsztatjuk.

\begin{matrix}I : \{4 2 6 7 1 3 5\} \\ I′ : \{4 6 7 1 2 3 5\} \end{matrix}

2 pontú csere

• Kijelölünk az egyedben két pozíciót – P_{1}, P_{2}.

• A P_{1}-en és a P_{2}-n levő elemeket felcseréljük egymással.

\begin{matrix}I : \{4 2 6 7 1 3 5\} \\ I′ : \{4 1 6 7 2 3 5\} \end{matrix}

2 pontú inverzió

• Kijelölünk az egyedben két pozíciót – P_{1}, P_{2}.

• A P_{1} és P_{2} közötti részt megfordítjuk, azaz a P_{1} + n helyen lévő elemet felcseréljük a P_{2} − n helyen lévővel, ahol n ∈ \{1, …, m\}, m = ⌊\frac{P_{2}−P_{1}}{2} ⌋.

\begin{matrix}I : \{4 2 6 7 1 3 5\} \\ I′ : \{4 1 7 6 2 3 5\} \end{matrix}

A felsorolt mutációk bármelyike adaptívvá tehető, ha a két pozició kiválasztásánál korlátozzuk a pontok távolságát, és ez a korlátozás az idő előrehaladtával egyre csökken. Így kezdetben még nagy változást okozhatnak a mutációk, de az algoritmus vége felé – ahogy egyre közelebb vagyunk az optimális megoldáshoz – már csak keveset módosítanak.

4.4 Más megközelítés

Az utazó ügynök probléma megoldásánál, mint láttuk, egyre intelligensebb genetikus operátorokat használunk, egyre messzebb kerülünk az eredeti egyszerű alapoktól. Ennek a tendenciának erőteljes megnyilvánulása, amikor a genetikus eszközöket csak arra használjuk, hogy keretet adjanak a lokális keresése eljárásunknak. A genetikus operátorok biztosítják, hogy a keresési tér minél nagyobb részét megvizsgáljuk, de közben az egyedek gyorsított evolúcióban vesznek részt, valamilyen hatékony túrajavító eljárással visszük őket a helyi optimumba.

Ilyen algoritmust kapunk, ha például a 2.3. részben leírt eljárást illesztjük be genetikus algoritmusba.

• Generálunk véletlenszerűen egy induló populációt.

• A Lin-Kerninghan eljárás segítségével minden egyedet lecserélünk egy nála jobbra.

• Meghatározzuk az reprodukcióban részt vevő egyedeket – az alkalmasságtól függő valószínűséget figyelembe véve – és létrehozzuk az utódokat.

• Alkalmazzuk a mutációs operátort az egyedekre.

• Kiválasztjuk a következő generációt.

• Az előző négy lépést ismételjük, amíg nem teljesül a megállási feltétel.

4.5 Zárás

Az előzőekben megismerkedhettünk az utazó ügynök probléma megoldásának klasszikus heurisztikákon alapuló, illetve genetikus algoritmusokat felhasználó módjaival. Természetesen nem került sor minden létező módszer ismertetésére még ebben a szűk témában sem, hiszen egyre újabb – bonyolultabb – és hatékonyabb heurisztikus eljárásokat dolgoznak ki, különösen a gyakorlatból adódó speciális esetekben, amikor az erősebb feltételek miatt még jobbá tehetőek az alkalmazott eljárások. És az evolúciós algoritmusok elveit felhasználva is hatékonyabb algoritmusokat nyernek. Mindezek ellenére jól megválasztott heurisztikákkal valószínűleg mindig jobb eredményt sikerül elérni, mint genetikus algoritmusokkal, és ez is igazolja azt a vélekedést a genetikus módszerekről, hogy nagyon hatékonyak olyan problémák esetén, amikor nem tudjuk felismerni a probléma szerkezetét, vagy az olyan bonyolult, hogy nem tudjuk kihasználni. Ilyen esetekben a genetikus algoritmusok mintegy felismerik a struktúrát és különösebb emberi erőfeszítés nélkül kihasználják azt. Azonban ha a problémának felismerhető és kezelhető struktúrája van, akkor hatékonyabb ezt kihasználó eljárásokat nyerhetünk kellő emberi munka árán.

Irodalom

[1] R. E. Burkard: Travelling salesman and assignment problems: a survey, Annals of Discrete Mathematics 4 (1979) 193–215

[2] D. E. Goldberg: Genetic Algorithms in search, optimization and machine learning, Addison Wesley, 1989

[3] B. E. Golden,W. R. Stewart: Empirical analysis of heuristics, The Traveling Salesman Problem, John Wiley & Sons, 1985

[4] J. H. Holland: Adaptation in natural and artifical systems, University of Michigan Press, Ann Arbor, 1975

[5] S. Lin,B. W. Kerninghan: An Effective Heuristic Algorithm for the Traveling Salesman Problem, Oper. Res. 21, 498–516 (1973)

[6] K-T. Mak, A. Morton: A modified Lin-Kerninghan traveling-salesman heuristic, Oper. Res. Letters 13 (1993) 127–132

[7] Z. Michalewicz: Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1992

[8] Or I.: Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, Ph.D Dissertation, Northwestern University, Evanston, Ill., 1976