Diplomamunka. Drónos áruszállítás optimalizálása heurisztikus algoritmusokkal. Miskolci Egyetem Gépészmérnöki és Informatikai Kar Logisztikai Intézet

Miskolci Egyetem Gépészmérnöki és Informatikai Kar Logisztikai Intézet

Diplomamunka Drónos áruszállítás optimalizálása heurisztikus algoritmusokkal

Készítette: Nádor József Neptun-kód: XQEI32 Szak: Logisztikai Mérnöki MSc

Miskolc, 2014

Tartalomjegyzék 1.

Bevezetés ....................................................................................................................... 1

2.

Szállítási módok ismertetése ......................................................................................... 2

3.

4.

5.

2.1.

A szállításhoz kötődő alapfogalmak ....................................................................... 2

2.2.

Közúti szállítás ........................................................................................................ 3

2.3.

Vasúti szállítás ........................................................................................................ 3

2.4.

Vízi szállítás ............................................................................................................ 4

2.5.

Légi szállítás ........................................................................................................... 5

2.6.

Kombinált szállítás ................................................................................................. 5

A drónos áruszállítási mód bemutatása ......................................................................... 7 3.1.

A drónos szállítás jellemzői .................................................................................... 7

3.2.

A drónok felépítése ................................................................................................. 8

3.3.

A drónok működése ................................................................................................ 9

3.4.

A drónos szállítási rendszerek eddigi tesztjei ....................................................... 10

Az útvonal tervezési probléma ismertetése ................................................................. 13 4.1.

A drónok útvonal tervezési problémáinak bemutatása ......................................... 13

4.2.

Az utazó ügynök probléma meghatározása .......................................................... 15

4.3.

A heurisztikus módszerek szükségessége ............................................................. 17

Heurisztikus algoritmusok ismertetése ........................................................................ 18 5.1.

Evolúciós algoritmusok ........................................................................................ 18

5.2.

A genetikus algoritmus ......................................................................................... 19

5.3.

Az Ant Colony algoritmus működésének bemutatása .......................................... 23

5.3.1.

Az algoritmus kialakulása ............................................................................. 23

5.3.2.

Az algoritmus működése ............................................................................... 24

5.3.3.

Az algoritmus egyes változatai ...................................................................... 26

5.3.4.

Az Ant Colony System algoritmus pszeudokódja ......................................... 28

6.

7.

8.

9.

Az inspyred keretrendszer ........................................................................................... 29 6.1.

A keretrendszer használatának követelményei ..................................................... 29

6.2.

A keretrendszer működése .................................................................................... 29

Heurisztikus algoritmusok tesztelése........................................................................... 33 7.1.

Ackley ................................................................................................................... 34

7.2.

Griewank ............................................................................................................... 36

7.3.

Rastrigin ................................................................................................................ 37

7.4.

Rosenbrock ........................................................................................................... 39

7.5.

Sphere ................................................................................................................... 40

7.6.

Hátizsák feladat ..................................................................................................... 42

7.7.

Az utazóügynök probléma .................................................................................... 44

Az elkészített algoritmus bemutatása .......................................................................... 45 8.1.

Az algoritmus használata ...................................................................................... 45

8.2.

Az algoritmus működése ...................................................................................... 51

8.3.

Futási eredmények ................................................................................................ 52

Összegzés .................................................................................................................... 55

10. Summary...................................................................................................................... 56 11. Irodalomjegyzék .......................................................................................................... 57

Diplomamunka

Nádor József

1. Bevezetés A diplomamunkám témája a drónos áruszállítás során jelentkező útvonal-tervezési problémák meghatározása és egy megoldási alternatíva megvalósítása. A dolgozat első részében a különböző áruszállítási módokat szeretném bemutatni, elsődlegesen kitérve arra, hogy az egyes szállítási típusok milyen előnyökkel, illetve hátrányokkal rendelkeznek. Ezek közé szeretném elhelyezni a drónos áruszállítást, amely jelenleg a logisztikának még egy feltérképezetlen területének tekinthető. Emiatt fontosnak tartom bemutatni a szállítás során használt anyagmozgató eszköznek a felépítését és a működését. Természetesen kitérek arra is, hogy jelenleg milyen területeken alkalmazzák őket, és milyen lehetőségek rejlenek a jövőbeli alkalmazásukban. A következőkben a felmerülő útvonal-tervezési problémának a pontos definiálására törekszem. Mivel az ilyen jellegű problémák rendkívül számításigényesek, ezért heurisztikus algoritmusok használata célszerű a megoldáshoz. Ezek az algoritmusok nagyon sokszínűek lehetnek, mind a működésük, mind pedig a számítási teljesítményük tekintetében, éppen ezért szeretnék néhányat közülük kielemezni, és különböző teszteket elvégezni különféle matematikai problémákon, melyekkel a hatékonyságukat össze tudom hasonlítani. Minderre a python programozási nyelvet és az arra írt inspyred nevű keretrendszert megfelelőnek találom, így ezeknek a használatát tűztem ki célul. Végül természetesen az alkalmasnak talált algoritmusok felhasználásával és továbbfejlesztésével magát a dolgozat tárgyát képező problémát kívánom megoldani. A dolgozat megírása során a célom tehát, hogy minél nagyobb részletességgel feltárjam az adott problémakört, és ismertessem a lehetséges megoldási alternatívákat Ezeknek az alkalmasságát tesztekkel és számításokkal igazoljam, végül pedig az eredményeket felhasználva egy hatékony algoritmust készítsek.

1

Diplomamunka

Nádor József

2. Szállítási módok ismertetése [1] A drónos szállítási mód bevezetése előtt fontos összehasonlítani a különböző áruszállítási módokat és az ezekhez kapcsolódó alapvető fogalmakat.

2.1. A szállításhoz kötődő alapfogalmak A szállítás témakörébe tartozó alapvető fogalmak a következők: 

Áruszállítás: Az áruszállítás anyagok, termékek (áruk) térbeli áthelyezése, a feladóhelyről a rendeltetési helyre. A díjazás ellenében végzett áruszállítást árufuvarozásnak nevezzük.



Közlekedés: A közlekedés személyek és áruk helyváltoztatása, ami rendszerint technikai eszközök, berendezések igénybevételével valósul meg, és elsődlegesen térbeni, földrajzi távolságok leküzdésére irányul. A közlekedés célja a személyek és áruk helyváltoztatásának szabályozott és gazdaságos lebonyolítása.



Közlekedési munkamegosztás: célja, hogy a közlekedési ágak azt a feladatot lássák el, amelyben a leghatékonyabban és leggazdaságosabban tudnak működni a nemzetgazdaság rendszerében.



Közlekedési kooperáció: célja, hogy lehetővé tegye az ágak összehangolt munkáját a szállítási feladatok elvégzése során.



A közlekedési ágazatok koordinációja: a közlekedési munkamegosztást és kooperációt egységesen a közlekedési ágazatok koordinációjának nevezzük, melynek célja az egységes, optimális belső struktúrájú közlekedési rendszer kialakítása, összehangolt működtetése és fejlesztése.

A közlekedés, mint rendszer felbontható a közlekedési ágak szerinti alrendszerekre, amelyek a következők: 

közúti-,



vasúti-,



vízi-,



légi közlekedés,



csővezetékes szállítás.

A termelés, az elosztás, a fogyasztás és a csere folyamatában nézve az árutovábbítás feladata, hogy a tér- és időbeli távolságot áthidalja, azaz a termelési folyamatokból

2

Diplomamunka

Nádor József

kikerülő félkész és késztermékeket a fogyasztóhoz, vagy az újbóli felhasználóhoz továbbítsa.

2.2. Közúti szállítás Rövid távolságú, elsősorban helyi- vagy regionális viszonylatban gazdaságos árufuvarozási mód, azonban számos előnye miatt a távolsági forgalomban is alkalmazzák. Előnyei: 

a legsűrűbb vonalhálózattal rendelkezik így nincs szükség átrakásra,



rövid eljutási idő,



szinte minden árufajta szállítható,



nagymértékű alkalmazkodóképesség a fuvaroztatók igényeihez,



kis áruigénybevétel, valamint kisebbek az ebből adódó károk,



rugalmas szerződéskötés és tarifakialakítás.

Hátrányai: 

nagymértékű függőség a környezeti hatásoktól, előre nem látható eseményektől (pl.: időjárás, forgalmi viszonyok),



viszonylag nagy a szállítás fajlagos energiaigénye és a környezetszennyező hatása,



nagy az élőmunka igény és a balesetveszély,



viszonylag kis árumennyiség továbbítására alkalmas,



útvonal korlátozások, és hétvégi szállítási tilalmak korlátozhatják,



a nemzetközi forgalom engedélykontingensekhez kötött.

2.3. Vasúti szállítás Nagy árumennyiségek viszonylag nagy távolságra való szállítása esetén előnyös kötöttpályás áruszállítási mód. Előnyei: 

viszonylag független a külső környezeti hatásoktól,



a közúti szállításhoz képest kisebb a szállítás fajlagos energiaigénye,



szinte minden árufajta szállítását lehetővé teszi a vasúti kocsi típusok széles választéka,



a közúti szállításhoz képest kisebb a környezetkárosító hatása,



előre jól kalkulálható tarifarendszer.

3

Diplomamunka

Nádor József

Hátrányai (a kötött pályából adódóan): 

viszonylag hosszú az áruk átfutási ideje,



kicsi a hálózatsűrűség, esetleg az áruk átrakására van szükség,



nagy dinamikus igénybevétel, különösen tolatásnál,



kevésbé rugalmas alkalmazkodóképesség a fuvaroztatói igények változásaihoz.

2.4. Vízi szállítás A természetes folyami-, illetve tengeri utakat igénybe vevő, csak kikötővel rendelkező helyeket felkeresni tudó szállítási mód. A vízi áruszállítást elsősorban tömegáruk nagy távolságra történő továbbítására célszerű igénybe venni, azonban az áruk eljutási ideje viszonylag hosszú is lehet. Előnyei: 

rendkívül költségtakarékos (1/3-a a vasúti, 1/8-a a közúti szállítás költségének),



nagy tömegeket és nagyméretű árukat is képes szállítani (1500-1800 t),



a többi közlekedési ághoz képest a legkisebb a környezetkárosító hatása,



nagyon biztonságos,



kicsi az üzemanyag szükséglete,



nem jelenik meg a pályák kiépítésének költsége, legfeljebb a medertisztításra szánt összegekkel kell számolni,



díjszabásai viszonylag rugalmasak,



főként ömlesztett áruk, folyadékok szállítására kitűnően alkalmas.

Hátrányai: 

viszonylag hosszú az áruk eljutási ideje,



kiépített kikötőkre van szükség, ami nagy összegű beruházásokat igényel,



alacsony sebesség jellemzi,



az időjárás erősen befolyásoló tényező,



nem háztól házig történik a továbbítás, ezért többszöri átrakásra van szükség,



a többi közlekedési ághoz képest a legnagyobbak a szállítás közben fellépő áruigénybevételek, ezért un. tengerbiztos csomagolást kell alkalmazni,



egyes szakaszok csak szezonálisan használhatók.

4

Diplomamunka

Nádor József

2.5. Légi szállítás Légi jármű kizárólag a légifolyosókon közlekedhet, és csak a repülőtérrel rendelkező helyeket tud felkeresni. A légi áruszállítást elsősorban akkor célszerű igénybe venni, ha kis mennyiségű, tömegegységre vetítve nagy értékű árukat kell nagy távolságra, rövid határidővel eljuttatni. Előnyei: 

