A heurisztikus információ alkalmazása a problémamegoldásban Simon és Newell egy korai írásában jelenik meg (Simon és Newell, 1958). A „heurisztikus keresés” frázis és a célhoz való távolságot becsülő heurisztikus függvény használata azonban valamivel későbbről származik (Newell és Ernst, 1965; Lin, 1965). Doran és Michie részletesen, kísérleti alapon tanulmányozták a heurisztikus keresési algoritmusok alkalmazását számos problémára, nagy hangsúlyt fektetve a 8-as és a 15-ös kirakójátékra (Doran és Michie, 1966). Habár Doran és Michie a heurisztikus keresésnél elméleti úthossz és „behatolás” (az úthossz és az eddig vizsgált csomópontok számának aránya) elemzéseket végzett, úgy tűnik, figyelmen kívül hagyták az aktuális úthossz nyújtotta információt. A heurisztikus keresésbe az aktuális úthosszt is beszámító A^* algoritmust Hart, Nilsson és Raphael dolgozták ki (Hart és társai, 1968), néhány későbbi korrekcióval (Hart és társai, 1972). Az A^* algoritmus optimális hatékonyságát Dechter és Pearl (Dechter és Pearl, 1985) mutatták ki.

Az eredeti A^* algoritmust ismertető cikk bevezette a heurisztikus függvények konzisztenciájának feltételét. A heurisztikák monotonitási feltételét a konzisztenciafeltételnek egy egyszerűbb feltétellel való kiváltására Pohl vezette be (Pohl, 1977), de Pearl megmutatta, hogy a két feltétel ekvivalens (Pearl, 1984). Az A^*-ot megelőző számos algoritmus használta a nyitott és a zárt listával ekvivalens fogalmakat. Ezek közé tartozik a szélességi, a mélységi és az egyenletes költségű keresés (Bellman, 1957; Dijkstra, 1959). Különösképpen Bellman munkája mutatta meg az additív útköltség fontosságát az optimalizálási problémák egyszerűsítésében.

Pohl elsőként tanulmányozta az A^* algoritmus heurisztikahibája és időigénye közötti összefüggést (Pohl, 1970; 1977). Annak bizonyítása, hogy az A^* algoritmus lineáris időben fut, ha a heurisztikus függvény hibája egy állandó korlát alatt van, Pohl és Gaschnig cikkében található (Pohl, 1977; Gaschnig, 1979). Pearl ennek az eredménynek egy erősebb megfogalmazását adta meg, amely megengedte a hiba logaritmikus növekedését (Pearl, 1984). A heurisztikus keresés hatékonyságát jellemző „effektív elágazási tényező” mértéket Nilsson javasolta (Nilsson, 1971).

Az A^* algoritmusnak rengeteg változata létezik. Pohl javasolta a dinamikus súlyozási technikát, amelyben kiértékelő függvényként az A^*-ban használatos egyszerű f(n) = g(n) + h(n) helyett az aktuális úthossz és a heurisztikus függvény alábbi súlyozott összege szerepel: f_w(n) = w_gg(n) + w_hh(n) (Pohl, 1973). Ez a módszer a keresés előrehaladtával dinamikusan állítja a w_g és w_h súlyokat. Kimutatható, hogy a Pohl-féle algoritmus ε-elfogadható – azaz garantálja a megoldás megtalálását az optimális megoldáshoz képest 1 + ε tényezőn belül. Itt ε az algoritmus egy bemeneti paramétere. Ugyanilyen tulajdonságú a A^*_ε algoritmus (Pearl, 1984), amely a perem minden olyan csomópontját kiválaszthatja, amely a perembeli minimális f-költségű csomóponttól f-költségben (1 + ε)-os tényezőn belül van. A kiválasztást úgy lehet lebonyolítani, hogy ez a keresési költségeket minimalizálja.

