4.4. Lokális keresés folytonos terekben

A 2. fejezetben bemutattuk a diszkrét és a folytonos környezet közötti különbséget, arra is rámutatva, hogy a valósvilág-beli környezetek többsége folytonos. Az eddig leírt algoritmusok közül azonban egyik sem képes a folytonos állapottereket kezelni. Az állapotátmenet-függvény az esetek többségében végtelen számú állapottal térne vissza! Ez a részfejezet egy nagyon rövid bevezetőt ad néhány olyan lokális keresési technikához, melyek folytonos térben keresik az optimális megoldást. A téma irodalma óriási. Sok alaptechnika már a 17. században napvilágot látott, Newton és Leibniz kalkulusának kifejlődését[45] követően. E technikákhoz a könyvben több helyen fogunk folyamodni, beleértve a tanulásról, a látásról és a robotikáról szóló fejezeteket. Röviden, mindenhol, ahol a valós világgal foglalkozunk.

Fontos

Evolúció és keresés

Az evolúció elméletét Charles Darwin az On the Origin of Species by Means of Natural Selection c. művében (Darwin, 1859) dolgozta ki. A központi gondolat igen egyszerű: a reprodukcióban (mutációként ismert) eltérések fordulnak elő, és azokat a következő generációk nagyjából a reprodukciós fitnessre gyakorolt hatásuk arányában megtartják.

A darwini elméletet annak ismerete nélkül dolgozták ki, hogy a szervezetek tulajdonságai hogyan öröklődnek és módosulnak. E folyamatokat irányító valószínűségi törvényeket első ízben Gregor Mendel szerzetes azonosította (Mendel, 1866), aki borsóval kísérletezett, saját szavaival mesterséges megtermékenyítést alkalmazva. Sokkal később Watson és Crick feltárták a DNS-molekula szerkezetét és ábécéjét – AGTC (adenin, guanin, timin, citozin) – (Watson és Crick, 1953). A standard modellben a betűszekvenciában változás pontmutáció és „keresztezés” révén áll be (ahol az utód DNS-e a szülői DNS-ek hosszú részleteinek kombinálásával jön létre).

A lokális keresési algoritmus analógiájáról írtunk már. A sztochasztikus nyaláb keresés és az evolúció közötti alapvető különbség a szexuális reprodukció használata, ahol az utódokat több egyedből hozzuk létre, és nem csak egyből. Az evolúció tényleges mechanizmusai azonban sokkal gazdagabbak, mint amit a genetikus algoritmus lehetővé tenne. A mutációhoz például az átfordítás, a duplikálás, a DNS nagy szegmenseinek a mozgatása is hozzátartozik. Egyes vírusok a DNS-t az egyik szervezetből veszik és egy másik szervezetbe beillesztik. Vannak átvihető gének is, amelyek nem tesznek mást, csak egy génállományon belül többezerszer lemásolják magukat. Olyan gének is vannak, amelyek a potenciális reprodukciós partnereknél ezeket a géneket nem tartalmazó sejteket megmérgezik, növelve így a sokszorozódás esélyét. A legfontosabb tény, hogy maguk a gének tartalmazzák annak a mechanizmusnak a kódját, amely által a génállomány reprodukálódik, és egy szervezetté alakul át. A genetikus algoritmusokban ezek a mechanizmusok különálló programok részei, vagyis a manipulált füzérekben nem jelennek meg.

A darwini evolúció igencsak kis hatékonyságú mechanizmusnak tűnhet, hiszen vakon létrehozott kb. 1045 szervezetet, anélkül hogy a keresési heurisztikáin egy csöppet is javított volna. Darwin előtt 50 évvel a különben neves francia természettudós Jean Lamarck egy olyan evolúció elméletet javasolt (Lamarck, 1809), ahol egy szervezet az élete során, adaptációja révén megszerzett tulajdonságokat is képes az utódoknak átadni. Az ilyen mechanizmus hatékony lenne, de úgy tűnik, a természetben nem fordul elő. Sokkal később James Baldwin látszólag hasonló elmélettel állt elő (Baldwin, 1896), hogy a szervezet élete alatt megtanult viselkedés növelhetné az evolúció sebességét. Lamarck elméletével ellentétben a Baldwin-elmélet a darwini evolúcióval teljesen konzisztens, hiszen alapja egy szelekciós nyomás, amely olyan egyedekre hat, amelyek lokális optimumokat találtak a genetikus felépítésük által engedélyezett viselkedések között. A korszerű számítógépes szimulációk alátámasztják a „Baldwin-effektus” valós voltát, feltéve, hogy a „közönséges” evolúció olyan szervezeteket képes kialakítani, amelyeknél a belső hatékonysági mérték a saját tényleges fitness-értékükkel valahogy korrelál.

Kezdjük egy egyszerű példával. Tegyük fel, hogy valahol Romániában három új repülőteret szeretnénk létesíteni úgy, hogy a városoknak (lásd 3.2. ábra) a hozzájuk legközelebb eső repülőtérhez való távolságösszegük legyen minimális. Az állapotteret ekkor a repülőterek (x1, y1), (x2, y2) és (x3, y3) koordinátái definiálják. Ez egy hatdimenziós tér, azt is mondhatjuk, hogy az állapotokat hat változó (variable) definiálja (általánosságban az állapotokat a változók n-dimenziós x vektora definiálja). Ebben a térben való mozgás a térképen a repülőterek áthelyezésének felel meg. Az f(x1, y1, x2, y2, x3, y3) célfüggvényt, ha a legközelebbi városok már megvannak, bármely állapot esetére viszonylag könnyű kiszámítani, általánosságban azonban igen nehéz ezt leírni.

