TDK-dolgozat. Marcsák Gábor Zoltán

TDK-dolgozat

Marcsák Gábor Zoltán

MISKOLCI EGYETEM GÉPÉSZMÉRNÖKI ÉS INFORMATIKAI KAR Anyagmozgatási és Logisztikai Tanszék

TUDOMÁNYOS DIÁKKÖRI DOLGOZAT

Internetes optimáló alkalmazás készítése JavaFX környezetben az utazó ügynök probléma megoldására

Marcsák Gábor Zoltán I. éves logisztikai mérnök MSc szakos hallgató

Konzulens: Prof. Dr. Jármai Károly egyetemi tanár Anyagmozgatási és Logisztikai Tanszék

Miskolc, 2013

Köszönetnyilvánítás A bemutatott kutató munka 2012 július 1-től 2013 február 28-ig a TÁMOP4.2.1.B-10/2/KONV-2010-0001 jelű projekt részeként, további részei 2013 március 1-től aTÁMOP-4.2.2.B-10/1-2010-0008 jelű projekt részeként az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.

Tartalomjegyzék 1

BEVEZETÉS ......................................................................................................... 1

2

A JAVAFX KERETRENDSZER................................................................................. 2 2.1

MI AZ A JAVAFX? .................................................................................................... 2

2.2

FEJLESZTŐI KÖRNYEZET ............................................................................................. 4

2.3

A KERETRENDSZER FELÉPÍTÉSE .................................................................................... 6

2.3.1 Moduláris felépítés ......................................................................................... 7 2.3.2 Asztali vagy web alkalmazás? ...................................................................... 11 2.3.3 Leírások, forráskódok ................................................................................... 12 3

VIZSGÁLT OPTIMÁLÁSI PROBLÉMÁK................................................................. 13 3.1

FOLYTONOS MATEMATIKAI FÜGGVÉNYEK GLOBÁLIS SZÉLSŐÉRTÉKEINEK KERESÉSE ................ 13

3.2

HEURISZTIKUS ALGORITMUSOK MATEMATIKAI FÜGGVÉNYEK OPTIMÁLÁSÁRA ...................... 15

3.2.1 Bacterial Foraging ........................................................................................ 16 3.2.1.1 Elméleti háttér .................................................................................................. 16 3.2.1.2 Az algoritmus működése................................................................................... 17 3.2.1.3 Pszeudokód ....................................................................................................... 17

3.2.2 Differential Evolution.................................................................................... 17 3.2.2.1 Elméleti háttér .................................................................................................. 17 3.2.2.2 Az algoritmus működése................................................................................... 18 3.2.2.3 Pszedokód ......................................................................................................... 19

3.2.3 Particle Swarm ............................................................................................. 19 3.2.3.1 Elméleti háttér .................................................................................................. 19 3.2.3.2 Az algoritmus működése................................................................................... 20 3.2.3.3 Pszeudokód ....................................................................................................... 21

3.2.4 Az algoritmusok tesztelése ........................................................................... 22 3.3

AZ UTAZÓ ÜGYNÖK PROBLÉMA ................................................................................ 26

3.3.1 Miért nehéz megoldani az Utazó ügynök feladatot? ................................... 27 3.4

HEURISZTIKUS ALGORITMUSOK AZ UTAZÓ ÜGYNÖK PROBLÉMA MEGOLDÁSÁRA .................. 28

3.4.1 Ant Colony .................................................................................................... 28 3.4.1.1 Elméleti háttér .................................................................................................. 28

I

3.4.1.2 Az algoritmus működése................................................................................... 29 3.4.1.3 Pszeudokód ....................................................................................................... 29

3.4.2 Simulated Annealing .................................................................................... 30 3.4.2.1 Elméleti leírás .................................................................................................... 30 3.4.2.2 Az algoritmus működése................................................................................... 31 3.4.2.3 Pszeudokód ....................................................................................................... 31

3.4.3 Tabu Search .................................................................................................. 31 3.4.3.1 Az algoritmus működése................................................................................... 32 3.4.3.2 Pszeudokód ....................................................................................................... 32

3.4.4 Az Utazó ügynök feladat specifikálása a teszthez........................................ 33 3.4.5 Az algoritmusok tesztelése, az Utazó ügynök feladat megoldása ............... 34 3.4.5.1 Az algoritmusok paraméterezése ..................................................................... 34 3.4.5.2 Teszteredmények .............................................................................................. 35

3.5

AZ ALGORITMUSOK TOVÁBBFEJLESZTÉSI LEHETŐSÉGEI ................................................... 37

4

ÖSSZEFOGLALÁS .............................................................................................. 38

5

MELLÉKLET ....................................................................................................... 39 5.1

A BACTERIAL FORAGING ALGORITMUS PSZEUDOKÓDJA.................................................. 39

5.1.1 Chemotaxis and Swim .................................................................................. 40 6

IRODALOMJEGYZÉK ......................................................................................... 41

II

Ábrajegyzék 1. ÁBRA: A JAVAFX SCENE GRAPH ...................................................................................................... 4 2. ÁBRA: JAVAFX SCENEBUILDER ........................................................................................................ 5 3. ÁBRA: AZ OPTIMÁLÓ ALKALMAZÁS FUTÁS KÖZBEN .............................................................................. 6 4. ÁBRA: AZ OPTIMÁLÓ ALKALMAZÁS MODULÁRIS FELÉPÍTÉSE ................................................................... 7 5. ÁBRA: MODULÁRIS FELÉPÍTÉS A SCENEGRAPH VONATKOZÁSÁBAN ......................................................... 8 6. ÁBRA: A KERETRENDSZER ÜRES MUNKAFELÜLETTEL ........................................................................... 10 7. ÁBRA: A KERETRENDSZER A KIVÁLASZTOTT LISTAELEMHEZ TARTOZÓ MUNKAFELÜLETTEL............................ 10 8. ÁBRA: PLATFORM KIVÁLASZTÁSA NETBEANS KÖRNYEZETBEN .............................................................. 11 9. ÁBRA: ACKLEY'S TESZTFÜGGVÉNY .................................................................................................. 14 10. ÁBRA: E. COLI BAKTÉRIUM KOLÓNIA ............................................................................................ 16 11. ÁBRA: A DARWINI EVOLÚCIÓ ...................................................................................................... 18 12. ÁBRA: MADÁRRAJ RENDEZETT MOZGÁSA ...................................................................................... 20 13. ÁBRA: PARTICLE SWARM KERESÉS INDÍTÁSA .................................................................................. 22 14. ÁBRA: PARTICLE SWARM KERESÉS EREDMÉNYE............................................................................... 23 15. ÁBRA: RASTRIGIN'S TESZTFÜGGVÉNY ............................................................................................ 24 16. ÁBRA: HANGYÁK ÉLELEMKERESÉS KÖZBEN ..................................................................................... 28 17. ÁBRA: TEMPERÁLÁS SORÁN KIALAKULÓ KRISTÁLYSZERKEZET ............................................................. 30 18. ÁBRA: UTAZÓ ÜGYNÖK PROBLÉMA GRÁFJÁNAK MEGJELENÍTÉSE JAVAFX CANVAS VEZÉRLŐVEL ................. 33 19. ÁBRA: A KÖRUTAK KÖLTSÉGÉNEK VÁLTOZÁSA TSP MEGOLDÁS SORÁN................................................. 36 20. ÁBRA: A KÖRUTAK KÖLTSÉGÉNEK VÁLTOZÁSA ANT COLONY ALGORITMUS PARAMÉTEREZÉSÉVEL ............... 37

III