Az A^* keresési algoritmus és más állapottérben kereső algoritmusok nagyban hasonlítanak az operációkutatás területén elterjedten alkalmazott elágazik-és-korlátoz (branch-and-bound) technikákhoz (Lawler és Wood, 1966). Az állapottérbeli keresés és az elágazik-és-korlátoz algoritmus közötti kapcsolatot részletesen vizsgálták Dana Nau, Laveen Kanal és Vipin Kumar (Kumar és Kanal, 1983; Nau és társai, 1984; Kumar és társai, 1988). Martelli és Montanari megmutatták a kapcsolatot a dinamikus programozás (lásd 17. fejezet) és bizonyos típusú állapottérbeli keresések között (Martelli és Montanari, 1978). Kumar és Kanal CDP – „összetett döntési folyamat” – néven megpróbálta „egységes alapokra hozni” a heurisztikus keresést, a dinamikus programozást és az elágazik-és-korlátoz technikákat (Kumar és Kanal, 1988).

Mivel az 1950-es évek végén, az 1960-as évek elején a számítógépek még csak legfeljebb pár száz szónyi memóriával rendelkeztek, így a memóriakorlátozott keresés már a kezdeti időkben is intenzíven kutatott terület volt. Doran és Michie Graph Traverser programja (Doran és Michie, 1966) az egyik legkorábbi keresőprogram, a memóriakorlát által megengedett mértékben legjobbat-először keresést hajt végre, majd kiválaszt egy operátort. Az IMA^* algoritmus (Korf, 1985a, 1985b) volt az első széles körben alkalmazott optimális, memóriakorlátozott heurisztikus keresési algoritmus; ennek számos változatát ki is dolgozták. Az IMA^* algoritmus hatékonyságának részletes elemzése és az algoritmus valós értékű heurisztikákkal kapcsolatos nehézségeinek tárgyalása a (Patrick és társai, 1992)-ben jelent meg.

Az RLEK (Korf, 1991, 1993) valójában egy kicsit bonyolultabb, mint a 4.5. ábrán bemutatott algoritmus, amely közelebb áll a függetlenül kifejlesztett ún. iteratívan kifejtő (iterative expansion) vagy IK (IE) (Russell, 1992) algoritmushoz. Az RLEK felső és alsó korlátot használ. A két algoritmus viselkedése azonos elfogadható heuriszitikák esetén. Az RLEK azonban a csomópontokat a legjobbat-először sorrendben akkor is kifejti, ha a heurisztika nem elfogadható. A legjobb alternatív út számontartásának gondolata korábban jelent meg Bratkónál (Bratko, 1986) az A^* elegáns Prolog implementációjában és a DTA^* algoritmusban (Russell és Wefald, 1991). Ez utóbbi a metaállapotterekkel és a metaszintű tanulással is foglalkozik.

Az MA^* algoritmus először Chakrabartinál jelent meg (Chakrabarti és társai, 1989). Az EMA^* vagy Egyszerűsített MA^* az MA^* implementációs kísérleteiből született meg, mint az IK egy összehasonlító algoritmusa (Russell, 1992). Kaindl és Khorsand az EMA^* felhasználásával megalkottak egy kétirányú keresési algoritmust, amely jelentősen gyorsabb, mint a korábbi algoritmusok (Kaindl és Khorsand, 1994). Korf és Zhang az oszd-meg-és-uralkodj megközelítést írják le (Korf és Zhang, 2000). Zhou és Hansen pedig bevezették a memóriakorlátozott A^* gráfkeresést (Zhou és Hansen, 2002). Korf áttekintést ad a memóriakorlátozott keresési technikákról (Korf, 1995).

Held és Karp (Held és Karp, 1970) nagy hatású cikke a minimális-feszítőfa alkalmazását (lásd 4.8. feladat) taglalja az utazó ügynök problémára, megmutatva, hogy a relaxált probléma vizsgálatával hogyan lehet elfogadható heurisztikákra jutni.

Prieditis a Jack Mostow-val végzett korábbi kutatásokra építve (Mostow és Prieditis, 1989) sikeresen automatizálta a probléma relaxálási folyamatát (Prieditis, 1993). A mintaadatbázisok használatát az elfogadható heurisztikák előállítására Gasser, valamint Culberson és Schaeffer kezdeményezték (Gasser, 1995; Culberson és Schaeffer, 1998). A diszjunkt mintaadatbázisokat Korf és Felner írják le (Korf és Felner, 2002). A heurisztikák valószínűség-alapú értelmezését Pearl és Hansson és Mayer mélyrehatóan vizsgálták (Pearl, 1984; Hansson és Mayer, 1989).