a személyszállítás és az árutovábbítás legtöbbször össze van kapcsolva a maximális kapacitás kihasználtság érdekében,



nagy szállítási távolságok esetén viszonylag rövid az áruk eljutási ideje,



a többi közlekedési alágazathoz képest viszonylag kicsik az árukat érő igénybevételek, ezért kicsi a csomagolás költségigénye is,



a szállítási határidők betartását egyedül a szélsőséges időjárási viszonyok zavarhatják.

Hátrányai: 

a szállítási mód az áruknak csak egy bizonyos köre esetén vehető számításba (kizárt áruk: gyúlékony anyagok, robbanóanyagok, lőfegyverek és lőszerek, stb.),



az áruk repülőtérre való fel-, illetve elfuvarozására és e miatt gyakran többszöri átrakására, átmeneti tárolásra van szükség, ami jelentős mértékben megnövelheti az áruk eljutási idejét,



a többi közlekedési alágazathoz képest a legnagyobb a szállítás fajlagos energiaigénye, ezért viszonylag magasak a fuvardíjak,



környezetvédelmi szempontból kedvezőtlen lehet a zajhatás és az emisszió.

2.6. Kombinált szállítás A kombinált szállítás esetén egy szerződés keretében két vagy több szállítási alágazat vesz részt egy adott szállítási feladat megoldásában, az áru egy szállítási egységben jut el a feladótól a címzettig. Konténeres szállítás esetén két vagy több közlekedési alágazat együttműködésével bonyolítják le a feladó és a címzett közötti konténerforgalmat. Huckepack szállítási rendszerek esetében pedig az egyik közlekedési alágazat szállítójárművein továbbítják a másik közlekedési alágazat szállítójárműveit.

5

Nádor József

Diplomamunka

1. ábra A kombinált szállítás fő csoportjai

Előnyei: 

a környezetszennyezés és a zajártalom csökkenése,



a közutak zsúfoltságának csökkenése,



a közlekedésbiztonság növekedése,



a közutak elhasználódásának lassítása,



kedvezőbb energia- és nyersanyag-felhasználás,



a vasút és a vízi út szabad kapacitásának kihasználása,



a közúti fuvarpiac megvédése, illetve növelése.

Hátrányai: 

speciális szállítóeszközöket igényel (pl.: zsebes kocsi, konténerszállító kocsi),



a közlekedési alágazatok kapcsolódásánál terminálok igénybevételére van szükség,



huckepack szállítási mód esetén a jármű miatt keletkező holttér csökkenti a szállítási célra kihasználható teret.

6

Nádor József

Diplomamunka

3. A drónos áruszállítási mód bemutatása [2] 3.1. A drónos szállítás jellemzői A drónokkal megvalósított anyagmozgatás a logisztikának jelenleg még egy kevésbé feltérképezett területe. A drónok alatt kisméretű pilóta nélküli repülőgépet kell érteni. Az ilyen járműveket hívhatjuk pilóta nélküli légi járműveknek (Unmanned Aerial Vehicle, UAV) vagy távolról irányított (légi) járműveknek is (Remotely Piloted (Aerial) Vehicle, RPV). A drónok elsősorban katonai feladatokra alkalmazott repülőeszközök, melyek valamilyen

ön-

vagy

távirányítással

(leggyakrabban

a

kettő

kombinációjával)

rendelkeznek, emiatt fedélzetükön nincsen szükség pilótára. Amennyiben a drónokat anyagmozgató gépként vizsgáljuk, akkor megállapíthatóak a következők: 

anyagmozgatási feladat szerint szállító berendezések,



a mozgás időbeli alakulása szerint szakaszos működésűek,



a mozgás térbeli korlátja szerint pályához nem kötöttek,



a működés automatizáltsága szerint automatikus vezérlésűek



a mozgatott anyagok szerint darabáruk szállítására alkalmasak.

2. ábra A drónok vázlatos képe

7

Diplomamunka

Nádor József

A drónos szállítási előnyei: 

rendkívül rövid az áruk átfutási ideje,



elhanyagolható a környezetkárosító hatása (csak energiaigénye van),



nem jelenik meg a pályák kiépítésének költsége,



kicsi a szállítás fajlagos energiaigénye,



kis élőmunka igény (automatizált rendszer),



díjszabása lehet egységes

A drónos szállítás hátrányai: 

csak nagyon kis méretű és tömegű áru szállítására alkalmas,



a szállítási távolság korlátozott,



kizárólag meghatározott területeken valósítható meg a szállítás.

3.2. A drónok felépítése A drónok anyagmozgatási eszközként való felhasználásakor minden esetben egy többrotoros helikopterre kell gondolni. A rotorok száma eltérő lehet, általában négy (quadrocopter), hat (hexacopter) vagy nyolc (octocopter) rotort alkalmaznak, a működi elv azonban minden esetben megegyezik. Egy quadrocopter elvi felépítése a 3. ábra látható:

3. ábra A drónok felépítése: 1. giroszkóp, gyorsulásmérő, 2. rádió antenna, 3. váz, 4. motor vezérlő panel 5. motor, 6. propeller 7. fő vezérlő panel, 8. akkumulátor

8

Nádor József

Diplomamunka

A drónok esetében rendkívül sokféle megvalósítással lehet találkozni, azonban néhány főbb elem mindegyiken megtalálható. A vázuk sok esetben szénszálas anyagból készül, a cél természetesen a kis tömeg és a különböző mechanikai hatásokkal szembeni ellenállás. A váz átmérője 500mm környékén mozog általában. A felhajtóerőt a rotorokat hajtó kefe nélküli (brushless) egyenáramú motorok biztosítják. A hagyományos (kefés) egyenáramú motornál jobb hatékonyság és megbízhatóság jellemzi, kisebb zaj, valamint hosszabb élettartam (nincs kefe, ami elkopjon), emellett nem keletkeznek szikrák és kisebb az elektromágneses interferencia (EMI) is. Minden motorhoz egyenként kapcsolódik egy vezérlő áramkör (Electronic Speed Controller - ESC) amelynek a feladata a motorok fordulatszámának szabályozása, irányának beállítása esetlegesen a motorok fékezésének vezérlése. A motorvezérlő áramkörökhöz kapcsolódik a fő vezérlő áramkör, amely begyűjti a szenzorok adatait, ezek alapján szabályozva a motorvezérlőket. A legalapvetőbb szenzorok, amelyek megtalálhatók a drónokon, a giroszkóp és a gyorsulásmérő. Ezeknek az értékeivel már képes az egy helyben történő lebegésre. Megtalálható még egy rádiós modul, amellyel lehetővé válik a kommunikáció az irányítóval. Tartalmazhat még távolság érzékelőket, amelyek

működhetnek lézeres, optikai,

esetleg ultrahangos

elven.

Segítségükkel meghatározhatóak a közelben lévő akadályok vagy akár a magasság is. Nagyobb magasságok esetén légnyomás érzékelő használata szükséges. Ezek mellett a rendszer része lehet egy kamera is, amellyel alakzat felismerésre nyílik lehetőség. A drónokon helyet kap még egy akkumulátor is, amely megszabja a repülési időtartamot.

3.3. A drónok működése A többrotoros helikopterek már régóta léteznek, de a gyakorlatban nem elterjedt típusai a helikoptereknek. Elterjedésüknek gátja kezdetben a motorok egymástól független, ugyanakkor

összehangolt

működtetésének

bonyolultsága

és

megvalósításának

költségessége volt. Az első ilyen helikoptereket robbanómotorral hajtották, de a módszer nem bizonyult működőképesnek. A technika fejlődésével azonban lehetővé vált a rotorok összehangolt működtetésének megoldása. Bár ilyen típusú ember szállítására alkalmas helikopterek soha nem jutott el valódi civil vagy katonai alkalmazásig, kisméretű, pilótanélküli társaikkal viszont az utóbbi időben egyre gyakrabban találkozni. Ez köszönhető az elektronika és szabályzástechnika fejlődésének. Mindemellett meg kell

9

Nádor József

Diplomamunka

említeni, hogy az ilyen típusú helikopterek kialakítása mechanikailag egyszerűbb a hagyományos helikopterekénél, hiszen nincs szükség a bonyolult és drága rotoragyra. A gép mozgását a rotorok szögsebességeinek változtatásával lehet befolyásolni, semmilyen más beavatkozó jelre nincs szükség. Egy quadrocopter mozgása például következőképpen történik (4. ábra): 

a rotorok kizárólag felfelé ható erő kifejtésére képesek,



a szemközti rotorok azonos irányban forognak, kettő az óramutató járásával megegyező, kettő pedig azzal ellentétes irányban,



az emelkedéshez vagy süllyedéshez mind a négy rotor fordulatszámát azonos mértékben kell változtatni,



ha csak két szemközti rotor fordulatszámát növeljük, akkor lehetőség van a függőleges tengely menti forgásra,



ha az egyik rotor fordulatszámát növeljük, a vele szemközti rotorét pedig csökkentjük úgy, hogy a másik két pár változatlan marad akkor a helikopter dőlésszöge fog változni.

4. ábra Magasság, forgás és dőlésszög változtatás

3.4. A drónos szállítási rendszerek eddigi tesztjei A drónok logisztikai alkalmazására jelenleg csak néhány példa van, viszont az utóbbi időben több cég nyilatkozik arról, hogy kutatják a technológiában rejlő lehetőségeket, esetleg már tesztelnek is ilyen típusú rendszereket. Az Egyesült Arab Emírségek kormánya egy olyan rendszer tesztelését kezdte meg 2014. februárjában, melynek segítségével az eddig hagyományos postai úton kiküldött hivatalos dokumentumokat majd drónok szállítanák az állampolgárok házához. A tervek szerint a drónok retinaszkennerrel és ujjlenyomat-olvasóval is fel lesznek szerelve, hogy a fogadó felet azonosítani tudják a csomag átadása előtt. Az Egyesült Arab Emírségek egyébként 10

Nádor József

Diplomamunka

már teszteli a kis távirányítású légi járművek használhatóságát, a rendőrség például nagyobb sportrendezvények biztosításakor használja a terület légi megfigyelésére, a tűzoltóság pedig a tűzesetek hatékonyabb kezelése érdekében kezdte használni azokat. [3] A DHL is már bejelentette, hogy végrehajtották az első sikeres drónkísérletüket, melynek során egy csomagot szállítottak egy gyógyszertárból a cég központjába. A kisméretű, sárgára festett, négyrotoros gép (a cég közleményében Parcelkopternek nevezi) körülbelül két perc alatt tette meg az egy kilométeres távot, ledobta a csomagot, majd visszarepült a kiindulási pontra. A teszt során a drón még négyszer ismételte meg a manővert sikeresen. [4] A UPS, a világ legnagyobb csomagküldő vállalata is már jó ideje teszteli a drónokat csomagok és áruk mozgatására, viszont ők nem kizárólag kereskedelmi felhasználásban gondolkodnak, hanem sokkal inkább a raktárhelyiségek közti csomagmozgatásban, illetve repterek és távolabbi depók közti szállításban vennék nagy hasznát a robotizált járműveknek, jelentősen csökkentve ezzel a költségeket és a szállítási időket. [5]

5. ábra DHL Parcelkopter