1 Bevezetés Az optimálás mindennapi életünk egyik meghatározó tevékenysége. A legtöbb ember folyamatosan azon dolgozik, hogy az adott feltételek mellett a maga, vagy mások számára valamilyen szempontból legkedvezőbb kimenetelt válassza ki egy probléma megoldása során. E mindenki által végzett tudatos vagy tudat alatti tevékenység az optimálás. A tudományág széleskörű matematikai alapokkal, módszerekkel rendelkezik. Számos kiváló algoritmust dolgoztak ki a különböző optimálási problémák megoldására. A számítógépek rohamos fejlődése ellenére még mindig sok olyan feladat ismert, mely nem megoldható pusztán a számítási teljesítményre alapozva. A megoldást az informált kereső, úgynevezett heurisztikus algoritmusok jelentik. Előnyük, hogy nagy bonyolultságú feladatoknál is sok esetben sikerrel alkalmazhatók. Legfontosabb hátrányuk azonban, hogy nem garantálható teljes bizonyossággal az optimális megoldás megtalálása [1]. A különböző heurisztikus algoritmusok a tudomány számos területén korábban megoldhatatlannak vélt problémák megoldásával bizonyították létjogosultságukat. A célom egy olyan korszerű web alkalmazás megvalósítása volt, mely egyedülálló gyűjteménye a modern heurisztikus algoritmusoknak. A program megvalósításához a napjainkban újdonságnak számító JavaFX technológiát használtam. Az alkalmazást böngészőből, Interneten keresztül lehet elérni, így könnyen hozzáférhető bárki számára, aki érdeklődik a témában. Nem igényel külön telepítést, és további hatalmas előnye a technológiának, hogy ugyanolyan futási sebesség érhető el a webes felületen, mintha asztali alkalmazásról lenne szó. Ezen utóbbi jellemző nélkülözhetetlen a számításigényes optimálási feladatok megoldásához. A megvalósult program fő eleme a keretrendszer, mely egy felhasználóbarát felhasználói felület. A keretrendszerbe moduláris elven, komponensenként épülnek a különböző Java nyelven megvalósított optimáló algoritmusok, így lehetővé téve a program későbbi egyszerű bővítését, fejlesztését. A felhasználó szabadon állíthatja az optimáló eljárások legtöbb futási paraméterét, valamint lehetősége van az algoritmusok forráskódjának mentésére, melyet szabadon átírhat, megváltoztathat. 1


2 A JavaFX keretrendszer A

heurisztikus

algoritmusok

gyűjteményéhez

mindenekelőtt

egy

keretrendszert kellett fejlesztenem, mely tárolja, rendszeri azokat. A program tervezésekor több fontos szempontot vettem figyelembe: 1. Egy Interneten bárki számára könnyen és gyorsan hozzáférhető web alkalmazást szerettem volna létrehozni, amit nem kell külön telepíteni, böngészőből használható. 2. A legtöbb heurisztikus algoritmus implementációja sokkal egyszerűbb modern, objektum orientált paradigmát követő programozási nyelvek segítségével. Annak ellenére, hogy a nem informált kereső eljárásokhoz viszonyítva kevesebb számítás árán jutnak eredményre, bonyolult problémák esetén fontos a választott technológia futási sebessége. 3. Alapvető követelmény a könnyen kezelhető, informatív felhasználói felület. A beépített heurisztikus algoritmusok története, elméleti leírása és pszeudokódja egyaránt elérhető kell legyen. A működésük megértése azonban gyakorlati példákkal szemléltetve sokszor egyszerűbb, ehhez is ki kellett dolgoznom a megfelelő programrészeket. 4. Fontos volt továbbá, hogy az algoritmusok gyűjteményét könnyen bővíteni lehessen. A keretrendszer ennek megfelelően egyfajta moduláris struktúrát követ. Az új tartalom ezáltal könnyen illeszthető a már meglévőhöz. A fent vázolt szempontok figyelembevételével a viszonylag újnak számító JavaFX technológiát választottam a megvalósításhoz.

2.1 Mi az a JavaFX? A JavaFX az amerikai szoftveróriás Oracle Corporation Java alapú szoftver platformja, melynek segítségével asztali alkalmazások mellett web alkalmazások (RIA- Rich Internet Application) is fejleszthetők, valamint modern és gyors grafikus felhasználói interfészt biztosít alkalmazásainkhoz. Az első verziója (JavaFX 1.0) 2008. December 4-én jelent meg. Kifejlesztését leginkább az indokolta, hogy egy egységes GUI könyvtárat hozzanak létre a Java projektek 2


számára. A korábban elterjedt megoldások közül a két legnépszerűbb, a SWING és az AWT (Abstract Windowing Toolkit) a modern kinézet és technológiai lehetőségek tekintetében egyre kevésbé voltak versenyképesek a konkurens fejlesztői platformok (.NET, JavaScript, Flash, Android, iOS) GUI könyvtáraival. A JavaFX technológia tehát a népszerű Java platform új generációs GUI platformja, mely többek között olyan elvárásoknak is megfelel, mint a gyors alkalmazás fejlesztés (RAD- Rapid Application Development), a modern grafikus kártyák hardveres gyorsításának kihasználása, valamint animációk, multimédiás tartalmak megjelenítése. Mindehhez jól megtervezett, produktív fejlesztői felületet biztosít, valamint megőrzi a Java technológia egyik legnagyobb előnyeként számon tartott platformfüggetlenséget. A legnépszerűbb operációs rendszerek, melyeken elérhető a JavaFX: Windows (Windows XP, Windows Vista, Windows 7, Windows 8), különböző Linux disztribúciók, Mac OS X. A közeljövőben valószínűleg az egyre nagyobb népszerűségnek örvendő Android, Windows 8 és iOS alapú mobil eszközök, táblagépek és okostelefonok is támogatni fogják, mivel elkészítik a platform ARM processzor architektúrához igazított változatát. A JavaFX 2.0 előtti verziók egy JavaScript-hez hasonló, JavaFX Script nevű dekleratív nyelvet használtak. A fordító a JavaFX Script kódot a Java kódhoz hasonlóan bájtkóddá alakította, amit a Java Virtuális Gép (JVM- Java Virtual Machine) értelmez. A fejlesztők azonban nem fogadták egyöntetű lelkesedéssel, hogy a GUI használatához egy új szkript nyelvet is el kell sajátítaniuk, ezért a JavaFX 2.0 már teljes mértékben Java alapokon nyugszik. Az alkalmazásokat natív Java könyvtárak használatával készíthetik a fejlesztők. A JavaFX felhasználói felület egyik fő jellemzője, hogy a különböző felületelemek és vezérlők egy hierarchikus fa struktúrát (Scene Graph) (1. ábra: A JavaFX Scene Graph) alkotnak. A fa struktúra paradigma nagymértékben leegyszerűsíti a felhasználói felületek létrehozását, valamint a komplex vizuális effektek és transzformációk használatát [2]. A legfrissebb JavaFX verzió a 2.2-es, ami 2012. augusztus 14-én jelent meg, és szerves részét képezi a Java SE (Standard Edition) fejlesztői platformnak. Az alkalmazások futtatásához elegendő a JRE (Java Runtime Environment) telepítése. 3


1. ábra: A JavaFX Scene Graph

2.2 Fejlesztői környezet A JavaFX technológiát számos integrált fejlesztői környezet (IDE- Integrated Development Environment) támogatja, a hivatalos ajánlás szerint a méltán népszerű NetBeans-t érdemes használni a kódoláshoz. Nagy mértékben képes gyorsítani és egyszerűsíteni a fejlesztést, köszönhetően intelligens kódkiegészítő, projekt kezelő és

hibakereső

moduljainak.

Rendelkezik

továbbá

beépített

verziókövető

lehetőségekkel (Subversion, Mercurial, Git), mely szintén fontos egy nagyobb projekt sikeres megvalósításához. A felhasználói felület létrehozására JavaFX esetén alapvetően két módszer létezik: 1. A NetBeans, vagy más IDE használatával az alkalmazás logikával együtt, Java kódban hozzuk létre a felhasználói felület elemeit. 2. Nagy mértékben leegyszerűsítheti a fejlesztést azon napjainkban egyre terjedő

szemléletmód,

mely

szerint

a

felhasználói

felület

létrehozását

különválasztják a kódolástól. Az Android, iOS és .NET technológiák is hasonló paradigmát követnek. A JavaFX esetében ezért kidolgoztak egy XML alapú, 4


úgynevezett FXML leíró nyelvet a GUI elmeinek megadásához. Az elemek kinézete a webfejlesztésben elterjedt CSS (Cascading Style Sheet) stílusleíró nyelv segítségével könnyen és sokrétűen s testre szabható. Mindkét megközelítésnek megvan a maga előnye és hátránya. Előbbi esetben elegendő a Java nyelv ismerete, viszont nagyobb méretű kódot fogunk kapni. Utóbbi esetben az FXML használata tanulást igényel. A felhasználói felület létrehozását zását egy külön fejlesztői eszköz, a JavaFX SceneBuilder támogatja. A fejlesztő egy grafikus szerkesztőben drag&drop módszerrel készíti a felületet, ezáltal nem kell kódolnia (2. ábra: JavaFX SceneBuilder).. A SceneBuilder automatikusan hozza létre a felhasználói felhasználói interfész fa struktúráját leíró FXML kódot. A

felület

elemeket

az

FXML ben FXML-ben

definiált

azonosítójuk

(ID)

vagy

vezérlőfüggvényeik segítségével integrálhatjuk a Java kódba.

2. ábra: JavaFX SceneBuilder Mivel a fejlesztés során során fontos szempont volt, hogy az internetes optimáló alkalmazásban található gyakorlati példákat és algoritmusokat a felhasználók egyszerűen letölthessék és módosíthassák, ezért kizárólag Java kódot használtam a felhasználói felület létrehozásához is. Összefoglalásképpen Összefoglalásképpen tehát a fejlesztés során használt fejlesztői környezet komponensei: komponensei 1. Java SE (Standard Edition) 7, minimum update 6 verzió 2. NetBeans IDE, minimum 7.0 verzió 5