A heurisztikus keresési algoritmusok messze legátfogóbb irodalma Pearl Heuristics c. könyve (Pearl, 1984). Ez a könyv különösen jó áttekintést nyújt számos oldalhajtásról és az A^* különféle változatairól, és azok tulajdonságainak szigorú bizonyításait is tartalmazza. Kanal és Kumar elkészítették az alapvető és lényeges heurisztikus kereséssel foglalkozó cikkek antológiáját (Kanal és Kumar, 1988). A keresési algoritmusokkal kapcsolatos új eredmények rendszeresen az Artificial Intelligence folyóiratban jelennek meg.

A lokális keresési technikáknak a matematikában és a számítógépes tudományokban hosszú történetük van. Valóban, a Newton–Raphson-módszert (Newton, 1671; Raphson, 1690) egy igen hatékony lokális keresési módszernek lehet tekinteni folytonos terekben, ahol a gradiens információ rendelkezésre áll. Az ilyen információt nem igénylő optimalizáló algoritmusok klasszikus forrása Brent munkája (Brent, 1973). A nyalábkeresés, melyet lokális keresési algoritmusként mutattunk be, a beszédfelismerési célokra alkalmazott dinamikus programozás korlátozott szélességű változataként indult a HARPY rendszerben (Lowerre, 1976). A megfelelő algoritmust részletesen Pearl vizsgálta (Pearl, 1984, 5. fejezet).

A lokális keresés témaköre a nagy kényszerkielégítési problémák, mint például az n-királynő (Minton és társai, 1992) és a logikai következtetés (Selman és társai, 1992) területén elért meglepően jó eredményeknek és a véletlenség, a többszörös egyidejű keresés és más javítás beépítésének köszönhetően az utóbbi években megélénkült. Az ilyen algoritmusok reneszánsza, melyeket Christos Papadimitriou „New Age” algoritmusoknak nevez, felkeltette az elméleti számítógép-tudományokkal foglalkozó kutatók érdeklődését is (Koutsoupias és Papadimitriou, 1992; Aldous és Vazirani, 1994). Az operációkutatás területén népszerűségnek örvend a hegymászó keresés egy változata, amit tabukeresési algoritmusnak (tabu search) hívnak (Glover, 1989; Glover és Laguna, 1997). Az emberi rövid távú memóriamodellre alapozva ez az algoritmus karbantartja az előbb meglátogatott k állapot tabulistáját, melyeket újra meglátogatni nem szabad. Ezáltal az algoritmus hatékonysága megnőtt a gráfkeresésben, és képes egyes lokális minimumokból kimenekülni. A hegymászó keresés másik hasznos javítása a STAGE algoritmus (Boyan és Moore, 1998). Az ötlet az, hogy használjuk a véletlen újraindítású hegymászó keresés révén nyert lokális maximumokat a tájfelszín általános alakjának felderítésére. Az algoritmus a lokális maximumokra sima felületet illeszt, és a globális maximumot analitikusan számítja ki. Ez lesz az új újraindítási pont. Az algoritmus a gyakorlatban működőképesnek bizonyult nehéz problémák esetén. Gomes (Gomes és társai, 1998) azt mutatta meg, hogy a futási idő eloszlása a szisztematikusan visszalépő algoritmusok esetén sokszor lassan lecsengő eloszlás (heavy-tail distribution), ami azt jelenti, hogy a nagyon hosszú futási idők valószínűsége nagyobb, mint amit a normális eloszlás alapján jósolni lehetne. Ez megadja a véletlen újraindítási mechanizmus elméleti igazolását.

A szimulált lehűtést először Kirkpatrick és szerzőtársai írták le (Kirkpatrick és társai, 1983), akik az algoritmust közvetlenül a statisztikus fizika területén összetett rendszerek szimulálására használt Metropolis-algoritmustól kölcsönözték (Metropolis és társai, 1953). A Metropolis-algoritmust állítólag Los Alamosban egy estély során találták ki. A szimulált lehűtés mára már különálló kutatási részterületet alkot, ahol évente több száz cikket publikálnak.