A folytonosság problémái egyszerűen elkerülhetők, ha az egyes állapotok szomszédságát diszkretizáljuk. Egyszerre például csak egy repülőteret, csak x vagy y irányban egy rögzített ±δ lépéssel lehet áthelyezni. Ez 6 változó mellett, minden állapotban 12 követőt eredményez. Ehhez az előbb megismert bármelyik lokális keresési algoritmust alkalmazhatjuk. A sztochasztikus hegymászó keresést és a szimulált lehűtést közvetlenül, a tér diszkretizálása nélkül is alkalmazhatjuk. Ezek az algoritmusok a követőket véletlen módon választják ki, amelyek megvalósítása δ hosszúságú véletlen vektorok generálásával lehetséges.

Sok módszer található, melyek megkísérlik a felszín gradiensét (gradient) felhasználni a maximum megtalálásához. A célfüggvény gradiense egy ∇f vektor, amely a legmeredekebb emelkedő nagyságát és irányát adja meg. Problémánk esetén:

Egyes esetekben a maximumot a ∇f = 0 egyenlet megoldásával találhatjuk meg (ezt megtehetnénk például akkor, ha csak egy repülőteret helyeznénk el; a megoldás az összes város koordinátáinak számtani közepe lesz). Sok esetben azonban ezt az egyenletet zárt alakban nem lehet megoldani. Három repülőtér esetén például a gradiens kifejezése attól függ, hogy az adott állapotban mely városok esnek legközelebb az egyes repülőterekhez. Ez azt jelenti, hogy a gradienst lokálisan, és nem globálisan tudjuk számítani. Ennek ellenére még mindig folyamodhatunk a legmeredekebb emelkedő hegymászáshoz a pillanatnyi állapotot az

x x + α ∇(x)

képlettel frissítve, ahol α egy kis konstans. Más esetekben nem biztos, hogy a célfüggvény differenciálható formában áll a rendelkezésünkre – például a repülőterek helyeit egy konkrét esetben esetleg egy nagyméretű gazdasági szimulációs szoftvercsomag futtatásával határozhatjuk meg. Az ilyen esetekben az ún. empirikus gradiens (empirical gradient) meghatározásához folyamodhatunk, minden koordináta mentén egy kis pozitív és negatív változáshoz kiszámítva a választ. Az empirikus gradiens keresés ugyanaz, mint a legmeredekebb emelkedő hegymászás az állapottér diszkretizált változatában.

Az „α egy kis konstans” kifejezés mögött az α-t beállító módszerek óriási választéka rejlik. Az alapprobléma az, hogyha α túl kicsi, túlságosan sok lépésre van szükség. Ha α túl nagy, a keresés könnyűszerrel túllő a maximumon. A vonalkeresés (line search) módszere e problémát úgy kísérli megoldani, hogy a pillanatnyi gradiens irányát – általában α ismételt megduplázásával – meghosszabbítja, amíg f nem kezd újra csökkeni. Az a pont, ahol ez megtörténik, lesz az új aktuális állapot.

Sok probléma esetén a legjobb algoritmus a jó öreg Newton–Raphson-módszer (Newton, 1671; Raphson, 1690). Ez a gyökhelykeresés, azaz a g(x) = 0 alakú egyenletek megoldásának általános módszere. Működésének alapja az x gyök új becslésének számítása a Newton-formula szerint:

x x g(x)/g′(x)

f maximumának vagy minimumának megkereséséhez olyan x-et kell megkeresni, amire a gradiens nulla (azaz ∇f (x) = 0). A Newton-formula g(x)-e így ∇f (x) lesz, és a frissítési egyenlete az alábbi mátrixos formában

írható fel, ahol Hf (x) a második deriváltak mátrixa (Hesse-mátrix), melynek Hij elemeit a ∂2f /∂xixj második deriváltak adják meg. Mivel a második deriváltak mátrixának n2 eleme van, a Newton–Raphson-módszer sokdimenziós terekben drága lesz, ami számos közelítő módszer kifejlesztéséhez vezetett.

A lokális keresési módszerek számára a lokális maximumok, a gerincek és a fennsíkok folytonos terekben ugyanúgy gondot jelentenek, mint diszkrét terekben. A véletlen újraindítás és a szimulált lehűtés alkalmazható (itt is), és gyakran segít. A sokdimenziós folytonos terek azonban terebélyes helyek, ahol könnyű elveszni.

Az utolsó téma, amivel érdemes futó ismeretséget kötni a korlátozott optimalizálás (constrained optimization). Egy optimalizálási probléma korlátozott, ha a megoldásnak minden változójának értékeire nézve valamilyen kemény korlátozást kell teljesítenie. A repülőteres problémánkban korlátozhatjuk például a helyszíneket, hogy a repülőterek Románián belül és szárazföldön (nem tavak közepén) helyezkedjenek el. A korlátozott optimalizálás nehézségei a korlátozások és a célfüggvény természetén múlnak. A legismertebb kategóriát a lineáris programozási (linear programming) problémák jelentik, ahol a korlátozások lineáris egyenlőtlenségek, amelyek egy konvex régiót képeznek, és ahol a célfüggvény szintén lineáris. A lineáris programozási problémákat változó számban polinomiális időben meg lehet oldani. Olyan problémákat is tanulmányoztak, ahol más típusú korlátozások és célfüggvények fordulnak elő. Ilyen problémák például a kvadratikus programozási feladat, a másodrendű kónikus programozási feladat stb.



[45] A többváltozós kalkulus és a vektoraritmetika ismerete hasznos ennek a részfejezetnek az olvasásához.