Dr. Gubán Ákos* Birkás Petra** A „SZENT JAKAB-ÚT” PROBLÉMÁK
BEVEZETÉS Egy általánosítható optimalizálási probléma megoldásának elsı lépéseit írja le a cikk. Az alap probléma az El Camino zarándokúttal kapcsolatban merült fel. Az út vázlatos térképét az 1. ábra mutatja be.
1. ábra Az El Camino és a zarándokszállások helyei A térképen látszik, hogy a zarándokok számára több pihenı hely áll rendelkezésre az út során. A zarándok célja az utat a legrövidebb idı alatt megtenni. Természetesen néhány zarándok „paraméter” meg kell adni. Ismert a zarándok átlag sebessége, a maximálisan megtehetı út hossza. De a szállások is rendelkeznek paraméterekkel, mégpedig telítettségi mértékkel. A mérték azt mutatja meg, hogy egy véges diszkrét szállással rendelkezik, ezek a szállások egy kezdeti idı után, fokoza*
BGF Pénzügyi és Számviteli Fıiskolai Kar Salgótarjáni Intézete, fıiskolai docens, PhD. Régió Finansz Zrt, Salgótarján, pénzügyi referens.
**
49
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK tosan kezdenek megtelni. Mivel az alap esetben nem tervezzem a több egymással versengı zarándok modellezését, ezért a szállásra vetítem a telítettséget, és ennek alapján képzem az értéket. Ez a mérték a napi idı függvénye, és minden nap ez az érték a maximumról indul újra, és egy megadott idıponttól kezdıdıen csökken. Ezek alapján a zarándok célja úgy megtervezni a teljes utat, hogy a lehetı legnagyobb távolságot tegye meg minden nap úgy, hogy a korlát alatt maradjon, és a nap végén rendelkezzék szállással. A feladat tovább bonyolódik, ha figyelembe vesszünk egyéb feltételeket, mint bolt a szállás közelében, vagy a szálás telítettségi mutatót egy valószínőségi változó modellez. A probléma modellje akkor lesz teljes, ha a maximális út nem feltétlen rögzített konkrét érték, hanem környezetfüggı érték lesz. A cikk célja a feladat többfokozatú modellezése, és a modellekhez optimalizáló eljárások megalkotása. AZ EGYSZERŐSÍTETT RENDSZER MODELLJE Legyen: n a lehetséges szálláshelyek (továbbiakban hely) száma; Dij : i, = 0...n; j > i a elhelyezkedés szerint rendezett helye, közötti távolság trianguláris mátrix. A mátrix egyszerősíthetı egy vektorral, de ebben az esetben a mátrix egy diagonális körüli elemét származtatni kellene a vektorból. A probléma szempontjából egyszerőbb a mátrix használata. Az i = 0 a kiindulási helyet jelenti. Fi : i = 1...n a helyek maximális szabad kapacitás vektora;
Tij : i = 1...n; j = 0;1 a helyek kezdeti és vég idıpontjai. A mátrix elsı oszlopa mutatja meg, mikor kezdıdik a hely maximális értéken csökkentése. A második oszlop pedig megmutatja, mikor telik be a hely, illetve a zárás idıpontja. (Ti 0 < Ti1 ) v a zarándok (továbbiakban pont) sebessége; m a pont maximális megtehetı távolsága. Kezdetben legyen t a pont napi indulási idıpontja 0 ≤ t ≤ max Ti1 , valamint jelentse Te a nap végének idıpontját. BIZTOS SZÁLLÁS ESETE Ebben a pontban azt az esetet nézzük meg, amikor a zarándok minden szálláson rendelkezik szabad hellyel. A feladat megadni a legrövidebb napszámot, amivel a teljes táv teljesíthetı és a hozzátartozó eljárást megalkotni. Ekkor nincs szükség az F, T mátrixokra, a sebességre, valamint az indulási idıpontra. (Ez a téli eset, bár a valóságban ekkor kisebb a n értéke.) Fontos feltétel, hogy legyen megoldás, azaz létezik a helyek egy olyan sorozata: i1 ,...il , hogy i1 = 0; il = n és ik −1 < ik valamint Dik −1ik ≤ m . A továbbiakban tegyük fel, hogy van lehetséges megoldás. Egy optimális megoldást egy egyszerő mohó algoritmussal választhatjuk ki. Elve: mindig azt a következı helyet választjuk, amelyik még az adott maximális távolságon belül van és a legtávolabbi. Azaz, legyen N j : 0 ≤ j ≤ n; n ∈ N az igénybe vett helyek vektora N 0 = 0 . A j-edik elemhez konstruáljuk meg az elérhetı helyek halmazát:
{
Pj := i j < i ≤ n; D ji ≤ m; j < i
(
d j = min m − DN j −1 ,i i∈Pj
50
)
}
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK és
N j : DN j −1 ,i = m − d j . Ebben az esetben a megtett napok száma j és ez az optimum. A helyszámra vonatkozó teljes indukcióval belátható, hogy minden esetben a legtávolabbi lehetséges hely választása biztosítja a legnagyobb távolságot ugyanazon idı mellett. j = 1 esetén nyilvánvaló. Tegyük fel, hogy j –re igaz, a j+1 elem választása során, mivel j –re a lehetséges legtávolabb vagyunk, az elıtte lévı helyekrıl elérhetı összes hely innen is elérhetı, esetleg ez a halmaz bıvülhet más elemekkel, mivel a legtávolabb vagyunk. Az elkészített szoftver segítségével az 1. táblázat adataira kapjuk a következı megoldást (2. ábra). 1. táblázat Szállások száma: 70, maximális megtehetı út (km): 70 km Szállás azonosító 1 2 3 4 5 6 7 8 9 10 11 12 13 14
km 12 23 21 50 22 12 9 10 13 42 20 12 30 40
Szállás azonosító 15 16 17 18 19 20 21 22 23 24 25 26 27 28
km 21 60 32 10 12 9 5 10 44 21 5 7 13 15
Szállás azonosító 29 30 31 32 33 34 35 36 37 38 39 40 41 42
km 21 22 7 21 13 10 15 17 32 41 33 10 9 21
Szállás azonosító 43 44 45 46 47 48 49 50 51 52 53 54 55 56
km 10 13 15 18 21 22 20 3 15 7 21 3 10 14
Szállás azonosító 57 58 59 60 61 62 63 64 65 66 67 68 69 70
km 19 20 28 24 10 8 11 15 15 10 17 18 13 12
2. ábra Egy megoldás egyszerő esetre TELÍTİDİ SZÁLLÁSOK ESETE Az elızı modell egy bonyolultabb változata. Ebben az esetben minden nap a megadott két idıpont között fokozatosan telik a szálláshely. Most számunkra csak a telítıdés idıpontja számít csak, azaz a pontnak el kell tudni érnie a kiválasztott helyet a telítettség elıtt. Az eljárást lényegesen nem bonyolítja a kényszer feltétel. Most viszont szükség van a sebesség paraméterbıl származó maxi-
51
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK m . Ebbıl származtatjuk a maximális beérkezési idıt: t a = t + t t . Legyen v Pj := i 0 ≤ i ≤ n; t a < Ti1 ; D ji ≤ m; j < í a j helyrıl elérhetı helyek halmaza. A választás csak in-
mális utazási idıre t t =
{
}
nen történhet. Az elızı gondolatmenet szerint, válasszuk azt az im -t, amelyik ezek közül a legtávolabb van: D jim = max D ji . Ismét az elızı gondolatmenethez hasonlóan teljes indukcióval igai∈Pj
zolható, hogy az eljárás az optimumot biztosítja. Az eset tovább általánosítható, ha csak a „telitı függvény” ismert minden helyre. A függvényre csak az alábbi kikötést kell tenni: a.) monoton csökkenı, nem negatív függvény; b.) D f j = [Ti 0 ; Te ] c.)
f i (Ti 0 ) = pi : pi > 0 a maximális helyszám (lehet tetszıleges pozitív valós érték);
{
}
Ebben az esetben, Ti1 = inf T T ∈ [Ti 0 ; Te ]; f i (t ) = 0 . Ez alapján a fenti módszer már használható. Az elkészített szoftver segítségével a fenti algoritmus néhány esetét mutatja a következı két ábra. Az elsı esetben teljesíthetı az adatokra az út.
3. ábra Megoldható telítıdı szállás A második esetben nem lesz olyan szállás a hatodik napon.
4. ábra Nem megoldható eset 52
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK
VÉLETLENSZERŐEN TELÍTİDİ SZÁLLÁSOK ESETE A modellben minden szálláshoz a nap minden pillanatához tartozik egy valószínőség érték. Mely azt mutatja meg, az adott pillanatban mekkora annak a valószínősége, hogy van szabad hely. Ebben az esetben a feladatot többféleképpen is átfogalmazhatjuk. a.) Melyik az a legrövidebb idı, amely alatt biztos szálláshelyek mellett teljesíthetı az út? b.) Melyik az a legrövidebb idı, amely egy megadott biztonsági szint mellett biztosít szállást minden nap? (Az elızı eset 1 biztonsági szinthez tartozó speciális eset.) c.) Rögzítjük hány nap kell az út során biztos szállással rendelkezni, a többihez csak egy biztonsági szintet rendelünk. A megoldáshoz minden helyhez rendeljünk egy „telítettség” függvényt. melyre teljesül: 1.
függvény,
D pi = [Ti 0 ; Te ]
2. monoton csökken; 3. Legyen , illetve általánosan . Az a. és b. eset ezek segítségével könnyen megoldható. Az eljárás pontosan megegyezik az elızıvel azzal a különbséggel, nem a értéket használjuk a határnak, hanem a illetve . Legyen az így kapott helyek sorozata:
és legyen
valamint
Ekkor annak a valószínősége, hogy minden esetben rendelkezünk szállással:
A c. eset megoldása eltér az elızıtıl. Ezzel a problémával nem foglalkozom ÁLTALÁNOS ESET Az általános esetben két fontos fogalmat kell jól meghatározni. Az egyik a „távol van”, „közel van”, „még elérhetı” stb., valamint a „fáradtságot”. Azaz a problémánk alapját az adja, hogy a korábban megtett távok függvényében, mennyire fáradtunk el az elızı napokban, és ennek megfelelıen, melyik szállás lesz még elérhetı távolságban, és melyek lesznek „távol”. Ezek a paraméterek mutatják: nem kétértékő logikával állunk szemben, sıt egy szabályozásról lesz szó. Pont ilyen problémák megoldására használják a fuzzy logikákat, és a fuzzy szabályozásokat. 53
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK RÖVIDEN A FUZZY LOGIKÁRÓL A fuzzy logika alkalmazása esetén halmazba tartozás 0 (nem), illetve 1(igen) értékei helyett, hanem köztes értékek is léteznek, amelyek megmutatják, hogy egy adott elem milyen mértékben tartozik egy halmazhoz. Azaz az alaphalmaz minden eleméhez hozzárendelünk egy számot, általában 0 és 1 (néha -1 és 1 között), ami jellemzi az elem A halmazba való tartozásának mértékét. Ezt a hozzárendelést a halmaz tagsági függvényének nevezzük. Az alkalmazás során dıl el a használt tagsági függvény, melynek alakja többféle lehet. A fuzzy halmazok között is értelmezhetık mőveletek, melyek a halmaz mőveletek általánosítása. Részletes definíciói ismertek ezzel itt most nem foglalkozunk. RÖVIDEN A FUZZY IRÁNYÍTÁSI RENDSZEREKRİL A fuzzy irányítási rendszerek legfontosabb eleme a szabálybázis, azaz a „ha a bemenet , akkor a kimenet ” alakú szabályok halmaza. Az egyszerő modellek, mint a ZADEH- vagy MAMDANI-féle, általában homogén szabálytípusból épülnek fel, a bonyolultabb hierarchikusan strukturált szabálybázisokban az alszabálybázisok strukturálisan is különbözhetnek. A fuzzy szabálybázis szerkezetileg hasonlít az más AI-ban alkalmazott szakértı szabálybázisokra, de ebben az esetben a szimbólumok mellett fuzzy tagsági függvényeket is használnak. A fuzzy irányítási rendszerek további összetevıje az illeszkedési mértéket meghatározó egység, amely a szabálybázis antecedens elemeit hasonlítja össze az aktuális megfigyelés tagsági függvényével vagy konkrét értékével. A fuzzy irányítási rendszer harmadik egysége a következtetı gép. A következtetı gép lényege, hogy az illeszkedési mérték meghatározása után a kapott súlyokat a fuzzy szabálybázisban található tüzelı szabályok konzekvenseivel kombinálja. Többféle megoldási mód használatos. A fuzzy irányítóknál szükség van arra, hogy valamilyen konkrét crisp beavatkozó érték jelenjék meg, amely a következtetı gép kimenetén elıálló fuzzy tagsági függvény defuzzifikálásával történik. Így a negyedik alkotóelem a defuzzifikáló egység, amely számos különbözı technika közül választva valamilyen módon a kapott fuzzy tagsági függvény legjellemzıbb, legtipikusabb elemét, vagy középértékét választja ki.
5. ábra Általános fuzzy irányítási rendszer vázlata AZ ÁLTALÁNOS ESET FUZZY MODELLJE Két bemeneti halmazt határozunk meg, az egyik az elızı nap útviszonyaitól függı „fáradtság” mutatót adja meg, a második az út erısség definíciós halmaz. Kimenet a megtehetı távolság leíró, illetve egy fáradtság lesz. 54
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK Legyen a fáradtság 0-100 skálán mérhetı mennyiség, a fogalom definícióját az alábbi elemek alkotják: Fáradtság:={nagyon (n), közepesen (k), fáradt (f), alig (a), nem(p)} Öt fuzzy halmazzal modellezhetı, ezek tagsági függvénye:
6. ábra A „Fáradtság” fuzzy halmazok A második bementi halmazrendszer az „Útviszony” lesz, mely a következı elemeket tartalmazza: Útviszony={sík (s), lankás (l), közepes szintkülönbség (k), erıs szintkülönbség (e)} a szintkülönbség maximálisan 1500 méter, ezért erre skálázzuk a függvényeket.
55
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK
A tagsági függvények a következık:
7. ábra Az „Útviszony” fuzzy halmazok Végül a távolság kilométerben: Távolság:={rövid (r), kevés (k), elég (e), megfelelı (m), jó (j), távol (t)}
56
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK
A szabályozás három lépésben történik. Az elsı lépésben az elızı napi fáradtság értékbıl és az útviszonyból meghatározzuk a megtehetı távolságot. A második lépésben kiválasztjuk a megfelelı szálláshelyet, majd a harmadik lépésben megadjuk az új fáradtság mutatót. (A kezdeti fáradtság a nem(p) értéket tartalmazza.) Mivel két antecedens van rendszerben ezért a szabálybázist mátrix alakban tudjuk ábrázolni, ahol a mátrix elemei a konzekvensek lesznek. A mátrix sorait a fáradtság, míg az oszlopait az útviszony címkézi. s
l
k
e
p
j
j
m
e
a
j
m
e
k
f
m
m
e
k
k
m
e
e
k
n
m
e
k
k
Ezek után a két antecendest kell fuzzifikálni. Elsı lépésben a szabályok aktivitását adjuk meg méghozzá fuzzy-AND mővelet segítségével. Tehát bármely bejövı x fáradtság, illetve y nehézség érték esetén egy adott (i,j) szabály aktivitása:
Ezek után meghatározzuk a fuzzy kimeneti értéket. Számunkra teljesen megfelel az egyik jól használható megoldás a max-prod eljárás. Az eljárás lényege, hogy az (i,j) szabály konklúziójának tagsági függvényének és a szabály aktivitásának szorzatát vesszük, majd megkeressük ezek maximumát. Ez adja a kimeneti nyelvi értéket. Amennyiben több halmaz is teljesíti, akkor a rendszerben súlyozással választunk. A megkapott távolság nyelvi értéket fuzzyfikálnunk kell ahhoz, hogy konkrét maximum távolságot kapjunk. Erre a MAX módszeren belül a súlypont-módszert fogjuk használni. Ami a kimeneti görbe alatti terület súlypontjának abszcissza-értékét fogja eredményül adni:
Miután rendelkezésre álla maximális megtehetı távolság a korábban alkalmazott mohó algoritmus segítségével, megkereshetjük a lehetséges szálláshelyet. Miután az aktuális szálláshelyet kiválasztottuk, a megtett út hosszának, nehézségének, valamint az elızı napi fáradtság értéknek a segítségével, egy újabb fuzzy eljárás segítségével meghatározzuk a fáradtság értéket. Ez egy kissé bonyolultabb, több szabályt tartalmazó eljárás, mivel, itt három antecendest fogunk a következtetésben használni. A kapott érték alapján az eljárás ismételten elvégzi a távolság szabályozást. Ennek elemeit nem részletezzük, mivel hasonló módon mőködik, mint e fenti eljárás.
57
DR. GUBÁN Á., BIRKÁS P.: A „SZENT JAKAB-ÚT” PROBLÉMÁK
ÖSSZEFOGLALÁS A fenti cikkben egy távolságelemzı rendszer mőködésének egy megoldását adtuk meg. Mivel az eredeti probléma sok bizonytalan, nem pontosan „kvantifikálható” mennyiséget tartalmaz, ezért a fuzzy szabályozás megoldását választottuk végsı módszernek. A közbülsı részmegoldások mind csak ennek elıkészítését szolgálták. A végsı eljárás egy jól mőködı szimulációját adja a rendszernek. IRODALOMJEGYZÉK KÓCZY L. T.- TIKK D.: Fuzzy rendszerek, www.hik.hu/tankonyvtar/site/books/b120/ D. DUBOIS, H. PRADE, Fundamentals of fuzzy sets , Kluwer Academic Publishers, 2000. GUBÁN M., GUBÁN Á.: Egy fuvarozási vállalat szállítmányozási feladatának matematikai modellje és tervezett megoldási algoritmusa „Globalitás és vállalkozás” Tudomány napja, BGF Budapest, 2001, pp. 226-235.
58