Optimális megoldások keresése folytonos térben több terület alapfeladata, az optimalizálás elméletet, az optimális szabályozás elméletet és a variációkalkulust (optimization theory, optimal control theory, calculus of variations) beleértve. Ezekről alkalmas (és gyakorlati) áttekintést Press (Press és társai, 2002) és Bishop (Bishop, 1995) adnak. A lineáris programozás (LP, linear programming) a számítógépek egyik első alkalmazása volt. A szimplex algoritmust (simplex-algorithm) (Wood és Dantzig, 1949; Dantzig, 1949) még mindig alkalmazzák annak ellenére, hogy a legrosszabb esetben exponenciális komplexitású. Az LP egy gyakorlati polinomiális idejű algoritmusát Karmarkar (Karmarkar, 1984) dolgozta ki.

A genetikus algoritmusok fejlődésének fontos előfutára volt Sewall Wright munkája a fitness tájfelszín (fitness landscape) fogalmáról. Néhány statisztikus, Boxot (Box, 1957) és Friedmant (Friedman, 1959) is beleértve, az ’50-es években használt már evolúciós technikákat optimalizálási problémákra, e megközelítés azonban csak akkor kezdett népszerűvé válni, amikor Rechenberg (Rechenberg, 1965; 1973) az evolúciós stratégiákat (evolution strategies) a szárnyprofilok optimalizálási problémáinak megoldásába bevezette. Az 1960-as és 1970-es években John Holland (Holland, 1975) kiállt a genetikus algoritmusok mellett, azt tartva, hogy a genetikus algoritmusok hasznos eszköznek bizonyulnak és segítenek abban, hogy jobban megértsük a biológiai és egyéb adaptációt (Holland, 1995). A mesterséges élet (artificial life) mozgalom (Langton, 1995) ezt a gondolatot egy lépéssel tovább viszi, a genetikus algoritmusokkal létrehozott eredményeket nem problémamegoldások, hanem inkább szervezeteknek tekintve. Hinton és Nowlan (Hinton és Nowlan, 1987), valamint Ackley és Littman (Ackley és Littman, 1991) munkája ezen a területen sokban hozzá járult, hogy a Baldwin-hatás következményeit feltárjuk. Smith és Szathmáry (Smith és Szathmáry, 1990) munkáját mint az evolúció általános hátterét bemutató munkát ajánljuk.

A legtöbb összehasonlítás a genetikus algoritmusok és más megközelítések (különösképpen a hegymászó keresés) között azt találta, hogy a genetikus algoritmusok lassabban konvergálnak (O’Reilly és Oppacher, 1994; Mitchell és társai, 1996; Juels és Wattenberg, 1996; Baluja, 1997). Az ilyen eredmények a GA közösségben nem nagyon népszerűek, azonban e közösségen belül a legutóbbi olyan kísérletek, hogy a populációalapú keresést a Bayes-tanulás egy formájaként értelmezzük (lásd 20. fejezet) talán segít, hogy e terület és a kritikusai közötti szakadék eltűnjön (Pelikan és társai, 1999). A GA hatékonyságára magyarázatot adhat a kvadratikus dinamikus rendszerek (quadratic dynamical systems) elmélete (Rabani és társai, 1998) is, lásd például Lohn és társainak (Lohn és társai, 2001) a GA antennatervezésre alkalmazott példáját és Larrañaga (Larrañaga és társai, 1999) munkáját, ahol a GA-t az utazó ügynök problémára alkalmazták.

A genetikus programozás (genetic programming) a genetikus algoritmusokkal közeli rokonságban van. Az elsődleges különbség az, hogy a mutált és az összekombinált reprezentációk nem bitfüzérek, hanem programok. A programokat kifejezésfák alakjában reprezentáljuk. A kifejezéseket valamilyen standard nyelvből meríthetjük, mint például a Lispből, de lehetnek egy olyan nyelv elemei, melyet kifejezetten áramkörök, robotszabályozók stb. reprezentálására terveztünk. A keresztezés a részfák és nem a részfüzérek összeillesztését jelenti. A mutáció ezen formája garantálja, hogy az utódok jól definiált kifejezések lesznek, ami nem biztos, hogy sikerülne, ha a programok manipulációját füzérszinten oldanánk meg.

A genetikus programozást övező jelenlegi érdeklődést John Koza (Koza, 1992) munkája váltotta ki, a módszer azonban visszavezethető Friedbergnek (Friedberg, 1958) a gépi kóddal folytatott korai kísérleteihez és Fogelnek (Fogel és társai, 1996) a véges állapotú automatákkal folytatott vizsgálataihoz. Mint a genetikus algoritmusok esetén itt is vita folyik a módszer hatékonyságát illetően. Koza (Koza és társai, 1999) sok olyan kísérletet ír le, amelyeket genetikus programozás felhasználásával az automatizált áramkörtervezés területén végzett.