2.3 A keretrendszer felépítése Az internetes optimáló alkalmazás létrehozásával elsődleges elsődleg célom, hogy összegyűjtsem a különböző intelligens heurisztikus algoritmusokat, és segítségükkel olyan

problémákat

oldjak

meg,

melyek

hagyományos

módszerekkel

megoldhatatlanok. Az algoritmusok gyűjteményének egyszerűen bővíthetőnek kell lennie, az elméleti ti leírás és pszeudokód mellett pedig gyakorlati példákkal is szemléltetem a működésüket. Egyfajta interaktív webes tudásgyűjteményt szerettem volna tehát létrehozni a témában, melyhez a JavaFX platform kiváló alapot biztosított.

3.. ábra: ábra Az optimáló alkalmazás futás közben

A 3. ábra az internetes optimáló alkalmazást mutatja futás közben. A program elrendezéséhez az e-könyv könyv olvasó programok (Pl. Adobe Reader, Foxit Reader) szolgáltak mintául. A különböző vezérlők vezérlők az alsó és felső sávokban helyezkednek el, a tartalomjegyzék a bal oldalon található, a tartalom megjelenítésére pedig a fennmaradó

terület

szolgál.

A

program

intelligensen méretezi magát. 6

képernyőfelbontás képernyőfelbontás

függvényében


2.3.1 Moduláris felépítés Az egyszerű erű bővíthetőség érdekében egy olyan keretrendszert hoztam létre, mely moduláris elven épül fel. Kidolgozott módszerem alapja a JavaFX SceneGraph hierarchikus fa struktúra, mely egyszerűen átlátható és menedzselhető.

4.. ábra: ábra Az optimáló alkalmazás moduláris felépítése

A 4. ábra az internetes optimáló alkalmazás moduláris felépítését mutatja színkódok segítségével: 1. A zöld téglalap maga a keretrendszer, mely az alkalmazás gerincét képezi. Minden komponens ezen zen belül található. Célom az volt, hogy a tartalom bővítése a lehető legegyszerűbben kivitelezhető legyen. 2. A sárga téglalappal jelölt elem a program központi vezérlője, mely egyben tartalomjegyzékként is funkcionál. 3. A piros téglalappal jelölt rész a munkafelület, munkafelület, mely a központi vezérlőn kiválasztott tartalomnak megfelelően dinamikusan változik.

7


5. ábra:: Moduláris felépítés a SceneGraph vonatkozásában

Az 5. ábra szintén a moduláris felépítést szemlélteti, azonban mindezt a SceneGraph fa struktúra vonatkozásában. Jól látható a keretrendszeren belül a különböző felületelemek hierarchikus elrendezése. A sárga téglalappal jelölt tartalomjegyzéket a JavaFX TreeView vezérlő biztosítja. A TreeView segítségével egy többszintű listát jelenítek meg, meg, valamint hozzárendelek a listához egy úgynevezett Listener-t. t. Ha a felhasználó kiválaszt egy listaelemet, a Listener megkapja a vezérlést, és lehetőség van az esemény lekezelésére. Tegyük fel, a felhasználó kiválasztja a tartalomjegyzékből, tartalomjegyzékből, hogy a Particle Swarm heurisztikus algoritmus elméleti leírása érdekli. A Listener ekkor végrehajtja a kiválasztott listaelemhez kapcsolódó programkódot. A cél az, hogy a piros téglalappal jelölt munkafelületen (4. ábra:: Az optimáló optimáló alkalmazás moduláris felépítése) felépítése megjelenjen az algoritmus elméleti leírása. A munkafelületet egy Pane (Pane pageArea) típusú vezérlő adja, mely az egyik legegyszerűbb tároló a különböző felületelemek számára. Hierarchikus struktúra lévén, a Pane tárolónak is tetszőleges számú leszármazottja leszármazottja (Children) 8


lehet, melyeket dinamikusan lehet hozzáadni vagy elvenni a struktúrához. A Particle Swarm elméleti leírását tartalmazó felületelemet ennek megfelelően dinamikusan, leszármazottként adom hozzá a munkafelület tárolóhoz. A SceneGraph segítségével ez könnyedén megvalósítható, a leszármazott hozzáadása után pedig a felhasználó azonnal láthatja az elérni kívánt tartalmat. Figyelni kell azonban arra, hogy elvileg egyszerre több leszármazottja is lehet a munkafelület tárolónak, melyek közül csak az utoljára hozzáadott látszik a képernyőn, mivel eltakarja a korábban hozzáadott tartalmakat. Annak ellenére, hogy nem látszanak, a memóriában helyet foglalnak. Ez a jelenség felesleges memória erőforrás felhasználást jelent, ezért új tartalom hozzáadása előtt mindig kiürítem a munkafelület tároló leszármazott listáját. Az új tartalom hozzáadása a fent ismertetett módszerrel egyszerűen megvalósítható, mindössze egy új listaelemet (TreeItem) kell hozzáadni a tartalomjegyzékhez, valamint a tartalomjegyzék eseménykezelőjében (Listener) definiálni kell az új listaelem kiválasztásakor végrehajtandó tevékenységeket. Az esetek túlnyomó többségében ez a tevékenység munkafelület tartalmának megváltoztatását jelenti. Ennek megfelelően az utolsó fontos teendő, hogy létrehozzuk az új tartalomhoz kapcsolódó munkafelület interfészt. A különböző munkafelület tartalmaknak szintén egy Pane típusú tároló a kiinduló pontja. Az egyszerűség kedvéért létrehoztam egy Tartalom nevű általános osztályt, mely a Pane osztály leszármazottja (extends), így annak minden tulajdonságával és metódusával rendelkezik. Új tartalom létrehozásakor a Tartalom osztály származtatott osztályát kell létrehozni (Pl. class BacterialForagingUI extends Tartalom), és ezen belül egyszerűen felépíthető a további felhasználói felület, valamint a felületelemekhez tartozó alkalmazás logika. Összefoglalásképpen tehát a 6. ábra a keretrendszert mutatja üres munkafelülettel. Ha a felhasználó a tartalomjegyzékből kiválasztja a számára érdekes elemet, a munkafelületen megjelenik a listaelemhez kapcsolódó tartalom (7. ábra). Az ismertetett moduláris felépítésnek köszönhetően az internetes optimáló alkalmazás tartalma gyorsan és egyszerűen bővíthető. 9


6.. ábra: ábra A keretrendszer üres munkafelülettel

7. ábra:: A keretrendszer a kiválasztott listaelemhez tartozó munkafelülettel

10


2.3.2 Asztali vagy web alkalmazás? A JavaFX technológia egyik legnagyobb előnye, hogy asztali és webes alkalmazások egyaránt létrehozhatók használatával, ráadásul a fejlesztés során nem szükséges kiemelt figyelmet fordítani arra, hogy mely platformra fejlesztünk. Az optimáló alkalmazással szemben az egyik fontos követelmény az volt, hogy Interneten bárki számára ámára könnyen és gyorsan hozzáférhető legyen, amit nem kell külön telepíteni, böngészőből használható. Elsősorban tehát web alkalmazást létrehozása volt a célom, azonban lehetővé tettem a felhasználók számára, hogy letölthessék a szoftvert, így asztali alkalmazásként alkalmazásként is képes működni, melyhez nem szükséges állandó Internet elérés.

8.. ábra: ábra Platform kiválasztása NetBeans környezetben

A NetBeans fejlesztői környezetben, a Projekt tulajdonságai menüpontban lehet beállítani, hogy asztali vagy web alkalmazást szeretnénk létrehozni (8. ábra). A Java technológiára jellemző .JAR kiterjesztésű fájl, mely a futtatható programot tartalmazza, asztali és web alkalmazások esetében teljes mértékben megegyezik. Az egyetlen különbség, önbség, hogy web alkalmazás létrehozása során a .JAR fájl mellett 11