A legérdekesebb és legkonkrétabb terve azonban a világ legnagyobb online áruházának az Amazonnak van a drónok használatával kapcsolatban. 2013 decemberében bejelentette, az Amazon Prime Air nevű leendő új szolgáltatását, ami 30 percen belüli kiszállítást ígér a jövőben robotrepülők segítségével. A tervek szerint maximum 2,2 kg súlyú csomagokat 16 kilométeres távolságra szállítanák octocopterek segítségével. A súlyhatár nem tűnhet nagynak, azonban az Amazon termékeinek a 86%-a esik bele ebbe az intervallumba. A

11

Nádor József

Diplomamunka

vásárlóknak tehát az online áruházban történő megrendelés leadásakor csak ki kellene választani a Prime Air szolgáltatást, majd megjelölnie azt a helyet ahova a csomagot a gép a kiszállításkor el tudná helyezni.

6. ábra Amazon Prime Air

A technikai nehézségek mellett nem elhanyagolható tényező a szabályozás hiánya sem, ezért az amerikai légügyi hatóság engedélyekhez kötnék a drónok használatát. A robotokra szerelt kamerák és érzékelők miatt tartanak a magántulajdon megsértésétől és a megfigyelésektől is, hiszen a hátsó udvarokba vagy ablakon át képet kaphat a cég a vásárlási preferenciákról, utat engedve a célzott reklámok. Ráadásul mindezek mellett még a balesetek kockázatával is számolni kell. [6][7]

12

Diplomamunka

Nádor József

4. Az útvonal tervezési probléma ismertetése 4.1. A drónok útvonal tervezési problémáinak bemutatása Az útvonal tervezési probléma alapjául tekintsük az Amazon cég drónos szállításra vonatkozó terveit. A termékeket a vevő, a cég internetes áruházában tudja kiválasztani és megrendelni. A szokásos rendelési adatokon túl meg kell adnia az áru lerakási helyét is. Az Amazon központi rendszere fogadja az adatokat, majd továbbítja a helyi depónak, ami megfelelő közelségben van a vevőhöz. Ez a helyi raktár, ami megkapta a szállítási koordinátákat valamint a kiszállítani kívánt cikkszámot olyan dobozokba helyezi el az árut, amely felszerelhető a drónokra. A drónok az áruval ezután felrepülnek egy megfelelő magasságba a célkoordinátához repülnek, majd ott leereszkednek és leteszik az árut, a visszaút pedig ugyanazon az útvonalon történik. Miután visszaérkezett a drón, egy esetleges akkumulátorcsere után újabb csomagot tud elszállítani. Amennyiben egy ilyen rendszer működése kezdetét venné, a rendelési igények megnövekedését eredményezné, hiszen hosszabb távon egy gyorsabb, költséghatékonyabb, nyomon követhetőbb szállítást biztosítana. Mivel minden egyes megrendeléshez egy külön drónra lenne szükség, egy nagyobb város esetén rengeteg oda-vissza útra lenne szükség. Ha javítani szeretnénk a rendszer hatékonyságán, akkor egy drónnak egynél több csomagot kellene tudnia szállítania, és egy körúttal elhelyeznie őket úgy, hogy a lehető legkisebb távolságot tegye meg. Ha sok koordináta adott ahova szállítani kell, akkor ezeket a pontokat még ráadásul fel is kell osztani a drónok között úgy, hogy minél kevesebb drónra legyen szükség. A drónok alapvetően háromféle korláttal rendelkeznek, melyeket figyelembe kell venni: 

távolsági korlát,



a maximálisan szállított csomagok száma,



súlykorlát.

A távolsági korlátot az akkumulátor kapacitása határozza meg elsősorban. Ha egy feltöltéssel például 10km-t tudnak megtenni, akkor a depó ennek a felében, egy 5km sugarú körben tudja biztosítani a csomagok kiszállítását drónokkal. A maximálisan szállított csomagok száma a felszerelhető tárolók számával egyezik meg, tehát egyszerre ennyi helyre tud kiszállítani, mielőtt visszatérne. A súlykorlát is összefügg ezzel, a szállított csomagok össztömege nem lehet több egy meghatározott értéknél, mivel egy

13

Nádor József

Diplomamunka

bizonyos határon túl a motorok terhelése miatt a megtehető távolság drasztikusan csökkenne. Adott tehát egy központi raktár, amit a kiindulási pontnak tekintünk, és más pontok, ahova a csomagokat kell kiszállítani valamint távolsági és kapacitás korlát. Mindezt szemléltethetjük egy gráfon ahol a depó és a szállítási koordináták a gráf pontjainak felelnek meg, a köztük lévő távolságok pedig a gráf éleinek hosszával egyeznek meg. Ezt a (teljes) gráfot kell bejárni a minimális számú körutakkal úgy, hogy a körutak mindegyike érinti a gráfnak egy kitüntetett pontját (depó) és a körutak lefedik a gráf minden más pontját, valamint ezeken a pontokon pontosan egyszer haladnak át. Mindemellett adott a körutak pontjainak maximális száma (kapacitás korlát) is, és a körutak maximális úthossza (távolság korlát vagy súlykorlát) is. A matematikában ennek a problémának az alapját az utazóügynök problémának (Travelling Salesman Problem - TSP) hívják, jelen feladat megoldásához pedig ennek egy kibővített (több ügynökös) változatára (Multiple Travelling Salesman Problem - MTSP) lesz szükség. A 7. ábra szemlélteti egy egyszerű TSP problémának a megoldását, amelyről akár ránézésre is megállapítható, hogy az optimális megoldás.

7. ábra Az utazóügynök probléma megoldása

14

Nádor József

Diplomamunka

A 8. ábra látható ugyanennek a ponthalmaznak egy olyan megoldása ahol a (199, 255) koordináta egy kitüntetett pont és kapacitás korlátja (a körutak által lefedett maximális pontok száma) négy. Itt szintén az optimális megoldás látható, és ez már tulajdonképpen az MTSP probléma megoldása.

8. ábra Az utazóügynök probléma többügynökös változata