A genetikus algoritmusokról és a genetikus programozásról az Evolutionary Computation és az IEEE Transactions on Evolutionary Computation folyóiratok írnak. Idevágó cikkeket még a Complex Systems, az Adaptive Behavior és az Artificial Life folyóiratokban is találunk. A legfontosabb konferenciák az International Conference on Genetic Algorithms és a Conference on Genetic Programming, amelyek a közelmúltban Genetic and Evolutionary Computational Conference néven fuzionáltak. A terület jó áttekintését adják Melanie Mitchell és David Fogel írásai (Mitchell, 1996; Fogel, 2000).

Az ismeretlen állapottereket feltáró algoritmusokkal évszázadok óta foglalkoztak. Egy labirintusban való mélységi keresés implementálható például úgy, hogy bal kezünket folyamatosan a falon tartjuk. A hurkokat elkerülhetjük, ha a keresztezéseket megjelöljük. A mélységi keresés kudarcba fullad, ha a cselekvések nem visszafordíthatók. Az Euler-gráfok (Eulerian graphs) (azaz olyan gráfok, ahol minden csomópontban ugyanannyi él megy be, mint ki) feltárásának általánosabb problémáját Hierholzer (Hierholzer, 1873) algoritmusa oldotta meg. A tetszőleges gráfok feltárásának első részletes algoritmikus vizsgálatát Deng és Papadimitriou (Deng és Papadimitriou, 1990) végezték, akik egy teljesen általános algoritmushoz jutattak el, azonban kimutatták, hogy az általános gráf feltárására nem adható korlátos kompetitív arány. Papadimitriou és Yannakakis (Papadimitriou és Yannakakis, 1991) azt a kérdést vizsgálták, hogy hogyan található meg a célhoz vezető út geometriai úttervező környezetben (ahol minden cselekvés visszafordítható). Kimutatták, hogy négyzet alakú akadályok esetén kis kompetitív arány érhető el, az általános téglalap alakú akadályok esetén azonban korlátos arány nem érhető el (lásd 4.19. ábra).

A TRTA^* algoritmust, a valós idejű keresés (real-time search) vizsgálatának részeként olyan környezetekben, ahol az ágensnek cselekednie kell egy rögzített idejű keresést követően (a kétjátékos játékokban egy megszokottabb helyzet) Korf (Korf, 1990) fejlesztette ki. A TRTA^* valójában a megerősítéses tanulási algoritmus egy speciális esete sztochasztikus környezetekben (Barto és társai, 1995). Az optimizmus bizonytalanság melletti stratégiája – mindig a legközelebbi még nem meglátogatott állapotok felé tartani – olyan feltárási mintát eredményezhet, amely a nem informált esetben kevésbé hatékony, mint az egyszerű mélységi keresés (Koenig, 2000). Dasgupta (Dasgupta és társai, 1994) kimutatta, hogy egy kiegyensúlyozott fában a cél megkeresésére, amikor heurisztikus információ nincs, az online iteratívan mélyülő keresés optimálisan hatékony. A TRTA^* számos informált változatát is kifejlesztették, különböző módszereket alkalmazva, a gráf már ismert részein belüli keresésre és frissítésre (Pemberton és Korf, 1992). Egyelőre még nem sikerült megérteni, hogy heurisztikus információ alkalmazása esetén hogyan kell a célokat optimális hatékonysággal megkeresni.

A fejezet azért nem foglalkozott a párhuzamos keresési (parallel search) algoritmusokkal, mert ezek tárgyalásához a párhuzamos architektúrák terjedelmes ismertetésére lett volna szükség. A párhuzamos keresés egyre fontosabb témakörré válik mind az MI, mind pedig az elméleti számítógép-tudomány területén. Egy az MI idevágó irodalmába történő rövid bevezető Mahanti és Daniels cikkében (Mahanti és Daniels, 1993) található.

4.1.

Kövesse végig az A^* működését a Lugasból Bukarestbe utazás problémájára alkalmazva, légvonalban mért távolság heurisztikát alkalmazva. Azaz adja meg az algoritmus által megvizsgált csomópontok szekvenciáját az f-, g- és h-értékükkel együtt.