létrejön egy .HTML (HyperText Markup Language) és egy .JNLP (Java Network Launching Protocol) kiterjesztésű fájl is. Ha a három komponenst elhelyezzük egy webszerveren, és a .HTML fájlt megnyitjuk internet eléréssel egy böngésző segítségével, elindul JavaFX alkalmazásunk online felületen keresztül. Gyakorlatilag az összes népszerű böngésző (Internet Explorer, Firefox, Chrome, Safari, Opera) támogatja a technológiát. Bonyolult optimálási problémák megoldásakor fontos a megfelelő futási sebesség. Felmerülhet a kérdés, hogy ha webes felületen keresztül futtatjuk az optimáló alkalmazást, akkor jelentkezik-e bármi nemű lassulás az asztali módhoz képest. Ha interneten keresztül megnyitunk egy JavaFX alkalmazást, akkor az először letöltődik a böngésző gyorsítótárába (cache), majd a helyi gépen a JVM futtatni kezdi. Az asztali alkalmazáshoz képest tehát csak addig tapasztalható késlekedés, amíg az alkalmazás letöltődik. Onnantól kezdve ugyanaz a JVM futtatja a web alkalmazást, ami az asztali alkalmazást is futtatná, ezért kijelenthető, a számítások gyorsaságát tekintve semmilyen különbséget nem jelent, hogy online vagy offline módban futtatjuk az optimáló alkalmazást.

2.3.3 Leírások, forráskódok Az algoritmusokhoz kapcsolódó elméleti leírások, képletek és pszeudokódok megjelenítésére a HTML formátumot választottam. A JavaFX szerencsére rendelkezik egy úgynevezett WebView vezérlővel, mely a HTML tartalom megjelenítésére szolgál. Az algoritmusok, valamint a gyakorlati példák Java forráskódját a felhasználóknak szintén lehetőségük van a programon belül böngészni. A moduláris felépítés lehetővé teszi, hogy a különböző gyakorlati példákat a felhasználók NetBeans projektként menthessék, módosíthassák. Ezek a független NetBeans projektek tulajdonképpen azon programmodulok, melyeket az alkalmazás a munkafelületre betölt, miután a tartalomjegyzékből a felhasználó kiválasztotta a tartalmat.

12


3 Vizsgált optimálási problémák Az élet számos területén találkozhatunk optimálási problémákkal, legyen szó mérnöki, informatikai, biológiai, vagy bármilyen egyéb tudományterületről. A [3, 4, 5] forrásművekben a mérnöki tudományterületen felmerülő optimálási problémákra

találhatunk példákat, melyek a nagyszámú változó, feltétel, és bonyolult célfüggvény vagy célfüggvények miatt csak modern számítástechnikai eszközökkel oldhatók meg. A problémák megoldásához szükséges azok matematikai megfogalmazása. A változókat szokás döntési változóknak nevezni, mely változók értékei alapján a célfüggvény vagy célfüggvények segítségével meghatározható egy skalár érték. Az optimálás célja e skalár érték maximálása vagy minimálása. A döntési változók és a skalár értékére feltételeket definiálhatunk. Az optimálási probléma sok esetben visszavezethető folytonos matematikai függvények globális szélsőértékeinek keresésére, ahol a döntési változók a matematikai függvény dimenzióit adják. Az internetes optimáló alkalmazással ez volt az első problémakör, amit vizsgáltam. A második az egyik legtöbbet kutatott optimálási feladat, az utazó ügynök probléma, ezen belül is az egyhurkú szimmetrikus változat, melynek megoldásához speciális számítási algoritmusok szükségesek. A dolgozat írásakor összesen 6 heurisztikus algoritmust érhető el az alkalmazásban, ez a szám azonban folyamatosan bővül.

3.1 Folytonos keresése

matematikai

függvények

globális

szélsőértékeinek

Az egyik leggyakoribb optimálási feladat a folytonos matematikai függvények globális szélsőértékeinek keresése. Vegyük például az egyik legegyszerűbb egyváltozós függvényt, melynek képlete: ݂ ሺ‫ݔ‬ሻ = ‫ ݔ‬ଶ

(1)

Az egyetlen döntési változó az ‫ݔ‬. Tegyük fel, hogy az értéke a [-5; 5] tartományba eső értékeket vehet fel, ezzel egy, a változóra vonatkozó feltételt definiáltunk. Keressük e matematikai függvény globális minimum értékét. 13


A legtöbben valószínűleg azonnal meg tudják mondani, hogy a függvény globális minimuma az 0 értéknél van. A globális maximum értékének meghatározása sem jelent nagyobb kihívást, igaz abból mindjárt két darab is van, az 5 és az 5 értékeknél. tékeknél. Ha az ember korábban már találkozott ezzel a függvénnyel, akkor hatalmas előnyt élvez akár a leggyorsabb számítógéppel szemben is, nevezetesen hogy probléma specifikus ismeretekkel rendelkezik a vizsgált függvényt illetően. A számítógépnek a feladat dat megoldásához kereső algoritmusra van szüksége. szüksége. Általában analitikus módszerrel valamilyen logika szerint végigiterál a lehetséges megoldásokon, majd a számítás végén megadja a megoldást. Az egyváltozós függvény után tekintsünk egy kétváltozós folytonos függvényt, melynek képlete: 20 , 20 exp0.20. 5 ଶ ଶ exp0.5cos2 cos2

(2)

Ez alapján valószínűleg már kevesebben tudnák azonnal megmondani, hogy a függvénynek hol vannak a globális szélsőértékei. A képlet képlet egy gyakran használt optimálási tesztfüggvényt, az a Ackley's függvényt (9. ábra) definiálja [6].

9. ábra: Ackley's tesztfüggvény

14


Tegyük fel, hogy az ‫ ݔ‬é‫ ݕ ݏ‬döntési változók [-32,768; 32,768] tartományba eső értékeket vehetnek fel. A függvény globális minimum a az ‫ = ݔ‬0, ‫ = ݕ‬0 pontban található, értéke 0. Gyakran előfordul, hogy a fentieknél sokkal bonyolultabb matematikai függvények globális szélsőértékeit keressük. A nagyméretű, sokváltozós problémák esetében a hagyományos kereső eljárások csődöt mondanak. A lehetséges megoldások száma túl sok ahhoz, hogy mindegyiket külön megvizsgáljuk. Ebben az esetben nyújtanak segítséget a heurisztikus algoritmusok.

3.2 Heurisztikus algoritmusok matematikai függvények optimálására A heurisztika kifejezés a görög heureszisz szóból származik, melynek jelentése rátalálás. A hagyományos kereső eljárásokkal szemben a heurisztikus algoritmusok próbálgatással, a korábban megszerzett tapasztalatok felhasználásával jutnak eredményre. Szokás ezért informált kereső eljárásoknak is nevezni őket. Mint az a bevezetésben említésre került, hatalmas előnyük, hogy nagy bonyolultságú problémák esetében is képesek viszonylag rövid idő alatt, kevés számítás árán eredményt szolgáltatni. Hátrányuk azonban, hogy nem garantálható teljes bizonyossággal az optimális megoldás megtalálása. Lokális kereső eljárások, mivel nem vizsgálják a teljes probléma teret, minden lehetséges kimenetelt (sok esetben ez egyébként is fizikai képtelenség), és a korábban bejárt utat sem tárolják. Bizonyos korábban szerzett ismereteket azonban eltárolnak, rendelkeznek tehát probléma specifikus ismeretekkel a megoldás során. A heurisztikus algoritmusok hatékonyságáról megoszlanak a vélemények. Korábban megoldhatatlannak vélt problémákra képesek optimális, vagy ahhoz közeli megoldást adni. Egyesek szerint azonban attól, hogy egy bizonyos problémára elfogadható megoldást találnak, semmi sem garantálja, hogy egy hasonló feladatra is jobb megoldást adnak, mint akár egy véletlen kereső algoritmus. Ezen aggályokat írja le a No-Free-Lunch (Nincs ingyen ebéd) teória, melyről bővebben a [7] forrásműben olvashat az érdeklődő.

15


3.2.1 Bacterial Foraging Az első beépített heurisztikus algoritmus a Bacterial Foraging (Baktérium táplálkozás), ami egy Swarm Intelligence (Rajintelligencia) elven működő eljárás. A rajintelligencia (kollektív intelligencia) módszerek közös tulajdonsága, hogy nagyszámú homogén egyed viselkedésmintáin alapulnak. Az alapelv szerint lehetséges hogy egy individuális egyed nem képes megoldani adott feladatot, azonban ha nagyszámú egyed csoportot alkot, akkor a csoport kollektív intelligenciája már elég lehet a feladat sikeres megoldásához [8].

3.2.1.1 Elméleti háttér Az algoritmust először Liu és Passino írta le [9] 2002-ben, viszonylag újnak számít a természeti jelenségeken alapuló rajintelligencia stratégiák családjában. Az E. coli baktériumkolóniák (10. ábra: E. Coli baktérium kolónia) táplálékkereső és reprodukciós viselkedésmintáin alapul a működése. Az Escherichia Coli az ostoros baktériumok családjába tartozik. Ostorszerű végtagjai, az úgynevezett flagellumok segítségével képes az önálló úszásra. Ez a mozgás a kemotaxis, mely során a során a fő cél a tápanyagban gazdag helyek elérése, továbbá a valamilyen okból veszélyesnek ítélt helyek elkerülése.