4.2. Az utazó ügynök probléma meghatározása [8] Legyen adott 𝑛 város és jelöljük ezeket az 1, 2, … , 𝑛 számokkal. Legyenek ismertek az egyes városok közötti nemnegatív utazási költségek (vagy távolságok, vagy idők), jelölje ezeket 𝐶𝑖𝑗 , amely értékeket egy 𝐶 = (𝐶𝑖𝑗 ) mátrix segítségével adunk meg. Egy ügynöknek munkája során minden városba el kell mennie. Az utazó ügynök feladat a legkisebb költségű (vagy legrövidebb távolságú, vagy legrövidebb idejű) körút meghatározása oly módon, hogy minden várost csak egyszer látogathat meg az ügynök a körútja során. Feladatunk tehát megállapítani, hogy milyen sorrendben látogassa meg az ügynök a városokat. Legyen a feladat döntési változója 𝑥𝑖𝑗 , ahol 1, 𝑥𝑖𝑗 = { 0,

ha az ügynök az i városból a j városba utazik egyébként

15

Nádor József

Diplomamunka

A körúthoz szükséges feltétel, hogy egy tetszőleges 𝑖 városból egy és csak egy városba mehet az ügynök, ezt az alábbi összefüggéssel írhatjuk le és ennek minden 𝑖 városra igaznak kell lennie: 𝑥𝑖1 + 𝑥𝑖2 +. . . +𝑥𝑖𝑛 = 1,

𝑖 = 1, … , 𝑛

A körúthoz szükséges feltétel továbbá az is, hogy egy tetszőleges 𝑗 városba egy és csak egy városból érkezhet az ügynök, ezt az alábbi összefüggéssel írhatjuk le és ennek minden 𝑗 városra igaznak kell lennie: 𝑥1𝑗 + 𝑥2𝑗 +. . . +𝑥𝑛𝑗 = 1,

𝑗 = 1, … , 𝑛

Szükséges továbbá az 𝑥𝑖𝑗 = 1 változók indexeire vonatkozó indexlánc feltétel, amely biztosítja, hogy a megoldás körút: 𝑖1 , 𝑖2 , … , 𝑖𝑛−1 , 𝑖𝑛 , 𝑖1, ahol 𝑖𝑗 a meglátogatott városok és minden 𝑗-re (𝑗 = 2,3, … , 𝑛) különböző. A feladat célfüggvénye, azaz a körút végrehajtásának költsége: 𝑐11 , 𝑥11 + 𝑐12 , 𝑥12 +. . . +𝑐𝑖𝑗 , 𝑥𝑖𝑗 +. . . +𝑐𝑛𝑚 , 𝑥𝑛𝑚 . Mivel 𝐶𝑖𝑖 = ∞ (𝑖 = 1,2, … , 𝑛) választással a minimalizálás miatt mindig biztosítható az 𝑋𝑖𝑖 = 0 megoldás, így a következőkben mindig feltesszük, hogy 𝐶𝑖𝑖 = ∞. Az utazó ügynök feladat matematikai megfogalmazása tehát a következő: 𝑛

𝑛

∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗 → 𝑚𝑖𝑛 𝑖=1 𝑗=1 𝑛

∑ 𝑥𝑖𝑗 = 1,

𝑖 = 1, … , 𝑛

𝑗=1 𝑛

∑ 𝑥𝑖𝑗 = 1,

𝑗 = 1, … , 𝑛

𝑖=1

𝑥𝑖𝑗 = 0 vagy 1,

𝑖, 𝑗 = 1, … , 𝑛

és a megoldás körút

16

Diplomamunka

Nádor József

4.3. A heurisztikus módszerek szükségessége [9] Annak érdekében, hogy kimutassuk, a lehetséges útvonalak közül melyik a legrövidebb (analóg módon legrövidebb időben és legkevesebb költségét tekintve), meg kell vizsgálnunk az összes lehetséges variációt, majd kiválasztani a minimumát ami 𝑛! számú számítást igényel. A faktoriális számsort egy ma rendelkezésre álló átlagos személyi számítógép legfeljebb 9-ig képes belátható időn belül kezelni, ami azt jelenti, hogy ezzel a módszerrel mindössze 9 földrajzi pont között határozhatunk meg optimális útvonalat. Különleges technikai berendezésekkel, jelen fejlettségi szinten a lehetőségek mindössze 12-ig bővíthetők, amely így is messze alatta marad a valós helyzetekben előálló számoknak, ahol nem ritka a százas nagyságrendű megoldandó feladat sem. A probléma enyhítésére köztes, ún. heurisztikus megoldásokat alkalmazhatunk, amelyek ismert megközelítése, hogy a lehetséges útvonalak közül csak néhány, véletlenszerűen kiemelt variációt vizsgál és vet össze. Az összevetésekből végül valószínűsíthetően optimális eredményt szűr ki. Ennek a módszernek hátránya, hogy pusztán közelítőleges eredményt ad. Viszonylag kicsit annak a valószínűsége, hogy a kapott eredmény a globális optimum lesz.

17

Nádor József

Diplomamunka

5. Heurisztikus algoritmusok ismertetése [13] A metaheurisztikus algoritmusok olyan informált (heurisztikus) keresési algoritmusok, amelyek problémaspecifikus tudást is felhasználnak a megoldás megtalálása során. Az általános jellemzőjük, hogy egy heurisztika segítségével választják ki a következő lépésben kiértékelendő csomópontokat, ami az optimális megoldás elhelyezkedésére vagy távolságára ad becslést.

5.1. Evolúciós algoritmusok Az evolúciós algoritmusok populáció alapú heurisztikus optimalizációs algoritmusok. A biológiai értelemben vett evolúció alapján működnek, egyszerűsített modellezései az evolúciónak. Az ember számtalan probléma megoldásához merítette az alapötletet a természetből, például: 

madarak szárnya – repülőgép szárny,



bambuszrúd – rúdugrók üvegszálas rúdja,



halak léghólyagja – tengeralattjárók merülése berendezése,



emberi szemlencse – fényképezőgép optikája.

Amit az ember gondolkodással próbál megoldani, azt a természet gyakran hatékonyabban oldotta meg a változatosság és a szelekció eszközével. A többnyire kétszülős biológiai szaporodás és a többnyire külső hatásoknak köszönhető véletlenszerű megváltozás, a mutáció az egyedek sokszínűségét eredményezi. A túlélésért folyó verseny a jobb, életképesebb egyedek kiválogatódását, tulajdonságaik továbbörökítésének lehetőségét hordozza magában. E két működés a populáció környezeti elvárásoknak való jobb megfelelését, állandó alkalmazkodását jelenti. Az

evolúciós

algoritmusok

populációjának

egyedei

megfeleltethetők

a keresés

állapotterében található állapotok egy részhalmazának, az egyedek életképességét, jóságát mérő ún. fitness függvény megfeleltethető a keresés kritériumfüggvényének.

18

Nádor József

Diplomamunka

9. ábra Az evolúciós algoritmusok általános működése

Az evolúciós algoritmusok lépései a következők: 

legyen P0 a kezdeti populáció, k=0 a ciklusváltozó kezdőértéke



ha a megállási kritérium teljesül, az algoritmus adja vissza a Pk populációt



egyébként a Pk populáció bővítése szükséges új egyedekkel



Pk populációból az új Pk+1 populáció előállítása szelekcióval



a k ciklusváltozó inkrementálása és a 2. pont ismétlése

A 3. pontban a bővítés alkalmazhat szülőválasztást, keresztezést és mutációt. A 4. lépés feladata a populáció létszámának eredeti értéken tartása a vesztes egyedek törlésével.

5.2. A genetikus algoritmus A genetikus algoritmus egy globális kvázioptimum megtalálására kifejlesztett kereső algoritmus, mely alapvetően problémafüggetlen. A problémára vonatkozóan rendelkezésre álló információ bevihető az algoritmusba a valós egyedeknek megfelelő fenotípusról a számításban alkalmazott modelljére, a genotípusra való áttéréskor, valamint a keresztezés és a mutáció módjának megválasztásakor. Az ily módon kialakított, problémára szabott genetikus algoritmusok hatékonysága megnő. A globális optimum megtalálásában az egzakt analitikus módszerekhez viszonyítva lassú és pontatlan, de diszkrét állapottereken is működik, és igénytelen a feladattal szemben.

19

Diplomamunka

Nádor József

A genetikus algoritmus nevét az élőlények utódaiban megjelenő kombinálódott szülői génekről, mint az utód tulajdonságainak hordozójáról kapta. A genetikus algoritmus alkalmazásának kulcskérdése a fenotípusról genotípusra való leképezés, azaz az egyed egyes tulajdonságait reprezentáló „gének”, azaz kromoszómarészletek kialakítása, tehát minden egyes állapothoz egy karaktersorozat, azaz bitminta rendelhető, amely kihat az alkalmazható operátorokra, végeredményben pedig az algoritmus hatékonyságára. Mivel egyszerre egy populációt, azaz egyedek egy csoportját kezeli, a globális optimum fellelésének megnő az esélye. Az állapottér feltárásában a következők játszanak szerepet: 

a kezdeti populáció egyedeinek eloszlása az állapottéren



a keresztezések interpoláló hatása



a mutációk extrapoláló, a keresztezéssel kialakult belterjességből, lokalizáltságból kivezető hatása

A kezdeti mutációk az állapottér hatékony feltárását eredményezik. A globális optimum köré gyűlt késői populációkból viszont már csak gyorsan elhaló mutációk származnak, mivel azok életképessége a populáció többi tagjához képest alacsony. A populáció fejlődése az egyedek fejlődésén keresztül realizálódik. A szelekciónak köszönhető látszólag spontán fejlődés nem csak a véletlen eredménye: a jobb célfüggvény (fitness) értéket reprezentáló egyedek aránya a populációban egyre nő, míg a kevésbé életképeseké csökken. Az egyedek a módszer memóriájaként is felfoghatók: a jó tulajdonságú egyedek megtartásával az algoritmus megtanulja a jó célfüggvény értéket adó tulajdonságokat, a gyengébbeket eredményező tulajdonságok pedig elfelejtődnek az azokat hordozó egyedek kihalásával.

20

Nádor József

Diplomamunka

10. ábra Példa a genetikus algoritmusra: az egyedek távolsága az optimumtól a 0. és az 5000. iterációban

A szelekciós operátor feladata a szülőegyedek kiválasztása a keresztezés számára. A különféle szelekciós módszerekben közös, hogy a rátermettebb egyedeket jelentősebb arányban választják ki tulajdonságaik továbbörökítésére, de általában a gyengébb egyedek is kapnak egy kis esélyt. Ha a régi populáció legrátermettebb egyede mindig átkerül az új populációba, a szelekció elitista. A szelekcióban alkalmazott technikák a következők: 

Rátermettség: arányos választás, az egyed kiválasztásának valószínűsége arányos a populáció rátermettségi átlagához viszonyított rátermettségével. A rátermettség gyakran azonos az egyedhez tartozó függvényértékkel, ritkábban azonban csak a szelekcióhoz alkalmazott egyedjellemző neve.



Párok versenyeztetése: véletlenszerűen kiválasztott két egyed közül a versenyt nyerő, azaz a nagyobb rátermettségi értékű lesz a kiválasztott. A módszer alkalmazható több, mint két versenyzős esetben is.



Rangsorolás: a keresztezés interpolációs hatásából eredő állapottér feltárás hatásának

lecsökkenését

eredményezi,

ha

mindig

ugyanazok

az

ősök

szelektálódnak, örökítik tovább tulajdonságaikat. Ez a veszély fenyeget azoknál a módszereknél, amelyek a kiválasztást közvetlenül a rátermettség értékére alapozzák. Rangsorolás esetén a közvetlen rátermettségi értékek helyett a rátermettségi sorrendre alapozott szelekciót végzünk. A keresztezés operátor szerepe az utódok, azaz az új egyedek előállítása. A keresztezés megválasztására nincsen általános módszer, mindig az adott feladathoz kell igazodnia. Speciális keresztező operátort igényelhetnek az olyan esetek, amikor összefüggés van a

21

Nádor József

Diplomamunka

gének között (intelligens keresztezés). A leggyakoribb módszerek a keresztezésre a következők: 

egypontos keresztezés: véletlenszerű keresztezési pont kiválasztása

11. ábra Egypontos keresztezés



egyenletes keresztezés: ötven százalék eséllyel cserélődik minden egyes gén

12. ábra Egyenletes keresztezés

A mutáció operátor olyan új egyedet hoz létre, mely mentes a keresztezés belterjességétől, azaz az ősökétől merőben elütő tulajdonságokat hordozhat. A keresztezéstől kisebb gyakorisággal alkalmazott művelet. A módszer lényege az adott egyed kromoszómájának egy véletlenszerűen választott génjét egy másik génre cseréljük ki.

13. ábra A mutáció operátor

22

Diplomamunka

Nádor József

5.3. Az Ant Colony algoritmus működésének bemutatása [10] 5.3.1. Az algoritmus kialakulása Az Ant Colony Optimisation (ACO) a hangyák szociális viselkedésének modellezésén alapuló metaheurisztikus módszer. Az eljárás a biológiai folyamatok által inspirált egyik nagy területhez, a raj intelligencia (Swarm Intelligence) csoporthoz tartozik. Az algoritmusnak az 1992-es publikációja óta számos kiegészítése is megjelent már. Az alapötlet a hangyák élelemgyűjtő viselkedéséből származik, legelső felhasználása pedig ebből adódóan a legrövidebb utak keresésének problémáját hivatott megoldani. Az eljárás számos kombinatorikai probléma megoldását lehetővé teszi. Ezek közé sorolható például az utazó ügynök probléma (TSP), a hátizsák probléma (Knapsack Problem), a kvadratikus hozzárendelési feladat (QAP), a gráf színezési probléma és számos egyéb ütemezési, útvonal tervezési, halmazelméleti és egyéb más jellegű problémák is, mint például elektronikai áramköri tervezés, képfeldolgozás, vagy az adatbányászat. A módszer alapját a hangyák viselkedése adja. Kezdetben véletlenszerűen keresik az élelemforrást. Amennyiben élelmet találnak, visszatérnek a bolyba. Mindeközben feromonnal jelölik meg az utat, így ha más hangyák megtalálják ezt a feromonjelet, akkor nagyobb valószínűséggel választják ezt az utat a véletlenszerű vándorlás helyett. A feromon párologása miatt viszont idővel az útvonal „vonzereje” csökken. Így annak a valószínűsége is, hogy a hangyák a megjelölt utat választják. Minél hosszabb az út, a feromonok annál tovább párolognak, mivel a hangyáknak több időbe kerül az út bejárása. A rövidebb utakon a feromon mennyisége magasabb lesz, mivel ezek gyorsan bejárhatók így a hangyák a feromont gyorsabban pótolják, mint ahogy az elpárologna. A feromon párolgása segíti elő, hogy az algoritmus ne ragadjon le lokális optimumnál. Mikor a hangyák egy rövid utat találnak az élelemforráshoz, a pozitív visszacsatolás miatt igen nagy valószínűséggel fogják azt az utat választani. Az Ant Colony eljárás igen sok kombinatorikus optimálási probléma megoldására alkalmas, és ezek köre az új kutatásokkal egyre szélesedik. Ilyenek például a kvadratikus hozzárendelés, utazó ügynök probléma, vagy éppen a járművek valós idejű irányítása.

23

Nádor József

Diplomamunka 5.3.2. Az algoritmus működése Az Ant Colony optimalizáló módszer lépései: 

a döntési gráf előállítása



a célfüggvény meghatározása



inicializálás és a kezdeti paraméterek beállítása, melyek o az iterációk maximális száma o a hangyák száma o a minimális feromon szint a gráf élein o a feromon párolgási állandó o az útválasztási kitevő



iterációs lépések o a hangyák következő lépésének kiszámítása o feromon aktualizálása

A hangyák a gráf egyes pontjaiban döntési helyzetbe kerülnek, kivéve ha az adott pontból csak egy út vezet tovább, ekkor biztosan azt az utat választják. Egy adott pontba lépés valószínűsége egyenesen arányos a pontba futó élen található feromon mennyiségével. Tehát minél több a feromon az adott élen, annál vonzóbb lesz a hangyák számára, és annál nagyobb valószínűséggel választják azt az utat.

14. ábra Útvonalválasztás

24

Nádor József

Diplomamunka Az útvonalválasztást a következő képlet írja le: 𝛼

(𝜑𝑁𝑥𝑦 )

𝑃𝑁𝑞𝑥𝑦 =

∑𝑛𝑖=1(𝜑𝑁𝑥𝑖 )

𝛼

Ahol: 

𝑃𝑁𝑞𝑥𝑦 : az 𝑦-adik pont felkeresésének valószínűsége az 𝑥. pontból, a 𝑞-adik hangyánál



𝜑𝑁𝑥𝑦 : az 𝑥-edik és 𝑦-adik pontokat összekötő élen lévő feromon mennyisége



𝛼 : útválasztási együttható



𝑛 : az 𝑥-edik pontból kiinduló élek száma



𝑞: a 𝑞-adik hangya

Ha egy hangya eléri a célt, a kezdeti pontba visszaindulva a bejárt útvonalon feromont rak le. Ez fordítottan arányos az általa megtett úttal. A hangyák által befutott mindenkori minimális út költségét tároljuk (𝑀𝑖𝑛(𝐶)), mivel a modellben a lerakott feromon mennyisége a költséggel fordítottan arányos. A lerakott feromon mennyisége a 𝜑𝑁𝑞𝑥𝑦 = 𝜑𝑁𝑥𝑦 +

∑𝑛𝑖=1 𝐶𝑖

2 − 𝑀𝑖𝑛(𝐶) + 1

összefüggéssel számíható. Ahol: 

𝜑𝑁𝑥𝑦 : az 𝑥-edik és 𝑦-adik nodeot összekötő élre kerülő feromon mennyisége



𝑛 : a hangya által bejárt élek száma



𝐶𝑖 : az 𝑖-edik pontba eljutás költsége



𝑀𝑖𝑛(𝐶) : a mindenkori minimális költség

A feromon párolgási folyamat gyakorlatilag a felejtés egy formája. Lehetővé teszi, hogy a hangyák a keresési térben új területeket is felfedezzenek. Megakadályozza, hogy az algoritmus egy lokális optimumnál leragadjon.

25

Nádor József

Diplomamunka A feromon párolgás megvalósítását a 𝜑𝑁𝑥𝑦 > 𝜑𝑚𝑖𝑛 akkor 𝜑𝑁𝑥𝑦 = 𝜑𝑁𝑥𝑦 ∙ (1 − 𝑝) összefüggés szemlélteti, ahol: 

𝜑𝑁𝑥𝑦 : az 𝑥-edik és 𝑦-adik pontokat összekötő élre kerülő feromon mennyisége



𝑝 : a feromon párolgási állandó

5.3.3. Az algoritmus egyes változatai [11] Az alap Ant colony algoritmusnak számos változata jelent meg, amelyek különböző módon javítják a teljesítményét. Az 1. táblázat szemlélteti, hogy a vizsgált algoritmusok milyen hatékonysággal oldják meg a C-TSP (Chinese Travelling Salesman Problem) problémát.

15. ábra A C-TSP probléma optimális megoldása

A kínai utazó ügynök probléma 31 kínai nagyváros körbejárását jelenti. Az algoritmusok a következők: 

Ant System (AS) – az alap algoritmus



Elitist Strategy for Ant System (EAS)



Rank based version AS (ASrank)



Max-Min Ant System (MMAS)



Ant Colony System ACS (ACS)

26

Nádor József

Diplomamunka Száz futtatás során elért eredmények a következők: Algoritmus

Legjobb

Legrosszabb

Optim.

Átlag

arány

Relatív

Iterációk

Átlagos

hiba

száma

idő

AS

15420

15669

0%

15569.05

1.071%

3000

12.221

EAS

15404

15625

48%

15447.4

0.282%

4000

16.409

ASrank

15404

15593

63%

15413.74

0.063%

4000

16.662

MMAS

15404

15593

55%

15428.54 0.159%

5000

20.386

ACS

15404

15779

40%

15442.42

10000

5.546

0.249%

1. táblázat A különböző Ant Colony algoritmusok összehasonlítása

A táblázatban szereplő 15404-es eredményt tekintjük a globális optimumnak, mivel a CTSP problémát előzőleg tizenkét féle algoritmussal tesztelték és mindegyike ezt az optimumot adta. A legjobb és legrosszabb nevű oszlop jelenti az algoritmusok által elért legjobb és legrosszabb eredményeket a száz futás során. Az optim. arány oszlop megadja, hogy milyen arányban sikerült elérni a globális optimumot. Itt megfigyelhető, hogy az alap algoritmus minden esetben leragadt egy lokális optimumnál. Az átlag adja meg a futások átlagos eredményét, a relatív hiba pedig a következőképp számítható: r𝑒𝑙𝑎𝑡í𝑣 ℎ𝑖𝑏𝑎 =

á𝑡𝑙𝑎𝑔 − 𝑔𝑙𝑜𝑏á𝑙𝑖𝑠 𝑜𝑝𝑡𝑖𝑚𝑢𝑚 𝑔𝑙𝑜𝑏á𝑙𝑖𝑠 𝑜𝑝𝑡𝑖𝑚𝑢𝑚

Az egyes algoritmusok lefutási száma (iterációk száma) olvasható még a táblázatban, illetve az átlagos lefutási idejük (átlagos idő) másodpercben. Megfigyelhető hogy a négy továbbfejlesztett algoritmus száz lefutás során mind megtalálja a globális optimumot 31 városnál, viszont ennek az aránya közepesnek mondható (4063%). A táblázat egyetlen jelentős kiugró értékkel rendelkezik, ez pedig az ACS algoritmus átlagos lefutási ideje, amely harmada, illetve negyede a másik három algoritmusnak. Ha mindent számításba veszünk, bár az ACS a leggyengébb találati értékekkel rendelkezik, mégis annak a legcélszerűbb a használata egy TSP probléma megoldásában.

27

Diplomamunka

Nádor József

5.3.4. Az Ant Colony System algoritmus pszeudokódja [12]

Ahol: 

𝑚 : a hangyák száma, általában kis érték, például 10



𝜎 : helyi feromon együttható, az értéke általában 0.1



𝛽 : heurisztikai együttható, általában 2 és 5 közötti érték, például 2.5



𝜌 : feromon párolgási állandó, általában 0.1



𝑞 0 : a legjobb út választásának valószínűsége, étéke általában 0.9

28

Diplomamunka

Nádor József

6. Az inspyred keretrendszer 6.1. A keretrendszer használatának követelményei [14] Az inspyred keretrendszer a Python programozási nyelvhez íródott ingyenes, nyílt forráskódú függvénykönyvtár, amely kibővíti a nyelv képességeit a biológia által inspirált algoritmusokkal. A könyvtár neve is erre utal, az inspire, és a python szavak összetételéből alkották. Az inspyred használatához a következőkre van szükség: 

Python 2.6+ vagy 3+,



Numpy és Pylab python modulok tudományos számításokhoz,



Pylab és Matplotlib modulok az analizáló funkciókhoz,



Parallel Python (pp) modul a többprocesszoros futtatáshoz.

A Python programozási nyelv egy általános célú, magas szintű programozási nyelv, melyet 1991-ben mutattak be. A nyelv tervezési filozófiája az olvashatóságot és a programozói munka megkönnyítését helyezi előtérbe a futási sebességgel szemben. A Python többek között a funkcionális, az objektumorientált, az imperatív és a procedurális programozási paradigmákat támogatja. Dinamikus típusokat és automatikus memóriakezelést használ, ilyen szempontból hasonlít a Perl és Ruby nyelvekhez, emellett szigorú típusrendszerrel rendelkezik. Interpreteres nyelv, ami azt jelenti, hogy nincs különválasztva a forrás- és tárgykód, a megírt program máris futtatható, ha rendelkezünk a Python értelmezővel. A Python értelmezőt számos géptípusra és operációs rendszerre elkészítették, továbbá számtalan kiegészítő könyvtár készült hozzá, így rendkívül széles körben használhatóvá vált. Párhuzamosan fejlesztik a nyelv 2-es és 3-as verzióját, mivel az újabb verzió visszafelé nem kompatibilis. Jelenleg még a különböző modulok jobban támogatják a régebbi verziót ezért a feladat megoldása során is az került kiválasztásra.

6.2. A keretrendszer működése [15] A keretrendszer megalkotásának alapjául Ken de Jong “Evolutionary Computation: A Unified Approach.” című könyve szolgált. A cél az volt, hogy a probléma-specifikus számításokat különválasszák az algoritmus-specifikus számításoktól. Minden egyes algoritmusnak két probléma-specifikus része van: 

milyen formában kell előállítani a megoldásokat,



hogyan kell kiértékelni a megoldásokat.

29

Diplomamunka

Nádor József

Ezek a komponensek minden bizonnyal mások lesznek minden egyes problémánál. Például egy doboz optimális méreteinek meghatározásánál a megoldás egy három elemű, valós számokból álló lista lesz, melyek a hosszúságot, szélességet, és a magasságot reprezentálják. Ezzel ellentétben egy labirintusból való kijutás megoldásához egy listára van szükség elempárokkal, melyeknél minden pár tartalmazza a szomszédos elemeket. Másrészről vannak algoritmus specifikus komponensek is, melyek nagy valószínűséggel nem rendelkeznek információval a problémáról, melyeket megoldanak. Ezek közé a komponensek közé tartozik a szülők kiválasztásáért felelős mechanizmus, az utódok megalkotásának módja, illetve az, hogy az egyedek hogyan cserélődjenek az egyes generációkban. Az n-pontos keresztezés operátor használatánál például tudnunk kell, hogy megoldásként egy listát várunk, melyet fel lehet vágni több darabra, de arról nem szükséges informálni az algoritmust, hogy milyen típusú adatokat tartalmaz a lista. Ezek lehetnek számok, egy szöveg, vagy bármilyen egyéb típus. A fő tervezési alapelve tehát a keretrendszernek, hogy el legyenek szeparálva a problémaés algoritmus-specifikus komponensek, így lehetőség legyen minél általánosabb célú algoritmusok létrehozására. Az következő elkülöníthető egységekre van felosztva az inspyred keretrendszer: 

probléma-specifikus komponensek o generator: a megoldások létrehozásának módja, o evaluator: a megoldásokhoz rendelt fitness értékek számításának módja,



algoritmus- specifikus komponensek o observer: az egyes iterációk közötti állapotok megfigyelése, o terminator: az algoritmus leállási feltétele, o selector: megadja, mely egyedekből legyenek szülők, o variator: az utód egyedek meghatározásának módja, o replacer: megadja, hogy mely egyedek kerüljenek át a következő generációba, o migrator: a megoldások átkerülésének módja a következő populációba, o archiver: a megoldások tárolásának módja a populáción kívül.

30

Nádor József

Diplomamunka

Minden egyes komponens egy függvény tulajdonképpen, melyet a felhasználónak kell megírni. A 16. ábra szemlélteti, hogy a felsorolt komponensek hogyan épülnek be a rendszerbe, tehát az egyes függvények milyen sorrendben kerülnek meghívásra. A kezdeti populáció létrehozása a kiindulási egyedekből, és a generator használatával A kezdeti populáció kiértékelése az evaluator használatával A kiértékelések számának beállítása kezdeti populáció méretének számára A generációk számának 0-ra állítása Az observer meghívása a kezdeti populáción Amíg a terminator értéke nem igaz, ismétlés: Szülők kiválasztása a selector segítségével Az utód egyedek inicializálása a szülők számára Ismétlés minden egyes variator függvényen: Az utód egyedek beállítása a variator használatával Az utód egyedek kiértékelése az evaluator segítségével A kiértékelés számának frissítése Az egyedek cseréje a populációban a replacer segítségével Az egyedek áthelyezése a populációban a migrator segítségével Az egyedek archiválása a populációban a migrator segítségével A generációk számának növelése Az observer meghívása 16. ábra Az inspyred működése

A fent felsorolt függvények megírásával gyakorlatilag bármilyen algoritmus elkészíthető, melyekben így az egyes modulok átláthatóan és elkülönítve lesznek tárolva. Emellett természetesen a keretrendszer tartalmaz előre megírt modulokat, és algoritmusokat is. Ezek az algoritmusok a következők:

31

Nádor József

Diplomamunka 

Evolúciós számítások o Egy célfüggvényes 

Genetic Algorithm



Evolution Strategy



Simulated Annealing



Differential Evolution Algorithm



Estimation of Distribution Algorithm

o Több célfüggvényes





Pareto Archived Evolution Strategy (PAES)



Nondominated Sorting Genetic Algorithm (NSGA-II)

Raj intelligencia algoritmusok o Particle Swarm Optimization o Ant Colony Optimization

32

Diplomamunka

Nádor József

7. Heurisztikus algoritmusok tesztelése Az inspyred algoritmusainak összehasonlítására készítettem különböző teszteket Python programozási nyelven, amelyek az algoritmusok hatékonyságait, valamint a futási idejüket vizsgálják. Folytonos problémák esetében megoldás mindig a valós számok halmazán értelmezett. A tesztelést egy célfüggvényes széles körben használt tesztfüggvényeken, valamint diszkrét optimalizálási problémákon végeztem el: 

Folytonos problémák o Ackley o Griewank o Rastrigin o Rosenbrock o Sphere



Diszkrét problémák o Knapsack o Travelling Salesman Problem

A folytonos problémák megoldásához a következő függvények kerültek felhasználásra: 

Genetic Algorithm - GA



Evolution Strategy - ES



Differential Evolution Algorithm - DEA



Particle Swarm Optimization – PSO

A diszkrét problémák a következő algoritmusokkal lettek tesztelve: 

Evolutionary Computation- EC



Ant Colony System - ACS

A tesztek során az algoritmusok a keretrendszer által ajánlott paraméterekkel lettek lefuttatva. A GA és ES algoritmusokhoz Gauss mutáció lett hozzáadva, ami a futási idejüket nagyjából 10-20%-al növelte, viszont a hatékonyságuk nagyságrendekkel jobb lett. Minden esetben 30000 iterációt végeztek az algoritmusok, 100-as populáció számnál ez 3000 generációt jelent. Minden esetben 20-szor lettek lefuttatva a különböző tesztfüggvényeken, és ezeknek a futásoknak az átlagai lettek megjelenítve a grafikonokon.

33

Nádor József

Diplomamunka A vizsgált paraméterek a következők: 

fitness értékek: az algoritmusok hatékonyságát mérő szám, a kisebb érték a kedvezőbb



futási idő: az algoritmusok lefutásának átlagos értéke másodpercben kifejezve, természetesen itt is a kisebb éték a kedvezőbb

7.1. Ackley 𝑛

1 𝑛 1 ) ∑ 𝑓(𝑥) = −20𝑒 −0.2 √ ∑ 𝑥𝑖2 − 𝑒 𝑛 𝑖=1 cos(2𝜋𝑥𝑖 + 20 + 𝑒 𝑛 𝑖=1

ahol 𝑛 a dimenziók száma, és 𝑥𝑖 ∈ [−32,32] ahol 𝑖 = 1, … , 𝑛.

17. ábra Az Ackley tesztfüggvény ábrázolása

34

Nádor József

Diplomamunka

Ackley - futási idő 12 10,3436 10 8

6,7916

6 4 2

1,1453

1,1138

0 GA

ES

DEA

PSO

18. ábra Ackley tesztfüggvény – a fitness értékek átlaga

A 18. ábra látható az Ackley tesztfüggvényen mért futási idők átlaga. A többi tesztfüggvényen is ugyanilyen arányúak a mért adatok, csak minimális eltérés tapasztalható. Látható, hogy a GA és PSO algoritmusok nagyságrendekkel gyorsabban futnak le, mint a társaik.

Ackley - fitness értékek 0,0030 0,0025 0,0025 0,0020 0,0020 0,0015

0,0010 0,0005

3,34E-04 6,22E-16

0,0000 GA

ES

DEA

PSO

19. ábra Ackley tesztfüggvény – a futási idők átlaga

35

Nádor József

Diplomamunka

A 19. ábra látható, hogy az EC algoritmus a leghosszabb futásidő ellenére a legrosszabb eredményt produkálta. Hasonlóan rosszul teljesített a GA is, tehát erre a problémára biztosan nem ezek a megfelelő algoritmusok. A DEA valamivel jobb eredményt mutat, de a futásideje is hosszú volt. A PSO algoritmus nagyságrendekkel jobban teljesített és a futási ideje is megfelelő volt.

7.2. Griewank 𝑛

𝑛

𝑖=1

𝑖=1

1 𝑥𝑖 𝑓(𝑥) = ∑ 𝑥𝑖2 − ∏ cos ( ) + 1 4000 √𝑖 ahol 𝑛 a dimenziók száma, és 𝑥𝑖 ∈ [−600,600] ahol 𝑖 = 1, … , 𝑛.

20. ábra A Griewank tesztfüggvény ábrázolása

36

Nádor József

Diplomamunka

Griewank - fitness értékek 0,6 0,4784

0,5 0,4 0,3 0,2 0,1

0,0185

0,0044

1,33E-07

0,0 GA

ES

DEA

PSO

21. ábra Griewank függvény – fitness értékek összehasonlítása

A 21. ábra látható a Griewank tesztfüggvényen végzett mérések eredményei. A függvény jellegéből adódóan itt minden algoritmus rosszabb eredményt adott. A GA algoritmus nagyon messze volt ebben az esetben az optimumtól.

7.3. Rastrigin 𝑛

𝑓(𝑥) = ∑(𝑥𝑖2 − 10 cos(2𝜋𝑥𝑖 ) + 10) 𝑖=1

ahol 𝑛 a dimenziók száma, és 𝑥𝑖 ∈ [−5.12,5.12] ahol 𝑖 = 1, … , 𝑛.

37

Nádor József

Diplomamunka

22. ábra A Rastrigin tesztfüggvény ábrázolása

Rastrigin - fitness értékek 0,00030

2,70E-04

0,00025 0,00020 1,50E-04 0,00015 0,00010 0,00005 6,88E-06

0,00E+00

0,00000 GA

ES

DEA

PSO

23. ábra Rastrigin függvény – fitness értékek összehasonlítása

A 23. ábra látható Rastrigin függvényen is hasonló eredmény rajzolódik ki, mint a többi grafikonon, a PSO algoritmus ebben az esetben nulla értéket adott.

38

Nádor József

Diplomamunka

7.4. Rosenbrock 𝑛−1

𝑓(𝑥) = ∑[100(𝑥𝑖2 − 𝑥𝑖+1 )2 + (𝑥𝑖 − 1)2 ] 𝑖=1

ahol 𝑛 a dimenziók száma, és 𝑥𝑖 ∈ [−5,10] ahol 𝑖 = 1, … , 𝑛.

24. ábra A Rosenbrock tesztfüggvény

Rosenbrock - fitness értékek 0,045

0,0414

0,040 0,035 0,030

0,025

0,0207

0,020 0,015 0,010

0,0075

0,005 1,12E-06 0,000 GA

ES

DEA

PSO

25. ábra Rosenbrock függvény – fitness értékek összehasonlítása

39

Nádor József

Diplomamunka

A Rosenbrock egy egészen más jellegű függvény, mint az előzőleg bemutatottak, itt a GA az előzőekhez képest jobb eredményt mutat (25. ábra).

7.5. Sphere 𝑛

𝑓(𝑥) = ∑ 𝑥𝑖2 𝑖=1

ahol 𝑛 a dimenziók száma, és 𝑥𝑖 ∈ [−5.12,5.12] ahol 𝑖 = 1, … , 𝑛.

26. ábra A Sphere tesztfüggvény

40

Nádor József

Diplomamunka

Sphere - fitness értékek 1,2E-06 1,00E-06 1,0E-06

9,18E-07

8,0E-07 6,0E-07 4,0E-07 2,0E-07 5,02E-08

8,16E-35

0,0E+00 GA

EC

DEA

PSO

27. ábra Sphere függvény – fitness értékek összehasonlítása

A Sphere tesztfüggvény a legegyszerűbb függvény a felsoroltak közül. Ebben nincsenek lokális optimumok, tehát a függvények nem tudnak ezekben elakadni. Egyszerű jellege az eredményeken is meglátszik, itt minden algoritmus megfelelően teljesített, a PSO ismét kategóriákkal jobb eredményt adott. Összességében elmondható, hogy a különböző evolúciós számításokon alapuló algoritmusok közepes eredménnyel képesek közelíteni a tesztfüggvények optimumait. Természetesen a futási idejük, vagy éppen a teljesítményük javítható a paraméterek állításával. A legnagyobb problémájuk hogy a teljesítményük a probléma függvényében nagy ingadozást mutat. Előre nehezen megjósolható hogy az adott problémára melyiknek az alkalmazása adja a legkedvezőbb eredményt, ezt gyakorlatilag csak próbálkozással lehet kideríteni. A raj intelligencia algoritmusokhoz tartozó PSO az előzőekkel ellentétben minden egyes tesztben rendkívül jó eredményeket produkált. Futásideje megfelelő volt, a fitness értékekben pedig nagyságrendekkel jobban teljesített. Mindemellett a paraméterek módosításával ennél az algoritmusnál is fokozható a teljesítmény.

41

Nádor József

Diplomamunka

7.6. Hátizsák feladat [8] A hátizsák feladat az előzőekkel ellentétben már egy diszkrét optimalizálási probléma. A feladat elnevezése a következő megfogalmazásra utal: egy turista hátizsákjában n különböző hasznos holmit szeretne a túrájára vinni. Az egyes tárgyak súlya legyen 𝑎1 , 𝑎2 , … , 𝑎𝑛 és a hátizsákjában legfeljebb 𝑏 súlyt tud elvinni. Az összes tárgy nem fér a hátizsákjába, ezért a turista szelektálni kénytelen. Minden tárgynak ad egy, a tárgynak a túra során betöltendő hasznosságát mérő számértéket, amelyek legyenek 𝑐1 , 𝑐2 , … , 𝑐𝑛 . A válogatást úgy végzi, hogy a súlykorlátozás betartása mellett a magával vitt tárgyak összértéke (összhasznossága) minél nagyobb legyen. A válogatást tárgyanként egy 0 vagy 1 értéket felvehető döntési változóval írhatjuk le. Legyen a döntési változó 𝑥𝑗 , amelynek értéke legyen az alábbi: 𝑥𝑗 = {

1, ha a j-edik tárgyat a turista beteszi a hátizsákjába 0, ha a j-edik tárgyat a turista nem teszi be a hátizsákjába.

A ∑𝑛𝑗=1 𝑎𝑗 , 𝑥𝑗 mennyiség azt jelenti, hogy mennyi a hátizsákba behelyezett tárgyak összes súlya, a ∑𝑛𝑗=1 𝑐𝑗 , 𝑥𝑗 mennyiség pedig azt jelenti, hogy mennyi a hátizsákba behelyezett tárgyak összes hasznossága. Így a fenti probléma matematikai megfogalmazása a következő: Legyenek adottak a 𝑐 = (𝑐1 , 𝑐2 , … , 𝑐𝑛 ), 𝑎 = (𝑎1 , 𝑎2 , … , 𝑎𝑛 ) vektorok és a b szám, amelyek pozitív egészek és ∑𝑛𝑗=1 𝑎𝑗 > 𝑏. Meghatározandó az 𝑥 = (𝑥1 , 𝑥2, … , 𝑥𝑛 ) vektor úgy, hogy 𝑛

∑ 𝑐𝑗, 𝑥𝑗 → 𝑚𝑎𝑥 𝑗=1 𝑛

∑ 𝑎𝑗 𝑥𝑗 ≤ 𝑏 𝑗=1

𝑥𝑗 = 0 vagy 1,

𝑗 = 1,2, … , 𝑛

Általában minden olyan integer programozási feladatot hátizsák feladatnak neveznek, amelynek csak egyetlen feltétele van. A fentebb megfogalmazott hátizsák feladatot bináris hátizsák feladatnak is nevezhetjük, amelynek két fő jellemző tulajdonsága van: 

csak egy feltételt tartalmaz,



a benne szereplő összes alapadat (𝑎𝑗 , 𝑐𝑗 , 𝑏) pozitív egész szám.

42

Nádor József

Diplomamunka A hátizsák feladaton végzett tesztek a következő ábrán láthatóak:

Knapsack Problem - eredmények 5000 4302

4500 4000

3955

4141 3824

3543

3500 3000

2629

2500 2000 1500 1000 454

500

105

0 Átlag

Maximum EC

Minimum

Szórás

ACS

28. ábra A hátizsák feladaton végzett tesztek eredményei

A teszt során az algoritmusok leállítási feltétele egy időkorlát volt. Ez az idő 3 másodpercre lett állítva, és a 20 legjobb fitness érték lett feljegyezve mindkét algoritmus esetében és a következő statisztikák lettek az adatokból kiszámítva: 

átlag,



maximum – a sorozat legjobb fitness értéke,



minimum –a sorozat legrosszabb fitness értéke,



szórás.

A mérési adatokon látható hogy az EC algoritmus nagyon változó eredményeket produkált, bár a legjobb eredmény mellett a legrosszabbat is ez az algoritmus szolgáltatta. Az ACS algoritmus ehhez képest konzisztensnek tekinthető eredményekkel rendelkezik. Ezt a megállapítást jól tükrözi a szórás, amely a nagyjából a negyede az EC algoritmusnak.

43

Nádor József

Diplomamunka

7.7. Az utazóügynök probléma

Traveling Salesman Problem - eredmények 3000 2500

2304

2412

2487

2555 2239

2240

2000

1500 1000 500 68

67

0 Álag:

Maximum

EC

Minimum

Szórás

ACS

29. ábra Az utazóügynök feladaton végzett tesztek eredményei

Az utazóügynök probléma megfogalmazása a 4.2 fejezetben olvasható részletesen. A teszt egy 30 pontból álló problémán lett lefuttatva 20-20 alkalommal. Az algoritmusok futási ideje 1 másodperc volt mindkét esetben. Az eredmények nem mutatnak nagy eltérést ebben az esetben, az EC algoritmus minden esetben egy kicsivel jobban teljesít. Látható hogy az utazóügynök feladat megoldására mind az evolúciós alapú algoritmus mind a raj intelligencia alapú algoritmus jól használható a probléma megoldására.

44

Diplomamunka

Nádor József

8. Az elkészített algoritmus bemutatása Az előző fejezetekben ismertetésre került, hogy a drónos áruszállítás során milyen megoldandó problémák lépnek fel. Ezek közül az egyik a legrövidebb utak kiválasztásának problémája, melyet a matematikában tulajdonképpen többügynökös utazóügynök problémának (Multiple Travelling Salesman Problem) nevezünk. Az algoritmus, amelyet készítettem alapvetően ezt a problémát hivatott megoldani, bár nem csak és kizárólag a drónos szállításra alkalmazható, hanem gyakorlatilag bármely hasonló (egy vagy több) ügynökös utazóügynök feladat megoldására felhasználható. Az algoritmus Python programozási nyelven íródott, és a már részletesen ismertetett inspyred keretrendszer képzi az alapját. Az algoritmus továbbá futtatható és használható a forrásfájl elindításával, bármilyen programozói tudás nélkül, vagy akár beilleszthető más Pythonban írt forráskódba is modulként, és használható a beépített függvényekhez hasonlóan.

8.1. Az algoritmus használata Az algoritmus és a hozzá tartozó függvények egy mTSP.py fájlban találhatóak, ez a fájl a következő struktúrával rendelkezik: 

MTSPSolver (osztály) o set_points() o set_ec_algorithm() o set_acs_algorithm() o solve()



make_points()



plot_points()

Az alábbi felsorolásból látni, hogy egyes metódusok az MTSPSolver osztályban találhatók, ezek az algoritmus részét képzik, tehát a működését befolyásolják, a többi (az osztályon kívül eső) függvények az algoritmus használatát könnyítik meg, például a pontok megadását segítő grafikus felület megjelenítésével, vagy éppen az eredményhalmaz megjelenítésével. Hasonló függvényekkel természetesen szabadon bővíthető az algoritmus.

45

Nádor József

Diplomamunka

A használathoz mindenek előtt rendelkezni kell az inspyred keretrendszerrel1, valamint az ahhoz szükséges modulokkal. Az ehhez szükséges összes információ megtalálható a hivatalos weboldalon. Az inspyred működéséhez szükséges követelmények telepítése után létre kell hozni egy új (.py kiterjesztésű) fájlt, és importálni az mTSP osztályt a következő módon: from mTSP import * Ehhez az mTSP.py fájlnak mindenképpen egy olyan útvonalon kell elhelyezkednie a fájlrendszerben, ahol a Python azt megtalálja. Ezek az útvonalak az adott operációs rendszer környezeti változóiból olvashatók ki. Ezek mellett az útvonalak mellett a rendszer még az adott fájl könyvtárában is keresi az osztályt ahol hivatkozunk rá, tehát az is elég ha egyszerűen az új fájl mellé helyezzük amit létrehoztunk. Az importálás után már használható is az algoritmus. Következő lépésként példányosítani kell az mTSP osztályt a következő módon: mTSP = MTSPSolver(my_points) Az egyenlőség bal oldalán szereplő példányt tetszőlegesen elnevezhetjük. Az osztály konstruktora egy ponthalmazt vár paraméterként, amelyet kötelezően meg kell adni. Ezek tulajdonképpen a gráf pontjait jelentik, amelyen az algoritmus majd a számításokat végzi. Python nyelven ezt a következőképp definiálhatjuk: my_points = [(20.0, 30.5), (82.4, 96.3), (12.4, 64.8)] Egy listát kell készíteni tehát, melynek elemei koordináták. Az elemek lehetnek valós vagy egész számok, a lista elemszáma pedig tetszőleges lehet. A fenti példában egy három elemszámú, valós számokból álló tömb kerül átadásra a paraméterként. Fontos megjegyezni, hogy a lista első koordinátájának kitüntetett szerepe van, ez az a pont ahonnan a körutak kiindulnak, tehát ez a pont a gráf minden egyes körútjában benne lesz.

1

https://pypi.python.org/pypi/inspyred

46

Nádor József

Diplomamunka

A példányosítás után is lehetőség van a ponthalmaz módosítására a set_points() nevű metódus segítségével: mTSP.set_points(my_points) Az ezt követő lépésben megadható a problémát megoldó algoritmus típusa, a kívánt paraméterekkel együtt. Ehhez a következő metódusok állnak rendelkezésre: 

set_ec_algorithm() – Evolutionary Computation,



set_acs_algorithm() – Ant Colony System.

Az Evolutionary Computation használata során a következő paraméterek megadására van lehetőség: 

pop_size (alapérték: 100): az egyedek száma a populációban,



max_generations (alapérték: 50): a generációk maximális száma, tehát a leállási feltétel,



tournament_size (alapérték: 2): az egyedek száma, melyek átkerülnek a következő generációba véletlenszerű kiválasztás útján. Amennyiben az itt megadott érték meghaladja a populációszámot, akkor ennek az értéke a teljes populációval lesz egyenlő.



num_selected (alapérték: pop_size): a szelekció során kiválasztott egyedek száma, alapértéke megegyezik a populáció számával,



num_elites (alapérték: 1).

A következő példa a metódus meghívását szemlélteti: mTSP.set_acs_algorithm(pop_size=30, num_selected=15) Azok a paraméterek, melyek nem kerülnek megadásra, az alapértelmezett értéküket fogják felvenni.

47

Nádor József

Diplomamunka

Az Ant Colony System használatakor az alábbi paraméterek állítására van lehetőség: 

pop_size (alapérték: 10): az egyedek száma a populációban,



max_generations (alapérték: 50): a generációk maximális száma, tehát egy leállási feltétel,



initial_pheromone (alapérték: 0): a kezdeti feromon mennyisége az útvonalakon,



evaporation_rate (alapérték: 0.1): a feromon felszívódásának mértéke,



learning_rate (alapérték: 0.1): a hangyák tanulásának mértéke.

A következő példa a metódus meghívását szemlélteti: mTSP.set_acs_algorithm(pop_size=30, max_generations=100, learning_rate=0.2) Amennyiben egyik metódus sem kerül megadásra, akkor a set_ec_algorithm() lesz beállítva az alapértelmezett paraméterekkel. Az algoritmusok paraméterezése után legvégül a solve() metódust kell megadni, ami végrehajtja a szükséges számításokat, ehhez pedig két paramétert lehet megadni: 

max_capacity (alapérték: végtelen): a maximális kapacitás egy korlát, amely megadja, hogy a gráfban legfeljebb hány pontot tartalmazhatnak a körutak,



max_distance (alapérték: végtelen): a maximális távolságot jelenti, ez szintén egy korlát, amely meghatározza a körutak éleinek a maximális hosszát.

Amennyiben a max_distance paramétert túl kis értékre állítjuk, és lesznek elérhetetlen pontok a gráfban, akkor az algoritmus egy hibaüzenettel jelzi a problémát, melyben kiírja, hogy legalább mekkora korlátra van szükség ahhoz, hogy a gráfot elő tudja állítani. Ha a felsorolt két paraméter közül az egyik sem kerül megadásra, akkor az algoritmus tulajdonképpen egy általános utazóügynök problémát fog megoldani. A solve() metódus visszatérési értéke egy több dimenziós lista, amely a pontok bejárási sorrendjét tartalmazza. A következő példa egy három körútból álló gráf pontjainak sorrendjét szemlélteti: [[0, 12, 11, 10, 9, 0], [0, 8, 7, 6, 5, 0], [0, 4, 3, 2, 1, 0]] A metódusok mellett az osztály tartalmaz publikus adattagokat (a Python programozási nyelvben minden adattag publikus, ezért nem szokás metódusok létrehozása a beállításukhoz, lekérdezésükhöz), melyekkel az algoritmus futtatása után különböző paraméterek kérdezhetőek le:

48

Nádor József

Diplomamunka 

node_coordinates: megadja a pontok halmazát, melyen a számításokat végezzük,



edge_weights: egy többdimenziós lista, amely a pontok közötti távolságokat adja meg,



result_node_sequence: egy több dimenziós lista, amely az eredményül kapott gráf pontjainak bejárási sorrendjét tartalmazza (megegyezik a solve() metódus visszatérési értékével),



result_node_coordinates: több dimenziós lista, amely az eredményül kapott gráf pontjainak koordinátáit adja vissza a bejárási sorrendben,



result_node_lengths: egy lista, amely az eredményül kapott gráf körútjainak a hosszát tartalmazza,



result_graph_length: egy számérték, amely az eredményül kapott gráf teljes úthosszát tartalmazza.



max_distance: szintén egy számérték, amely a beállított távolság korláttal egyezik meg. Amennyiben nincs megadva korlát, akkor 0-t ad eredményül (ez a végtelen értéknek felel meg).

Az mTSPSolver osztályon kívül található még néhány függvény, amely megkönnyíti az algoritmus használatát. Az első a make_points() függvény, amely a pontok előállítását segíti grafikus felülettel. Egyetlen opcionális bemenő paramétere van, mellyel egy előre definiált ponthalmazt adhatunk meg. Ebben az esetben a grafikus felületen ezek a pontok egyből látszanak, és lehetőség van a bővítésükre. A kimenő paraméter természetesen szintén egy ponthalmaz, amelyet így később át tudunk adni az MTSPSolver osztályból létrehozott példánynak. A következő példában három koordináta kerül átadásra a make_points() függvénynek, ami megnyit egy ablakot, ahol újabb pontokat lehet megadni. Végül az összes átkerül a my_points nevű változóba, amit a következő sorban átadhatunk az MTSPSolver osztálynak. my_points = make_points([(20.0, 30.5), (82.4, 96.3), (12.4, 64.8)]) mTSP = MTSPSolver(my_points)

49

Nádor József

Diplomamunka A megnyíló ablak a következőképpen néz ki:

30. ábra A make_points() függvény

A másik függvény, amely megtalálható a fájlban a plot_points(), amely szintén egy grafikus felületet jelenít meg, de a funkciója ennek a függvénynek az, hogy az eredményül kapott gráfot megjelenítése. Három bemenő paraméterrel rendelkezik, melyek a következők: 

initial_points – az alap gráf pontjainak a halmaza,



result_coordinates – az eredményül kapott gráf pontjainak koordinátáit kell megadni a bejárás sorrendjében,



max_distance –megadható a távolság korlát. Ekkor az algoritmus egy szürke kört rajzol a gráf kezdőpontjától, melyből látható a maximális bejárható távolság.

A függvény meghívása: mTSP.solve(max_distance=800, max_capacity=5) plot_points(mTSP.node_coordinates, mTSP.result_node_coordinates)

50

Nádor József

Diplomamunka

Egy eredményül kapott gráf a következőképpen jelenik meg a grafikus felületen:

31. ábra A plot_points() függvény

8.2. Az algoritmus működése Az algoritmus működésének legfontosabb lépései a következők: 

egy ponthalmaz meghatározása,



a pontok közötti távolságok meghatározása,



a heurisztikus algoritmus meghatározása, paraméterezés, korlátok megadása,



az utazóügynök probléma megoldása,



az utazóügynök probléma megoldására kapott körút felbontása kisebb körutakra a korlátoknak megfelelően.

Az optimum megtalálásához a heurisztikus algoritmusnak jó eredményt kell szolgáltatnia. Ehhez fontos a paraméterek megfelelő beállítása. Az algoritmus jellegéből adódóan ezt legtöbbször csak többszöri futtatással és próbálgatással lehet elérni. A helyes beállítások megtalálására nincs meghatározott formula. Amint a körutat megtalálta az algoritmus,

51

Nádor József

Diplomamunka

elindul a legelsőnek meghatározott ponttól az éleken, és próbál minél nagyobb utat megtenni, majd visszatér a kezdőpontba. Innen egy újabb körutakat tesz mindaddig, amíg vannak szabad pontjai a gráfnak. Az algoritmus nem garantálja az optimális megoldás megtalálását, de az esetek túlnyomó részében megközelíti azt.

8.3. Futási eredmények Az

algoritmus

használatával

elvégeztem

néhány

egyszerűbb

tesztet,

amelyen

megfigyelhető a működése. Minden esetben ugyanazon a 18 véletlenszerűen választott ponton futtattam le az algoritmust különböző korlátok megadásával.

32. ábra Az mTSP algoritmus futási eredményeinek grafikus ábrázolása

52

Nádor József

Diplomamunka

A futási eredményeket a 32. ábra szemlélteti. Az ábra bal felső részében látható a korlátok megadása nélküli futtatás. Ez gyakorlatilag az általános utazóügynök probléma megoldása. Az eredményt tekinthetjük az optimális megoldásnak. Ettől az ábrától jobbra-lefelé haladva láthatóak a 2, 3, 4, 5, 6 értékű kapacitás korláttal lefuttatott eredmények (a kiindulópontot nem számolva, mivel a korlát a kiszállított csomagok maximális számát adja meg). Mind az öt esetben egy fix távolságkorlát lett meghatározva 1000 egység értékkel.

mTSP algoritmus - össztávolságok 6000 5000

5334 4227

4049

4000

3434

3377

3000

2393

2000 1000 0 2

3

4

5

6

Végtelen

33. ábra A vizsgált gráfok hossza a különböző paraméterekkel

A 33. ábra láthatóak az egyes körutak összesített távolságai az egyes kapacitási korlátoknak megfelelően. Az utolsó oszlop a korlátok nélküli utazóügynök megoldásának a hossza. Megfigyelhető, hogy a kapacitáskorlát milyen nagy hatással van a megtett utak távolságára, különösen 2 és 3 darab kiszállított csomag között látható számottevő különbség. Másik érdekesség, hogy a távolságkorlát miatt 5-nél több csomagot ebben az adott esetben nem lehet kiszállítani, ezt a 34. ábra is szemlélteti. Jelen problémánál, ha jobban növelnénk a kapacitás értékét, a távolság akkor is 3400 egység körül ingadozna.

53

Nádor József

Diplomamunka

mTSP algoritmus - a távolság korlát megközelítése 1000 859

900 810

844

800 705 700 600

593

500 2

3

4

5

6

34. ábra A gráf körútjainak hossza

A 34. ábra látható, hogy a különböző kapacitáskorlátokkal mennyire tudja megközelíteni az egyes körutak hossza az elérhető maximális távolságokat. Itt is megfigyelhető, hogy egy bizonyos határ felett már nem érdemes növelni a kapacitást. Jól látható hogy maga az algoritmus alkalmas az utazóügynök probléma különböző korlátokkal megadott változatának a megoldására. Bár a működéséből adódóan nem garantálható hogy az optimális megoldást adja a különböző problémákra, de az optimumtól való eltérés minimalizálható, ha a probléma méretének és típusának megfelelő paramétereket állítunk be.

54

Nádor József

Diplomamunka

9. Összegzés A diplomamunkám elkészítése során a drónos áruszállítási mód során jelentkező útvonaltervezési problémákat vizsgáltam meg, illetve egy megoldási alternatívát készítettem a problémára. A dolgozat első részében megvizsgáltam a különböző áruszállítási módok előnyeit és hátrányait, majd magát a drónos szállítási módot mutattam be, amely egy eddig szinte feltérképezetlen területe a logisztikának. Éppen ezért is tartottam fontosnak a drónoknak, mint anyagmozgató eszközöknek a felépítését és a működését is részletezni. Kitértem arra is, hogy jelenleg milyen területeken alkalmazzák őket, és milyen lehetőségek rejlenek a jövőbeli alkalmazásukban. A következő fejezetekben a használatuk során felmerülő útvonal

tervezési

problémákat

definiáltam

és

megállapítottam,

hogy

ezek

visszavezethetőek a matematikában az utazóügynök problémának egy speciális többügynökös esetére. Mivel a megoldásuk ezeknek rendkívül számításigényes, ezért az ilyen jellegű problémáknál célszerű heurisztikus algoritmusokat alkalmazni. Többféle algoritmust is megvizsgáltam a futási idő, illetve a számítási teljesítmény tekintetében különböző matematikai problémákon. Ezeket a teszteket Python programozási nyelven készítettem el az inspyred keretrendszer használatával, az eredményeket pedig a szemléletesség kedvéért grafikonokon is megjelenítettem. Később az alkalmasnak talált algoritmusok használatával oldottam meg az útvonal keresési problémát. Az utolsó fejezet tartalmazza az algoritmus működésének leírását, illetve egy dokumentációt a használathoz. Összegzésképpen

elmondható

hogy sikerült

az

adott

problémakört

részletesen

megvizsgálni, és magára a problémára is egy hatékony megoldást találni. Az elkészült algoritmus természetesen a jövőben az igényeknek megfelelően továbbfejleszthető, például az érintett pontok magassági adatainak számításba vételével, vagy akár az algoritmus többprocesszoros működésének optimalizálásával.

55

Diplomamunka

Nádor József

10. Summary In my thesis I am investigating the route planning errors occurring during drone deliveries and have created an alternative solution to this problem. In the first part I am investigating the pros and cons of various shipment methods, then introduced drone delivery itself, a method yet to be discovered in the field of logistics. This is the reason I found it so important to elaborate on the structure and function of drones as devices for transportation. I also mentioned the area where they are being used currently and their potentials in the future. In the following chapters I defined the route planning errors that occur while in use and found that they can be traced back to a special mulitagent case of the traveling salesman problem. Since the solution would require a great deal of computation, it is advised to use heuristic algorhythms in such cases. I have examined multiple algorhythms in terms of running time and computing performance on various mathematical problems. These test were created in Python programming language using the inspyred framework, and I also demonstrate the results on graphs as an illustration. Later on as I found the compatible algorhythms I used them to resolve the route planning issue. The last chapter contains the description of the algorhythm's function as well as a documentation to its use. In conclusion, it is safe to say that I have managed to examine the issue in detail and find an effective solution to it. The finished algorhythm, of course, can be developed according to future needs, for instance with taking the relevant height points into account or optimizing the algorhytm's multi processor functions.

56

Diplomamunka

Nádor József

11. Irodalomjegyzék [1]

Dr. Kovács György: Szállítás – szállítmányozás – fuvarozás c. előadás

[2]

Wikipedia.org http://en.wikipedia.org/wiki/Quadcopter

[3]

Reuters http://www.reuters.com/article/2014/02/10/us-emirates-drones-idUSBREA1906E20140210

[4]

DHL http://www.delivered.dhl.com/en/articles/2014/02/parcelcopter.html

[5]

The Verge http://www.theverge.com/2013/12/3/5169878/ups-is-researching-its-own-delivery-drones-tocompete-with-amazons

[6]

Amazon http://www.amazon.com/b?node=8037720011

[7]

Esti Hírlap http://www.estihirlap.hu/gazdasag/amazon-prime-air-a-dronpostas-mindig-ketszer-csenget/79333/

[8]

Dr. Nagy Tamás – Egészértékű programozás http://www.unimiskolc.hu/~matente/oktatasi%20tananyagok/EGESZERTEKU%20PROGRAMOZAS.pdf

[9]

Katona Vilmos - Matematikai prezentáció az útvonalterezés problémájának alternatív megoldásához http://www.epab.bme.hu/info/Hallgmun09t/Katona%20Vilmos/Leiras.doc

[10]

Kota László - Termelési mélység optimalizálása Ant Colony algoritmus alkalmazásával http://www.szrfk.hu/rtk/kulonszamok/2009_cikkek/Kota_Laszlo.pdf

[11]

Shuang Cong, Yajun Jia and Ke Deng - Particle Swarm and Ant Colony Algorithms and Their Applications in Chinese Traveling Salesman Problem http://www.intechopen.com/download/get/type/pdfs/id/8546

[12]

Jason Brownlee PhD. - Clever Algorithms: Nature-Inspired Programming Recipes http://www.cleveralgorithms.com/nature-inspired/swarm/ant_colony_system.html

[13]

Dr. Dudás László – Mesterséges intelligencia előadás http://ait.iit.uni-miskolc.hu/~dudas/MIEAok/MIea8.PDF

57

Diplomamunka [14]

Nádor József

Wikipedia http://hu.wikipedia.org/wiki/Python_(programoz%C3%A1si_nyelv)

[15]

GitHub http://inspyred.github.io/overview.html

A linkek utoljára ellenőrizve: 2014. május 2.

58