4.2.

A heurisztikus útalgoritmus (heuristic path algorithm) egy olyan legjobbat-először keresés, ahol a célfüggvény f(n) = (2 – w)g(n) + wh(n). Milyen w értékekre garantálható az algoritmus optimalitása? (Feltételezheti, hogy h elfogadható.) Milyen keresésről van szó, amikor w = 0? Amikor w = 1? És amikor w = 2?

4.3.

Bizonyítsa be az alábbi állításokat:

4.4.

4.5.

A 4.1.1. szakasz - A mohó legjobbat-először keresés részben láttuk, hogy a légvonalban mért távolságheurisztika a mohó legjobbat-először keresést félrevezeti, amikor Iaşiról Fogarasra szerettünk volna eljutni. Az ellenkező problémára azonban, vagyis amikor Fogarasról Iaşira szeretnénk eljutni, a heurisztika tökéletes. Léteznek olyan problémák, amelyek esetében a heurisztika mindkét irányban félrevezet bennünket?

4.6.

Találjon ki a 8-as kirakójátékra olyan heurisztikus függvényt, ami néha túlbecsül, és mutassa meg, hogy egy konkrét probléma esetén ez hogyan vezethet szuboptimális megoldáshoz (használhat számítógépet, ha ez segít). Bizonyítsa be, hogy ha h soha nem becsül túl c-nél jobban, az A^* algoritmus, h-t felhasználva, olyan megoldással tér vissza, melynek költsége az optimális megoldás költségét legfeljebb c-vel haladja meg.

4.7.

Bizonyítsa be, hogy ha a heurisztikus függvény konzisztens, akkor elfogadható. Szerkesszen egy elfogadható heurisztikus függvényt, amely nem konzisztens.

4.8.

4.9.

A 4.2.1. szakasz - A heurisztikus függvény pontosságának hatása a megoldás hatékonyságára részben a 8-as kirakójáték olyan relaxációját definiáltuk, ahol a lapka az A mezőről a B mezőre mozdulhat el, ha B üres. E probléma egzakt megoldása az ún. Gaschnig-heurisztikát (Gaschnig’s heuristics) definiálja (Gaschnig, 1979). Magyarázza meg, hogy miért lesz a Gaschnig-heurisztika legalább olyan pontos, mint h₁ (a rossz helyen lévő lapkák száma), és mutasson olyan eseteket, amikor mind h₁-nél mind h₂-nél pontosabb (Manhattan-távolság). Tud ajánlani a Gaschnig-heurisztikára egy hatékony számítási módszert?

4.10.

4.11.

Nevezze meg azokat az algoritmusokat, amelyek az alábbi speciális esetekből származnak:

4.12.

Néha egy adott problémához nem létezik jó kiértékelő függvény, azonban létezik jó összehasonlítási módszer: vagyis el lehet dönteni, hogy egy csomópont egy másik csomópontnál jobb-e anélkül, hogy valamilyen számértéket rendelnénk hozzájuk. Mutassa meg, hogy ez elégséges a legjobbat-először (best-first) keresés végrehajtásához. Létezik-e ilyen analógia az A^* esetére is?

4.13.

Hozza kapcsolatba a TRTA^* időkomplexitását az algoritmus tárkomplexitásával.

4.14.

Tegyük fel, hogy egy ágens a 4.18. ábrán látható 3 × 3 labirintus környezetben tartózkodik. Az ágens tudja, hogy a kezdeti pozíciója az (1,1), a cél a (3,3)-n van, és hogy a négy Fel, Le, Balra, Jobbra cselekvésnek a szokásos hatása van, hacsak egy fal nincs útban. Az ágens nem tudja a belső falak helyét. Minden egyes állapotban az ágens a legális cselekvések halmazát képes érzékelni. Azt is meg tudja mondani, hogy az állapotot meglátogatta-e már korábban, vagy pedig egy új állapotban van.

Jegyezze meg, hogy ez az eshetőségi terv az adott leírást kielégítő minden lehetséges környezet számára megoldás. A keresés és a végrehajtás átlapolódása tehát egy ismeretlen környezetben nem szigorúan szükséges.

4.15.

4.16.

4.17.

4.18.