Kvantitatív döntéselőkészítési módszerek a logisztikában. Ferenci Tamás

Kvantitatív döntéselőkészítési módszerek a logisztikában Ferenci Tamás [email protected]

Tartalomjegyzék 1. Bevezetés 1.1. Kvalitatív és kvantitatív döntéselőkészítés napjaink üzleti környezetében . . . . . . 1.2. A döntéselőkészítés szintjei és jellemzőik . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Kvantitatív döntéselőkészítési módszerek áttekintése . . . . . . . . . . . . . . . . .

2 2 3 3

2. Statisztikai modellalkotás 2.1. Az ökonometriai feladatok fajtái és kezelésük . . 2.1.1. Keresztmetszeti adatelemzés . . . . . . . 2.1.2. Idősoros adatelemzés . . . . . . . . . . . . 2.2. Az ökonometriai modellek alkalmazási lehetősége

. . . .

5 5 6 7 7

3. Szimuláció, szcenárióelemzés és érzékenységvizsgálat 3.1. Szimuláció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Szcenárióelemzés és érzékenységvizsgálat . . . . . . . . . . . . . . . . . . . . . . . .

9 9 10

4. Metaheurisztikák 4.1. Optimalizálás és a metaheurisztikák . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1. Az optimalizálás fogalma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2. Optimalizálási problémák a logisztikában . . . . . . . . . . . . . . . . . . . 4.1.3. Optimalizálási problémák megoldása, a megoldási módszerek csoportosítása 4.1.4. Mitől meta és mitől heurisztika a metaheurisztika? . . . . . . . . . . . . . . 4.2. Néhány logisztikában is használatos metaheurisztika . . . . . . . . . . . . . . . . . 4.2.1. Lokális keresésen (LS) alapuló metaheurisztikák . . . . . . . . . . . . . . . . 4.2.2. Ant colony optimization (ACO) . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3. Genetikus algoritmus (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 11 12 14 14 18 19 20 25 27

1

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1. fejezet

Bevezetés Ebben a fejezetben pár általános gondolatot tekintünk át döntéselőkészítő módszerek jelentőségével, (változó) szerepével, tipologizálásával kapcsolatban. Mindenhol rámutatunk a kimondottan logisztikához kapcsolódó szempontokra is. Elsőként, az 1.1. pontban rövid áttekintést adunk a döntéselőkészítő módszerek két nagy csoportjának (kvalitatív és a kvantitatív módszerek) változó szerepéről napjaink üzleti környezetében. Az áttekintést a logisztikai terület aktuális jellemzőivel zárjuk. Ezt követően az 1.2. pontban bemutatjuk, immár kifejezetten a logisztikát használva példaként, hogy a döntéseknek milyen szintjei definiálhatóak. A hangsúly azon lesz, hogy megmutassuk: milyen jellemzői vannak az egyes szinteknek, illetve ez hogyan befolyásolja a döntéselőkészítési feladatokat. Végül pedig az 1.3. pontban megismerkedünk azokkal a konkrét kvantitatív döntéselőkészítési módszertanokkal, melyek mostani tárgyalásunk fő tömegét fogják adni. Ebben a pontban természetesen csak áttekintő képet nyújtunk, a részletek ismertetése a következő fejezetek témája lesz.

1.1. Kvalitatív és kvantitatív döntéselőkészítés napjaink üzleti környezetében A vállalati gazdálkodás környezete folyamatosan változik, napjainkban gyorsabban mint bármikor máskor. A turbulens világgazdasági helyzet, a globalizáció, az egyre komplexebb vevői igények, a nemzetközi kereskedelem volumenének növekedése mind ahhoz vezetett, hogy a vállalati gazdálkodás során egyre több, és egyre komplexebb döntést kell meghozni [Chikán, 2008]. Ez két, csak első ránézésre ellentétes tendenciát is indukált. Az egyik a kvalitatív módszertanok intenzívebb kutatása – ez elsősorban a problémák komplexitásának növekedésével van összefüggésben. Egyre több olyan kérdésben kell döntést hozni, mely nehezen és/vagy pontatlanul fordítható csak le számokká, így a XX. század elejére alaposan kiismert kvantitatív módszerek csak korlátozottan alkalmazhatóak. Olyan problémákban, mint a ’make or buy’ dilemma, az üzleti partnerválasztás vagy épp a munkaerő-gazdálkodás, tipikusan nehezen számszerűsíthető, „soft” kérdések kerülnek elő. Ezek mind jobb megválaszolásának igénye vezetett a kvalitatív döntéselőkészítési, döntéstámogatási módszertanok gyors fejlődéséhez a XX. század legvégén és a XXI. században, különösen, mert az üzleti környezet már említett változásaival nagyban felértékelődtek e kérdések. E módszerek ezen felül egyre jobban beszivárognak a korábban „hard”-ként aposztrofált kérdések területére is. Másrészt viszont, a kvantitatív döntéselőkészítés, döntéstámogatás területén is történtek komoly előrelépések. Itt két fő motiváció emelhető ki. Az egyik a modern számítástechnikai lehetőségek megjelenése: nem csak (vagy talán: nem is elsősorban) a probléma konkrét megoldása terén, hanem a formalizás kapcsán. Lehetővé vált egyre több jelenségről egyre több információt gyűjteni (gondoljunk csak a szuper- és hipermarketek kasszáira), megoldhatóvá vált a hatalmas adatbázisok

2

kezelése, karbantartása, lekérdezése. Az új, korábban elképzelhetetlen információs bázis kapcsán természetesen merült fel az igény, hogy döntések megalapozásához használjuk fel tartalmukat. A másik motiváló tényező a döntések (egyre növekvő) számához kapcsolódik: az igény az egyre gyorsabb döntések meghozatalára ahhoz vezetett, hogy a feladatokat – különösen a rutinszerűeket – egységes módszertannal, hatékonyan, objektíven kell kezelni – erre pedig elsősorban a kvantitatív megközelítés alkalmas. Ahogy az előbb is utaltunk arra, hogy vannak jellegzetes területek, ahol jellemzően „soft” kérdések merülnek fel, úgy vannak olyanok, ahol a tipikus a „hard” szempontok alapján történő döntéshozatal. A logisztika számtalan részterülete mai napig ez utóbbi kategóriába tartozik (különösen az egyéb vállalati funkciókkal összevetve). Olyan kérdésekben, mint a telephelyválasztás, kapacitás-meghatározás máig elsődleges, olyanokban pedig, mint a túratervezés vagy a sorozatnagyság-meghatározás, szinte kizárólagos a kvantitatív megközelítés. Könyvünk mostani részében az lesz a célunk, hogy e területről adjunk áttekintést: be kívánjuk mutatni a főbb, logisztikában (is) használatos kvantitatív döntéselőkészítési módszereket. Mindezek előtt azonban érdemes még megismerkedni egy másik tipologizálással: a különböző döntési szintek specifikumaival a döntéselőkészítési módszerek szempontjából.

1.2. A döntéselőkészítés szintjei és jellemzőik Amint könyvünk már máshol is hangsúlyoztuk, a döntéshozatalhoz kapcsolódó feladatok (így a döntéselőkészítési munka is) nagyban eltér aszerint, hogy milyen szintű döntésről van szó. A „szint” fogalma alatt továbbra is a szokott, stratégiai–felsővezetői nézőpont szerinti megközelítést értjük. A legfelső szintet a logisztikai rendszer kialakítása és működtetése „feletti” döntések jelentik, ide elsősorban a ’make or buy’ dillemma, azaz a kiszervezés kérdése tartozik. Erre jellemző, hogy – miközben erős kvantitatív alapjai is vannak, elsősorban a költség/haszon elemzések révén – itt jelennek meg a leginkább a kvalitatív, „soft” szempontok. Számos olyan kérdés merül fel (goodwill, reputáció, ellátásbiztonság, kiszolgáltatottság stb.), melyek nem, vagy csak nagyon nehezen számszerűsíthetőek, így e téren gyakori a kvalitatív módszerek, illetve a szimulációs-, HA/AKKOR jellegű vizsgálatok alkalmazása. A rendelkezésre álló információk ezen a szinten általában erősen aggregáltak. Rátérve most már a logisztikai rendszer kialakításával és működtetésével kapcsolatos döntésekre (ezek immár funkcionális vezető hatáskörébe tartozó döntések – most feltételeztük, hogy a logisztikai rendszert házon belül valósítjuk meg), a felső szintet – a teljesítménycélok kijelölése után – a strukturális döntések jelentik. Ide tartozik a disztribúciós struktúra kialakítása, a telephelyválasztás (adott esetben a szállítási mód megválasztása is), vagy például a kapacitás-meghatározás (ezen belül kiemelten: a raktárkapacitás meghatározása). Ezekre jellemző, hogy már sokkal több kvantitatív elemet tartalmaznak (távolságok, keresletek, költségek stb.), de még mindig jelentős a kvalitatív szempontok szerepe (ellátsábiztonság, munkaerő jellemzői stb.). A rendelkezésre álló információk itt már részletesek, csak kevés esetben kerül aggregált információ felhasználásra. Végül pedig az utolsó szintet a működtetési döntések jelentik. Döntéselőkészítési szemmel ránézve, ide tartozik például a kereslet-előrejelzés, a DRP, a készletgazdálkodás, az útvonaltervezés, de adott esetben akár létszám-tervezés is. Ezek legfontosabb közös jellemzője, hogy jellemzően tisztán vagy szinte tisztán kvantitatívok; a kvantitatív módszertanok alkalmazásának tipikus példáit jelentik. A rendelkezésre álló információ szinte mindig részletezett. Most pedig nézzük meg kicsit már közelebbről, hogy mik lesznek azok a módszerek, amik a fenti problémák kezelésére alkalmasak!

1.3. Kvantitatív döntéselőkészítési módszerek áttekintése A döntéselőkészítési munka kvantitatív ága is számos módszert alkalmaz. Mi most hármat fogunk részletesebben is tárgyalni; kettőnél inkább csak áttekintést adunk, és utalunk a szakirodalomra, a harmadikat (a metaheurisztikákat) viszont mélységében is ismertetni fogjuk. (Ennek oka, hogy

3

míg az előbbi kettő a magyar nyelvű irodalomban is alaposan tárgyalt, addig ez utóbbival jóval kevesebben foglalkoztak, különösen a logisztikai alkalmazásokat tekintve.) Az első tárgyalt módszer a statisztikai modellezés lesz (2. fejezet). Ez vegytisztán kvantitatív módszer: akkor alkalmazható, ha a döntés szempontjából releváns információk számszerűsíthető formában rendelkezésre állnak. A statisztikai úton történő modellalkotás során tipikusan múltbeli információkat felhasználva próbálunk vagy összefüggéseket feltárni, vagy jövőre vonatkozó előrejelzéseket készíteni. Ehhez természetesen az is szükséges, hogy azonosítsuk a kérdés szempontjából releváns változók körét, és mérhetővé tegyük őket (operacionalizálás). Sokszor azonban a jelenségek olyan bonyolultságúak, hogy nem lehet szigorú analitikus modellt adni. Ilyenkor jöhet szóba a szimuláció alkalmazása (3. fejezet). A különféle Monte Carloszimulációs eljárások a sztochasztikus kérdéseknél jelenthetnek nagyon jó eszközt, akkor, ha a probléma bonyolultsága olyan, hogy az egzakt, analitikus megoldás lehetetlen, vagy nagyon nehézkés. Tipikusan ez a helyzet akkor, ha a vizsgált jelenségről van egy jól működő, de bonyolult struktúrájú modellünk (pl. egy folyamat lépéseinek bizonytalanságait valószínűségi változókkal írjuk le, és az egész folyamat teljesítményének jellemzőire vagyunk kíváncsiak). Ide sorolhatjuk továbbá a HA/AKKOR típusú szcenárióelemzéseket és érzékenységvizsgálatokat is. Végül pedig, egész tárgyalásunk leghangsúlyosabb pontját a metaheurisztikák fogják jelenteni (4. fejezet). Eltérően az előbbi kettőtől, ezek optimalizációs módszerek; jellemzőjük, hogy számos különféle problémára alkalmazhatóak, mégpedig úgy, hogy közelítően pontos, de cserében gyors választ adjanak. A legtöbb ilyen metaheurisztika az optimalizálás utóbbi pár évtizedben megjelent, modern eszköze, mely elválaszthatatlanul kötődik a számítástechnikai lehetőségek kibővüléséhez. Amint említettük is, a metaheurisztikák egyik fő jellemzője, hogy számos problémára alkalmazhatóak – ez alól a logisztika optimalizációs jellegű feladatai sem jelentenek kivételt. Mivel magyar nyelvű irodalomban metaheurisztikákról általában is keveset lehet olvasni, logisztikai alkalmazásaikról pedig végképp, így ezt a módszertant az előbbieket messze meghaladó részletességgel fogjuk tárgyalni. Elsőként bemutatjuk az optimalizációval kapcsolatos általános megfontolásokat (4.1. pont), majd négy jellemző metaheurisztikát (szimulált lehűtés, tabu keresés, genetikus algoritmusok, ant colony optimization) részleteiben is bemutatunk (4.2. pont). Külön ki fogunk térni mindegyiknél a logisztikai alkalmazásokra is.

4

2. fejezet

Statisztikai modellalkotás A gazdasági döntések támogatása, a gazdálkodás és gazdasági élet jelenségeinek vizsgálata a statisztika korai (és fontos) alkalmazásai közé tartozik. A fontosságot jelzi az is, hogy az ezzel foglalkozó tudományágnak külön neve van: azt a területet, mely társadalmi-gazdasági jelenségek statisztikai modellezésével foglalkozik, ökonometriának szokás nevezni. (Ami pedig a korai alkalmazást illeti, megjegyzendő, hogy Ragnar Frisch – a későbbi első közgazdasági Nobel-díjas – már a ’30-as évek elején megalkotta az ’ökonometria’ kifejezést.) Az ökonometria tisztán kvantitatív adatokat használ fel közvetlenül; ez azonban nem jelenti azt, hogy kvalitatív („soft”) szempontokat ne lehetne statisztikai modellekben felhasználni – ehhez azonban szükségünk van arra, hogy azokat is számszerűsíteni tudjuk. Ökonometriai modellezéshez először azonosítani kell a problémánk szempontjából releváns változókat, meg kell határozni a mérésük módját (ez utóbbit szokás operacionalizálásnak nevezni), majd begyűjteni a szükséges empirikus adatokat. (A változók köre a vizsgált kérdésből tárgyterületi ismeretek alapján határolható be; elméleti kutatásoknál nagyon gyakran valamilyen kutatási hipotézis adja.) A modellezéshez felhasznált adatok jellege alapján jól elkülöníthető csoportokba sorolhatóak az ökonometriai modellek, erről a 2.1. pontban lesz szó. Itt fogunk röviden a felhasznált statisztikai eszközökről is beszélni. Mindezek mellett fel kell állítanunk valamilyen modellt, mely leírja a változók közötti összefüggéseket. Az ökonometriai modellek jellemzően az algebrai modellek közé tartoznak, tehát a változók közötti kapcsolatot különféle egyenletek (illetve a változókra vonatkozó megkötések) adják. Az empirikus adatok birtokában lehetséges a modell megbecslése (tehát az ismeretlen paramétereinek konkrét értékeket kereshetünk a minta alapján). Ezzel azonban még nem ért véget az ökonometriai munka: a modelleket tesztelni, diagnosztizálni kell, hogy valóban megfelelnek-e azoknak a feltételeknek, melyekre a becslési eljárások támaszkodtak. Adott esetben ez egy iteratív folyamatot indíthat el, melynek során újraspecifikáljuk a modellt, újra diagnosztizáljuk stb. míg végül egy korrekt modellhez nem jutunk. Csak ezt követően kerülhet sor a modell alkalmazására. Arról, hogy egy ökonometriai modellt hogyan alkalmazhatunk, a 2.2. pontban lesz részletesebben szó. Ebben a fejezetben nem adunk részletes logisztikai példákat, elsősorban azért nem, mert e módszerek alkalmazása olyan széleskörű, mindent átható, hogy a legtöbb feladatnál előkerülnek így vagy úgy. Ehelyett utalunk az irodalomra: a magyar nyelvű könyvek közül [Maddala, 2004]-et és [Ramanathan, 2003]-at, az angol nyelvűek közül [Wooldridge, 2009]-et emeljük ki.

2.1. Az ökonometriai feladatok fajtái és kezelésük Az ökonometriai feladatok két jellegzetes csoportba sorolhatóak aszerint, hogy milyen jellegű adatokat kell felhasználnunk. Az egyik eset, ha az adatok különböző megfigyelési egységek adott időpontbeli állapotára vonatkoznak. (A megfigyelési egységeknek jellemzően persze több változóval vannak leírva.) Például

5

több vállalat disztribúciós rendszerére vonatkozó adatokat (felépítés és teljesítmény) ismerünk, és keressük köztük az összefüggést. (Az adatokat úgy értve, hogy – legalábbis eszmeileg – ugyanazon időpillanatra vonatkoznak, pl. 2013. január 1-én érvényes állapota az egyes vállalatok disztribúciós rendszereinek.) Ezt az esetet szokták keresztmetszeti adatelemzésnek nevezni, mi a 2.1.1. pontban fogunk vele foglalkozni. (Az elnevezés szemléletes: mintha minden vállalat adatainak alakulását (az időben) egy sor írná le és mi ezeket „keresztben” elvágnánk.) A másik lehetőség, hogy csak egyetlen változót figyelünk, de azt több időszakon keresztül. Például egyetlen vállalat disztribúciós teljesítményét vizsgáljuk, de egy több éves időszakon keresztül nézzük az alakulását. Ezt szokás idősoros adatelemzésnek nevezni. (Precízen szólva, ha tényleg csak egy változónk van, ez az ún. egyváltozós idősorelemzés.) Mi a 2.1.2. pontban fogunk ezzel foglalkozni. Végül két megjegyzés. Az egyik, hogy a fenti két esetet inkább csak az alkalmazási oldalról, a szemléletesség kedvéért választjuk el ilyen élesen; statisztikai szempontból nincs hatalmas különbség. (Olyannyira, hogy némelyik könyv egységes keretben tárgyalja a kettőt; megjegyezve, hogy csak abban van különbség, hogy a keresztmetszeti esetben a megfigyelési egységek sorrendje közömbös, idősoros modellnél viszont rendezés van rájuk érvényesítve.) A másik megjegyzésünk, hogy lehetséges a két modell kombinálása is, azaz egyszerre több megfigyelési egységet vizsgálni, több időszakon keresztül. Ezt az esetet szokás panelnek nevezni, ennek ökonometriai módszereivel itt egyáltalán nem foglakozunk.

2.1.1. Keresztmetszeti adatelemzés A keresztmetszeti adatelemzés legfontosabb eszköze a regresszió. Általában a regresszió alatt egy y = f (x1 , x2 , . . . , xp ) típusú függvénykapcsolatban az f függvény meghatározását értjük, melyhez adottak az (y, x1 , x2 , . . . , xp ) változók összetartozó értékeire vonatkozó megfigyelések (a minta). Például y jelöli egy vállalat disztribúciós rendszerének teljesítményét (jól látszik, hogy itt már az operacionalizálás sem egyszerű kérdés: hogyan lehet ezt egyetlen számmal leírni?), az x1 , x2 , . . . , xp változók pedig a disztribúciós rendszer felépítésére vonatkozó különböző leírók (raktárak fajtái és száma, használt járművek fajtái és száma, távolságok stb.). A kérdés tehát ez esetben úgy fogalmazható meg köznapilag: milyen kapcsolatba hozható a disztribúciós rendszer teljesítménye a felépítését leíró különféle jellemzőkkel. . . ? (A megválaszoláshoz több cég ugyanazon időpontra vonatkozó tényadatai állnak rendelkezésre a fenti változókról.) Így már az is érthető, hogy miért szokás y-t eredmény-, x1 , x2 , . . . , xp -ket pedig magyarázóváltozónak nevezni. Legtöbbször paraméteres regressziót használunk, azaz f függvényformáját leírjuk, csak épp ismeretlen paraméterekkel. Ennek a legnépszerűbb esete a lineáris regresszió, ekkor: f (x1 , x2 , . . . , xp ) = β0 + β1 x1 + β2 x2 + . . . + βp xp + ε. Itt a feladat a β0 , β1 , . . . , βp együtthatók megbecslése a minta alapján. Ez azért is népszerű módszer, mert a fenti együtthatóknak nagyon jól használható tárgyterületi értelmezésük lesz: βi azt fogja kifejezni, hogy ha az i-edik magyarázó változó értéke 1 egységgel nagyobb lenne (úgy, hogy ezen kívül minden mást változatlanul tartunk), akkor modellünk szerint várhatóan mennyivel változna az eredményváltozó értéke. Például, ha az i-edik magyarázó változó a raktárak száma, akkor βi azt fejezi ki, hogy eggyel több raktár modellünk szerint várhatóan mennyivel változtatja a disztribúciós rendszer teljesítményét. A feladat megoldására több módszer is létezik, aszerint, hogy a ε tagra milyen tulajdonságok teljesülnek. A legnépszerűbb a közönséges legkisebb négyzetek (OLS, ordinary least squares) módszere, mely azokat az együtthatókat fogja visszaadni becslésként, melyekkel az eredményváltozóra adható becslések a legközelebb vannak az eredményváltozó tényleges értékeihez a mintán. (A „közelséget” összesített négyzetes eltéréssel mérve.) A módszer előnye, hogy szemléletes, és bizonyos feltételek teljesülése esetén bizonyíthatóan nagyon előnyös statisztikai tulajdonságú becsléseket ad. E feltételek ellenőrzése a modelldiagnosztika már emlegetett feladatának a része. Megjegyezzük, hogy a módszer kiterjesztésével kezelhetőek azok az esetek is, amikor egy magyarázó változó nem folytonos (dummy változók használata), sőt, az is, amikor az eredményváltozó

6

kategoriális (logisztikus regresszió). Ez utóbbira példa lehet egy olyan feladat, melyben valamely valamely fuvareszköz használatának szükségességét (igen/nem!) hozzuk kapcsolatba a disztribúciós rendszer jellemzőivel. A fenti függvényformát ki lehet bővíteni úgy is, hogy nemlineáris esetek is kezelhetőek legyenek. Ezeknek az egyszerűbb esetei (ún. változóiban nemlineáris modellek) nem igényelnek lényeges bővítést a becsléselméleti oldalon.

2.1.2. Idősoros adatelemzés Az idősoros adatelemzés során egy jelenség időbeli alakulását vizsgáljuk. A legegyszerűbb eset az egyváltozós idősorelemzés, ekkor egyetlen változónk van, melyre különböző időpontokban vett megfigyelésekkel rendelkezünk. Lehetséges például – folytatva az előző pontot – hogy ez a változó valamely vállalat disztribúciós rendszerét írja le egy szempontból (pl. teljesített tonnakilométerek havonta) – tehát már csak egy vállalatról (és nem többről) van szó, viszont a vizsgált változót több időszakon keresztül megfigyeltük (és nem csak egyetlen időpillanatban). Az idősorelemzés egyik megközelítése az ún. determinisztikus idősorelemzés. Ebben feltételezzük, hogy az idősor alakulását néhány tényező függvényszerűen leírja (azaz e tényezők ismeretében az idősor alakulása pontosan meghatározható lenne), „véletlenséget” csak azért látunk az idősorban, mert nem tudunk minden tényezőt teljeskörűen és pontosan számbavenni. A determinisztikus idősorelemzés tipikus módszere, hogy meghatározza az idősor trendjét (hosszútávú alapirányzatát), az esetleges ciklusait és szezonalitását. A trend vizsgálatára alkalmazhatóak különféle analitikus eszközök, pl. paraméteres trendek (lineáris, négyzetes stb.) illesztése; ennek révén képet kapunk arra, hogy várhatóan milyen irányzat mentén alakul az idősor hosszú távon. Egy egyszerű lineáris trend esetén pl. a meredekségi paraméter megadja – az előbbi példánál – hogy havonta mennyivel nő vagy csökkent a teljesített tkm-ek száma. Fontos, hogy ez csak az alapirányzat: a fenti (ún. dekompozíciós) modellben figyelembe lehet venni az éven túli ingadozásokat (ciklicitás) és a jellegzetes éven belüli ingadozásokat (szezonalitás) is. Ez utóbbiak nagy jelentőségűek lehetnek: egy szezonális keresletű terméket (is) előállító vállalatnál nagyon is elképzelhető, hogy a teljesített tkm-ek száma a hónap vagy negyedév szerint hasonló mintázatú eltérést mutat minden évben (pl. az első negyedévben kevesebb a napernyő szállításának teljesítménye az adott évi alaphoz képest). Determinisztikus eszközökkel ez kezelhető; egy rendelkezésre álló minta alapján meghatározható pl. a szezonális eltérés minden negyedévre. A másik fő idősorelemzési iskola a sztochasztikus idősorelemzés. Ennek lényege, hogy többé már nem feltételezi, hogy legfeljebb gyakorlatilag nem, de elvileg megismerhető tényezők függvénye az idősor: abból indul ki ezzel szemben, hogy a véletlen tényezőknek folyamatépítő szerepük van. (Nem csak a tényleges és a becsült értékek adott időszaki eltéréséért felelnek.) Úgy is szokták mondani, hogy ez a modell feltételezi, hogy az idősor alakulásában öngeneráló hatások érvényesülnek: az idősor korábbi értékei, illetve a korábbi eltérései a becsült és a tényleges értékeknek befolyásolják, hogy az idősor hogyan alakul a jövőben. E filozófia legalapvetőbb modelljei az ún. ARIMA-modellek, melyek becslésének leghíresebb szisztematikus módszertana a Box–Jenkins-eljárás.

2.2. Az ökonometriai modellek alkalmazási lehetősége Minden ökonometriai modell alapvetően két célra használható fel: elemzésre és előrejelzésre. Az elemzés lényege, hogy a modell becsült paramétereit valamilyen tárgyterületi értelemmel ruházzuk fel. (Ilyen módon egyúttal a felmerülő gazdasági kérdéseket is megválaszolva.) Például lineáris regresszió esetén a magyarázó változók βi paraméterei megadják, hogy minden mást változatlanul tartva az adott magyarázó változó 1 egységgel nagyobb értéke esetén modellünk szerint várhatóan mennyivel nő vagy csökken az eredményváltozó. Ezáltal kvantitatíven megválaszolhatjuk az arra vonatkozó kérdéseket, hogy pl. adott tényező egy disztribúciós rendszer struktúrájában milyen kapcsolatban van annak teljesítményével. Hasonló példát idősoros elemzésből is hozhatunk: említettük, hogy lineáris trendnél a meredekség megadja az alapérték éves változásának nagyságát.

7

A másik felhasználás az előrejelzés. Ez nem más, mint eredményváltozó becslése egy olyan megfigyelési egységre, melynek csak a magyarázóváltozóit ismerjük, de az eredményváltozóját nem (tehát nem szerepel a mintában). Például 100 cég adatai alapján felállítjuk a modellt a disztribúciós rendszer jellemzői és teljesítménye közötti kapcsolatra, majd ezt arra használjuk, hogy egy 101. cégnél, melynél a teljesítményt nem, de a disztribúciós rendszerének jellemzőit ismerjük, megbecsüljük a disztribúciós teljesítményt. (Amint látható az „előrejelzés” szó itt nem olyan értelmű mint az időjárás-jelentésben: nem feltétlenül a jövőre vonatkozik. Egyszerűen azt értjük alatt, hogy eredményváltozót becslünk pusztán magyarázóváltozók ismeretében, felhasználva a már megbecsült modellt.) Idősorelemzésnél azonban ez a szó köznapi értelmében is előrejelzést jelent: ha van egy felparaméterezett modellünk (maradva az ottani példánál), akkor vele megbecsülhetjük, hogy adott időszakban milyen teljesítmény várható.

8

3. fejezet

Szimuláció, szcenárióelemzés és érzékenységvizsgálat Ebben a fejezetben három, részben rokonítható témával fogunk foglalkozni, melyek közös jellemzője, hogy sokkal kevésbé kvantitatívak, mint a statisztikai modellalkotás. Foglalkozunk a szimulációval (3.1. pont), valamint a szcenárióelemzéssel és az érzékenységvizsgálattal (3.2. pont). E módszerek részint kevésbé analitikusak (főleg a szimuláció és az érzékenységvizsgálat), részint inkább támaszkodnak „soft” szempontokra (főként a szcenárióelemzés). Amint már előre is bocsátottuk, ezekkel csak nagyon röviden, inkább csak említés szintjén foglalkozunk; a részleteket illetően viszont mindenhol utalunk a szakirodalomra.

3.1. Szimuláció A szimuláció alkalmazása olyan elterjedt egy sor területen (nagyon is beleértve a logisztikát is), hogy itt inkább csak pár példa felvillantására szorítkozhatunk. Szimulációt általában olyankor használnak, ha rendelkezésre áll valamilyen modell a jelenségre, de annak belső struktúrája túl bonyolult ahhoz, hogy analitikus eszközökkel vizsgálat tárgyává tehető legyen. Nagyon sokszor ez úgy valósul meg, hogy a modell sok – önmagában nem feltétlenül nagyon bonyolult – rész-modellből áll össze (adott esetben bonyolult struktúrában). Ilyenkor sokszor nem, vagy csak nagyon kényelmetlenül lehet analitikus eredményeket származtatni az egész modellre, de kényelmesen kaphatunk eredményeket szimulációs úton. Ennek jobb megértése érdekében nézzük egy konkrét példát! Adott egy disztribúciós rendszerünk olyan módon, hogy tudjuk mik az egyes komponensei (raktárok, fuvareszközök stb.), illetve van egy viselkedési modellünk (mikor, hová, milyen és mennyi árut kell továbbítani, mi történik várakoztatás esetén stb.). E modellek természetesen tipikusan sztochasztikus komponenseket is tartalmaznak (pl. adott fuvar végrehajtása nem konstans idő, hanem egy adott eloszlást követő valószínűségi változó). Ebben az esetben a rendszer teljesítménye (pl. egy kiszállítási idő eloszlása) elvileg ugyan vizsgálható analitikusan (a rendszer minden részének a viselkedése pontosan, determinisztikusan, ismert!), mégis ez sokszor rendkívül kényelmetlen. Ezzel szemben nagyon könnyen megtehető, hogy számítógépen „végrehajtunk” egy képzeletbeli kiszállítást: amikor fizikai árueljuttatás történik, annak idején a megfelelő eloszlást követő véletlenszám-generátorral számítjuk ki, a termék raktárbeli sorsát úgy határozzuk meg, hogy követjük a magatartási szabályokat stb. Végül kapunk egy kiszállítási időt – ez egy realizáció lesz a kiszállítási idő (most még ismeretlen) eloszlásából. Ezen a ponton kihasználhatjuk azt a tényt, hogy egy ilyen szimulált kiszállítás villámgyorsan „végrehajtható” számítógépen: a szükséges véletlenszám-generálások, szabály-kikeresések és -követések stb. a mai számítástechnikai lehetőségek mellett a másodperc törtrésze alatt lefuttathatóak. Nincs tehát semmi akadálya annak, hogy több százezer, vagy akár millió ilyet hajtsunk

9

végre – ennyi realizációból pedig már szinte tökéletesen rekonstruálható a keresett eloszlása a kiszállítási időnek. Látható, hogy a módszer hátránya, hogy erre az eloszlásra nem kapunk analitikus megoldást (tehát pl. nem lesz ismert formulával leírva), de számos gyakorlati feladat szempontjából a numerikus ismerete is tökéletesen elégséges. Néhány ilyen példa a logisztika területéről: kapacitás tervezése és optimalizálása konténerterminál számára [Legato–Mazza, 2001], konténerműveletek tervezése kikötőkben [Ramani et al, 1996], egész ellátási lánc tervezése [Busato–Berruto, 2008] és újratervezése [Vorst et al, 2009], reverz logisztikai hálózat tervezése [Kara et al, 2007], termeléstervezés [Li et al, 2009].

3.2. Szcenárióelemzés és érzékenységvizsgálat E két módszer közös annyiban, hogy mindkettő alternatív helyzeteket vet össze és elemez. A szcenárióelemzés a kvalitatívabb módszer, melyben a kutató első feladata felvázolni a vizsgált feladat szempontjából releváns, szóba jövő eshetőségeket. Ezek az eshetőség általában nem csak apró módosításokban térnek el egymástól, hanem lényegileg más helyzetet vetnek fel (pl. best-case és worst-case alakulása a makrogazdasági környezetnek). Ezen eshetőségek (ún. szcenáriók) meghatározása után a kutató mindegyikben külön-külön végigköveti a történéseket (valamilyen alkalmas módszerrel), majd az egyes végeredményeket összeveti egymással, kiértékeli. Ezzel a módszerrel sok esetben reálisabb képet lehet kapni mint önmagában az alapeseti elemzéssel, hiszen arról is lesz információnk, hogy a várttól eltérő környezeti jellemzők esetén milyen eredmény várható. Az érzékenységvizsgálat hasonlít a szcenárióelemzésre, két lényeges, összefüggő eltéréssel: érzékenységvizsgálatnál általában csak egyetlen (vagy legfeljebb néhány) paraméter értékét módosítjuk (nem az egész környezetre feltételezünk lényegileg más helyzetet), cserében viszont arra nem csak néhány eshetőséget vizsgálunk, hanem az összeset. Ez utóbbi úgy értendő, hogy kiszámítjuk a paraméter minden lehetséges (reális) értékére az elemzés kimenetét; ez az érzékenységvizsgálat legfőbb eredménye. Sokszor előfordul, hogy nem, vagy csak nagyon kényelmetlenül határozható meg analitikusan ez az összefüggés, természetesen ekkor használható szimuláció (3.1. pont) is! Ez itt azt jelenti, hogy a paraméter adott értéke mellett kiszámítjuk az elemzés kimenetét, majd ezt megismételjük nagyon sok különböző paraméter-értékre; így rekonstruáljuk az összefüggést a paraméter értéke és az elemzése eredménye között. Látható, hogy az érzékenységvizsgálat a kvantitatívabb módszer: általában azt feltételezzük, hogy a vizsgált paraméter numerikus (sokszor folytonos). Szcenárióelemzésben ezzel szemben lehetőség van „soft” szempontok érvényesítésére is, hiszen saját magunk vázolhatunk fel forgatókönyveket (így, általában), tehát nem csak paraméterek értékeinek állítására vagyunk korlátozódva. E két módszerrel kapcsolatban nem hivatkozunk tanulmányokra, hiszen – mint az a fentiekből is adódik – nem önmagukban használatosak, hanem más módszerek (beleértve a többi itt bemutatottat) kiegészítőjeként, azok erejét, robusztusságát fokozandó.

10

4. fejezet

Metaheurisztikák Ebben a fejezetben a logisztikai folyamatok modern tervezésében nagy szerepet játszó számítógépes optimalizációs eljárásokról, a metaheurisztikákról lesz szó. A metaheurisztikák alkalmazása lehetővé teszi, hogy gazdaságilag nagy jelentőségű optimalizációs problémákat oldjunk meg olyan területeken, mint a termeléstervezés, termelésellátás, telephelyválasztás vagy épp a disztribúció. A 4.1. pontban általában mutatjuk be ezt a területet. A fokozatos bevezetés kedvéért először magával az optimalizációval, mint matematikailag formalizálható gyakorlati problémával foglalkozunk, majd bemutatjuk (konkrét kérdések kapcsán), hogy az optimalizáció miért nagyon fontos kérdés a logisztikában. (Ez az általános ismerkedés az optimalizációval azért is fontos, mert – mint már utaltunk is rá – az eddig bemutatott módszerek nem célirányosan optimalizációsak.) Ezt követően foglalkozunk az optimalizációs problémák csoportosításával és megoldási módszereikkel, végül e csoportok közül kiemeljük és részletesen bemutatjuk mostani központi témánkat, a metaheurisztikákat. Ezt követően a 4.2. pontban néhány konkrét, logisztikai alkalmazások szempontjából fontos metaheurisztikát mutatunk be, jellegük szerint csoportosítva. Mindegyik metaheurisztikánál bemutatjuk alapötletüket, tipikus alkalmazási területeiket, erősségeiket, gyengeségeiket és a működésük alapvonalait is. Külön hangsúlyt fektetünk rá, hogy logisztikai alkalmazásaikra konkrét, irodalmi hivatkozásokkal is alátámasztott példákat is hozzunk. A metaheurisztikákba jó általános bevezetést nyújtanak, jellemzően a 4.2. pontban bemutatott konkrét algoritmusokat is ismertetve, a [Gendreau–Potvin (eds.), 2010], [Talbi, 2009] és [Luke, 2009] művek.

4.1. Optimalizálás és a metaheurisztikák Ebben a pontban bevezetjük az optimalizálás fogalmát (4.1.1. alpont), és alaposan körüljárjuk azt, hogy a metaheurisztikák helye, célja és értelme világos legyen. A későbbieket motiválandó, mutatunk is pár konkrét logisztikai kérdést (4.1.2. alpont), melyek megoldása optimalizálási problémára vezet. Az optimalizálás szó köznapi értelme („ jobb helyzet elérése jó döntések révén”) alapján megmutatjuk, hogyan lehet ezt a fogalmat formálisan megragadni, utána áttekintjük az optimalizálási módszereket. Természetesen eggyel sem fogunk részleteiben foglalkozni, most a célunk az, hogy ezek csoportosítása, kategóriái (és jellemzőik) áttekinthetőek legyenek (4.1.3. alpont). Ezt követően megmutatjuk, hogy a metaheurisztikák osztálya hol található, milyen közös jellemzőik vannak, milyen céllal alkalmazzuk őket (4.1.4. alpont).

11

4.1.1. Az optimalizálás fogalma Az optimalizálás 1 (optimization) kifejezést széleskörűen használják mind a tudományos-, mind a köznyelvben. Ez utóbbiban általában olyasmit értenek alatta, mint „a legjobb helyzet elérése”. Kicsit precízebben: olyan helyzetben, ahol valamiféle választási, döntési lehetőség van, a legjobb lehetőség kiválasztása. Ilyen értelemben beszélnek például egy utazás útvonalának optimalizálásáról (azaz, olyan útvonal megválasztásáról, hogy az útidő, üzemanyag-felhasználás stb. a legkisebb legyen), egy ház szigetelésének az optimalizálásáról (azaz, annak eléréséről, hogy a fűtési költség, zaj stb. a legkisebb legyen), pénz befektetésének optimalizálásáról (azaz olyan befektetési lehetőségek kiválasztásáról, hogy például a hozam a legnagyobb legyen) stb. A szó tudományos értelme lényegében ennek a formalizált megragadása. Az optimalizálási problémának két fő összetevője van. Az egyik döntési lehetőségek egy halmaza (jelölje X), melynek – mint halmaznak – az xi ∈ X elemei az egyes lehetséges döntések. Az előző bekezdés első példájában például lehet x1 = Vasút, x2 = Busz, x3 = Repülő, azaz X = {Vasút, Busz, Repülő}. A másik összetevő egy függvény (jelölje f ), általában célfüggvénynek vagy kritériumfüggvénynek szokás nevezni, mely az egyes lehetőségekhez (azaz X elemeihez) egy kiértékelést rendel, ez tipikusan egy valós szám2 , mely az adott lehetőség jóságának (vagy épp károsságának) a mértékét jelzi. (Precízen megfogalmazva tehát: f egy X-en ható függvény, általában f : X → R.) Ha például az értékelési szempont az útidő rövidsége, akkor könnyen elképzelhető a következő helyzet: f (x1 ) = 3, f (x2 ) = 2, f (x3 ) = 10. Az f – áttételesen – a preferenciáinkat ragadja meg, számszerűsített formában. A feladat az, hogy megkeressük: a döntési lehetőségek közül, a kiértékelések alapján, melyik a legjobb döntés, illetve, hogy ezzel milyen (legjobb) kiértékelést tudunk elérni. Ez utóbbi problémát röviden így foglalhatjuk össze matematikailag: max f (x) , x∈X

azaz keressük f (x) (a lehetséges kiértékelések) maximumát, midőn x végigfutja az összes szóbajövő alternatívát. A példánkban maxx∈{Vasút,Busz,Repülő} f (x) = 10, a fenti kiértékelő-függvény (útidő rövidség) alapján. (Az x-et szokás döntési változónak is nevezni.) Figyeljük meg, hogy a max kifejezés magát az optimális függvény-értéket (és nem az optimum felvételének a helyét) adta meg! Ez utóbbit arg max-szal fogjuk jelölni, így tehát az optimális döntés kiválasztásának problémáját a következőképp írhatjuk le matematikailag: arg max f (x) , x∈X

azaz keressük azt az x ∈ X lehetséges választást, mely mellett f (x) maximális. A példánkban tehát maxx∈{Vasút,Busz,Repülő} f (x) = Repülő lesz. Két megjegyzést fűzünk a fentiekhez. Az egyik, hogy nagyon gyakran a függvény-értéket nem maximalizálni, hanem minimalizálni kell. Jellemzően akkor találkozunk maximálizálási feladattal, ha a célfüggvény jóságot mér (profitot, megelégedettséget, ellenőrzésen megfelelt termékek arányát stb.), ilyenkor hasznosság-függvények is szokás nevezni, minimalizálásival pedig akkor, ha a célfüggvénnyel károsságot (veszteséget, elégedetlenséget, selejtarányt stb.) mérünk, ilyenkor szokás költség-függvénynek is nevezni. Ez utóbbi esetben max és arg max helyett min és arg min írható, ám ez nem jelent lényeges kibővítést: minden minimalizálási feladat felírható maximalizálásiként (és viszont), ugyanis max f (x) = − min [−f (x)] x∈X

x∈X

1A

magyar nyelvben néha az optimálás kifejezést használják, ám tartalmilag ugyanerre. Mi most az optimalizálás szót fogjuk alkalmazni. 2 Érdekes helyzet, ha a lehetőségeket nem egy szempont szerint értékeljük, ekkor ugyanis – ezt többszempontú döntéshozatalnak is nevezik – az egyes szempontok szerinti értékelések egymással ellentmondásba is kerülhetnek. (Tipikus példa egy autó árának és teljesítményének egyidejű optimalizálással.) Ezzel most nem fogunk a későbbiekben foglalkozni.

12

és arg max f (x) = arg min [−f (x)] . x∈X

x∈X

Azaz: egy függvény ott veszi fel maximumát, ahol az ellentettje a minimumát, és a kétféle optimum egymás ellentettje. Ez intuitíve is elég kézenfekvő: a {3, 2, 10} maximuma ott van, ahol a {−3, −2, −10} minimuma (harmadik elem) és a kettő érték épp egymás ellentettje (10 és −10). Mi most a továbbiakban mindig maximalizálási problémára fogunk gondolni, ha mást nem mondunk. A másik megjegyzés, hogy nagyon gyakran az alaphalmazt nem közvetlenül adjuk meg, hanem úgy mint egy nagyobb halmaz része: megadunk egy nagyobb halmazt, és rajta egy korlátozást, mely kijelöli a döntési lehetőségek halmazát. Például a gépkocsink v sebességét 40 és 70 km/h között választhatjuk meg. Ekkor a döntési lehetőségeket formálisan így írhatjuk fel: v ∈ [40, 70], azaz a v döntési változó eleme a [40, 70] zárt intervallumnak. Ehelyett ezt is mondhattuk volna: v ∈ R (azaz v egy valós szám), de úgy, hogy v ≥ 40 és v ≤ 70. Az optimalizálási probléma az első esetben: max f (v) , v∈[40,70]

míg a másodikban max f (v) v∈R

feltéve, hogy v ≥ 40, v ≤ 70. Nyilvánvaló, hogy a kettő teljesen ugyannak a problémának a felírása, csak másként megfogalmazva. Itt nincs is lényeges különbség a kettő között, azonban más esetekben (ha a korlátozásokból nem lehet, vagy nem érdemes meghatározni közvetlenül a döntési halmazt) nagyon is eltérő kezelést igényelhet a két eset. Az elsőt, amikor magát a döntési halmazt adjuk meg mindenféle korlátozás nélkül, feltétel nélküli optimalizálásnak (unconstrained optimization) is szokás nevezni, míg a második az ún. feltételes optimalizálás (constrained optimization). A fentiekben az ún. egydimenziós optimalizálást (one-dimensional optimization) írtuk le, melyben egyetlen döntési változónk van (x), egyetlen halmazzal, melyből veheti az értékeit (X). Gyakran nem ez a helyzet, és egyszerre több kérdésben is döntést kell hozni (pl. milyen járművel utazzunk, és mikor induljunk), ekkor többdimenziós optimalizálásról (multidimensional optimization) szokás beszélni. Az előbbi példában lehet döntési 1 ∈ X1 =  változó a jármű (x {Vasút, Busz, Repülő}) és az indulás időpontja (x2 ∈ X2 = Reggel, Délután, Éjjel ). Ez egy kétdimenziós optimalizálási feladat, hiszen a lehetséges alternatívákat az X1 × X2 halmaz elemei között keressük, esetleg korlátozással. Ezt a halmazt szokás keresési térnek is nevezni. (Itt a ×-tel jelölt direkt szorzat jelenti a két halmaz elemeinek összes lehetséges kombinációját, tehát 
X1 × X2 = (Vasút, Reggel) , (Vasút, Délután) , . . . , Repülő, Éjjel .) Az általános n-dimenziós optimalizálási feladatban n döntési változónk van (x1 , x2 , . . . , xn ), mindegyikhez saját tartomány, azaz hozzá tartozó döntési halmaz (X1 , X2 , . . . , Xn ). Ekkor a keresési tér az X1 × X2 × . . . × Xn (esetleg megkötésekkel), a kiértékelő függvény pedig f : X1 × X2 × . . . × Xn → R. (Tehát azt továbbra is feltesszük, hogy az egyes alternatívák egyetlen valós számmal jellemezhetőek (pl. f (Busz, Reggel) = 2,5), csak már több döntési változótól függenek.) Az optimalizálási problémák fontos megkülönböztető szempontja, hogy az X halmaz hány értéket vehet fel. Ha csak véges sokat (pl. X a magyarországi megyeszékhelyek halmaza), vagy legfeljebb megszámlálhatóan sokat (pl. X a természetes számok halmaza) akkor összefoglalóan diszkrét optimalizálásról (discrete optimization) szoktunk beszélni. (Ezen belül az előbbi esetet, amikor csak véges sok döntési lehetőségünk van, szokták kombinatorikus optimalizálásnak (combinatorial optimization) nevezni, az utóbbihoz hasonló problémákat pedig egészértékű programozásnak (integer programming) hívják.) Amennyiben X ennél nagyobb, végtelen számú elemből áll (ennek legegyszerűbb példája, amikor X a valós számok R halmaza), akkor folytonos optimalizálásról (continuous optimization) van szó. 13

Néha folytonos optimalizálási feladatokban X1 = X2 = . . . = Xn = R (azaz minden döntési változó egy valós szám lehet), ekkor a keresési tér épp Rn (azaz a valós számokból képezett n hosszúságú vektorok tere), esetleg megkötésekkel. Sokszor könnyíti a megértést az ilyen többdimenziós problémáknál is, ha a feladatot grafikusan képzeljük el. Célszerű a valós számokra és a kétdimenziós esetre (optimalizálás R2 -en) gondolni: a döntési változókat képzeljük el úgy, mint földrajzi koordinátákat (azaz az alternatívák különböző földrajzi pozíciókat jelentenek), a keresési tér legyen mondjuk Magyarország területe, a célfüggvény pedig a tengerszint feletti magasság. Ekkor a feladat nem más, mint megtalálni a Kékest, az optimális célfüggvény-érték pedig 1014.

4.1.2. Optimalizálási problémák a logisztikában Még mielőtt továbbmennénk, bemutatunk pár tipikus logisztikai kérdést, melyek optimalizálási problémára vezetnek. A lenti felsorolást semmiképpen sem szánjuk teljesnek, pusztán motivációt kívánunk szolgáltatni a későbbiekhez pár példa felvetésével. (Érdemes mindegyiknél végiggondolni, hogy mi a döntési lehetőségek halmaza, és mi a kiértékelő célfüggvény!) Termeléstervezés Milyen sorozatnagyságot válasszunk? Milyen input-kombinációt használjunk fel a termeléshez? Milyen feladatokra bontsuk a termelési folyamatot? Az egyes feladatokat hogyan rendeljük hozzá a rendelkezésre álló gépekhez? A munkaerőt hogyan osszuk be az egyes műszakokba? stb. Készletgazdálkodás Mekkora készletet tartsunk az egyes termékekekből? Mikor rendeljünk újra, és mennyit? stb. Disztribúció Milyen eszközt használjunk fel a disztribúcióhoz? Hogyan válasszuk meg a jármű útvonalát? Hogyan válasszuk meg a jármű közlekedtetésének időpontjait? Hogyan válasszuk meg a kiszállított áruk körét? Hová telepítsünk raktárat, gyárat és mekkora legyen a kapacitása? stb.

4.1.3. Optimalizálási problémák megoldása, a megoldási módszerek csoportosítása A matematika több ága is foglalkozik optimalizálási problémákkal; megoldásukra számtalan módszer alakult ki. A legegyszerűbb eset középiskolás eszközökkel kezelhető, pl. a maxx∈R x2 + 3 probléma két deriválással és egy egyenletmegoldással teljeskörűen megoldható. (A helyzet akkor sem lesz lényegesen bonyolultabb, ha a problémát feltételessé tesszük a keresési tér megszorításával, csak ekkor a lehetséges tartomány határpontjait is meg kell vizsgálni.) A gyakorlati feladatok szempontjából az egyik legfontosabb problémaforrás, ha a függvény explicit alakja nem ismert, kezelhetetlenül bonyolult, vagy egyéb okból nem lehetséges a deriváltjait előállítani, és megkeresni, hogy az hol váltanak előjelet. Természetesen a derivált legrosszabb esetben is közelíthető: ha mást nem is tudunk, legalábbis a célfüggvényt mindenhol ki kell tudnunk értékelni, így egy adott pont környezet empirikusan „feltérképezhető”. Ezen a gondolaton nyugszanak az ún. lokális keresésen (local search) alapuló megoldások: kiindulnak egy adott pontból, és a pont környezetét felderítve továbblépnek egy – valamilyen szempont szerint – jobb pontba, majd onnan folytatják az optimalizálást. Erre a legegyszerűbb példa a gradiens keresés (gradient ascent/descent) vagy legmeredekebb emelkedő módszere, mely egy adott pontból mindig abba az irányba lép, amerre a célfüggvény a legnagyobb meredekséggel emelkedik, azaz javul. (Hogy mekkorát kell lépni ebbe az irányba, az már egy külön kérdés.) Ehhez hasonló módszer a hegymászó keresés (hill climbing), mely szintén a legmeredekebb lejtő irányába lép, csak épp egyszerre csak egyetlen döntési változót változtatva. (Szemben a gradiens módszerre, mely akár az összes változó értékét módosíthatja egy lépésben.) Úgy is fogalmazhatnánk, hogy a gradiens módszer akármilyen irányba léphet, a hegymászó keresés csak a térkép valamelyik szélével párhuzamosan. Ennek megfelelően a hegymászó keresés hátránya, hogy egy térképen átlósan elhelyezkedő szűk

14

2.5

2.0

1.5

1.0

0.5

0.2

0.4

0.6

0.8

1.0

4.1. ábra. A lokális optimumba ragadás problémájának szemléltetése völgyben „ide-oda fog pattogni” a völgy két fala között, szemben a gradiens kereséssel, mely egyből megmászná a völgy oldalát. A gradiens keresésnek is van azonban hátránya a hegymászó kereséssel szemben: fenti formájában a deriváltak ismeretét igényli. Egy gyakorlati szempontból nagyon fontos példa arra, amikor ez nem áll fenn, az az eset, amikor a döntési változó diszkrét és nem folytonos (például a telephely pozícióját nem számszerű koordináták jelölik ki, hanem a szóba jövő városok név szerinti felsorolása). Ilyenkor nincs is értelme gradiens keresésről beszélni, azaz csak a hegymászó keresés jöhet szóba. Mindkét módszer közös problémája azonban az ún. lokális maximumba ragadás jelensége. Az igaz ugyan, hogy mindkét módszer, ha megáll, akkor olyan pontban áll meg, ahonnan semmilyen irányba lépve sem javítható a célfüggvény értéke, azonban ez még nem jelenti azt, hogy ténylegesen a legjobb pontban vagyunk! A térképes példánkkal élve: ha elindítjuk a gradiens keresést Budapestről, az jó eséllyel a Gellért-hegy tetején fog megállni (és valóban: onnan egyetlen irány sincs, amerre lépve javulna a célfüggvény, azaz magasabbra kerülnénk), mégsem találtuk meg a keresett optimumot, vagyis a Kékest. Az olyen típusú optimumot, mint a Gellért-hegy, ami csak a saját kis környezetében a legjobb választás, lokális optimumnak szokás nevezni, míg a feladat ténylegesen keresett megoldását globális optimumnak. (Nyilvánvaló, hogy a globális optimum egyben lokális optimum is, és hogy a globális optimum a lokális optimumok közül a legnagyobb.) Azt a feladatot, amikor a globális optimumot, tehát az egész keresési térben vett legjobb célfüggvény-értéket keressük, globális optimalizálásnak (global optimization) nevezzük. Látható tehát, hogy a gradiens keresés és a hegymászó keresés általában nem jó globális optimalizálásra. Mindezeket a 4.1. ábra szemlélteti. A feladat az, hogy a berajzolt függvény értékének maximumát megtaláljuk a [0, 1] intervallumon. Az világos, hogy az „igazi” (tehát: a globális) optimum a bal oldalon, 0,3-nál látható érték, ám az egyszerű gradiens keresesés, ha kb. 0,6-nál, vagy annál nagyobb értéktől indítjuk, a jobb oldalon látható csúcsot fogja megtalálni, oda fog konvergálni a keresés. A gradiens keresés számára ugyan ez a 0,9-nél látható érték a végpont, ott megáll (hiszen nem tud semerre sem javítást hozó irányba továbblépni), ám valójában ez csak egy lokális maximum – a keresés tehát beragadt egy lokális optimumba. (Az ábrán a zöld és piros sávok jelzik, hogy egy adott pontból indítva a gradiens keresést, az a globális optimumot találja-e meg, vagy csak a lokálisat.) A gyakorlatban jelentkező problémák másik fő forrása a korlátozások megléte többdimenziós esetben. Önmagában a többdimenziós optimalizálás még nem nagy probléma, ha a függvény ismert, igaz, ekkor már haladóbb eszközökre van szükség. (Deriváltak helyett parciális deriváltakat kell használni, és a második deriváltra vonatkozó egyszerű előjel-teszt helyébe – minimum – a Hesse-mátrix determinánsának vizsgálata lép.) A gond az, hogy ha korlátozó feltételek is adva vannak, akkor a keresési tér határai nem megszámlálható sok pontot jelentenek (mint egydimenziós esetben), hanem egész felületeket, rajtuk végtelen sok ponttal, így ezeket nem lehet egyszerűen

15

csak „egyesével leellenőrizni”. Bizonyos speciális esetekre szerencsére létezik könnyen kézbentartható megoldás. Erre a legismertebb példa az, ha a célfüggvény lineáris a döntési változókban (azaz f (x1 , x2 , . . . , xn ) = c1 x1 + c2 x2 + . . . + cn xn alakú, ahol c1 , c2 , . . . , cn ∈ R valós konstansok), és a megkötések is mind lineárisak (azaz a1i x1 + a2i x2 + . . . + ani xn ≤ bi alakúak, ahol b1 , b2 , . . . , bn ∈ R valós konstansok). Ez az ún. lineáris programozás (linear programming) alapfeladata, melynek megoldására gyakorlatban nagyon jól bevált algoritmus létezik (Dantzig szimplex algoritmusa 1947-ből), sőt, létezik olyan algoritmus is, mely bizonyosan nagyon előnyösen függ a probléma méretétől (a változók és a megkötések számától), azaz a futásidő nem nő túl drasztikusan a probléma növekedtével (Karmarkar algoritmusa 1984-ből). A fentiek mind ún. determinisztikus optimalizálási (deterministic optimization) eljárások voltak, hiszen a bemenet alapján matematikailag előre meghatározható műveleteket hajtanak végre, az egyetlen kérdés, hogy ehhez mennyi időre van szükségük. És épp ez a determinisztikus algoritmusok fő problémája: bizonyos feladatok esetében ez kivárhatatlanul hosszú lenne (vagy nem is biztos, hogy eredményre vezetne). Érdekes módon erre már olyan példát is lehet hozni, ahol a keresési tér nem is végtelen, tehát csak véges sok alternatíva közül3 kell a legjobbat kiválasztani, és mégis bajban vagyunk a determinisztikus algoritmusokkal. (Az tehát triviális, hogy ez miért kezelhető determinisztikus algoritmussal: egyszerűen exhausztíve végignézzük az összes4 lehetőséget; ezt szokás brute-force keresésnek („nyers erő módszere”) vagy kimerítő keresésnek is nevezni.) Legyen példának okáért ugyanis a probléma a következő: adott n város, és köztük (minden pár között) a távolságok. A feladat megadni egy olyan végigjárási sorrendjüket (minden várost érintve), tehát egy olyan körutat, hogy az összesen megtett út a legrövidebb legyen. (Ez az ún. utazó ügynök (TSP, Travelling Salesman Problem) probléma.) A keresési tér tehát itt egy olyan halmaz, ami a lehetséges végigjárási sorrendeket tartalmazza – ez egy véges halmaz, hiszen n várost n! számú sorrendben lehet elvileg felkereseni. Ez azonban elképesztően gyorsan nő n-ben, így determinisztikus optimalizálással (minden lehetséges sorrendet végigpróbálva) már n = 30 körül is kivárhatatlanul hosszú lenne a megoldás ideje, akármilyen gyors számítógépet is használnánk. (A feladat még egy szempontból érdekes. Bár a fenti megoldás (minden lehetséges sorrend végigpróbálása) nyilván csak egy determinisztikus algoritmus a lehetséges sok közül, és valóban adható ennél hatékonyabb algoritmus is (ún. dinamikus programozással), jelenlegi tudásunk szerint elvileg sem létezhet olyan determinisztikus algoritmus, ami a problémát kivárható idő alatt megoldja. Javítani tehát lehet az algoritmust, de jelenlegi tudásunk szerint soha nem lehet kivárható idejűvé tenni.) Ezzel a kérdéssel a számítástudomány bonyolultságelméletnek nevezett területe foglalkozik. Jelenlegi tudásunk alapján léteznek olyan problémák (ún. NP-teljes, illetve általában, NP-nehéz problémák), melyekre elvileg sem létezik minden esetben bizonyosan jó megoldást szolgáltató, és mégis, a probléma méretének növekedetével semmiképp sem nagyon lelassuló megoldási módszer. Pont az ilyen „kivárhatatlan” esetek léte vetette fel a gondolatot, hogy a problémát ne a determinisztikus algoritmusok javítgatásával próbáljuk megoldani, hanem valamilyen drasztikusan más megközelítéssel. Egy lehetőség, ha a feladatot valamilyen véletlenség beiktatásával oldjuk meg. Hogy mutassunk erre egy egyszerű példát, menjünk vissza a gradiens kereséshez. Amint ott láttuk, a módszer hátránya, hogy könnyen lokális optimumba ragadhat. Módosítsuk most a módszert úgy, hogy elsőként véletlenszerűen választunk egy pontot a keresési téren, elindítjuk onnan a gradiens keresést, és feljegyezzük, hogy hová értünk, majd ezt sokszor megismételjük (mindannyiszor véletlenszerűen választott kiindulási pontból). Vegyük észre, hogy ezzel a módszerrel kiküszöböljük az egyszerű gradiens keresés hátrányát; a példánknál maradva, előbb vagy utóbb elindítjuk az algoritmust a Mátra közeléből. 3 Tehát, a már bevezetett definícióval élve: kombinatorikus optimalizálási feladatról van szó. Az érdekesség kedvéért megjegyezzük, hogy a XX. század közepén, a számítógépek döbbenetes ütemű kezdeti fejlődését látva, sokan úgy gondolták, hogy az ilyen problémák tudományosan érdektelenek lesznek, hiszen „majd a gép végigpróbálgatja a megoldásokat”. A következő feladat épp arra világít rá, hogy ez miért nem lett így, és miért jelent a kombinatorikus optimalizálás a mai napig igen intenzíven kutatott területet. 4 Megjegyzendő, hogy bizonyos esetekben ennél azért eljárhatunk ügyesebben is, ennek klasszikus példái a „szétválasztás és korlátozás” (branch and bound) elvű algoritmusok, melyek a keresési teret több részre bontják (szétválasztás) úgy, hogy meg tudják mondani, hogy melyikben lehet a keresett optimum és melyikben nem (korlátozás), ezért a keresést csak a kisebb, szóba jövő részben folytatják tovább.

16

A 4.1. ábra példáját tekintve: annak a valószínűsége, hogy egy, [0, 1]-en véletlenszerűen választott pontból indított keresés a globális optimumot találja meg, kb. 58,4%. (Ennyi a zöld csík hosszának aránya az egész keresési térhez képest.) Ez tehát azt jelenti, hogy 41,6% valószínűséggel csak lokális optimumot találunk. Igen ám, de ha kétszer futtatjuk le a keresést (mindkétszer egymástól függetlenül, véletlenszerűen választott kezdőpontból), akkor már csak abban az esetben nem találjuk meg az igazi (globális) optimumot, ha pechünkre mindkétszer a piros csíkból indulunk. Ennek a valószínűsége már csak 0,4162 = 17,3%, azaz két indításból már 82,7% valószínűséggel megtaláljuk az igazi optimumot is. Általában is, annak a valószínűsége, hogy k indításból meglesz az igazi optimum 1 − 0,416k (ez pl. k = 10-re már 99, 98%). Másrészt viszont, ezt a módszert alkalmazva, többé már nem tudunk biztosat mondani a keresésről. Ha például megállapodás szerint mindig a döntési változók egy adott, kitüntetett értékéből indítjuk a gradiens keresést, akkor az, hogy hová fogunk megérkezni, egy meghatározott pont (legfeljebb idő kell, amíg megtaláljuk). A fenti módszerrel ezt fel kell adnunk: az, hogy a kereséssel hová fogunk jutni, azon is múlik, hogy milyen véletlen pozíciókat generálunk a keresés újraindításához, azaz egy véletlenszerű, általunk nem befolyásolható tényezőn. Ez olyannyira igaz, hogy még arról is csak véletlen kijelentést tehetünk, hogy az algoritmus mennyire működik jól: csak annyit tudunk mondani, hogy minél tovább futattjuk, annál jobb megoldást találunk, sőt, ebben a konkrét esetben az is elmondható, hogy ha a futási idő tart a végtelenhez, akkor a globális optimum megtalálásának a valószínűsége tart az 1-hez. (Ezért is írtuk azt az előző bekezdés végén, hogy „előbb vagy utóbb”.) A 4.1. ábra példáján precízen így fogalmazhatunk: limk→∞ 1 − 0,416k = 1. (Ez nyilván mindig 1 lesz, mindaddig, amíg a rossz terület aránya (itt most 0,416) 1-nél kisebb szám – csak épp, minél kevéssel kisebb, annál lassabban tart ez a függvény az 1-hez.) Ám véges időtartam után legfeljebb valószínűségekben beszélhetünk a helyes megoldás megtalálásáról. Az iyen, véletlenséget felhasználó módszereket összefoglalóan sztochasztikus optimalizálásnak (stochastic optimization) nevezzük. A fent példaként bemutatott módszer neve egyébként véletlenszerű újraindításos hegymászó keresés (random restart hill climbing), a legegyszerűbb sztochasztikus optimalizálási módszerek egyike. A sztochasztikus optimalizálás tehát nem ad feltétlenül jó megoldást, de van egy hatalmas előnye: egyáltalán lehetővé teszi a megoldást! Ha ugyanis a függvényt analitikusan nem ismerjük, akkor az egzakt optimum pontos megtalálása elvileg csak kimerítő kereséssel lett volna lehetséges – ez folytonos esetben elvileg is végtelen idő lenne, de diszkrét esetben – azaz kombinatorikus optimalizálásnál – is kivárhatatlan a legtöbb gyakorlati esetben. Ezzel szemben a sztochasztikus optimalizálás nagyon is belátható idő alatt ad eredményt; az előbbi fejtegetésből pedig még az is látható, hogy jellemzően nem is rosszabbat. Általában is igaz, hogy a sztochasztikus optimalizálási módszerek használatával egyfajta kompromisszumot kötünk: • Elfogadjuk, hogy a kapott megoldás nem feltétlenül, garantáltan az egzakt optimum, csak annak – reményeink szerint nem rossz – közelítése. . . • . . . de cserében a futási idő sokkal rövidebb. Az eddigi fejtegetésekből már világos, hogy ez miért lesz vonzó számos gyakorlati probléma esetében (gondoljunk az NP-teljes feladatokra, ahol az egzakt optimum bizonyosan csak kivárhatatlanul hosszú idő alatt lenne megtalálható). A sztochasztikus optimalizálási módszereknek a gyakorlatban még két előnye szokott előkerülni. Az egyik a robusztusság: ha a keresési tér nem egyszerű matematikai eszközökkel adott, hanem zajos, bizonytalan, pontatlan, hiányosan leírt stb. (ami mérnöki problémáknál előfordul), a sztochasztikus módszerek sokszor még ez esetben is tűrhető teljesítményt nyújtanak (szemben egy sor determinisztikus módszerrel, amelyek nagyon gyorsan teljesen használhatatlanná válnak ilyen körülmények között). A másik előny, hogy a sztochasztikus módszerek általában meglehetősen egyenletesen derítik fel a keresési teret, így túl korán megállítva őket is van remény nem nagyon szuboptimális megoldás megkapására. (Több olyan probléma van, ahol a determinisztikus algoritmusok kifejezetten gyenge eredményt adnak egészen az igazi optimum elérésének közvetlen közelségéig.) 17

Fontos, hogy a sztochasztikus optimalizálást ne keverjük össze azokkal a módszerekkel, melyeknél a modell paraméterei tartalmaznak bizonytalanságot. Ilyen optimalizálási problémák is léteznek ugyanis, például kifejezendő a valós feladatokban sokszor meglévő ismerethiányt, mérési hibát stb., lehetnek például egy lineáris programozási feladatban a célfüggvény együtthatói konkrét számok helyett valószínűségi változók. Az ezt megoldó egyik módszer az ún. sztochasztikus programozás, azonban ennek semmi köze a fenti sztochasztikus optimalizáláshoz, ez egy nagyon is determinisztikus eljárás, csak épp konkrét számok helyett valószínűségi változókon dolgozik. (Néha azonban, kissé megtévesztő módon, ilyenkor is sztochasztikus optimalizálásról szoktak beszélni.)

4.1.4. Mitől meta és mitől heurisztika a metaheurisztika? A sztochasztikus optimalizálási módszerekkel tehát feladjuk a megoldási menet (és emiatt persze az egzakt megoldás elérésének ismerete) feletti biztos ismeretet, cserébe a gyorsabb végeredményelérésért. Ez egyáltalán nem irracionális: a TSP példája azt mutatja, hogy bizonyos esetekben a pontos megoldás megkeresése kivárhatatlan időt jelent, így ekkor egy nem biztosan jó (de elég jó) eredményt szolgáltató, de cserébe kivárható idő alatt lefutó algoritmus teszi – gyakorlati szempontból – egyáltalán lehetővé a megoldást. A metaheurisztikák kifejlesztését épp a bonyolultságelmélet ’70-es évekbeli fejlődése, a már említett NP-teljes problémák jobb megértése motiválta: ekkor vált világossá, hogy vannak problémák, amikre nem csak azért nincsen általában is kivárható idejű megoldást szolgáltató algoritmus, mert még nem találtunk ki ilyet, hanem nem is várható, hogy ilyen létezzen. Így tekintve a kérdést viszont az a fontosabb, hogy minél gyorsabb és, noha közelítő, de legalább minél jobb közelítést adó algoritmusokat találjunk. A heurisztika szó eredetileg épp az ilyen gondolkodásmód leírására szolgált: nem bizonyíthatóan mindig jó, de az esetek többségében azért elfogadható közelítést adó megoldási módszer. Ezek általában tapasztalatokon, intuíción alapulnak; például egy tipikus heurisztika: „ha vörös az ég alja naplementekor, tiszta idő lesz”. (Ez valóban heurisztika, és nem városi legenda, ugyanis a jelenségre létezik természettudományos magyarázat.) Mindazonáltal nyilvánvaló, hogy közel sem beszélhetünk mindig biztosan működő algoritmusról ez esetben – ám cserében összehasonlíthatatlanul könnyebben és gyorsabban ad eredményt, mint mondjuk egy pontosabb, de csak számítógéppel megoldható időjárási modell. (Szokták a köznyelvben is azt mondani az ilyenre, hogy „heurisztikus gondolkodásmód”.) Így már világos, hogy miért alkalmazzák a gyorsan dolgozó, de csak közelítő eredményt adó algoritmusokra a heurisztika elnevezést. (Mellesleg az is igaz, hogy sok esetben ezek tényleg valamilyen intuitív ötleten, gyakorlatban bevált fogás leképezésén alapulnak.) Mondunk egy másik, immár optimalizálási példát is a heurisztika fogalmára. A már bemutatott TSP-feladat megoldására szolgáló egyik heurisztika így szól: ha már van egy részkörútunk (azaz olyan körút, ami nem minden várost tartalmaz, vannak meg nem látogatott városok), akkor bővítsük a körutat a hozzá legközelebb eső meg nem látogatott várossal úgy, hogy a körút hozzá legközelebb eső meglátogatott városából nem annak körút szerint rákövetkező városába lépünk, hanem előbb átlépünk ebbe a meg nem látogatott városba, majd utána lépünk a rákövetkező meglátogatott városba, lényegében tehát „teszünk egy kitérőt”. Ezzel kapunk egy eggyel több várost tartalmazó részkörutat; mindezt addig folytatjuk, míg végül az utolsó várost is bevonjuk, és az így kapott utat fogjuk visszaadni megoldásként. (E stratégia neve: legközelebbi szomszéd heurisztika.) Ez egy heurisztika: semmilyen garancia nincs nem hogy arra, hogy a kapott út optimális lenne, de még arra sem, hogy mennyivel lehet rosszabb a kapott út mint az optimum (nem tudunk tehát olyat mondani, hogy legfeljebb 10%-kal vagy 20%-kal stb. eredményez hosszabb utat ez az algoritmus egy adott problémára, mint annak optimuma). Valóban, bebizonyítható, hogy bizonyos értelemben tetszőlegesen rosszabb út kapható, mint az optimum, sőt, kellően rafináltan olyan patologikus példát is lehet konstruálni, amin a legközelebbi szomszéd heurisztika konkrétan a legrosszabb (leghosszabb) utat adja vissza megoldásként. . . Mégis, általában ez az algoritmus jól teljesít: ha a pontok véletlenszerűen helyezkednek el a síkon, akkor igazolható, hogy mintegy 25%-kal ad csak rosszabb megoldást, mint a – csak drasztikusan lassabban kiszámolható – optimum. Tehát nagyon sok gyakorlati esetben ugyan némileg szuboptimális útvonalat ad vissza, de egyrészt nem nagyon szuboptimálisat (csak kicsit), másrészt ezt szinte összehasonlíthatatla18

nul gyorsabban teszi, mint amennyi idő alatt a pontos optimum megtalálható. Így nem meglepő, hogy a gyakorlatban sokszor jóval többet ér egy ilyen heurisztika, mint a kivárhatatlan pontos optimum-keresés. A meta kifejezés általában az éppen vizsgált tárgyszint fölötti szintre, magasabb absztrakciós szintre utal. Nagyon gyakran egy fogalom alkalmazása saját magára, vagy a saját csoportjának egy másik elemére; ilyen értelemben beszélhetünk például metamatematikáról (magának a matematikának a tanulmányozása matematikai eszközökkel), metatudásról (a tudásról magáról szerzett tudásunk), metanyelvről (egy nyelvet leíró nyelv) stb. A metaheusztika szóban ezt egy kicsit más értelemben5 használják: nem heurisztikák fölötti heurisztika, hanem problémák fölötti heurisztika, mégpedig olyan értelemben, hogy a metaheurisztika több különböző problémára is alkalmazható heurisztika. Vegyük példának az előzőekben ismertetett legközelebbi szomszéd heurisztikát! Ez ugyan jó szolgálatot tesz TSP-feladatok megoldására, ám a „mindig a legközelebbi szomszédot iktassuk be a körútba” tanács nem sokra használható például készletgazdálkodási feladatok megoldásában. . . Ezzel szemben, a 4.2. pontban bemutatandó heurisztikák többféle, gyakran teljesen különböző tartalmú feladatok megoldására is használhatóak. Ezt úgy érik el, hogy általános „recepteket” tartalmaznak optimalizálási feladatok megoldására, és nem konkrétan egy adott probléma kontextusára építenek. Nem használnak fel nagyon problémaspecifikus elemeket (mint a fenti heurisztikánál a körút, a legrövidebb út keresése, pont távolsága stb.), más szóval kevés vagy szinte semmi előfeltevéssel nem élnek a megoldandó problémára vonatkozóan. Így számtalan problémára alkalmazhatóak lényegi módosítás nélkül. (Megjegyzendő, hogy ez, bár nagyon kényelmes, de cserébe természetesen némileg korlátozza a teljesítményt is (egyfajta trade-off jelentkezik), ezért az igazán nagyteljesítményű problémamegoldásnál be szoktak a metaheurisztikákba is vinni problémaspecifikus elemeket, „testreszabják” őket az épp megoldandó feladatra.) Összefoglalva tehát arra, hogy mi a metaheurisztika, nem tudunk egyetlen, univerzálisan elfogadott definíciót adni: az irodalomban sokféleképp meghatározták már ezt a fogalmat. Mégis, ha valamilyen meghatározást, körülírást kéne adnunk, akkor az, a tulajdonságainak a hangsúlyozásával, a következőképp hangozhatna: metaheurisztikáknak nevezzünk a sztochasztikus optimalizáció nem-problémaspecifikus (sok különböző probléma megoldására alkalmazható, a probléma kapcsán kevés előfeltevést használó), általában csak közelítő, nem garantáltan optimális eredményt adó, de cserében gyors (elfogadható futásidő alatt elfogadható pontosságú közelítést adó) módszereit.

4.2. Néhány logisztikában is használatos metaheurisztika Ebben a pontban bemutatunk pár népszerű, logisztikai feladatok megoldásában is gyakran használt metaheurisztikát. Először két, lokális keresésen alapuló metaheurisztikát ismertetünk (4.2.1. alpont), a szimulált lehűtést (SA) és a tabu keresést (TS). Ezt követően két népszerű, nem lokális keresésen alapuló metaheurisztikát, az ant colony optimization-t (ACO) és a genetikus algoritmusokat (GA) mutatjuk be. Az egyes eljárások ismertetésénél bemutatjuk a módszer alapgondolatát, tárgyaljuk a legfontosabb működési kérdéseket is, de a technikai részletekbe nem megyünk bele. Nagy hangsúlyt fektetünk arra is, hogy mindegyik módszernél idézzünk, ha csak példálózó jelleggel is, logisztikai alkalmazásokat. Fontos észbentartani, hogy nincs „tökéletes” metaheurisztika, annál is inkább, mert az, hogy egy adott feladat megoldására mi a jó metaheurisztika, a feladattól is függhet (és persze azon, hogy mit értünk jó alatt). „Nincs ingyenebéd”: nincs olyan eljárás, ami minden szempontból a legjobb lenne. Természetesen arra vannak eredmények, hogy egyes metaheurisztikáknak milyen előnyei és milyen hátrányai vannak (erre utalni is fogunk), de a választást egy adott gyakorlati probléma esetén mindig az előnyök, a hátrányok, és az egyes szempontok adott probléma szerinti fontosságának a figyelembevételével kell meghozni. Szerencsére nagyon sok olyan vizsgálat is létezik, amik több metaheurisztikát vetnek össze adott feladatra, sokféle szempont szerint. Egy gyakorlati probléma megoldásánál (a megoldó metaheurisztikákban szerzett tapasztalatán, esetleg gyakorlott szakember megkérdezésén túl), ezek tanulmányozása is segíthet. 5 Pontosan

emiatt, a metaheurisztika kifejezés nem is a legszerencsésebb egyes szerzők szerint.

19

Végül megjegyezzük, hogy nagyon sokszor nem is egy konkrét módszer alkalmazása a célravezető, hanem különböző megközelítések kombinálása (ezeket szokták hibrid megoldásnak nevezni).

4.2.1. Lokális keresésen (LS) alapuló metaheurisztikák A lokális keresés (LS, local search) olyen optimalizációs eljárások összefoglaló neve, melyek jellemzője, hogy a keresési térben pontról szomszédos pontra ugranak, míg el nem érik a legjobb(nak vélt) megoldást. Ez azt jelenti, hogy kiindulnak egy kezdeti pontból (amit választhatunk véletlenszerűen, vagy akár szintén valamilyen heurisztikus megfontolás alapján), majd megvizsgálják a pont szomszédait, és valamilyen stratégia szerint átugranak a szomszédok közül egyre. Ezt követően ott újra megvizsgálják a szomszédokat, és újra ugranak és így tovább, mígnem egy pontban úgy nem döntenek, hogy nem érdemes tovább ugrani, az a pont a megoldás. Jól láthatóan minden lokális keresési eljárásnak két kritikus része van: az, amelyik eldönti, hogy a szomszédok közül melyikbe érdemes ugrani, és az, amelyik dönt arról, hogy mikor kell az ugrálást abbahagyani. A lokális keresések tehát iteratív optimalizálási eljárások, melyek egy kezdeti lehetséges pontból indítva kicsiny (lokális) javítások sorozatán keresztül igyekeznek a legjobb célfüggvény-értékhez eljutni. A lokális keresések jól láthatóan csak akkor alkalmazhatóak, ha előtte definiáljuk a „szomszédosság” fogalmát, azaz meg tudjuk mondani, hogy egy adott ponthoz mely pontok vannak „közel”. Amennyiben a keresési tér dimenzióit valós számok alkotják (azaz az egyes döntési változók valós számok lehetnek), ez nem okoz problémát: a jól ismert euklideszi (térbeli) távolság alkalmazható. Más esetekben azonban (gondoljunk csak a 4.1. pontban látott X = {Vasút, Busz, Repülő} példára!) már önmagában az is feladat, hogy definiáljuk, hogy egy adott pont (tehát adott döntési változó-érték) környezetét (tehát a hozzá „közel” lévő döntési változó-értékeket) mi jelenti. A lokális keresések legnagyobb problémája a már bemutatott lokális optimumba ragadás problémája, illetve általában az a tény, hogy nagyon rosszul konvergálnak azokban a régiókban, ahol a célfüggvény lapos (ezeket szokták platónak (plateau) is hívni): elképzelhető ugyan, hogy az algoritmus Szolnokról indítva megtalálná a Kékest, ám – különösen kezdetben – hihetetlenül lassan haladna, hiszen az Alföld közepén alig lehet „érezni” az emelkedést a Mátra felé. A most következő algoritmusok kis túlzással mind erre a problémára igyekeznek (más és más) megoldást adni. A legkézenfekvőbb lokális keresésen alapuló eljárás a gradiens keresés, illetve a hegymászó keresés. (Ahogy már volt róla szó, ez utóbbi nem igényli a deriváltakat, így akkor is van értelme, amikor a derivált fogalmilag nem értelmezhető a problémára, például mert diszkrét pontokból áll a keresési tér, melyek között nincs távolság értelmezve.) E keresési eljárásokról már korábban volt szó, és mivel az előbb említett lokális optimumba ragadás miatt önmagukban ritkán alkalmazzák, így a mélyebben nem részletezzük őket. Szimulált lehűtés (SA) A szimulált lehűtés (SA, simulated annealing) lokális keresésen alapuló, memóriamentes, globális optimalizálásra szolgáló metaheurisztika. Azonban míg a gradiens keresés mindig a célfüggvény javításának irányába6 lép, addig a szimulált lehűtés – bizonyos feltételek szerint – megengedi a célfüggvényt rontó lépést is (azért, hogy így hosszabb távon mégis jól járjon, azáltal, hogy elkerüli a lokális optimumba ragadás problémáját). A szimulált lehűtés számítógépen nagyon könnyen implementálható, működésének sikerült alapos matematikai hátteret is adni, viselkedése jól ismert, ezért népszerű metaheurisztika. További előnye, hogy matematikailag bizonyítható, hogy ha elég ideig hagyjuk futni, akkor garantáltan megtalálja a globális optimumot. Ez sajnos azonban nem olyan „tökéletes” eredmény, mint amilyennek hangzik: arra vonatkozóan, hogy adott, véges ideig futtatva milyen jó megoldást talál a szimulált lehűtés, csak jóval gyengébb eredmények vannak. 6 Sőt, a gradiens keresés mindig a legnagyobb javítás irányába lép („legmeredekebb emelkedő módszere”), tehát ha több javító irány („emelkedő”) van, akkor közülük is mindig a legjobbat választja. Tehát nem csak, hogy lefelé nem lép, de nem-legmeredekebb emelkedő irányába sem.

20

A szimulált lehűtést elsősorban, de közel sem kizárólag, diszkrét optimalizálási problémák megoldására alkalmazzák. A szimulált lehűtés bemutatása A hagyományos gradiens keresés legnagyobb problémája, hogy a mindig legmeredekebb emelkedést választó megközelítés könnyen lokális maximumba vezet, ahogy azt már mi is említettük. Ennek több feloldása lehetséges. Azzal, hogy megengedjük, hogy az algoritmus ne csak a legmeredekebb emelkedő irányába léphessen (de azért mindig emelkedő irányba) bizonyos tulajdonságai javíthatóak ugyan (a hegymászó keresés esetén ezt szokták sztochasztikus hegymászó keresésnek nevezni), de a lokális maximumba ragadás általában nem oldódik meg. Az egyik lehetőség arra, hogy ezen még jobban segítsünk, az, ha továbbvisszük ezt a gondolatot, és megengedünk célfüggvényt rontó lépést (lejtő irányába mozgást) is. A szimulált lehűtés bemutatása előtt erre hozunk egy másik egyszerű példát, a küszöb-elfogadásos keresést (TA, threshold acceptance). Ez a módszer egyszerűen egy küszöbértéket (egyetlen számot) használ arra, hogy a rontás irányába lépést szabályozza: a küszöbérték megadja, hogy legfeljebb mekkora rontás fogadható el, azaz ha az éppen kipróbált irány javít a célfüggvényen, vagy ront, de nem többet, mint a küszöbérték, akkor azonnal elmozdul abba az irányba, különben viszont új iránnyal próbálkozik. A szimulált lehűtés hasonlít a TA-hoz annyiban, hogy szintén megengedi a célfüggvényt rontó irányba lépést, ám bonyolultabb nála abban, hogy ezt nem „bináris” módon szabályozza (küszöb fölött rögtön lép, alatta soha), hanem valószínűségi alapon: egy adott irányba először kiszámol egy lépési valószínűséget, utána egy véletlenszám-generálással biztosítja, hogy pont ekkora valószínűséggel lépjen tovább ebbe az irányba. Ha továbblépett, akkor az új pontban kezdi elölről az algoritmust, ha nem, akkor egy új irány után néz, arra is valószínűséget számol, és akkora valószínűséggel lép arrafelé és így tovább. A valószínűség természetesen a meredekségtől függ: javító lépésnél az értéke 1 (tehát ilyen lépést, a TA-hoz hasonlóan, azonnal megtesz), viszont rontó lépésnél a rontás mértékétől függ, mégpedig úgy, hogy azzal exponenciálisan csökken. (Így tehát, legalábbis elvileg, tetszőlegesen nagy rontást is tehet, igaz ennek a valószínűsége nagyon kicsi lesz.) A valóságban még egy további trükköt alkalmaz a SA: a rontó lépés megtételének a valószínűsége nem csak a rontás mértékétől függ, hanem attól is, hogy mennyi ideje keres az algoritmus (tehát hányadik lépést teszi meg). Kezdetben még viszonylag nagy rontásokkal szemben is elfogadó, később ezek megtételének a valószínűsége egyre jobban csökken. Ez kicsit precízebben fogalmazva azt jeleni, hogy a rontó lépés megtételének a valószínűsége e

− ∆f t k

,

ahol ∆f a rontás mértéke (az új helyen vett és az aktuális célfüggvény-érték különbsége), tk pedig a megtett lépések k számától függő, azzal jellemzően folyamatosan csökkenő, de legalábbis nem növekvő paraméter. (A gyakorlatban ez úgy valósítható meg, hogy generálunk a [0, 1] intervallumon egy egyenletes eloszlású U [0, 1] véletlenszámot (ez számítástechnikailag könnyen megoldható feladat), majd összehasonlítjuk e

− ∆f t k

-val, és ha kisebb annál, akkor megtesszük a rontó lépést. − ∆f

Könnyen belátható ugyanis, hogy ennek a valószínűsége épp e tk lesz.) tk értékét hőmérsékletnek7 szokás nevezni, ezt (mint k függvényét) pedig ennek megfelelően hűtési profilnak hívják; ez mutatja tehát meg, hogy hogyan „cseng le” a rontó lépések megtételének a valószínűsége. Összefoglalva tehát: a szimulált lehűtés egy adott pontból induló, lokális információkat használó keresés. A döntési halmazban úgy bolyong, hogy minden lépésnél dönt: ha a lépés javít a célfüggvény-értéken, akkor azt azonnal megteszi, ha ront, akkor csak bizonyos valószínűséggel. Ez a valószínűség ráadásul a lépések számával egyre csökken, így inkább csak a keresés elején hajlandó rontó lépéseket tenni, később egyre kevésbé. Mindezeket a 4.2. ábrán látható folyamatábra szemlélteti. Ezzel a módszerrel az a cél, hogy elkerüljük a lokális optimumba ragadást. A Budapestről indított keresés nem feltétlenül fog a Gellért-hegy tetején megállni, mert – különösen az elején – bizonyos eséllyel elindul lefelé is, és van rá remény, hogy rátaláljon a Mátra felé vezető irányra. Bár 7 Az

elnevezés oka a módszer fizikai analógiájából fog világossá válni, ezt a pont végén mi is bemutatjuk.

21

START Kezdőpozíció kiválasztása, lépésszámláló k = 1-re állítása

Lépési irány kiválasztása

Az új irányba lépve javul a célfüggvény?

igen

nem

k lépésszámláló növelése

A dobott U [0, 1] véletlenszám kisebb∆fmint − e tk ?

igen

nem

nem

Teljesült a megállási feltétel?

igen STOP 4.2. ábra. A szimulált lehűtés folyamatábrája

22

Lépés a kiválasztott irányba

a fenti valószínűségi stratégia első ránézésre nem tűnhet megnyugtatónak, a helyzet az, hogy alkalmasan válaszott lehűtési profillal8 a szimulált lehűtés elég általános feltételek mellett garantáltan megtalálja a globális optimumot, ha kellő ideig hagyjuk keresni. Sajnos ez az eredmény, ahogy már utaltunk is rá és ami miatt itt a „kellő ideig” kifejezés is szerepel, csak aszimptotikus. Ez azt jelenti, hogy az állítás precízen úgy hangzik, hogy ha a keresés ideje tart a végtelenhez, akkor (alkalmas lehűtési profil mellett) 1 valószínűségű esemény lesz, hogy az algoritmus megtalálja a valódi globális optimumot. Sajnos az optimalizálás véges időtartamú működése során elért eredmény jóságára (azaz a gyakorlatban fontos kérdésre) csak jóval gyengébb megállapítások ismeretesek. A szimulált lehűtés előnye, hogy a viselkedése jól leírható matematikai formalizmussal is. (Ez azért nagy előny, mert így a teljesítményére vonatkozóan (például a globális optimumba konvergálás meglétére, annak sebességére) matematikai analízis is végezhető.) Ez a matematikai analízis azon alapul, hogy az aktuális pontok valószínűségi változók egymásutánjával (sztochasztikus folyamattal) modellezhetőek. Kihasználva, hogy az aktuális pontban hozott döntés nem függ attól, hogy milyen úton érkeztünk a pontba, az ún. Markov-láncok elmélete alkalmazható. Végezetül megjegyezzük, hogy a szimulált lehűtés a nevét egy metallurgiai eljárásról kapta. Kristályos anyagoknál az optimális (hibamentes) kristályszerkezet elérésének egyik klasszikus módja, hogy az anyagot nagyon felhevítik (hogy a kristályszerkezet teljesen felbomoljon), majd rendkívül lassan újrahűtik (hogy így lehetőséget adjanak arra, hogy a kristályok a lehető legszabályosabban rendeződjen és rögzüljenek). Mivel egy kristály esetén a tökéletesen szabályos kristályrács a minimális energiájú állapot (ez a globális optimum), egy kristályhibát tartalmazó (de egyébként megszilárdolt) rács a lokális optimum. A nagyobb hőmérséklet az átrendeződés révén történő hibaeltüntetésre ad módot, azt teszi lehetővé, hogy az atomok átugorjanak szabályosabb rácsot hozva létre. A felhevításre azért van szükség, mert az átugrás során ideiglenesen magasabb energiájú állapot is létrejöhet – a melegítés pont abban segít, hogy ennek ellenére rendeződjön a rács. Ez az lokális optimumba ragadás problémájának megoldása: amikor a szimulált lehűtés algoritmusában lehetőséget adunk a rontó lépések megtételére, akkor éppen az ilyen, ideiglenesen magasabb energiájú állapoton keresztül történő rendeződéseket szimuláljuk. A szimulált lehűtés Kirkpatrick és Cerny munkásságának nyomán került be a köztudatba a ’80-as évek közepén; lényegében az első közismert metaheurisztika volt. Eredete azonban egészen az ’50-es évekig vezethető vissza, a statisztikus mechanikai inspirációjú Metropolis-algoritmusra. Szimulált lehűtés a logisztikában A következőkben megemlítünk pár logisztikai alkalmazást, ahol a felmerülő optimalizációs problémát szimulált lehűtéssel oldották meg. A lenti lista semmiképp sem teljeskörű áttekintés, inkáb csak pár – lehetőleg minél változatosabb területekről származó – példát szerettünk volna hozni. • Optimális létesítményelhelyezés járműközlekdési szempontokra tekintettel [Yu et al, 2010]. • Reverz logisztikai rendszer kialakítása [Psihvaee et al, 2010]. • Munkaerő ütemezése: beosztás készítése a munkavállalóknak folyamatosan működő üzemben [Brusco–Jacobs, 1993]. • Vasúti járművek flottaméretének tervezése [Sayarshad–Ghoseiri, 2009]. • Utazóügynök probléma megoldása [Golden–Skiscim, 1993]. • Optimális létesítményelhelyezkedés meghatározása [Golden–Skiscim, 1993]. • Többféle jármű optimális útvonalszerkesztése [Lin et al, 2009]. • Optimális járatszerkesztés: legjobb (minimális költségű) járműútvonal meghatározása, kapacitáskorlátok, ellátandó pontok igényeinek figyelembevételével [Osman, 1993]. • Disztribúciós hálózat optimális kialakítása [Jayaraman–Ross, 2003]. • Gyártócella tervezése [Vakharia–Chang, 1990]. 8 Ezzel kapcsolatban a legfontosabb eredmény, hogy a hőmérsékletet nagy kezdőértékről kell indítani, és „kellően lassan” kell csökkenti, de hogy ez pontosan mit jelent, hogy az eljárás hatékony is legyen, annak kitalálása a gyakorlatban persze nem feltétlenül egyszerű feladat

23

Tabu keresés (TS) A tabu keresés (TS, tabu search) szintén lokális keresésen alapuló, de memóriát használó, globális optimalizálásra szolgáló metaheurisztika. A tabu keresés a gradiens kereséshez hasonlít annyiban, hogy mindig a legnagyobb javítás irányába lép, ám a lokális optimumba ragadás problémáját egész más módon igyekszik elkerülni. Ehhez, szemben a szimulált lehűtéssel, memóriát is használ, azaz nyomon követi (bizonyos értelemben) a már meglátogatott pontokat, „emlékszik” rá, hogy milyen módon érkezett az aktuális pontba, ahol döntenie kell, hogy merre lépjen tovább. (A szimulált lehűtés ilyen értelemben memóriamentes volt: egy adott pontban állva kizárólag azt tudta, hogy mi az adott pont, semmilyen információt nem tárolt arról, hogy korábban hol járt a keresés során.) A TS teljesítményére és működésére vonatkozóan sajnos csak jóval gyengébb elméleti eredmények érhetőek el, mint a szimulált lehűtéshez esetében. A tabu keresés bemutatása A tabu keresés lényege, hogy a keresési folyamat során információkat tárol el, melyek később segíthetik azt, hogy jó döntést hozzunk, hogy egy adott pontból merre (melyik szomszédra) lépjünk tovább. Ennek legegyszerűbb esete, ha feljegyezzük, hogy mik voltak a már meglátogatott pontok, és a későbbiekben ilyen pontra már nem lépünk újból. (Azaz, amikor egy pontban állva döntenünk kell, hogy a szomszédjai közül melyikre lépünk tovább, akkor e szomszédok közül nem választjuk azokat, melyekben már jártunk.) A valóságban a tabu keresés ennél bonyolultabb szabályokat használ, ám az elv, miszerint az összes szomszéd közül kizárunk bizonyosakat (ha tudunk) a korábban meglátogatott pontokban eltárolt információk alapján, és így csak egy kisebb számú szóba jövő szomszéd közül választunk, általában jellemzi a TS-t. Az keresés közben gyűjtött információkat tároló adatbázist tabu listának szokás nevezni. (Nevét épp az itt említett legegyszerűbb esetről kapta, hiszen ekkor ez az adatbázis nem más, mint egy lista a már meglátogatott (és emiatt később kerülendő, „tabunak” számító) pontokról. Természetesen a módszer neve maga is innen származik.) Tehát: a TS során mindig a legnagyobb javulás irányába lépünk. . . ami nem tabu. Hogy világos legyen, hogy ez miért segít elkerülni a lokális optimumba ragadást, gondoljuk végig mi történik, ha helyi maximumba lépünk. A sima hegymászó keresés ezen a ponton nem lépne tovább sehová sem, hiszen a környezetének minden tagja kisebb célfüggvényű. Ezt természetesen a tabu keresés is érzékeli, ám mivel az adott pontra már lépett egyszer (az előző lépésben, amikor „felért” a lokális maximumba), ezért helyben sem maradhat, hiszen az a pont a rálépés pillanatában bekerült a tabu listába, így a következő döntésnél már tabu. Az algoritmus tehát kénytelen lejönni a csúcsról! (Természetesen akkor sincs baj, ha ez véletlenül a globális maximum lenne, mert az algoritmus a keresés során addig talált legjobb megoldás helyét és értéket feljegyzi, és arra mindvégig emlékezik.) Sőt, ennél kicsit több is igaz: nem csak, hogy lejönni kénytelen, de a tabu lista miatt ráadásul az is szükségszerű, hogy másik úton jöjjön le. A tabu lista alkalmazása tehát kikényszeríti a célfüggvény jobb feltérképezését. Az már ennyiből is látszik, hogy a tabu keresés szinte csak diszkrét problémáknál alkalmazható – folytonos esetben szinte értelme sincs például azonos pontba visszalépésről beszélni, hiszen ennek esélye (a végtelen sok pont miatt) elenyésző: egy folytonos keresés jó eséllyel soha nem érinti kétszer ugyanazt a pontot, teljesen mindegy, hogy milyen stratégiát alkalmaz. (Ha mégis folytonos esetre alkalmazzák a TS-t, akkor egy lehetséges megoldás, hogy nem pontos egyezőséget, hanem hasonlóságot (közelséget) vizsgálnak.) A fent ismertetett tabu lista az ún. rövid távú memória. A valóságban annyi eltérés van a fenti leíráshoz képest, hogy nem magukat a konkrét megoldásokat tárolják el a tabu listában (ez sokszor kivitelezhetetlen is lenne, különösen mert a tabu lista méretét ésszerű korlátokon belül kell tartani hatékonysági okokból kifolyólag), hanem csak bizonyos jellemzőit, tulajdonságait. Ez viszont ahhoz vezethet, hogy egy még nem is vizsgált megoldás is tabu listára kerülhet. Elkerülendő azt, hogy emiatt „elnézzen” egy megoldást a keresés, a TS algoritmusok ún. aspirációs kritériumokat használnak; a legnépszerűbb szerint a tabu lista által tiltott helyre nem lép az algoritmus, kivéve, ha az javít az addigi legjobb célfüggvény-értéken. A valóságban számos további trükköt lehet a rövid távú memória kapcsán felhasználni, némelyik algoritmus például több tabu listát is használ, van amelyik dinamikusan állítja a tabu lista hosszát stb. 24

A rövid távú memória minden tabu keresésnek az alapját képezi, ám valójában az igazi tabu keresési algoritmusok gyakran ennél komplexebb memóriát alkalmaznak, hogy a teljesítményüket maximalizálják. Az egyik ötlet az ún. intenzifikáció, amihez a középtávú memóriának nevezett komponenst használják fel. Ennek lényege, hogy az ígéretesnek tűnő területeket igyekeznek alaposabban is felderíteni. A módszerek különbözőek lehetnek (tipikus, hogy ideiglenesen korlátozzák a keresési teret valamilyen alkalmasan definiált „ígéretes régióra”, hogy ott jobb feltérképezést végezzen az algoritmus), de az mindenesetre látható, hogy ez egyfajta „anti-tabu”, ami priorizálja az eddig jónak tűnő megoldások környékének a felderítését. Nem minden tabu keresés használ középtávú memóriát, bizonyos esetekben a szokásos felderítés is elég alapos, ezért nincs szükség az intenzifikálásra. A másik trükk az ún. diverzifikálás, amit a hosszú távú memória alapján végeznek az algoritmusok. Ez, az intenzifikációhoz hasonlóan, szintén egy kézenfekvő ötleten alapszik, lényegében annak komplementere: ha már elég sokat dolgoztunk a keresési tér egy adott régiójában, akkor igyekezzünk más régiókat is felderíteni! A diverzifikációt az a tény motiválta, hogy a tabu keresés (a rövidtávú memória ellenére is), néha sajnos túl lokális, azaz túlságosan egy régiójában mozog a keresési térnek. A diverzifikáció lényege, hogy a hosszú távú memória alapján az algoritmus ezt a tényt észleli, majd valamilyen módon (erre többféle stratégia is elképzelhető: véletlen újraindítás egy eddig ritkán látogatott ponton, a keresés folytonos torzítása az eddig fel nem derített régiók felé stb.) igyekszik új régiókat is felderíteni. Tabu keresés a logisztikában A következőkben megemlítünk pár logisztikai alkalmazást, ahol a felmerülő optimalizációs problémát tabu kereséssel oldották meg. A lenti lista semmiképp sem teljeskörű áttekintés, inkáb csak pár – lehetőleg minél változatosabb területekről származó – példát szerettünk volna hozni. • Gépjárművek túratervezése: kapacitás- és úthossz-korláttal [Gendreau et al, 1994], késés engedélyezésével [Taillard et al, 1997], időablakokkal [Cordeau et al, 2001], periodikus esetben [Cordeau et al, 1997], több ellátóhelyes esetben [Cordeau et al, 1997], [Renaud et al, 1996], sztochasztikus keresletű esetben [Gendreaue et al, 1997]; a különböző variánsok áttekintéséért lásd [Maischberger–Cordeau, 2011]. • Daruk ütemezése hajók kirakodásához [Samarra et al, 2007]. • Munkerő ütemezése: beosztás készítése többműszakos munkarendhez [Dowsland, 1998]. • Ellátási lánc tervezése [Melo et al, 2012]. • Konténer-rakodás tervezése [Bortfeldt et al, 2003]. • Létesítmény elrendezés (facility layout) tervezése [Chiang–Kouvelis, 1996]. • Hálózattervezés [Crainic–Gendreau, 2002].

4.2.2. Ant colony optimization (ACO) Az ant colony optimization (ACO; magyarul „hangya kolónia optimalizálás” lehetne, de ezt olyan ritkán használják, hogy inkább maradunk az eredetinél), egy előbbieknél is sokkal újabb, biológiailag inspirált optimalizálási módszer. (Szokás raj intelligenciának is nevezni azt a területet, amihez az ACO is tartozik.) A TS-hez hasonlóan használ memóriát, ám hatalmas eltérése mind a TS-hez, mind az SA-hoz képest, hogy a célfüggvény felületét párhuzamosan deríti fel: a TS és az SA egyaránt egyetlen pontban vizsgálódik (és azt igyekszik minél jobb irányba juttatni), addig az ACO egy egész „keresőpopulációt” használ az optimum megtalálásához. Az ACO alapváltozatában kombinatorikus optimalizálási problémáknál alkalmazható algoritmus, de kiterjesztették folytonos optimalizálási esetekre is. Az ACO-ra vonatkozóan csak gyenge elméleti eredmények érhetőek el. Sikerült ugyan bizonyítani a konvergenciát (azaz, hogy előbb vagy utóbb de biztos eléri a globális optimumot), ám ezt is csak bizonyos probléma-típusokra. A konvergencia-sebességre vonatkozóan még kevesebb elméleti eredmény ismert.

25

Az ACO bemutatása Amint már említettük is, az ACO egy biológiailag inspirált módszer; manapság számos ilyen algoritmus megismerése, fejlesztése folyik. A raj intelligencia (SI, swarm intelligence) területéhez tartozó algoritmusok közös jellemzője, hogy decentralizált, önszerveződő rendszerek kollektív viselkedését próbálják felhasználni; gyakran biológiai analógiák (hangya kolónia, madárraj) alapján. Jellemző ezekre, hogy képesek bonyolult feladatokat is megoldani úgy, hogy közben nincs központi irányítás: az önállóan cselekvő egységek döntéseiből alakul ki egy hatékony kollektív viselkedés. A feladatmegoldás tehát általában elosztott és párhuzamos. Az ACO alapját a hangyák útválasztási módszere képezi. Ehhez tudni kell, hogy a hangyák (pl. amikor a kolóniából indulva tápanyagot keresnek), eleinte szinte véletlen bolyongást követve vándorolnak. Az egyetlen tényező, ami ezt befolyásolja az, hogy mindeközben feromonnal megjelölik az útvonalukat, márpedig az ilyen jeleket nagyobb valószínűséggel követik. Eleinte ez nem sokat módosít, hiszen úgyis mindenki véletlenszerűen keresgél. Igen ám, de ha az egyik hangya megtalálja az élelemforrást, onnantól azon fog mozogni a kolónia és a forrás között, így megnő a valószínűsége, hogy valaki rátalál (hiszen a feromon-jelzés erősebb lesz ezen az ösvényen). De ezzel még nincs vége: ha valaki talál egy rövidebb utat (erre van esély, hiszen a feromon-jelzés csak befolyásolja a mozgásokat, de nem determinálja teljesen!), akkor az még vonzóbb lesz, ugyanis a rövidebb úton kevésbé párolog el a feromon (hamarabb visszatérnek rá a hangyák, újrajelölve azt – ez a pozitív visszacsatolás), így még csábítóbbá válik. És így tovább, mígnem előbb vagy utóbb megtalálják az optimális utat az élelemforráshoz. Ez a visszacsatolás tehát kulcsfontosságú: nyilvánvaló, hogy ha a feromon-szintek állandóak lennének, akkor a hangyák a végtelenségig véletlenszerűen bolyonganának. A visszacsatolás azonban megteremti azt a terelő „hatást”, mely végeredményben az instabil bolyongásból az optimumba történő eljutáshoz vezet. Ennek a szisztémának az adaptivitás is jellemzője. Tegyük fel, hogy a hangyák egy nyílegyenes úton közlekednek a kolónia és az élelemforrás között, ám erre az útra elhelyezünk egy akadályt, nem szimmetrikusan. Eleinte a hangyák mindkét oldalról kerülni fogják az akadályt, ám a fenti mechanizmusok révén hamar előáll az az állapot, amikor szinte minden hangya az optimális úton halad, azaz a rövidebbik oldalán kerüli az akadályt. A fentiek fényében talán nem is kell magyarázni a kapcsolatot az optimalizálással. Külön szemléletes a lokális optimumba ragadás elkerülése (azaz, hogy egy megtalált útvonal ellenére is lesznek máshol keresők (ráadásul számuk – a feromon párolgása révén – az útvonal jóságával fordítottan lesz arányos), akik találhatnak még jobb útvonalat). Jól látható, ahogy teljesülnek a felvezetőben mondottak: ez a módszer alapvetően nem globálisan oldja meg a problémát (egyetlen, központilag felügyelt kereséssel), hanem lokális döntéseket hozó, de mindeközben egymással kommunikáló ágensek révén. A kommunikáció azonban nem közvetlenül ágens és ágens közötti, hanem a környezetben hagyott „nyomok” révén, azokon keresztül történik. (Ezt az indirekt, nem-szimbolikus kommunikációt szokták stigmergiának is nevezni.) Ez a kommunikáció lokális – az információ csak a nyom környezetében tartózkodó ágensek számára elérhető. Az ACO alkalmazása teljes közvetlen olyan esetekre, amikor gráfon kell optimális útvonalat találni. A dologban az a szerencsés, hogy számos kombinatorikus optimalizálási probléma megfogalmazható ilyen módon (gráfokon), így ezek az első alkalmazásai között voltak az ACO-nak. Ilyen esetekben a megvalósítás úgy néz ki, hogy a gráf minden éléhez hozzárendelnek egy „feromonszintet” (mint változót), majd számítógéppel rengeteg hangya mozgását szimulálják. A hangyák a feromon-szintek és az élek költségei alapján választanak irányt egy adott csomópontban, de sztochasztikusan (tehát ezek csak a valószínűségeket szabják meg, a konkrét döntést véletlenszámgenerátorral hozza az ágens). Végül pedig, miután a szimuláció minden hangyája befejezte a keresést, a végleges útvonaluk jósága alapján módosítják az élek feromon-szintjeit. (Tipikusan úgy, hogy szimulálják az „elpárolgást” (azaz mindenhol egységesen csökkentik a feromon-szintet), majd meg is növelik azokat, de ezt már a hangyák útvonalai alapján.) Ezt követően újabb szimuláció következik (egy szimulációs körön belül természetesen számos – szimulált – hangya mozog). Végső soron a globális eredmény lokális döntésekből adódik ki – ahogy a biológiai analógia esetén is. Ez önmagában még csak egy ügyes gráf-algoritmus, de bizonyos megfontolássokal a módszer általános metaheurisztikává is kiterjeszthető (az ún. megoldás komponensek alapján). Ennek lényege,

26

hogy a megoldást részekből rakják össze, és a keresés arról szól, hogy az aktuális rész-megoldást újabb és újabb komponensekkel egészítik ki, lehetőleg úgy, hogy az optimális össz-megoldáshoz haladjanak. (Ehhez egy ún. konstrukciós gráf használatával visszavezetik gráf-algoritmussá az optimalizálási problémát.) Általában lokális heurisztikákat is felhasználnak. Ez a megoldás abban is eltér a lokális keresésen alapulóktól, hogy nem egy teljes megoldást javít lehetőleg az optimumig, hanem a semmiből rak össze egy lehetőleg optimális megoldást. Az ACO gyakorlatban tapasztalt teljesítményéről elmondható, hogy a jól kiismert, statikus problémákhoz, melyekre nagyon jó heurisztikák állnak rendelkezésre, általában nem versenyképes (pl. nagyméretű TSP), ezzel szemben a rosszul strukturált, dinamikus problémákra a legjobb elérhető megoldások között van. (A dinamikus problémák különösen jelentősek például épp az útválasztási, túratervezési feladatokban, ahol figyelembe kell venni az útlezárásokat, baleseteket stb. – ilyen helyzeteket más módszerek nem, vagy csak nagyon rosszul tudnak kezelni.) A fenti leírás csak egyfajta minimális változata az algoritmusnak. Valójában nagyon sok változatát, alformáját is kidolgozták az ACO-nak (Ant System, MAX-MIN Ant Sytem, Ant Colony System stb.), melyek számos hangolható paraméterben tudnak eltérni (a feromon-szintek módosítása (erre önmagában legalább egy tucat stratégia létezik), a hangyák száma, probléma-specifikus heurisztikus információ esetleges felhasználása stb.). ACO a logisztikában A következőkben megemlítünk pár logisztikai alkalmazást, ahol a felmerülő optimalizációs problémát ant colony optimization-nel oldották meg. A lenti lista semmiképp sem teljeskörű áttekintés, inkáb csak pár – lehetőleg minél változatosabb területekről származó – példát szerettünk volna hozni. • Túratervezési feladatok legkülönbözőbb változatai: [Bell–McMullen, 2004], [Yu et al, 2009], [Rizzoli et al, 2007], [Fuellerer et al, 2009], [Bell–Griffis, 2010]. • Termelésütemezés: [Shyu et al, 2004], [Yagmahan–Yenisey, 2008]. • Ellátásilánc-optimalizálás: [Silva et al, 2006]. • Készletgazdálkodás: [Huang–Lin, 2010].

4.2.3. Genetikus algoritmus (GA) A genetikus algoritmus egy ’70-es évek közepén indult, szintén biológiailag inspirált optimalizációs módszer. A biológiai motiváció azonban eltér az ACO-tól: a rendszer a biológiai evolúciót igyekszik absztrakt eszközökkel megragadni, és a valóságban tapasztalt erejét arra felhasználni, hogy optimalizációs problémákat oldjunk meg. A GA egyik legfontosabb jellemzője, hogy többpontos keresést valósít meg: nem egyetlen pontot igyekszik jobb irányba juttatni, hanem a kritériumfelület számos pontján dolgozik egymással párhuzamosan (természetesen úgy, hogy ezek kapcsolatban vannak – a célfüggvényen túl – egymással is). A GA az egyes keresési pontokat egyedeknek nevezi, és a célfüggvény alapján egyfajta jóságot (fitneszt) rendel hozzájuk. A GA kulcsa, hogy ezeken az egyedeken a biológiai élőlényekhez hasonló transzformációkat (mutáció, kereszteződés) definiál, melyektől azt várja, hogy az „egyedeket” – a biológiai evolúcióhoz hasonlóan – nagyobb jóságúvá teszi (azaz a kritériumfelület jobb pontjába juttatja). Ehhez egyedek egy nagyobb csoportját (populáció) használja fel – így jelenik meg a keresés párhuzamossága. A genetikus algoritmusok egyik fontos előnye, hogy komoly elméleti háttere létezik viselkedésüknek (léteznek matematikai formalizmusú modellek, melyek az algoritmus várható futásáról nyilatkoznak), mely lehetővé teszi, hogy szigorú matematikai eszközökkel vizsgáljuk tulajdonságaikat. Megjegyezzük, hogy a genetikus algoritmusok témájában magyar nyelvű összefoglaló könyv is született ([Várkonyiné Kóczy (ed.), 2002]).

27

A genetikus algoritmusok bemutatása A GA az optimalizációs algoritmusok egy szélesebb családjának, az evolúciós algoritmusoknak (EA) egyik tagja. (Ide tartoznak még többek között az evolúciós stratégiák (ES) és az evolúciós programozás (EP) is, számos származtatott változattal – mint a genetikus programozás (GP) – együtt.) Ezen algoritmusok közös jellemzője, hogy a biológiai evolúcióból merítenek inspirációt optimalizálási feladatok megoldásához. A genetikus algoritmus következőkben bemutatott lépéseit a 4.3. ábra fogja szemlélteti. A genetikus algoritmusok alapja a populáció, melynek tagjai az egyedek. Minden egyed egy megSTART oldást jelent a vizsgált problémára, így a populáció nem más, mint szóba jövő megoldások egy halmaza. Az első kérdés, hogy egy adott megInicializálás oldást hogyan lehet a további feladatokra alkalmas módon megadni; egy ilyen megadást nevezünk reprezentációnak vagy más szóval kódolásnem Kiértékelés nak. A GA-ban tipikus, hogy a megoldásokat vektorokkal (általában rögzített, L hosszúságú vektorokkal) reprezentáljuk, melynek komponensei legSkálázás egyszerűbb esetben binárisak (értékük 0 vagy 1). Ekkor tehát az „egyed” lényegében azonosítható egy L hosszúságú 0-1 sorozattal. Ezt szokás Szelekció sztringnek vagy kromoszómának is nevezni. Például L = 8-ra egy lehetséges kromoszóma a következő: 01110100. Azt már a konkrét feladat dönti el, hogy hogyan érdemes a probléma megoldását Keresztezés 0-1 sorozatra lefordítani – szokásos eljárás, hogy minden egyes szám valamely tulajdonság meglétét vagy meg nem létét jelzi; de eljárhatunk úgy Mutáció is, hogy a keresési teret egyszerűen felírjuk kettes számrendszerben. Az előbbi értelemre gondolva szokták az egyes számokat génnek nevezni (hiReprodukció szen a megoldás, az egyed valamely tulajdonságát kódolja), az egész kromoszómát együtt pedig az egyed genotípusának nevezni. (Követve a biológiai analógiát, magát a megoldást, amit a kromoszóma reprezentál (pl. milyen tulajdonságokkal bír) szokás fenotípusnak nevezni.) Teljesült a A fentiek megválasztása (populáció mérete, megállási reprezentáció stb.) után következő feladat, hogy feltétel? az egyes egyedek jóságát jellemezzük; erre egy kiértékelő függvényt használunk. (Ez felel meg az eddigi szóhasználatunkban a célfüggvénynek, jellemzi, hogy az adott egyed – ami ugye nem más, igen mint egy potenciális megoldás a problémára – mennyire jó megoldás.) Valójában a későbbi műSTOP veletekben nem közvetlenül a kiértékelő függvény által szolgáltatott értéket használjuk fel, hanem azt a többi egyed kiértékeléseinek figyelembevé- 4.3. ábra. A genetikus algoritmus folyamatábtelével átskálázzuk. Az így kapott, későbbiekhez rája ([Várkonyiné Kóczy (ed.), 2002] alapján) felhasznált mutatószámát az egyed jóságának fitnesznek nevezzük. A skálázás több módon történhet, a legegyszerűbb eset, ha a kiértékelő függvény által szolgáltatott értéket elosztjuk ezek egész populációban vett átlagával; esętleg ki is vonhatjuk az átlagot és eloszthatunk a populáció szórásával. A fitnesztől elvárjuk, hogy az egyed jóságá-

28

val nőjön, illetve arányosan kifejezze az egyedek közti különbségeket is. (A skálázásra épp ezért van szükség: ha magukat a nyers kiértékeléseket használnánk, akkor előfordulhatna, hogy például mindegyik nagyon nagy értéket vesz fel, így a különbségek „eltűnnek” köztük.) Összességében a fentiekkel reprezentálni tudtuk a probléma lehetséges megoldásait, és meg tudtuk határozni a jóságukat. A feladat, hogy ezek alapján az egyedeket – a célfüggvény szempontjából – jobb egyedekre cseréljük. Azokat az egyedeket, melyek egyszerre léteznek, generációnak nevezi a GA. (A legegyszerűbb esetben az egyes generációk populációnak N -nel jelölt egyedszáma állandó.) A feladat tehát, hogy adott generációt – valamilyen módon – jobb tulajdonságokból álló generációra cseréljünk. És itt jön képbe igazán a biológiai analógia. Összehangban ugyanis az evolúció példájával, a következő generáció a megelőzőek módosításával fog létrejönni, olyan módon, hogy ennek során az egyedek fitnesze is szerepet játszik. Egész pontosan két alapvető folyamat zajlik: • Az egyedek közül a jobb fitneszűeknek van több esélyük továbbjutni a következő generációba. • A továbbjutó egyedek sem változatlan módon jutnak tovább: belőlük képezett párok kromoszómáiban lévő gének véletlenszerűen kicserélődhetnek, illetve az egyedek egyes génjei véletlenszerűen módosulhatnak önmagukban is. A fenti első lépést szelekciónak nevezik, és a természetes kiválasztódást modellezi. A szelekció célja, hogy azok az egyedek vegyenek nagyobb valószínűséggel részt a későbbi folyamatokban, melyek jobb fitnesszel bírnak – ez fejezi ki a „szelekciós nyomást”, mely a keresést tendenciájában az ígéretes irányokba irányítja. A szelekció az a lépés, melynek során az egyedek fitnesze felhasználásra kerül. A konkrét kivitelezése sokféle lehet, legegyszerűbb az ún. rulettkerék szelekció. Ennek lényege, hogy N darab sorsolást végzünk, melyek mindegyikében kiválasztjuk a régi generáció egy egyedét, mégpedig úgy, hogy a kiválasztás valószínűsége az egyed fitneszével legyen arányos. (A módszer onnan kapta a nevét, hogy legegyszerűbb úgy elképzelni, mintha egy rulettkerék peremét a régi generáció egy-egy egyedét képviselő N színnel befestenénk, úgy, hogy a csík hosszúsága az egyed fitneszével legyen arányos, majd N -szer megpörgetnénk a golyót.) Fontos észrevenni, hogy a fenti szelekció – szemben a szó köznapi értelmével – nem kiválasztotta az egyedek egy részét (és eldobta a többit), csökkentve így a populáció méretét. Ezzel szemben, a szelekció után kapott (átmeneti) populáció pont ugyanolyan méretű mint az eredeti – csak épp közben elképzelhető, hogy egy régi egyed több példányban is bekerült, míg más egyáltalán nem. Az egyedek jósága tehát megjelenik: amelyik magasabb fitneszű, annak több esélye van továbbjutni, illetve több példányban továbbjutni. A második lépést összefoglaló nevén genetikus műveletnek nevezzük, részlépései az ún. genetikus operátorok. Az első genetikus operátor a keresztezés. Ennek lényege, hogy a szelekció után létrejött átmeneti populáció elemeit párokba rendezik, majd kromoszómáikat adott valószínűséggel kombinálják. (Tehát mindegyik párnál sorsolnak egy „cinkelt pénzérmével”, és így adott valószínűséggel kereszteznek, különben pedig változatlanul megy tovább a két egyed.) A keresztezés legegyszerűbb módszere az egypontos keresztezés: kijelölünk egy helyet a kromoszómákon, és az utána lévő géneket felcseréljük a két egyed között. Például a 01110100 és 110011001 egyedek keresztezéséből létrejön a 011011001 és 11010100 egyed (a keresztezés a harmadik gén után történt). Ez értelemszerűen kibővíthető két-, illetve többpontos keresztezéssé, melynek során több pontot jelölünk ki, és köztük felváltva cseréljük meg, illetve hagyjuk eredeti helyükön a géneket. Elterjedt még az ún. uniform keresztezés is, melynek lényege, hogy minden gént egymástól függetlenül adott valószínűséggel (tipikusan 50-50%) cseréljük meg, illetve hagyjuk helyén. A keresztezés alkalmazása után létrejött újabb átmeneti populáción kerül végrehajtásra a mutáció operátora. Ennek legegyszerűbb esete során az összes egyed összes génjén végigmegyünk, és mindegyiket egy adott (tipikusan igen kicsi) valószínűséggel módosítjuk. (Bináris reprezentációnál ez értelemszerűen a bit átfordítását jelenti, például a 011011001-ből 011011011 lesz.) A keresztezés szolgálja azt a célt, hogy a meglevő jó tulajdonságú egyedekből még jobbakat kaphassunk (tapasztalatok szerint ez adja a genetikus algoritmus igazi erejét), míg a mutáció révén a keresés kis valószínűséggel, de az aktuálisan jónak tűnő tartománytól lényegesen eltérő pontra is elugorhat (tesz próbát ott is, aminek a jósága semmilyen módon nem következik az 29

eddigiekből, mintegy „hasraütésszerűen”, így biztosítva, hogy ne köteleződjünk el egy esetleges lokális optimumnál; fenntartja a „genetikai diverzitást”). Mutáció nélkül könnyen bekövetkezhetne, hogy az összes egyed túl hamar a keresési tér adott részébe koncentrálódik (ún. korai konvergencia). A GA bemutatása ezzel lényegében teljes. A fentieken túl szükség van egy inicializációra, mely a legelső populációt elhelyezi a keresési térben (jobb ötlet híján történhet véletlenszerűen is), illetve egy reprodukcióra, mely a mutáció után kapott populációból a végleges, következő generációt előállítja. Ez történhet egyszerűen úgy, hogy a régi populációt lecseréli a mutáció utánira, de úgy is, hogy a régiből a legjobb egyedet megtartja, és a mutáció utáni egyiket (véletlenszerűen, vagy a legrosszabbat) kidobja (elitizmus). Az egész eljárás addig tart, amíg valamilyen leállási feltétel nem teljesül (pl. adott számú generáció után, vagy ha az egymást követő generációk legjobb elemének fitnesze nem javul tovább). Amint mondtuk, mindezeket összefoglalóan mutatja a 4.3. ábra. A genetikus algoritmusok egy komoly előnye, hogy működésükre vonatkozóan több megalapozott, szabatos matematikai modell áll rendelkezésre. Itt kell megemlíteni az ún. szkémaelméletet, illetve vele szoros összefggésben az építőkocka hipotézist. Ezek lényegében arról szólnak, hogy mialatt a GA a felszínen kromoszómákat válogat, közben implicite szkémákról hoz döntéseket. (Szkémáknak nevezik az olyan sztringeket, melyek egy vagy több pozíciója nem megkötött, például a ∗01 három bites szkéma fedi a 001 és az 101 kromoszómát is.) Létezik matematikai elmélet, mely arra ad korlátokat, hogy az ilyen szkémák (tehát a rájuk illeszkedő kromoszómák) száma hogyan alakul egy GA futása alatt. Másrészt, magáról a populáció összetételéről (fitneszek eloszlásáról), és a konvergenciáról is számot adó matematikai modellek is születtek; közülük a legalapvetőbb a Vose–Liepins-modell. Ez a modell matematikai apparátussal formalizálja a GA viselkedését. Továbbfejlesztései, és az egyéb megközelítések még komolyabb eszköztárat (Markov-folyamatok, statisztikus mechanikai analógiák stb.) használva teszik lehetővé, hogy a GA tulajdonságairól elméletileg tudjunk nyilatkozni. A genetikus algoritmus egy sor gyakorlati probléma esetében nagyon jó eredményt ért el, mindmáig az optimalizáció legnépszerűbb módszerei között van, megszámlálhatatlan sok mérnöki és egyéb alkalmazással. A teljesítménye azonban nagyban függ a problémareprezentációtól (melynek jó megtalálása alapvetően továbbra is tárgyterületi tudást igényel) és a paraméterek finomhangolásából (mely számtalan lehetőséget ad, a populáció méretének beállításától a keresztezés konkrét módján át az elitizmus használatáról való döntésig). A fentiek ellenére is, a konvergencia matematikailag sokkal ingatagabb lábakon áll. Sőt, egész pontosan elmondható, hogy még az a (meglehetősen gyenge) állítás sem igazolható, mint az SA esetében (hogy ti. végtelen idő alatt 1 valószínűséggel a globális optimumba konvergálna): a GA fenti, legegyszerűbb változata (szokták kanonikus GA-nak is nevezni), elitizmus nélkül, még ezt sem teljesíti. Ehhez azonban vegyük azt is figyelembe, hogy a GA-t eredetileg nem is általános célú, statikus függvény-optimalizálónak szánták, hanem egy robusztus, adaptív kereső-eljárásnak (mely problémákra tényleg jól is teljesít). Mindazonáltal, a GA egyes módosításaira a fent említett matematikai formalizmussal már bizonyítható például a konvergencia. Genetikus algoritmusok a logisztikában A következőkben megemlítünk pár logisztikai alkalmazást, ahol a felmerülő optimalizációs problémát genetikus algoritmussal oldották meg. A lenti lista semmiképp sem teljeskörű áttekintés, inkáb csak pár – lehetőleg minél változatosabb területekről származó – példát szerettünk volna hozni. • Disztribúciós hálózat tervezése: [Berry et al, 1998]. • Ellátási lánc tervezése: [Zhou–Min, 2011], [Hwang, 2002a], [Altiparmark et al, 2009]. • Ellátási lánc optimalizálása: [Farahani–Elahipanah, 2008], [Lee et al, 2009]. • Túratervezés és variánsai: [Hwang, 2002b], [Tan, 2001], [Ho et al, 2008]. • Szállítmány-konszolidáció optimalizálása: [Zhang et al, 2011]. • Raktárfolyamatok optizmlizálása: [Yao–Chu, 2008]. • Ügyfelek disztribúciós központokhoz rendelése: [Zhou et al, 2002]. • Cellás gyártórendszer tervezése: [Wu et al, 2007]. 30

Irodalomjegyzék [Chikán, 2008] A Chikán, Vállalatgazdaságtan, Aula Kiadó, Budapest, 2008. [Maddala, 2004] GS Maddala, Bevezetés az ökonometriába, Nemzeti Tankönyvkiadó, Budapest, 2004. [Ramanathan, 2003] R Ramanathan, Bevezetés az ökonometriába – alkalmazásokkal, Panem, Budapest, 2003. [Wooldridge, 2009] JM Wooldridge, Introductory Econometrics: A Modern Approach, SouthWestern Cengage, Mason, 2009. [Legato–Mazza, 2001] P Legato, RM Mazza, Berth planning and resources optimisation at a container terminal via discrete event simulation, European Journal of Operational Research, Vol 133, No 3, pp. 537–547, 2001. [Ramani et al, 1996] KV Ramani, An Interactive Simulation Model for the Logistics Planning of Container Operations in Seaports, Simulation, Vol 66, No 5, pp. 291–300 , 1996. [Busato–Berruto, 2008] P Busato, R Beruto, Logistics design process of biomass supply chain: simulation and optimization models, Agricultural and biosystems engineering for a sustainable world. International Conference on Agricultural Engineering, Hersonissos, Crete, Greece, 2325 June, 2008 pp. OP-2155. [Vorst et al, 2009] JGAJ van der Vorst, SO Trompb, DJ van der Zeec, Simulation modelling for food supply chain redesign; integrated decision making on product quality, sustainability and logistics, International Journal of Production Research, Vol 47, No 23, pp. 6611–6631, 2009. [Kara et al, 2007] S Kara, F Rugrungruang, H Kaebernick, Simulation modelling of reverse logistics networks, International Journal of Production Economics, Vol 106, No 1, pp. 61–69, 2007. [Li et al, 2009] J Li, M González, Y Zhu, A hybrid simulation optimization method for production planning of dedicated remanufacturing, International Journal of Production Economics, Vol 117, No 2, pp. 286–301, 2009. [Gendreau–Potvin (eds.), 2010] M Gendreau, J-Y Potvin (eds.), Handbook of Metaheuristics, Springer, New York, 2010. [Talbi, 2009] E-G Talbi, Metaheuristics – From Design to Implementation, Wiley, New York, 2009. [Luke, 2009] S Luke, Essentials of Metaheuristics, Lulu, 2009. [Brusco–Jacobs, 1993] MJ Brusco, LW Jacobs, A simulated annealing approach to the cyclic staffscheduling problem, Naval Research Logistics, Vol 40, No 1, pp. 69–84, 1993. [Golden–Skiscim, 1993] BL Golden, CC Skiscim, Using simulated annealing to solve routing and location problems, Naval Research Logistics, Vol 33, No 2, pp. 261–279, 1986.

31

[Osman, 1993] IH Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, Vol 41, No 4, pp. 421–451, 1993. [Jayaraman–Ross, 2003] V Jayaraman, A Ross, A simulated annealing methodology to distribution network design and management, European Journal of Operational Research, Vol 144, No 3, pp.629–645, 2003. [Vakharia–Chang, 1990] AJ Vakharia, YL Chang, A simulated annealing approach to scheduling a manufacturing cell, Naval Research Logistics, Vol 37, No. 4, pp.559–577, 1990. [Psihvaee et al, 2010] MR Pishvaee, K Kianfar, B Karimi, Reverse logistics network design using simulated annealing, The International Journal of Advanced Manufacturing Technology, Vol 47, Nos 1-4, pp. 269-281, 2010. [Yu et al, 2010] VF Yu, SW Lin, W Lee, CJ Ting, A simulated annealing heuristic for the capacitated location routing problem, Computers & Industrial Engineering, Vol 58, No 2, pp.288–299, 2010. [Lin et al, 2009] SW Lin, VF Yu, SY Chou, Solving the truck and trailer routing problem based on a simulated annealing heuristic, Computers & Operations Research, Vol 36, No 5, pp.1683– 1692, 2009. [Sayarshad–Ghoseiri, 2009] HR Shayarshad, K Ghoseiri A simulated annealing approach for the multi-periodic rail-car fleet sizing problem, Computers & Operations Research, Vol 36, No 6, pp.1789–1799, 2009. [Gendreau et al, 1994] M Gendreau, A Hertz, G Laporte, A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science, Vol 40, No 10, pp. 1276–1290, 1994. [Taillard et al, 1997] ED Taillard, P Badeau, M Gendreau, F Guertin, JY Potvin, A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, Vol 31, pp. 170–186, 1997. [Cordeau et al, 2001] JF Cordeau, G, Laporte, A Mercier, A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows, The Journal of the Operational Research Society, Vol 52, No 8, Part OR42, pp. 928–936, 2001. [Cordeau et al, 1997] JF Cordeau, M Gendreau, G Laporte, A tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems, Networks, Vol 30, pp. 105–119, 1997. [Renaud et al, 1996] J Renaud, G Laporte, FF Boctor, A tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems, Networks, Vol 30, pp. 105–119, 1997. [Gendreaue et al, 1997] M Gendreau, G Laporte, R Séguin, A tabu search heuristic for the multidepot vehicle routing problem, Computers & Operations Research, Vol 23, No 3, pp. 229–235, 1997. [Maischberger–Cordeau, 2011] M Maischberger, JF Cordeau, Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search, Lecture Notes in Computer Science, Vol 6701/2011, pp. 395–400, 2011. [Samarra et al, 2007] M Sammarra, JF Cordeau, G Laporte, MF Monaco, A tabu search heuristic for the quay crane scheduling problem, Journal of Scheduling, Vol 10, No 4–5, pp. 327–336, 2007. [Dowsland, 1998] KA Dowsland, Nurse scheduling with tabu search and strategic oscillation, European Journal of Operational Research, Vol 106, No 2–3, pp. 398–407, 1998.

32

[Melo et al, 2012] MT Melo, S Nickel, F Saldanha-da-Gama, A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon, International Journal of Production Economics, Vol 136, No 1, pp. 218–230, 2012. [Bortfeldt et al, 2003] A Bortfeldt, H Gehring, D Mack, A parallel tabu search algorithm for solving the container loading problem, Parallel Computing, Vol 29, No 5, pp. 641–662, 2003. [Chiang–Kouvelis, 1996] WC Chiang, P Kouvelis, An improved tabu search heuristic for solving facility layout design problems, International Journal of Production Research, Vol 34, No 9, pp. 2565–2585, 1996. [Crainic–Gendreau, 2002] TG Crainic, M Gendreau, Cooperative Parallel Tabu Search for Capacitated Network Design, Journal of Heuristics, Vol 8, No 6, pp. 601–627, 2002. [Bell–McMullen, 2004] JE Bell, PR McMullen, Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, Vol 18, No 1, pp. 41–48, 2004. [Yu et al, 2009] B Yu, ZZ Yang, B Yao, An improved ant colony optimization for vehicle routing problem, European Journal of Operational Research, Vol 196, No 1, pp. 171–176, 2009. [Rizzoli et al, 2007] AE Rizzoli, R Montemanni, E Lucibello, LM Gambardella, Ant colony optimization for real-world vehicle routing problems – From theory to applications, Swarm Intelligence, Vol 1, No 2, pp. 135–151, 2007. [Fuellerer et al, 2009] G Fuellerer, KF Doerner, RF Hartl, M Iori, Ant colony optimization for the two-dimensional loading vehicle routing problem, Computers & Operations Research, Vol 36, No 3, pp. 655–673, 2009. [Bell–Griffis, 2010] JE Bell, SE Griffis, Swarm Intelligence: Application of the Ant Colony Optimization Algorithm to Logistics-Oriented Vehicle Routing Problems, Journal of Business Logistics, Vol 31, No 2, pp. 157–175, 2010. [Shyu et al, 2004] SJ Shyu, BMT Lin, PY Yin, Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time, Computers & Industrial Engineering, Vol 47, No 2–3, pp.181–193, 2004. [Yagmahan–Yenisey, 2008] B Yagmahan, MM Yenisey, Ant colony optimization for multi-objective flow shop scheduling problem, Computers & Industrial Engineering, Vol 54, No 3, pp. 411–420, 2008. [Silva et al, 2006] CA Silva, JMC Sousa, TA Runkler, JMG Sa da Costa, Distributed optimisation of a logistic system and its suppliers using ant colonies, International Journal of Systems Science, Vol 37, No 8, pp. 503–512, 2006. [Huang–Lin, 2010] SH Huang, PC Lin, A modified ant colony optimization algorithm for multiitem inventory routing problems with demand uncertainty, Transportation Research Part E: Logistics and Transportation Review, Vol 46, No 5, pp. 598–611, 2010. [Várkonyiné Kóczy (ed.), 2002] A Várkonyiné Kóczy (ed.), Genetikus algoritmusok, Typotex Kiadó, Budapest, 2002. [Berry et al, 1998] LM Berry, BA Murtagh, GB McMahon, SJ Sugden, LD Welling, Genetic algorithms in the design of complex distribution networks, International Journal of Physical Distribution & Logistics Management, Vol 28, No 5, pp. 377–381, 1998. [Zhou–Min, 2011] G Zhou, H Min, Designing a closed-loop supply chain with stochastic product returns: a Genetic Algorithm approach, International Journal of Logistics Systems and Management, Vol 9, No 4, pp. 397–418, 2011.

33

[Hwang, 2002a] HS Hwang, Design of supply-chain logistics system considering service level, Computers & Industrial Engineering, Vol 43, No 1–2, pp. 283–297, 2002. [Altiparmark et al, 2009] F Altiparmark, M Gen, L Lin, I Karaoglan, A steady-state genetic algorithm for multi-product supply chain network design, Computers & Industrial Engineering, Vol 56, No 2, pp. 521–537, 2009. [Farahani–Elahipanah, 2008] RZ Farahani, M Elahipanah, A genetic algorithm to optimize the total cost and service level for just-in-time distribution in a supply chain, International Journal of Production Economics, Vol 111, No 2, pp. 229–243, 2008. [Lee et al, 2009] JE Lee, M Gen, KG Rhee, Network model and optimization of reverse logistics by hybrid genetic algorithm, Computers & Industrial Engineering, Vol 56, No 3, pp. 951-964, 2009. [Hwang, 2002b] HS Hwang, An improved model for vehicle routing problem with time constraint based on genetic algorithm, Computers & Industrial Engineering, Vol 42, No 2–4, pp. 361–369, 2002. [Tan, 2001] KC Tan, A messy genetic algorithm for the vehicle routing problem with time window constraints, Proceedings of the 2001 Congress on Evolutionary Computation, Vol 1, pp. 679686, 201. [Ho et al, 2008] W Ho, GTS Ho, P Ji, HCW Lau, A hybrid genetic algorithm for the multi-depot vehicle routing problem, Engineering Applications of Artificial Intelligence, Vol 21, No 4, pp. 548–557, 2008. [Zhang et al, 2011] Z Zhang, H Qin, A Lim, A genetic algorithm for the freight consolidation problem with one-dimensional container loading, Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp. 1707–1714, 2011. [Yao–Chu, 2008] MJ Yao, WM Chu, A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements, Omega, Vol 36, No 4, pp. 619– 631, 2008. [Zhou et al, 2002] G Zhou, H Min, M Gen, The balanced allocation of customers to multiple distribution centers in the supply chain network: a genetic algorithm approach, Computers & Industrial Engineering, Vol 43, No 1–2, pp. 251–261, 2002. [Wu et al, 2007] X Wu, CH Chu, Y Wang, W Yan, A genetic algorithm for cellular manufacturing design and layout, European Journal of Operational Research, Vol 181, No 1, pp. 156–167, 2007.

34