10. ábra: E. Coli baktérium kolónia

16


3.2.1.2 Az algoritmus működése A Bacterial Foraging lényegében az E. Coli baktériumkolónia egyedei által végzett kemotaxist másolja a keresés során. Az egyedek hol tudatosan, hol véletlenszerűen mozognak az egyre jobb megoldást adó pontok felé. A keresést három egymásba ágyazott ciklus valósítja meg. A külső ciklus maga a kemotaxis, a baktériumok mozgását megvalósító szakasz. Evolúciós algoritmusról van szó, az egyedek meghatározott élettartammal rendelkeznek. Minél jobb pozícióban vannak az adott probléma szempontjából, annál kevésbé csökken az élettartamuk, A középső ciklus a reprodukció, minden iteráció során az algoritmus rendezi az egyedeket élettartam szempontjából, majd a halmazt általában középen ketté bontva az idősebb baktériumok helyére átmásolja a fiatalabb példányokat, ezzel szimulálva az osztódást. A legbelső ciklus az elimináció, amikor véletlenszerű egyedek meghatározott valószínűséggel likvidálásra kerülnek [10].

3.2.1.3 Pszeudokód A Bacterial Foraging algoritmus pszeudokódja terjedelmére való tekintettel a mellékletben található [11].

3.2.2 Differential Evolution A Differential Evolution (Differenciális Evolúció) egy evolúciós algoritmus, mely eljárások közös tulajdonsága, hogy Darwin evolúciós elméletén alapul működésük. Ennek megfelelően központi eleme a természetes kiválasztódás, tehát a problémára jobb megoldást adó egyedek hozhatnak létre új generációt (Survival of the fittest theory) [12].

3.2.2.1 Elméleti háttér Az eljárást Storn és Price dolgozta ki 1995-ben [13]. Az evolúció során számos faj esetében megfigyelhető, hogy a generációváltásokkal az adott környezet 17


kihívásainak egyre inkább megfelelő egyedek jöttek létre. A leszármazott egyed új tulajdonságait a szülők tulajdonságainak keresztezéséből kapta.

11. ábra: A darwini evolúció

3.2.2.2 Az algoritmus működése Először adott számú (N) kiinduló egyedet hozunk létre véletlenszerű pozíciókban a problématéren belül. Az egyedszám az algoritmus futása során nem változik. Az iterációk során adott generáció (G index) minden tagjának egy új leszármazott egyedet (G+1 index) hoz létre keresztezéssel az alábbi differenciáló képlet (innen ered az algoritmus neve) alapján: ‫ݔ‬௜,ீାଵ = ‫ݔ‬௥భ,ீ + ‫ݔ(ܨ‬௥మ,ீି ‫ݔ‬௥మ,ீ )

(3)

‫ݔ‬௥ଵ , ‫ݔ‬௥ଶ , ‫ݔ‬௥ଷ Véletlenszerűen kiválasztott egyedek ‫ܨ‬

Mutációs konstans

Ezután összehasonlítja az eredeti és a leszármazott egyed rátermettségét az adott probléma szempontjából. A rátermettség fitnesz függvény alapján kerül meghatározásra. A kedvezőbb megoldást adó egyed lesz tagja a következő generációnak [14].

18


3.2.2.3 Pszedokód

3.2.3 Particle Swarm A Particle Swarm (Részecskecsapat módszer) a Bacterial Foraging algoritmushoz hasonlóan rajintelligencia módszer. Napjaink egyik legígéretesebb metaheurisztikus optimáló algoritmusa.

3.2.3.1 Elméleti háttér A Particle Swarm (részecske-csapat) (részecske algoritmust 1995--ben Eberhart és Kennedy dolgozta ki [15]. Működését a madár és halrajok mozgása inspirálta. A nagyszámú egyed mozgásában egyfajta rendezettség figyelhető figyelhető meg. Érzékelik egymás helyzetét, bizonyos mértékben pedig emlékeznek emlékeznek a korábbi pozíciókra.

19


12. ábra: Madárraj rendezett mozgása

3.2.3.2 Az algoritmus működése A keresés adott számú részecske létrehozásával kezdődik, amik véletlenszerű kiindulási pontokban helyezkednek el. A részecskék a problématérben az egyre jobb megoldást adó helyek felé mozognak, a csapatot a legjobb egyedek vezetik. Tisztában vannak aktuális és addigi legjobb pozíciójukkal, valamint a részecske csapat addigi legjobb pozíciójával, az új pozíció kiszámításához ezeket is figyelembe veszi az eljárás. Hogy az adott pozíció mennyire jó az adott keresés szempontjából, mindig egy fitness függvénnyel határozható meg. Az iterációk során az alábbi képletek alapján számítható ki a részecskék új pozíciója (4), (5): ܸ௜ௗ = ‫ܸ × ݓ‬௜ௗ + ܿଵ × ‫ ݀݊ܽݎ‬ሺ ሻ × ሺ‫݌‬௜ௗ − ‫ݔ‬௜ௗ ሻ + ܿଶ × ‫ ݀݊ܽݎ‬ሺ ሻ × ൫‫݌‬௚ௗ − ‫ݔ‬௜ௗ ൯ ‫ݔ‬௜ௗ = ‫ݔ‬௜ௗ + ܸ௜ௗ t ܸ௜ௗ ‫ݓ‬ ܿଵ ܿଶ ‫݌‬௜ௗ ‫݌‬௚ௗ

Részecske sebessége Gyorsulás konstans Egyéni súlyozás konstans Szociális súlyozás konstans Részecske eddigi legjobb pozíciója Csapat eddigi legjobb pozíciója

‫ݔ‬௜ௗ ‫ݐ‬

Részecske aktuális pozíciója Időegység

20

(5)

(4)


Az iteráció addig folytatódik, míg nem teljesül valamilyen leállási feltétel. Evolúciós iós algoritmusok esetében sokszor nem egyszerű egyértelműen jó leállási feltételt találni. A Particle Swarm módszernél a feltétel többek között lehet megszabott számú iteráció végrehajtása, vagy ha a csapat legjobb pozíciója bizonyos számú iteráció után sem se változott meg [16].

3.2.3.3 Pszeudokód

21


3.2.4 Az algoritmusok tesztelése A heurisztikus algoritmusok működésének gyakorlati szemléltetésére egy és többváltozós függvényeken végezhető globális minimum és maximum keresést építettem a programba. A felhasználó választhat az öt beépített tesztfüggvény (De Jong's, Rosenbrock's valley, Rastrigin's, Schwefel's, Easom's) közül, vagy sajátot is definiálhat. Egyváltozós függvény esetén a keresés egy grafikonon követhető nyomon. A 13. ábraán Particle cle Swarm algoritmussal, 10 darab részecske segítségével végeztem minimum keresést a Rastrigin's tesztfüggvény egyváltozós változatán. A függvény abszolút minimuma az x=0 pontnál van. Az algoritmus első lépése a részecskék létrehozása véletlenszerű pozíciókban. pozíció

13. ábra: Particle Swarm keresés indítása

A hullámzó kék vonal a Rastrigin's tesztfüggvény egyváltozós képe. A függőleges piros vonalak a részecskecsapat egyedei. Leállási feltételként 200 darab iteráció végrehajtását határoztam határoz meg. Az eredmény a 14.. ábraán ábra látható, az algoritmus futásának végére a részecskék szépen elrendeződtek a globális optimum körül.

22


14 ábra: Particle Swarm keresés eredménye 14.

Az algoritmusok működési működési paramétereit a felhasználó minden részletre kiterjedően állíthatja a megfelelő egfelelő vezérlők segítségével. Kétváltozós függvények esetében bonyolultabb a keresés szemléltetése, mivel az ábrázoláshoz 3 dimenziós felület leképezése, vagy speciális grafikon szükséges. sz Az internetes optimáló program továbbfejlesztésének egyik fő iránya e funkció megvalósítása lesz. A következő teszthez Rastrigin's tesztfüggvény kétváltozós változatát (15. ábra) választottam, melynek leíró képlete: , 10 ∙ 2 ଶ 10 cos2 ଶ 102

(6)

A tesztfüggvénynek az x=0.0, y=0.0 helyen van globális minimuma, melynek értéke 0.0. A teszt célja a következő kérdések megválaszolása volt: 1. Milyen hatékonysággal találják meg az algoritmusok algoritmusok az optimális megoldást? 2. Ha mindhárom algoritmus esetén azonos számú populációt adok meg, valamint leállási feltételként is ugyanazon iterációs korlátot kapják, akkor megállapítható, hogy melyik algoritmus működik a leggyorsabban. A leggyorsabb működés természetesen ermészetesen nem feltétlenül jelent egyúttal leghatékonyabbat is.

23


3. Fejlettebb leállási feltétel definiálásával milyen mértékben növelhető a hatékonyság?

15. ábra: Rastrigin's tesztfüggvény

A tesztelés során minden esetben 100-as 100 nagyságú yságú populációkkal dolgoztam. Leállási feltételként egy kivételtől (PSO*) eltekintve a 400 iterációs határt szabtam meg. Minden keresést háromszor ismételtem meg, majd a feljegyzett eredmények átlagát tüntettem fel a táblázatban. Idő [ms]

x

y

Fitness

PSO

26

-7,92*10-10

2,27*10-11

1,40*10-9

PSO*

18

3,82*10-10

-6,94*10-10

8,25*10-9

DE

30

5,17*10-6

-1,25*10-7

4,43*10-6

BFO

43

3,41*10-6

2,18*10-5

9,63*10-5

1. táblázat

Az algoritmusok hatékonyságának elemzéséhez először meg kell határozni, hogy milyen pontosságra van szükségünk. Ha négy tizedesjegy pontosság 24


megfelelő, akkor megállapítható, hogy mindegyik algoritmus megtalálta az optimális megoldást. Ellenben ha például nyolc tizedesjegy pontosságú keresésre van szükség, akkor a Differenciális Evolúció és a Bacterial Foraging esetében kiválóan megfigyelhető a heurisztikus algoritmusok gyenge pontja. Nagyon közel vannak az optimális megoldáshoz, de nem azt találták meg. Vélhetően nagyobb populáció vagy iterációszám javítana a pontosságon. A leggyorsabb működést a Particle Swarm produkálta, tehát iterációnként a PSO-nak van a legkisebb számításigénye a vizsgált algoritmusok közül. Érdekes módon egyben a leghatékonyabb algoritmus is a részecske-csapat volt az adott tesztkörülmények között. A táblázatban szereplő PSO* esetében leállási kritériumként iterációs határ helyett a feltétel az volt, hogy valamennyi részecske legjobb pozíciója egyezzen meg a globális legjobb pozícióval. Ez átlagosan 307 iteráció után következett be. A táblázatból leolvasható, hogy a 400 iterációs határhoz képest ez 23,25%-al kevesebb számítást jelent, ami pontosan megmutatkozik a futási időkben is. A heurisztikus algoritmusok tesztelése egy igen nehéz és összetett folyamat, mivel a sok paraméter és nagyszámú változó gyakorlatilag végtelen variációs lehetőséget jelent.

25


3.3 Az Utazó ügynök probléma Az Utazó ügynök probléma (TSP- Traveling Salesman Problem) egy gráfelméleti feladat, elnevezését azonban onnan kapta, hogy egy mindennapi életből vett példával szokták szemléltetni: Adott bizonyos számú város, továbbá ismerjük a távolságot minden város között. Egy ügynök körutat szeretne tenni a városokban úgy, hogy mindegyiket pontosan egyszer érinti, és az útiköltség a lehető legkisebb legyen. Az útiköltség egyenesen arányos a városok közötti távolsággal. A feladat tehát olyan útvonal meghatározása, melynek költsége minimális. A probléma gráfelméleti megfogalmazása szerint adott egy teljes súlyozott gráf, és e gráfon keressük a legkisebb összsúlyú Hamilton kört. A gráf csúcspontja a városok, élei pedig a városokat összekötő utak. Az élek súlyozása az útiköltségnek felel meg. A gráf teljes, mivel feltételezzük, hogy tetszőleges városból közvetlenül eljuthatunk bármelyik másikba. A dolgozatban a klasszikus szimmetrikus utazó ügynök feladattal foglalkozom. A szimmetrikus jelző azt jelenti, hogy az élek irányítatlanok, és tetszőleges él költsége mindkét irányban ugyanannyi. A feladatnak létezik asszimetrikus változata, melyről a [17] műben olvashat bővebben az érdeklődő. A Utazó ügynök pontos eredetéről megoszlanak a vélemények, a témában már a XIX. században is készültek publikációk [18]. Az általános változat matematikai megfogalmazása 1930-ban készült el. Azért bír különösen nagy jelentőséggel, mert számos gyakorlati alkalmazás vezethető vissza rá. A logisztikában a gyűjtő és elosztó

járatok

útvonalának

megtervezése

(futárszolgálat,

kommunális

hulladékszállítás) tipikusan ilyen alkalmazás. Az elektronikai gyártásban is gyakran előfordul, hogy egy nyákon bizonyos pontokat szeretnénk összekötni úgy, hogy a kötés hossza a lehető legrövidebb legyen. Az élet számos területén felmerül a TSP, ezért az egyik legtöbbet kutatott kombinatorikus optimalizálási probléma. A Springer Link és ScienceDirect tudományos archívumok szerint eddig több mint 20.000 publikáció foglalkozik a témával.

26


3.3.1 Miért nehéz megoldani az Utazó ügynök feladatot? Az Utazó ügynök problémát úgy lehetne teljes bizonyossággal megoldani, ha az összes lehetséges körútnak kiszámolnánk a költéségét. Az összes csúcs lehetséges permutációinak száma n!. Minden permutáció meghatároz egy Hamilton kört a teljes gráfban. A 2. táblázatban a TSP számítás mérföldkövei szerepelnek, könnyedén kiszámítható, hogy adott számú csúcspont esetében mennyi lehetséges megoldás van: Csúcspontok száma

Lehetséges megoldások száma

Megoldás éve

5

120

-

10

3628800

-

25

1,55112101*10-25

-

49 város (USA 48 tagállam fővárosa és Washington) 120 város (NyugatNémetország) 532 telefonközpont (USA AT&T)

6,08281864*1062

1954

6,68950291*10198

1977

?

1987

666 nevezetesség a világon

?

1987

4461 város

?

1988

13509 város (USA)

?

1998

24978 város (Svédország)

?

2004

85900 pont (Integrált áramkör)

?

2006

2. táblázat

A táblázatból leolvasható, hogy viszonylag kis számú csúcspont esetén is rengeteg lehetséges megoldás létezik. Az Utazó ügynök probléma n méretű bemenet esetén O(n!) bonyolultságú, ezért nem oldható meg polinomiális időben. A TSP az NP-nehéz problémák osztályába tartozik, hatékony megoldás nem ismert nagyszámú csúcspont esetében. Érdekesség, hogy a híres fizikus, Stephen Hawking szerint a megfigyelhető univerzum nagyságrendileg 1078-1082 atomból áll [19]. 27


Nagyságrendileg ugyanennyi lehetséges megoldása van az Utazó ügynök problémának 60 város esetén. Nyilvánvaló, hogy bizonyos számú város felett az összes lehetséges megoldás vizsgálata fizikai képtelenség. A megoldást a heurisztikus algoritmusok jelentik, mivel nagy problémaméret esetén is képesek optimális, vagy ahhoz közelítő megoldást adni. Az internetes optimáló alkalmazásba három heurisztikus algoritmust építettem az Utazó ügynök feladat megoldására.

3.4 Heurisztikus algoritmusok az Utazó ügynök probléma megoldására 3.4.1 Ant Colony Az Ant Colony (Hangya kolónia) a Bacterial Foraging és Particle Swarm algoritmusokhoz hasonlóan egy rajintelligencia módszer.

3.4.1.1 Elméleti háttér A módszert Dorigo dolgozta ki 1992-ben [20], a hangyakolóniák táplálkozási és

kommunikációs

viselkedésmintái

inspirálták.

A

hangyák

kezdetben

véletlenszerűen keresik az élelmet. Ha valamelyik egyed táplálékot észlel, visszatér a kolóniához, útja során pedig feromont bocsát ki.

16. ábra: Hangyák élelemkeresés közben

28


A többi egyed érzékeli a feromont, és a véletlenszerű keresés helyett nagy eséllyel követnii kezdi az utat, valamint szintén feromont bocsájt ki. Egy idő után jól megfigyelhető útvonalak alakulnak ki, melyek az optimális pont felé vezetnek. A feromon egy idő után elpárolog, új utak keresésére kényszerítve az egyedeket.

3.4.1.2 Az algoritmus működése Az egyre jobb megoldások heurisztikus és probléma specifikus ismeretek alapján jönnek létre. A probléma specifikus ismereteket a feromonok helyzete és mennyisége szolgáltatja. A kiinduló permutáció véletlenszerűen jön létre. Ezután egy ciklus segítségével a hangyák h új permutációkat alakítanak ki.. Adott városból a legkisebb költségű úton próbálnak továbbmenni, az útjukat feromonnal jelzik. A legkisebb költség mellett a korábban elhelyezett feromonok is befolyásolják a döntésüket [21].

3.4.1.3 Pszeudokód

29


3.4.2 Simulated Annealing A Simulated Annealing (Szimulált Hűtés) algoritmus egy fizikai jelenségen alapuló heurisztika. A rajintelligencia és evolúciós eljárásokhoz hasonlóan a természet inspirálta kidolgozását.

3.4.2.1 Elméleti leírás A módszert Kirkpatrick, Gelatt és Vecchi dolgozta ki 1983-ban [22]. A metallurgiában bizonyos anyagok kedvező tulajdonságokra tesznek szert, ha felhevítik, majd szabályozott körülmények között lehűtik őket. A folyamat során átalakul kristályszerkezetük, mivel a felhevített anyagban az atomok képesek elmozdulni, a hűtési folyamat során pedig új, számukra kedvezőbb pozíciót vesznek fel (energiaminimumra törekednek).

17. ábra: Temperálás során kialakuló kristályszerkezet [23]

30


3.4.2.2 Az algoritmus működése A kiinduló permutáció véletlenszerűen véletlenszerű jön létre. Az algoritmus az iteráció során új permutációt hoz létre a sztochasztikus 2-opt 2 opt lokális kereső algoritmus segítségével. Ezután egy döntési függvény a permutációk költsége alapján meghatározza, hogy az új permutáció vagy a régi a jobb. Az iterációk iter során folyamatosan csökken a hőmérséklet, melynek következtében a döntési függvény egyre kifinomultabban működik.

3.4.2.3 Pszeudokód

3.4.3 Tabu Search A Tabu Search (Tabu keresés) egy sztochasztikus elven működő lokális kereső algoritmus, mely memóriával rendelkezik. rendelkezik. Ez a memória az úgynevezett tabu lista. Az eljárást ást Glover dolgozta ki 1986-ban 1986 [24].

31


3.4.3.1 Az algoritmus működése Az eljárás egy véletlenszerű induló permutáció létrehozásával kezdődik. A kiinduló

permutáció

alapján

annak

néhány

véletlenszerű

paraméterének

megváltoztatásával egy új permutációcsoportot hoz létre. Ha a csoportban bármelyik permutáció kedvezőbb megoldást ad a problémára, akkor onnantól kezdve az lesz az etalon megoldás. Annak elkerülésére, hogy az algoritmus fennakadjon egy lokális optimumon, az etalon megoldás bizonyos paramétereit tabu listára tesszük. Ha a keresés során újra előáll a tabu lista egy eleme, akkor azt az algoritmus tabunak nyilvánítja, nyilvánítja és újra próbálkozik. A tabu lista használatával jó eséllyel elkerülhető a lokális optimum.

3.4.3.2 Pszeudokód

32


3.4.4 Az Utazó ügynök feladat specifikálása a teszthez A heurisztikus optimáló algoritmusok teszteléséhez a Berlin52 feladatot választottam sztottam a TSPLIB gyűjteményből [25]. Mint a neve is mutatja, egy 52 csúcspontból álló problémáról van szó. Az optimális körút költsége 7542 egység, ideális esetben minden algoritmus erre az eredményre jut. A csúcspontok x és y koordináták alapján vannak megadva. A csúcspontok közötti távolságot az euklideszi távolság segítségével számítom ki, mely a Pitagorasz itagorasz tételen alapul. alapu Koordinátageometriában az xy sík két pontja, (x ( 1, y1) és (x2, y2) közötti euklideszi távolság: ଶ ଵ ଶ ଶ ଵ ଶ

(7)

Az internetes optimáló alkalmazásba beépítettem egy módszert a gráf megjelenítésére, amit a 18. 18 ábra szemléltet. A megvalósításhoz a JavaFX Canvas vezérlőjét használtam. Az algoritmusok tesztelése során azonban kikapcsoltam a megjelenítést, hogy az ne befolyásolhassa a futási időt.

18. ábra:: Utazó ügynök probléma probléma gráfjának megjelenítése JavaFX Canvas vezérlővel

33


A teszteket egy napjainkban középkategóriásnak mondható hordozható számítógépen végeztem, mely Intel Core I5 3317U típusú processzorral rendelkezik. Az energiagazdálkodási lehetőségeket kikapcsoltam, a processzor végig a maximális teljesítményén üzemelt. A gyártói specifikáció szerint ebben az állapotban 42 GFLOPS (FLOPS- FLoating point Operations Per Second) elméleti csúcsteljesítményre képes a CPU. Ez gyakorlatilag azt jelenti, hogy másodpercenként 42 milliárd lebegőpontos műveletet tud elvégezni [26]. Ha a Berlin52 problémának minden permutációját vizsgálni

szeretném

8,06581752*1067

(Brute-force

lehetőséget

kellene

módszer),

akkor

megvizsgálnom.

nagyságrendileg Ha

nagyvonalúan

feltételezzük, hogy egy permutáció megvizsgálása egy lebegőpontos műveletnek felel meg, akkor is 1,92043274*1057 másodpercig tartana a számítás. Tudva, hogy a Föld bolygó megközelítőleg 1,43173440*1017 másodperce keletkezett, belátható, hogy teljes fizikai képtelenség a tudomány jelenlegi állása szerint már 52 csúcspont esetében is megvizsgálni az összes lehetséges permutációt.

3.4.5 Az algoritmusok tesztelése, az Utazó ügynök feladat megoldása Az Utazó ügynök probléma megoldása során a fő cél a következő kérdések megválaszolása volt: 1. Milyen hatékonysággal találják meg a heurisztikus algoritmusok az optimális megoldást? 2. Ha mindhárom algoritmus esetén azonos számú iterációs korlátot adok meg, akkor megállapítható, hogy melyik algoritmus működik a leggyorsabban. A leggyorsabb

működés

természetesen

nem

feltétlenül

jelent

egyúttal

leghatékonyabbat is.

3.4.5.1 Az algoritmusok paraméterezése • A tesztelés során az Ant Colony és Tabu Search esetében 100-as iterációs határt szabtam meg • A Simulated Annealing algoritmus ezzel szemben 10000 iteráción át számolt. Az értékeket 100 iterációnként mentettem le. 34


• Az Ant Colony összesen 10 hangyával dolgozott. • A Simulated Annealing algoritmus 100000 fokról indult, a hőmérséklet változási tényező 0,98. • A Tabu Search tabu listájába 15 elem fért.

3.4.5.2 Teszteredmények A tesztelés során a feljegyzett eredményeket az alábbi táblázatban foglaltam össze: Idő [ms]

Legjobb költség

Eltérés az optimumtól

Ant Colony

8048,386

7772

+230

Simulated Annealing

1074,190

7818

+276

Tabu Search

1149,821

8460

+918

3. táblázat

Az algoritmusok hatékonyságának elemzésekor kiválóan megfigyelhető, hogy egyik sem az optimális megoldást adta vissza. Viszonylag közel vannak az optimális megoldáshoz, de nem azt találták meg. Vélhetően nagyobb populáció vagy iterációszám javítana a pontosságon. A legjobb eredményt az Ant Colony heurisztika szolgáltatta, azonban futási ideje is ennek volt a legnagyobb. A futás során permutációk költségének változását szemlélteti a 19. ábra. • Jól látható, hogy a Tabu keresésnél viszonylag egyenletesen csökkent az érték. • A Szimulált hűtés futása elején dinamikus költségcsökkentést produkált. • Az Ant Colony pedig a másik két eljárásnál egy eleve sokkal alacsonyabb költségszintről indított, azonban a kezdeti értéket nem sikerült szignifikáns mértékben lejjebb szorítania.

35

Internetes optimáló alkalmazás készítése JavaFX környezetben az utazó ügynök probléma megoldására 35000 Ant Colony 30000

K ö l t s é g

Simulated Annealing Tabu Search

25000 20000 15000 10000 5000

97

93

89

85

81

77

73

69

65

61

57

53

49

45

41

37

33

29

25

21

17

13

9

5

1

0 Iterációszám 19. ábra: A körutak költségének változása TSP megoldás során

A leggyorsabb működést a Simulated Annealing algoritmus produkálta annak ellenére, hogy 100-szor több iterációt hajtott végre. Kijelenthető, hogy az SA-nak van a legkisebb számításigénye a vizsgált algoritmusok közül. A heurisztikus algoritmusok tesztelése egy igen nehéz és összetett folyamat, mivel a sok paraméter és nagyszámú változó gyakorlatilag végtelen variációs lehetőséget jelent. Kipróbáltam mi történik akkor, ha az Ant Colony algoritmus 20 hangyával 200 iteráción keresztül dolgozik. Lényegében tehát megdupláztam a hangyák és az iterációk számát az előző méréshez képest. A feljegyzett eredmények az alábbi táblázatban tekinthetők meg.

Ant Colony

Idő [ms]

Legjobb költség

Eltérés az optimumtól

31712,217

7542

0

4. táblázat

A futási idő közel négyszeresére nőtt, azonban az Ant Colony algoritmus megtalálta a Berlin52 Utazó ügynök probléma optimális megoldását. 36

Internetes optimáló alkalmazás készítése JavaFX környezetben az utazó ügynök probléma megoldására 9000 Ant Colony 8500 K ö 8000 l t s 7500 é g 7000

1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 155 162 169 176 183 190 197

6500

Iterációszám 20. ábra: A körutak költségének változása Ant Colony algoritmus paraméterezésével

3.5 Az algoritmusok továbbfejlesztési lehetőségei A kutatókat folyamatosan foglalkoztatja, hogyan lehetne növelni a heurisztikus algoritmusok hatékonyságát. Az egyik leggyakoribb megközelítés a hibrid eljárások kidolgozása. A tesztjeim során is látható volt, hogy a különböző algoritmusok eltérő keresési karakterisztikát mutatnak, más-más szakaszban voltak a legerősebbek. A hibrid algoritmusok lényege hogy különböző eljárások erősségeit ötvözve próbálnak hatékonyabb keresést megvalósítani. Hibrid algoritmusokra példát a [27] (Simulated Annealing- Tabu Search hybrid), [28] (Particle Swarm- Ant Colony hybrid) forrásművekben találhatunk. Az algoritmusok továbbfejlesztésének másik megközelítése az adaptivitás megvalósítása. A tesztek során konstans paraméterekkel dolgoztam, melyeket az algoritmus futásának elején adtam meg. Elképzelhető azonban, hogy a keresés egy bizonyos szakaszában előnyösebb lett volna más értékű paraméter. Az adaptivitás lényege, hogy az algoritmus futás közben intelligens módon paraméterezi önmagát az adott problémának megfelelően [29]. Felmerülhet a kérdés, hogy milyen mértékben használható egy elsősorban folytonos matematikai függvények optimálására kitalált algoritmus például az 37


Utazó ügynök probléma megoldására. A különbség, hogy míg előbbi esetben a döntési változók lebegőpontos értéket vesznek fel, addig a TSP esetében a permutációk diszkrét értékekből épülnek fel. A megoldás a lebegőpontos értékek diszkretizálása, például az SPV (Smallest Position Value) szabály segítségével, amiről bővebben a [30] forrásműben olvashat az érdeklődő. Az eljárás segítségével például a Particle Swarm algoritmus is felhasználható az Utazó ügynök probléma megoldására.

4 Összefoglalás Dolgozatomban a heurisztikus optimáló algoritmusok működését, és a használatukban rejlő sokszínű lehetőségeket vizsgáltam. Véleményem szerint a tudomány és technológia fejlődésével számos új területen merül majd fel az igény a nagy bonyolultságú, hagyományos eszközökkel megoldhatatlannak tűnő számítási feladatok elvégzésére. Ez az a problémakör, ahol a metaheurisztikus optimáló algoritmusok a leginkább erősek. Célom, hogy tovább bővítsem a web alkalmazásba épített algoritmusok számát, valamint olyan új gyakorlati példákkal szemléltethessem működésüket, melyek

különböző

feladatokhoz

szerkezetoptimalizálási,

kapcsolódnak.

Szeretném

logisztikai,

továbbfejleszteni

operációkutatási a

már

meglévő

algoritmusokat adaptív paraméterezéssel, és újfajta hibrid eljárások kidolgozásával, tesztelésével. A web alkalmazás a http://users.iit.uni-miskolc.hu/~marcsak/ címen érhető el.

38


5 Melléklet 5.1 A Bacterial Foraging algoritmus pszeudokódja

39


5.1.1 Chemotaxis and Swim

40


6 Irodalomjegyzék [1]

JÁRMAI K., IVÁNYI M.: Gazdaságos fémszerkezetek analízise és tervezése, Műegyetemi kiadó, Budapest, 2001. ISBN 963 4206743

[2]

WEAVER J.: Pro JavaFX2 Platform, Appress, 2012. ISBN 978-1430268727

[3]

TÍMÁR I.: Műszaki problémák optimális megoldása, A Miskolci egyetem habilitációs füzetei, Miskolc, 2001.

[4]

VIRÁG Z., JÁRMAI K.: Szabványos kör keresztmetszetű többtámaszú tartók optimális méretezése, GÉP folyóirat, 2013/2. ISSN 0016-8572

[5]

ALI M. M., STOREY C. és TORN A.: Application of stochastic global optimization algorithms to practical problems, Journal of Optimization Theory and Applications, 1997. pp. 545-563

[6]

MOLGA M., SMUTNICKI C.: Test functions for optimization needs, 2005, http://www.zsd.ict.pwr.wroc.pl/files/docs/functions.pdf

[7]

WOLPERT D. H., MACREADY W. G.: No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, 1997. pp. 67–82

[8]

WOOLLEY A.W., CHABRIS C. F., PENTLAND A., HASHMI N., és T. W. MALONE: Evidence for a Collective Intelligence Factor in the Performance of Human Groups, Journal of Science Vol. 330, 2010. pp. 686-688

[9]

LIU Y. és PASSINO K. M.: Biomimicry of social foraging bacteria for distributed optimization: Models, principles, and emergent behaviors, Journal of Optimization Theory and Applications, 2002. pp. 603–628

[10] PASSINO K. M.: Bacterial foraging optimization, International Journal of Swarm Intelligence Research, 2010. pp. 1–16 [11] BROWNLEE J.: Clever Algorithms: Nature-Inspired Programming Recipes, Lulu, 2011. ISBN: 978-1-4467-8506-5 [12] DARWIN C.: On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life (1st ed., 1859), London, John Murray, 2008. ISBN 1-4353-9386-4. [13] STORN R. és PRICE K.:. Differential evolution: A simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95012, International Computer Science Institute, Berkeley, CA, 1995.

41


[14] PRICE K., STORN R. M. ÉS LAMPINEN J. A.:. Differential evolution: A practical approach to global optimization, Springer, 2005. [15] KENNEDY J. és EBERHART R. C.:. Particle swarm optimization, In Proceedings IEEE int’l conf. on neural networks Vol. IV, 1995. pp 1942–1948 [16] HU X., EBERHART R.: Solving Constrained Nonlinear Optimization Problems with Particle Swarm Optimization, In Proceedings of the 6th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2002), volume 5. Orlando, USA, IIIS, 2002. [17] CHEN N. H.: An Ant Colony Optimization and Bayesian Network Structure Application for the Asymmetric Traveling Salesman Problem, Lecture Notes in Computer Science Vol. 7198, 2012. pp 74-78 [18] BIGGS N.L., LLOYD E.K., és WILSON R.J.: Graph Theory 1736-1936, Clarendon Press, Oxford, 1976. [19] S. HAWKING: A Brief History of Time, Bantam, 10th anniversary edition, 1998. ISBN: 978-0553380163 [20] DORIGO M.: Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1992. [21] DORIGO M. és GAMBARDELLA L. M.: Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1997. pp. 53–66 [22] KIRKPATRICK S.: Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 1983. pp 975–986 [23] ZHANG K., FU Z.: Effects of annealing treatment on phase composition and microstructure of CoCrFeNiTiAlx high-entropy alloys, Intermetallics Volume 22, March 2012. pp 24-32 [24] GLOVER F.: Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 1986. pp 533–549 [25] TSPLIB: TSP and vehicle routing problem data, Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB), 1991. [26] INTEL CORPORATION: Intel® Corei5-3300 Mobile Processor Series, 2013. http://download.intel.com/support/processors/corei5/sb/core_i5-3300_m.pdf

42


[27] MURAT A., SERPIL E.: A hybrid simulated annealing-tabu search algorithm for the part selection and machine loading problems in flexible manufacturing systems, The International Journal of Advanced Manufacturing Technology, 2012. [28] SERAPIÃO A. B. S., MENDES J. R. P.: Classification of Petroleum Well Drilling Operations with a Hybrid Particle Swarm/Ant Colony Algorithm, Next-Generation Applied Intelligence, Lecture Notes in Computer Science Volume 5579, 2009. pp 301-310 [29] LI C.: An adaptive learning particle swarm optimizer for function optimization, Conference Publications, Leicester, 2009. pp 381-388 [30] TASGETIREN, M.F., SEVKLI, M., LIANG, Y.-C., GENCYILMAZ, G.: Particle swarm optimization algorithm for single-machine total weighted tardiness problem, Proceedings of Congress on Evolutionary Computation, Portland, Oregon, USA, 2004. pp 1412–1419

43

TDK-dolgozat. Marcsák Gábor Zoltán

Recommend Documents