Szakdolgozat. Heurisztikus optimalizálás a logisztikában. Anyagmozgatási és Logisztikai tanszék

Anyagmozgatási és Logisztikai tanszék

Heurisztikus optimalizálás a logisztikában

Szakdolgozat

Orbán Péter IQY9BH 3700 Kazincbarcika Móricz Zsigmond tér 18.


Tartalomjegyzék Tartalomjegyzék

-1-

Bevezetés

-3-

1.

Logisztika és raktározás 1.1

Logisztika

1.1.1

-5-

1.2.1

Beszerzés költségei

-8-

1.2.2

Raktározás

-8-

Optimálás

- 10 -

2.1

Bevezetés

- 10 -

2.2

Optimálás elemei

- 10 -

2.2.1

Célfüggvény

- 10 -

2.2.2

Tervezési változók, paraméterek

- 12 -

2.2.3

Megengedett tartomány, konvexitás

- 12 -

Optimálási eljárások és azok csoportosítása

Heurisztikus algoritmusok

- 12 - 14 -

3.1

Heurisztika

- 14 -

3.2

Heurisztika a számítástudományban

- 14 -

3.3

Heurisztikus algoritmusok

- 15 -

3.3.1 4.

Logisztika feladatai és céljai

-7-

2.3 3.

-4-

Beszerzés és raktározás

1.2

2.

-4-

„Swarm Intelligence” algoritmusok

Genetikus algoritmus

- 16 - 19 -

4.1

Bevezetés

- 19 -

4.2

A genetikus algoritmus egyed reprezentálása

- 19 -

4.2.1

Fitnesz

- 20 -

4.2.2

Populáció

- 20 -

-1-

Heurisztikus optimalizálás a logisztikában 4.3

- 21 -

4.3.1

Rekombináció

- 21 -

4.3.2

Mutáció

- 21 -

4.3.3

Szelekció

- 22 -

4.4 5.

A genetikus algoritmus műveletei

A genetikus algoritmus működése

- 22 -

A GeneticProgramming.exe bemutatása

- 25 -

5.1

Problémafelvetés

- 25 -

5.2

Programozási környezet és technikák bemutatása

- 26 -

5.2.1

Visual Studio

- 27 -

5.2.2

.NET keretrendszer

- 30 -

5.2.3

Visual C#

- 31 -

5.2.4

Programozási technikák

- 32 -

5.2.5

Tesztelés

- 33 -

5.2.6

Egyéb eszközök

- 34 -

5.3

GeneticProgramming.exe általános bemutatása, rendszerterv

- 34 -

5.4

Diagramok

- 37 -

5.5

A „genetikus programozás” implementálása

- 41 -

5.5.1

Paraméterek

- 42 -

5.5.2

Az adatok felvitele és feldolgozása

- 44 -

5.5.3

Az egyed implementálása, az Individual osztály

- 44 -

5.5.4

Felhasználó felület és osztályai

- 48 -

5.5.5

Az optimálási folyamat bemutatása

- 50 -

Összefoglalás

- 52 -

Irodalomjegyzék

- 53 -

Ábrajegyzék

- 54 -

SUMMARY

- 56 -

KÖSZÖNETNYILVÁNÍTÁS

- 57 -2-


Bevezetés Szakdolgozat témám interdiszciplináris jellegű, felöleli a logisztika, azon belül is a beszerzés és raktározás témakörét, melyet kiegészít az informatika. Számomra mint informatikus logisztika szakirányos hallgatónak az informatikai megközelítés volt evidens. Szakdolgozatom elkészítése során különböző célkitűzések megvalósítása lebegett a szemem előtt. Egyrészt a dolgozat minél sikeresebb abszolválása, másrészt az optimálási és programozási technikák minél mélyebb megismerése szorosan kötődve a logisztika területéhez. Az adott feladat kezdetben számomra idegen volt, és számtalan új technológiával, új gondolkodással kellett megismerkednem. Rengeteg döntést kellett hoznom rengeteg változóból. Az optimálási eljárás megválasztása a rengeteg lehetőség közül; ehhez először mindben el kellett mélyülnöm, hogy megérthessem azokat, és utána választani tudjak a megfelelő eljárások közül. Továbbá a megfelelő fejlesztési környezetet, nyelvet és technikákat is meg kellett választani. A XXI. században ez sem egyszerű feladat. A főbb nyelvek, mint a Java, C vagy C++ mellett számtalan hatékony programozási nyelv létezik, továbbá minden nyelvhez számtalan fejlesztési környezet, IDE tartozik. Ezek többsége nagyban hasonlít egymásra, ám a gyors és hatékony fejlesztéshez szükséges a nekünk leginkább tetszőt kiválasztani. A technikai megoldások mellett a probléma természetét is meg kellett vizsgálnom. Megismerkedni a beszerzési és tárolási elmélettel és gyakorlattal.

-3-


1. Logisztika és raktározás A dolgozatom első fejezete a logisztika és raktározás elméleti hátterével foglalkozik.

1.1 Logisztika „Napjainkban a logisztikának, mint interdiszciplináris tudománynak ugrásszerűen megnőtt a jelentősége a felsőoktatásban is. Mindez több okra is visszavezethető. Ezek a következők: a termelő és a szolgáltató vállalatok, közületek gazdasági eredményessége, hatékonysága, versenyképessége növekedésének egyik legfontosabb eszköze a logisztika, ezért az ilyen ismeretek birtoklása a munkaerőpiacon alapvetően meghatározó.”1 A logisztika a görög „logosz” szóból származik, jelentése számítás, tervezés, ok. A logisztika nem a görögök idejében született, mint megannyi újítás. A logisztika végigkíséri az emberiség történelmét egészen a mai modern logisztika kialakulásáig és térnyeréséig. A modern logisztika kialakulása a hadászathoz köthető. A történelemben a háborúk fontos szerepet töltöttek be a nemzetek, országok sorsában, ezért ezekben az ország minden forrását és a szakismeretek legjavát felhasználták. A modern piacgazdaság kialakulásával a gazdaság egyre inkább egyenlő szerepeket kapott. A logisztikának napjainkra sincsen kiforrott, pontos fogalma, különböző szakirodalmakban más-más meghatározásokat lelünk attól függetlenül, hogy a szerzője milyen irányból közelítette meg a problémakört. „A logisztika feladata anyagok és információk áramlásának tervezése, szervezése, irányítása, hatékony lebonyolítása.”2 Egy másik megfogalmazásban: „A logisztika feladata anyagok és rájuk vonatkozó információk áramlásának tervezése, szervezése, irányítása, hatékony lebonyolítása.”3

1

dr. Cselényi József – dr. Illés Béla: Anyagáramlási rendszerek tervezése és irányítása

2

dr. Prezenszki József: Logisztika I.

-4-


1.1.1 Logisztika feladatai és céljai A logisztika célja bonyolult, összetett folyamatok optimálássá tétele, a gazdasági folyamatokban a költségek csökkentése. A logisztika létrejöttét a gazdasági élet alapvető szűkössége és gazdasági verseny tette elengedhetetlenné – a magas költségek és a modern sokszereplős piacok. A logisztika fejlesztése a vállalkozás egészére nézve az elsődleges fontosságú feladatok közé tartozik, mivel a logisztikai költségek a költségek jelentős százalékát kitehetik. A logisztika céljai között tartják számon a termelés és az értékesítés támogatását, az értéknövelő szolgáltatások biztosítását, illetve a vevőkiszolgálás színvonalának folyamatos javítását. Ezek együttese adja a logisztikai teljesítményt, amely a logisztikai célfüggvény alapján számszerűsíthető. A logisztika legfőbb feladatát általában a „7M”- vagy a „9M”- elv mentén szokás meghatározni. Ezek alapján különböző tényezők kerülnek súlypontba. A „7M”- elv:  megfelelő minőség  megfelelő anyag  megfelelő költség  megfelelő helyen  megfelelő mennyiség  megfelelő információval ellátva  megfelelő vevőnek A 9M-elv a logisztika feladatát, küldetését határozza meg. A felsorolt tényezők egyforma súllyal esnek latba, amikor a 9M-elv a logisztika feladataként azt határozza meg, hogy:  a megfelelő információ  a megfelelő anyag  a megfelelő energia

3

Szegedi Zoltán – Prezenszki József: Logisztika-menedzsment

-5-

Heurisztikus optimalizálás a logisztikában  a megfelelő személyek jussanak el  a megfelelő mennyiségben  a megfelelő minőségben  a megfelelő időpontban  a megfelelő helyre  a megfelelő költséggel.

1.1. ábra Logisztika által integrált területek

A logisztika mint interdiszciplináris terület számtalan tudományterületet használ, és mint modern tudományág nagyban kötődik az informatikához. A logisztika nagy komplex rendszerekkel foglalkozik, melyekről adott pillanatban rengeteg adat érhető el. Ennek feldolgozását ma már komoly informatikai rendszerek végzik. Továbbá mivel a logisztika mindig az optimum elérésére törekszik, ezért nagyszerűen hasznosítja a számítás tudomány eredményeit. A logisztika legfőbb területei: 

beszerzés, alapanyag-ellátás



csomagolás



elosztási, áruterítési kommunikáció



készletgazdálkodás és irányítás -6-

Heurisztikus optimalizálás a logisztikában 

raktározás



szállítás és forgalom előrejelzés



anyagmozgatás



rendelés-feldolgozás és kommunikáció



informatikai háttér



üzem és raktárelhelyezés



visszáru-kezelés



vevőszolgálati szintek



selejtezés

1.2 Beszerzés és raktározás A beszerzés a logisztika egyik legjelentősebb tevékenysége, a beszerzés komoly költséggel jár minden vállalat életében, ezért pontos megtervezése központi kérdés egy logisztikai folyamatban. Fontossága miatt külön beszerzési logisztikának hívjuk A beszerzési logisztika áll az anyagáramlási folyamatok kezdeténél: biztosítja azokat a bemeneti készleteket, amelyek a termelés (vagy tágabb értelmezésben szolgáltatás) elvégzéshez szükségesek. Egy átlagos iparvállalat bevételének 55%-85%-át költi ezekre, így e feladat minél gazdaságosabb és megbízhatóbb ellátása létkérdés. A beszerzést két főbb csoportba lehet sorolni: alapanyag/termelő beszerzés: ún. direkt beszerzés, és az indirekt beszerzés: szolgáltatások/kiegészítő anyagok. A beszerző feladatai közé tartozik a beszállítók felkutatása, minősítése, versenyeztetése és értékelése. Minél nagyobb a beszerzési költségek aránya, annál nagyobb fontosságot kap a vállalatban a beszerzés, és így annál magasabb szervezeti egységben helyezkedik el. De akárhol is történjen a döntés, nagyon fontos, hogy más szervezeti egységekkel integráltan szülessen meg, ne képezzen más logisztikai egységektől elkülönült funkciót. Emiatt különösen értékes mind a vállalaton belüli (a szükségletek tekintetében), mint vállalaton kívüli (a kínálatok tekintetében) a beszerzéshez köthető információk szerepe.

-7-

Heurisztikus optimalizálás a logisztikában A beszerzési költségeket nagyban befolyásolja a megrendelt áruk mennyisége, hiszen az áruk szállítása, tárolása, darabára nagyban határozza meg a költségeket.

1.2.1 Beszerzés költségei A beszerzést számos változó határozza meg. Ezen adathalmazban nehéz prioritásokat felállítani, emellett egy komplex sokváltozós függvényt alkotnak, mely az időben folytonosan változik, optimálásuk hagyományos módszerekkel nehézkes. A beszerzést elsődlegesen meghatározó változó az aktuális kereslet és kínálat. Ezek hiába változhatnak egy optimálási folyamat során, állandónak tekinthetjük őket. Hiszen a beszerzés során a kereslet nagysága a minimum, a kínálat pedig a maximum. Ezeken kívül is számtalan változóval kell számolnunk. A legegyszerűbb és

viszonylag állandó mennyiség a darabár, amely

meghatározza, hogy mennyibe kerül egy egységnyi áru a beszállítótól. Ez az esetek egy részében a beszállító által meghatározott fix költség, de nagyon gyakori jelenség, hogy a rendelt árumennyiség befolyásolja a meghatározott árat. A szállítási költség megmutatja, hogy egy szállítmányozás egy adott szállítmányozó egységgel, mennyi költséggel jár. A költséget tekinthetjük pénz vagy időköltségben. A szállítási kapacitás meghatározza, hogy egy szállítmányozó egység mekkora mennyiségű árut képes egyszerre szállítani. Ezek mellett számos kevésbé fontos változó léphet fel az aktuális beszerzéstől függően.

1.2.2 Raktározás A beszerzés során beszerzett árut a beszerzés után raktározni kell, ha csak ideiglenes is. Egyedül ideális esetben nincs szükség raktározásra, ekkor minden abban a pillanatban kerül felhasználásra, amikor megérkezett. A beszerzés során a modern logisztikában a LEAN elvek mellett ez az egyik legfontosabb. Ez a „Just in Time elv” a modern kori logisztika egyik célkitűzése.

-8-

Heurisztikus optimalizálás a logisztikában A raktározást végző szolgáltatók feladata olyan létesítmények fenntartása, amelyek az áruk minőségét és mennyiségét veszteség nélkül megtartják, befogadó képességük és teljesítőképességük lehetővé teszi a szükség szerinti ki- és betárolást. A szolgáltató raktárak jellegzetes típusai a következők: gyűjtő- és elosztóraktárak, közraktárak, konszignációs raktárak, vámáruraktárak. A raktárlogisztika foglalkozik a beszerzési, termelési és elosztási folyamatokhoz szükséges raktárkapacitás biztosításával, üzemeltetésével. Feladata a raktárba érkező anyagok minőségi és mennyiségi átvétele, megőrzése és az igények szerinti rendelkezésre bocsátása. Ellátja a fenti funkciókkal összefüggő anyag- és információáramlást. A raktári rendszerek rugalmas, hatékony működéséhez a korszerű raktározástechnikai

megoldások

mellett

megfelelő

alkalmazására is szükség van.

-9-

számítógépes

raktár-irányítási

rendszer


2. Optimálás Dolgozatom második fejezete az optimálás elméleti hátterét és gyakorlati megvalósításait taglalja.

2.1 Bevezetés A történelem kezdetétől az emberek a mindennapi életük során tudatosan vagy tudattalanul optimáltak, hogy az adott feltételek mellett a számukra lehető legjobb eredményeket érjék el, kezdve a vetés meghatározásától egészen a modern repülők szerkezetoptimalizálásán át a logisztikai rendszereken belül véghezvitt optimálásig. A hétköznapok során ezeket az optimálási folyamatokat az ember tudattalanul végzi, ám a tudatosság nagyban megnöveli ezek hatékonyságát: célok pontos kitűzése, feltételek körültekintő körbejárása, megfelelő optimálási módszer választása, megfelelő célfüggvény választás nagyban növeli az optimálás pontosságát és megbízhatóságát, továbbá nagyban csökkenti a költségét. Az optimálási módszerek eredete Newton, Leibniz és Cauchy továbbá Bernoulli, Euler és Lagrange nevéhez kötődnek és azóta fokozatosan fejlődnek. Igazán a XX. és XXI. században nyernek komoly teret a repülő és űrjárművek szerkezetoptimálása során, ebben az időben jöttek létre a véges elemes számítási módszerek. Az optimálás módszertanát Schmidt 1960-ban dolgozza ki.

2.2 Optimálás elemei Az optimálási problémát magát a célfüggvény (esetleg több célfüggvény), a tervezési változók és a paraméterek együttese határozza meg.

2.2.1 Célfüggvény Az optimálási problémák során általában végtelen sok megoldási lehetőség merül fel. E számos lehetséges megoldás közül kell nekünk meglelni a legmegfelelőbbet, ehhez általában egy úgynevezett célfüggvényt (vagy költségfüggvényt) alkalmazunk, mellyel a lehetséges kimeneti megoldásokat tudjuk egymáshoz hasonlítani. Ennek a függvénynek a feladata a legkisebb vagy éppen legnagyobb költségek megtalálása.

- 10 -

Heurisztikus optimalizálás a logisztikában A költségfüggvény választása az optimálási folyamat egyik legfontosabb lépése, több költségfüggvény esetén fontos és elengedhetetlen lépés a különböző függvények prioritásainak megválasztása.

- 11 -


2.2.2 Tervezési változók, paraméterek Az optimálás során tekintett feltételeket két nagy csoportba oszthatjuk: ezek a tervezési változók és a paraméterek. A kettő között az a fő különbség, hogy a paraméterek bemenő fix adatok, melyek az optimálás folyamán nem változnak (pl.:anyagár, fajlagos munkaköltség). A tervezési változók pedig az optimális folyamat során változnak, az optimálást végző egyén tetszőlegesen határozhatja meg őket (pl.: geometriai, keresztmetszeti, topológiai, anyagminőségi).

2.2.3 Megengedett tartomány, konvexitás A változókra úgy tekinthetünk, mint a tervezési tér egy dimenziójára és a változók értékére, mint a tér egy pontjára. Tehát N változó mellett N-dimenziós hiperteret használunk az optimáláshoz általános esetben. Ekkor a változók lehetséges értékei adják meg a megengedett tartományt. Az optimum megtalálása után fontos annak meghatározása, hogy a meglelt optimum globális-e vagy csak lokális optimumot leltünk. Ez függ a megengedett tartománytól és a feltételektől. Konvex tartomány esetén a lokális optimum egyben globális optimum is, ha konkáv a tartomány, akkor pedig számos lokális optimum lehet.

2.3 Optimálási eljárások és azok csoportosítása Számos optimáló eljárás létezik napjaikra, mely nagy szabadságot enged a tervezőnek, hogy az adott problémára legmegfelelőbb eljárást válassza, legyen az matematikai vagy egyéb más megoldás. Az optimálás egy egyszerű modellje x.1 ábra, mely az emberi gondolkodást veszi alapul. A szintek között szoros kapcsolat és visszacsatolás található.4

4

Jármai,K. - Iványi,M.: Gazdaságos fémszerkezetek analízise és méretezése. Műegyetemi Kiadó, Budapest, 2001, 230 old.

- 12 -


1.2.1. ábra Optimálás egyszerű logikai struktúrája

- 13 -


3. Heurisztikus algoritmusok Dolgozatom harmadik fejezete a heurisztikával (vagy metaheurisztika), annak jelentésével, elméleti hátterével, gyakorlati megvalósításával foglalkozik. Tartalmazza továbbá különböző területek általi felhasználását, heurisztikus algoritmusok osztályozását és többet röviden be is mutat.

3.1 Heurisztika A heurisztika egy gyűjtőfogalom a tapasztalati alapú technikákra, melyek általában probléma megoldásra, tanulásra és felfedezésre szolgálnak. Ezek általában olyan folyamatok, melyek nem bizonyítottak, és nem logikai lépések során jutunk el a kiindulási állapottól a konklúzióig.

3.2 Heurisztika a számítástudományban A számítástudományban, a mesterséges intelligenciakutatásban és a matematikai optimálásban a heurisztikának (vagy meta heurisztikának) az általánosnál szűkebb, jobban definiálható jelentése van. A

számítástudományban

a

heurisztikai

technikákat

olyan

problémák

megoldásánál alkalmazzák, ahol a hagyományos megoldások túl lassúak vagy nem lehet őket alkalmazni az adott problémára. A heurisztika egy köztes megoldás, amely elég gyorsan elég pontos megoldást ad. Ez a megoldás lehet, hogy nem a legpontosabb vagy nem globális optimum, de még mindig érdemes alkalmazni, hiszen a számítási költség nagyban csökken. A heurisztika használata előtt mindenféleképpen mérlegelni kell, hogy mennyire pontos eredményre van szükségünk, esetleg szükségünk van-e az összes létező megoldásra, a heurisztika képes-e megoldani az adott problémát, továbbá a számítási költségek megfelelőek lesznek-e. Az ilyen módszerek alkalmazása során gondot jelent a probléma modellezése, illetve a kapott eredményeket nem kezelhetjük biztosan jó megoldásként. A kapott eredményeket elemezni kell, hogy megfelelőek-e, ami gyakran gondot okozhat.

- 14 -

Heurisztikus optimalizálás a logisztikában Az ilyen algoritmusok egy része mögött komoly elméleti háttér rejtőzik. Mások egyszerű megfigyeléseken alapulnak, melyek nem tartalmaznak mögöttes elméleteket, bizonyításokat. Ezeket az algoritmusokat a számítástechnika számtalan területén alkalmazzák, például: keresés, víruskeresés, különböző optimálási feladatok. Kedvelt probléma az Utazó ügynök esete. Jellemzően robosztus algoritmusok, melyek számtalan problémára képesek megoldást adni.

3.3 Heurisztikus algoritmusok Számtalan meta heurisztikus algoritmus létezik, melyek gyakorlatilag bármilyen problémára használhatóak. Általános megoldást adnak és a modellalkotás során kell az algoritmust az adott feladathoz szabni. A megfelelő algoritmus választása és a feladathoz igazítása komoly körültekintést igényel a programozótól és komoly nehézségeket jelent.5 A meta heurisztikus algoritmusokat is többféleképpen csoportosíthatjuk, például ábra 2.1.

5

Bianchi, Leonora; Marco Dorigo, Luca Maria Gambardella, and Walter J. Gutjahr (2009). "A survey on metaheuristics for stochastic combinatorial optimization". Natural Computing: an international journal 8 (2): 239–287. doi:10.1007/s11047-008-9098-4

- 15 -


2.3.1. ábra Heurisztikus Algoritmusok egy csoportosítása.

3.3.1 „Swarm Intelligence” algoritmusok „Swarm

Intelligence”

vagy

raj

intelligencia

fogalma

nincs

pontosan

meghatározva, de általában egy kollektív decentralizált, önvezérelt viselkedési rendszer, melyben különálló entitások léteznek. Az alapötletet a természetben megfigyelt rajok (hangyák, méhek, vándormadarak, emberi tömeg viselkedése) adják. Az ilyen megoldások során általában különálló entitások populációjával dolgoznak, melynek nincsen központi irányítása. Az egyedek külön-külön, egymástól függetlenül cselekszenek bizonyos egyszerű szabályok mentén.6 A „Swarm Intelligence” kategóriában számos algoritmus

6

Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989)

- 16 -

Heurisztikus optimalizálás a logisztikában tartozik pl.: „Ant colony”, „Artificial bee colony”, intelligens vízcsepp, több rajos optimálás, rész rajos optimálás.

3.3.1.1 „Ant Colony” Az „Ant Colony” optimálási eljárás 1992 jött létre és Marco Dorigo PhD értekezésben fejtette ki. A hangyák viselkedését modellezi. Működése egyszerű a hangyák tetszőleges utakon elindulnak és „feromon” utat hagynak magunk után, mely a távolság növelésével gyengül. Az útválasztásnál pedig a hangyák azt részesítik előnyben, amelyiken erősebb a „feromon” jelzés. Az algoritmus működése jól látszik a 2.2 és 2.3-as ábrákon7

2.3.2. ábra Ant colony működése8

2.3 ábra Ant colony működése

3.3.1.2 „Glow worm” és „firefly” algoritmus A „glow worm” és „firefly” a szentjánosbogár (firefly), illetve annak lárvája (glow worm) viselkedését modellezi, pontosabban hogy hogyan találják meg egymást a világító bogarak. Az egyedülálló egyedek megfigyelik a környezetüket, és ha látnak egy vagy több egyedet, akkor a döntést hozó elindul az egyik felé adott sebességgel. Egy

7

Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. ISBN 0-262-04219-3

8

http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Aco_branches.svg/400pxAco_branches.svg.png

- 17 -

Heurisztikus optimalizálás a logisztikában választás annál vonzóbb, minél fényesebb egy pont. A pont fényességét az adott pontban lévő egyedek fényereje és a távolság határozza meg.9

2.3.3. ábra Glow worm működése

A „Glow worm” és a „Firefly” algoritmusok között a fő különbség a keresési távolság. A „Fire fly” algoritmusban nincsen keresési távolság változás, így az képes több lokális optimum megtalálására.

3.3.1.3 .Szimulált lehűtés A szimulált lehűtés algoritmus a hegymászó algoritmus egy továbbfejlesztett változata, mely a fémolvadékok lehűlését veszi mintául. A szimulált lehűlés algoritmus működése során elindul az adott útvonalon és a „hőmérséklet” csökkenése és a következő lépésjavulás által megadott valószínűséggel lép tovább.10

9

K.N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multi-agent and Grid Systems,2(3):209222. 10

Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.12. Simulated Annealing Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8

- 18 -


4. Genetikus algoritmus Dolgozatom negyedik fejezete a fejlesztett program által használt genetikus algoritmussal foglalkozik mélyebben. Bemutatja annak tagjait, műveleteit felveti problémáit, használhatóságát.

4.1 Bevezetés Dr. David E. Goldberg szerint: „az elmúlt három milliárd év nem lehet hibás, a legerősebb algoritmust használja”. Az evolúciós algoritmusok a heurisztikus megoldások közé tartoznak már a számítástudomány kezdeti szakaszától, az 1950 évektől. Az evolúciós algoritmusok fejlődésének fontos állomásai: 1954 Barricelli megalkotja az első evolúciós szimulációt11 1966 Fogel Evolúciós programozás12 1975 Holland genetikus algoritmus13 1985 Smith kidolgozza a genetikus programozást14 Ezek az algoritmusok decentralizált önvezérelt heurisztikus algoritmusok. A biológia evolúción alapulnak és az alapján működnek. A genetikus algoritmus is ebbe a családba tartozik, Holland nevéhez köthető a megszületése. Alapja az egyed reprezentáció és az egyedek szaporítása, versenyeztetése.

4.2 A genetikus algoritmus egyed reprezentálása Az egyedek a lehetséges kimeneti megoldásokat reprezentálják. A genetikus algoritmusok egyik elsődleges művelete az egyed reprezentálás. Az egyednek 11

Barricelli, N.A. (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.

12

Fogel, L.; Owens, A.J.; Walsh, M.J. (1966). Artificial Intelligence through Simulated Evolution. Wiley. ISBN 0-471-26516-0. 13

Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0-26208213-6. 14

Smith, S.F. (1980). A Learning System Based on Genetic Adaptive Algorithms (PhD Thesis). University of Pittsburgh.

- 19 -

Heurisztikus optimalizálás a logisztikában szükségesnek kell lennie tulajdonságok tárolására, hogy azokat könnyen tudjuk változtatni. Az egyednek a természetben fellelhető géneket kell modelleznie. A két leggyakoribb megvalósítás a bitsoros és a valós vektoros. A bitsoros reprezentációnál egy bitsorozat, mely megvalósít egy mesterséges kromoszómát. Az egyes bitek jelzik, hogy az egyed rendelkezik-e az adott tulajdonsággal, esetleg egyéb tartalmat rendelnek hozzá. Előnyös, mert a bit sor elemei könnyen változtathatóak, kis helyen tárolhatóak, továbbá matematikailag is könnyen végezhetünk rajta tetszőleges műveleteket. Valós vektoros megvalósításkor az egyedeket egy valós számokból álló vektor reprezentálja. Ezt a megoldást olyan esetben használják, ha az adott tulajdonságokhoz mennyiségi értéket is szeretnének rendelni. Ezekkel a vektorokkal sok minden könnyen leírható, könnyen változtatható és végezhetők rajtuk műveletek, számítások. A valós vektoros reprezentálás egy speciális esete a permutációs reprezentáció. Erre akkor van szükség, ha bejárások összegére keresünk megoldást. Ekkor is valós vektorokat használunk.

4.2.1 Fitnesz A fitnesz vagy rátermettségi függvény az egyedek jóságát határozza meg. Megválasztása mindig problémafüggő és nagy körültekintést igényel. Az egyedek gén állományából ez a függvény számolja ki a fitnesz értéket, mely megmutatja, hogy az a megoldás, amit az adott egyed képez, számunkra mennyire elfogadható.

4.2.2 Populáció Az adott idő pillanatban létező egyedek összességét populációnak nevezzük. A számítási költségek miatt gyakori az egyedek kódolása. A kódolt egyed adja az egyed genotípusát. Műveleteket az egyed genotípusával végzünk, majd ennek segítségével határozzuk meg az optimális eredményt. Az egyedeket leíró tulajdonságok megjelenésének összességét fenotípusnak nevezzük. A genotípus kimeneti változói a gének, az adott különkülön egyedben felvett értékeit pedig allélnek nevezzük. A genetikus algoritmus minden egyes iterációs lépésben új és új egyedeket hoz létre, ezeket generációnak hívjuk.

- 20 -


4.3 A genetikus algoritmus műveletei A genetikus algoritmus futása során az egyedekkel számos műveletet végezhetünk, melyek alkalmazását a programozó dönti el.

4.3.1 Rekombináció A rekombináció az új egyedek létrehozását végzi. A rekombináció során a szülők génjeiből új egyed jön létre a gének keresztezésével. Ezt a gének keresztezésével érjük el melyet számtalan módon megoldhatunk.

4.3.1.1 Egypontos keresztezés Az egypontos keresztezés olyan keresztezési operátor, mely során a szülők génjeit egy pontban elvágjuk, és a szülők elvágott génjeiből keletkezik az új egyed génállománya. A legegyszerűbb megoldás, ha a géneket megfelezzük. A vágási pontot máshogy is képezhetjük. Ez a pont lehet fix, ekkor minden keresztezésnél ugyanabban a pontban vágjuk el a géneket. Változó, ekkor valamilyen matematika eljárással számolva mindig más helyen vágjuk el az egyedek génjeit.

4.3.1.2 Egyenletes keresztezés Az egyenletes keresztezés során az egyed 50% eséllyel örökli a szülő azonos génjeit.

4.3.1.3 Köztes keresztezés Az egyenletes keresztezéshez hasonló, ám itt az új egyed génjei a szülők génjeinek egy függvénye.

4.3.2 Mutáció A mutáció során csak bizonyos géneket változtatunk, ezt alkalmazhatjuk a meglévő populáció tagjain vagy az új egyed létrejöttekor. A mutáció nagyon hasznos művelet: meggyorsítja az algoritmus futását, csökkenti a generációszámot és segít elmozdulni az esetleg lokális optimumból.

- 21 -

Heurisztikus optimalizálás a logisztikában A mutáció legalapvetőbb formája, hogy az egyed bizonyos génjeit kicseréljük. A mutálódó gének számát és magukat a géneket bárhogy kiválaszthatjuk, leggyakrabban ezeket véletlenül generáljuk.

4.3.3 Szelekció A szelekció operátorral választjuk ki az egyedeket, akiket tovább szeretnénk vinni következő generációba.

4.3.3.1 Véletlen A legegyszerűbb, ám olykor a legkevésbé hatékony megoldás a véletlen választásos szelekció, ahol véletlenszerűen választunk egyedeket.

4.3.3.2 Sorba rendezés Az adott populáció elemeit sorba rendezzük és az első legjobb fitnesz értékű kerül kiválasztásra.

4.3.3.3 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.

4.3.3.4 Versenyeztetéses választás Véletlenszerűen kiválasztott két egyed közül a versenyt nyerő, azaz a nagyobb fitneszű lesz a kiválasztott. A módszer alkalmazható több mint kétversenyzős esetben is.

4.4 A genetikus algoritmus működése Az algoritmus működése nagyon egyszerű, melyet megfigyelhetünk a 3.1 ábrán. 0. lépésben létrehozza a 0. generációt, ez az ősgeneráció, a többi ebből fog származni. Innen kezdve minden iterációs lépésben fitneszt számolunk és ha elértük az optimumot, akkor kilépünk, ha nem, új generációt hozunk létre keresztezéssel, mutációval és szelekcióval.

- 22 -


4.1. ábra Genetikus Algoritmus működés

A „genetikus programozás” alkalmazása során gondosan és feladatspecifikusan kell fitnesz értéket és egyed reprezentálást választani, hogy a lehető legjobban, leggyorsabban és a lehető legbiztosabb megoldást kapjuk. Fontos megfelelő kilépési feltételeket is megadni (pl.: maximális generációszám, átlag fitneszjavulás). A „genetikus programozás” előnyei: robosztus és tetszőleges problémára, az aktuális feladathoz igazítva lehet használni, globális optimumot keres és „zajos” környezettben és „zajos” fitnesz függvény esetén is jó értéket kapunk, könnyű az implementálása. A „genetikus programozás” hátrányai: költségigényes eljárás, valamint komoly gondot jelent az adott probléma leképezése az algoritmus számára, valamint a megfelelő fitnesz függvény megválasztása, amiket ha nem a lehető legjobban választunk meg, akkor erősen romlik az algoritmus hatékonysága vagy esetlegesen hibás eredményeket kapunk. Másik nagy hátránya, hogy véges lépésben csak jó eséllyel közelítjük az optimumot. A „genetikus programozás” főbb felhasználásai: a genetikus programozás számos optimálási feladatra alkalmazható pl.: az utazó ügynök probléma megoldására. Ezeknek a feladatoknak a közös tulajdonságai: Nemlineáris feladatok, melyek optimuma nem áll elő részoptimumok összegeként. Nagyméretű sokdimenziós állapottér. Lokális extrémumok sokasága. A feladat összetevőinek a hatása az eredményre nem becsülhető. A különféle paraméter értékekkel adódó megengedett megoldások kiértékelése elégséges a legjobb - 23 -

Heurisztikus optimalizálás a logisztikában megoldás kiválasztásához. Továbbá ezek a feladatok jellemzően sokváltozós összetett problémák. Számos program használja ezeket az algoritmusokat optimalizálási problémák megoldására pl.: GaUI, MathLab.

- 24 -


5. A GeneticProgramming.exe bemutatása Dolgozatom ötödik fejezete a fejlesztett program bemutatásával foglalkozik, kezdve a fejlesztési lépésektől a programozási technikákon, megvalósításokon keresztül a felhasználó felület és működés bemutatásáig.

5.1 Problémafelvetés Az ipari termelésben fontos, meghatározó szerepet játszik a logisztika, főleg ha költséghatékony termelést akarunk elérni. A logisztika egyik legfőbb ága a beszerzés megvalósítása. A beszerzés során, az ipari folyamatainkon kívülről, külső személytől szerezzük be a szükséges alapanyagokat, félkész termékeket. Az ipari gyártás során komoly gondot jelent a beszerzés és raktározás megoldása, hiszen rengeteg külső változó befolyásolja az anyagok beszerzésének és tárolásának költségét, mely komoly összegekre rúghat nem optimális esetben. Továbbá a „just in time” elveknek is meg kell felelnie a költséghatékonyság növelése érdekében. Nem szabad azonban veszélyeztetni a gyártás fenntarthatóságát, egy készlethiány miatti leállás ugyanis óriási veszteségeket okozhat egy üzemnek. A raktározás és beszerzés megtervezésénél figyelembe kell venni az üzem alapanyagigényét, a beszerzési és szállítási, valamint a raktározási kapacitást és költséget. A raktározási költségek gyakran magasra rúgnak és a helykihasználtság miatt a raktározási kapacitás is kicsi, ezért törekedni kell arra, hogy minden beszállított terméket lehetőleg azonnal felhasználjunk, de figyelni kell a beszállítási költségek megugrására is. A mennyiség és az ár kérdése mellett komoly figyelmet kell fordítani az időtényezőre is, hogy minden a megfelelő időben legyen a megfelelő helyen. Egy hasonló probléma során számtalan költség merül fel. Elsőnek a beszerzési ár, mely a termék konkrét ára, amennyiért megkapjuk azt a gyártójától. Ez az ár gyakran csökken, ha több terméket rendelünk; ezt az árcsökkenést is bele kell kalkulálni a megrendelésbe. Akár komoly árcsökkenést érhetünk el egy nagyobb megrendelés esetén, ezért figyelembe kell venni, hogy milyen mennyiségenként mennyivel csökken az ár. Beszállítási költség: az a költség, melyért a megrendelt alapanyagot beszállítják az üzembe. Ez egy szállítóeszköz egyszeri oda-vissza útját írja le. - 25 -

Heurisztikus optimalizálás a logisztikában Beszállítási kapacitás: az egy forduló során beszállítható termék mennyisége. Raktározási költség: az a költség, amiért raktározzuk a terméket; ezt leggyakrabban fajlagosan, azaz egy termékre lebontva érdemes megadni. Továbbá meg kell határozni egy olyan elfogadható elégséges beszerzési költséget, mellyel számolhatunk és mely elérésre érdekében meghatározhatjuk a rendelni kívánt mennyiséget. Azonban minden költség mellett elsődleges szempontnak a termelés folytonosságát kell tekinteni. Az alaprendszert megvizsgálva leszűrhetünk néhány sejtést vagy elvárást, mely előre sejteti a rendszer viselkedését, a lehetséges kimeneteleket, és egyben kijelöli az optimálás irányát. Jelen esetben a szállítási költséget útra lebontva adjuk meg, ez azt jelenti, hogy bizonyos korlátig csökkeni fog a fajlagos szállítási költség, majd egy korlát, a szállítási kapacitás elérése után megugrik és ismét csökkeni kezd a következő korlátig. Ez azért van, mert egy úttal x darabot tudunk elhozni y költségért, de x+1 darabot 2y költségért. A rendelés növelésével pedig csökken a megrendelési ár, de nőnek a szállítási és tárolási költségek. Mint láthatjuk, ez egy sokváltozós rendszer, akár egy termék egy telephelyre történő megrendelése esetén is. Egy hasonló ilyen rendszert matematikai úton nagyon nehéz lenne optimálni, lévén számtalan görbe közös optimumát kell megtalálnunk, ezért valamilyen gépi optimálási módszert kell választani. Ilyen egyszerűen leképezhető rendszer esetén jó választás az evolúciós algoritmusok egyike. Ennek a feladatnak a megoldásra készült az általam írt program a GeneticProgramming.exe nevű alkalmazás. 5.2

Programozási környezet és technikák bemutatása

Egy új software fejlesztése során gondosan kell mérlegelni a felhasználni kívánt fejlesztőkörnyezet, a tervezési és tesztelési eljárásokat. Különösen igaz ez olyan esetben, ha új, esetlegesen bonyolult algoritmusokat implementálunk a programunkba .Ilyen esetekben külön oda kell figyelni az algoritmus pontos megértésére, emberi léptékű, vizuális szemléltetésére. Ezeken felül a dokumentációra is oda nagy figyelmet kell fordítani. Az alkalmazás fejlesztését a Visual Studio fejlesztőkörnyezetben végeztem és a Visual C# programozási nyelvet használtam. Többek között azért választottam ezt a - 26 -

Heurisztikus optimalizálás a logisztikában környezetet és technológiát, mert a Microsoft Visual Studio széles körben használt, piacvezető, integrált fejlesztői környezet, amely az “eszközök” leggazdagabb választékát biztosítja. A Visual C# az elsődleges nyelv .NET alkalmazások fejlesztéséhez. A Visual C# erősen típusos nyelv, felügyelt környezetben fut és köztes kódra fordul, ennek köszönhetően a forráskód helyessége teljes mértékben ellenőrizhető és nagyban megkönnyíti a tesztelési fázist. Az alkalmazások köztes kódra fordulnak, amelyet futtatáskor a futtatókörnyezet fordít át és optimalizál az aktuális processzor jellegzetességei szerint - ennek köszönhetően a köztes kódra fordított alkalmazások platform függetlenek. Természetesen ez nem tényleges platform függetlenség, hiszen az alkalmazás csak a saját futtatókörnyezetén fut, de ez a futtatókörnyezet különböző verziókban az összes platformokra létezik. Windows platformon ez a .net keretrendszer valamely verziója, a Unix alapú platformokon pedig a Mono keretrendszer tetszőleges verziója. Ezek a tulajdonságok nagyszerűen alkalmassá tették a platformot az alkalmazásom elkészítésére.

5.2.1 Visual Studio A fejlesztés során a Microsoft Visual Studio két verzióját használtam az MS Visual Studio 2010 és az MS Visual Studio 12. A Visual Studio a Micrososft fő fejlesztési környezete, erősen integrált, innovatív, számtalan kényelmi funkcióval rendelkezik. Segítségével könnyen fejleszthetünk számtalan környezetre, kezdve a mobil eszközökre történő fejlesztéstől a desktop alkalmazásokon át a nagy szerver vagy felhő környezetig.

- 27 -


5.1. ábra A "Visual Stuido New Project" menüje

5.2. ábra Visual Stuido felhasználói felület tervezés közben

- 28 -


5.3. ábra Visual Studio fejlesztés közben

A Visual Studioban lehetőség van szinte bármilyen platformra fejleszteni valamelyik .net nyelven. Ehhez támogatja a teszteléshez szükséges futtatási környezetet is(beépített web(IIS) és SQL szerver, windows phone 7 emulator, stb). A program lehetőséget biztosít közös munkára is akár távolból is a Team Foundation Serveren vagy Sharepointon keresztül, mellyel könnyen oszthatunk meg kódokat egymással, illetve tárolhatjuk projektjeinket közös központi helyen vagy akár a felhőben. Ezek a szolgáltatások nem csak egyszerűen megosztják vagy tárolják a kódot, hanem csakis olyan kódokat engednek megosztani, amelyek átmentek a beállított teszteken.15 A legújabb Visual Studio magában foglalja a Microsoft Blend-et melyet a fejlesztett program vizuális elemeinek kidolgozására használhatunk fel. A fejlesztő környezet számtalan hasznos kényelmi funkcióval rendelkezik, köztük az IntelliTrace, IntelliSense, vagy a számtalan gyors billentyű kombináció, melyek nagyban segítik a fejlesztést. Az IntelliSense egy kódkiegészítő szolgáltatás, ám ennél sokkal több, hiszen nem csak kódunkat egészíti ki, hanem javaslatokat tesz hibajavításra, változókat egyeztet és követ nyomon, ezzel nagyban megkönnyítve a fejlesztést.16

15

http://www.microsoft.com/hun/visualstudio/

16

http://msdn.microsoft.com/en-us/magazine/cc188694.aspx

- 29 -

Heurisztikus optimalizálás a logisztikában IntelliTrace szolgáltatásnak a tesztelésben és hibakeresésben van nagy szerepe. Segítségével a fordítás folyamán a debuggolás során megállási pontokat állíthatunk be és ezek között tetszőlegesen lépkedhetünk, ellenőrizve, hogy éppen a rendszer változói milyen értékeket vesznek fel, vagy lépésről lépésre elemezhetjük az algoritmusunk futását. Erre új algoritmusok implementálása során gyakran lehet szükség. Az IntelliTrace képes arra, hogy a debuggolás során megállított kódot akár szerkesszük is valós időben, köszönhetően a „just in time” fordításnak.17 Nem csak a tényleges kódolásban kapunk komoly segítséget a Visual Studio-tól, hanem

a

dokumentációt

és

tervezést

is

támogatja

automatikusan

generált

dokumentumokkal, melyet a szövegben elhelyezett commentek alapján szerkeszt össze egy xml fájlba. A Visual Studioval egyszerűen generálhatunk vagy szerkeszthetünk UML vagy akár depedency diagramot.

5.2.2 .NET keretrendszer A Microsoft által készített .NET keretrendszer gyors alkalmazásfejlesztést (RAD), platformfüggetlenséget és hálózati átlátszóságot támogató szoftverfejlesztői platform. A .NET Framework eszköztára a szoftverfejlesztés szinte minden aspektusát lefedi. A Javahoz hasonlóan platform független, virtuális gépen futó keretrendszer. Architektúrája magában foglalja a Common Language Infrastucture (CLI), a Common Languge Specificationt, a Common Type System (CTS), a Common Language Runtime (CLR) és a Common Intermediate Language-t. A .NET Framework alapját a CLI vagyis a Common Language Infrastructure jelenti. Ez azon szabályok együttese, amelyek leírnak egy nyelvfüggetlen fejlesztői és futtatókörnyezetet. A .NET Framework implementációját CLR-nek, Common Language Runtime-nak hívják. A CLI maga is négy fő részre oszlik. A CLS a CLI része. Azokat a szabályokat definiálja, amelyeket a CLI kompatibilis nyelveknek be kell tartania.

17

http://msdn.microsoft.com/en-us/magazine/ee336126.aspx

- 30 -

Heurisztikus optimalizálás a logisztikában A CTS a CLI azon része, amely a típusokat, azok memóriabeli reprezentációját, illetve egymással való kapcsolatukat írja le. A .NET minden nyelve ugyanazt a típusrendszert használja. A CLR vagy a CLI nyelven írt programok betöltéséért és végrehajtásáért felel. Felel továbbá a memóriakezelésért, kivételkezelésért illetve a kódbiztonságért is. A CIL. köztes kód. Minden CLI nyelvben megírt program erre a kódra fordul le. A fordító ezt a kódot külön optimálja a futás felgyorsítása érdekében, így előfordulhat, hogy akár gyorsabb futást érhetünk el mint natív kódra fordulásnál. Ezt a kódot a tényleges futtatáskor az ún. JITter (Just In Time fordító) fordítja le natív kódra, amelyet a processzor már tud kezelni.

5.2.3 Visual C# A Visual C# a .net által támogatott egyik fő nyelv. Robosztus, erősen típusos objektum orientál nyelv, melyet a .net keretrendszerben futó számos alkalmazás készítésére terveztek. Gyorsan fejlődő innovatív nyelv, mely széles osztály skálájával és kényelmi funkcióival lehetővé teszi a gyors softwarefejlesztést. C# az a programozási nyelv, ami a legközvetlenebb módon tükrözi az alatta működő, .NET keretrendszert, A primitív adattípusai objektumok, a .NET típusok megfelelői. Szemétgyűjtést használ, valamint az absztrakcióinak többsége (osztályok, interfészek, delegáltak, kivételek…) a .NET futtatórendszert használja közvetlen módon. A C# úgy nevezett C szerű nyelv. Nagyban hasonlít a C++-ra vagy a Java-ra, mivel ezek a nyelvek az elődei, ám a két nyelv előnyeit egyesíteni próbálja, hátrányaik elhagyása mellett. A lehetőségei közül néhány: A mutatók és a nem ellenőrzött aritmetika csak nem biztonságos módban használható. A legtöbb objektum-hozzáférés csak biztonságos hivatkozásokon keresztül tehető meg, és az aritmetikai műveletek ellenőrzöttek. Az objektumok nem szabadíthatók fel közvetlen módon (csupán dispose() függvény

segítségével

instruálhatjuk

erre

a

GarbageCollectort),

GarbageCollector szabadítja fel őket, mikor már nincs rájuk hivatkozás.

- 31 -

ehelyett

a

Heurisztikus optimalizálás a logisztikában A C# támogatja az öröklődést, akárcsak az objektum orientált nyelvek. A nyelv csak egyszeres öröklődést támogat, tehát egy osztálynak csak egy őse lehet, de egy osztály több interfészt is megvalósíthat. A C# erősen típusos nyelv. Az egyetlen implicit konverzió a biztonságosabb. Széles körben támogatja a generikus programozást, illetve a lambda kifejezések használatát. Tulajdonságok

(Properties)

használhatók,

amelyek

adattagnak

álcázott

metódusok. Ezek a tulajdonságok nagyban megkönnyítik a fejlesztők dolgát, továbbá komoly szintű támogatottsággal rendelkezik. A gyártó cég a Microsoft rengeteg tutorialt és segédletet biztosít, továbbá komoly szakirodalmat. Mindent elkövet a programozási nyelv megismertetésében, a felmerülő problémák megoldásában.18

5.2.4 Programozási technikák A modern software fejlesztésben nélkülözhetetlen a software technológia, mely azon technológiák és vezetési alapelvek összessége, melyek lehetővé teszik számítógépes programok tervszerű gyártását. A fejlesztés egészét tekintve az evolúciós módszert alkalmaztam. Az evolúciós fejlesztői eljárás nagyban hasonlít a tényleges evolúcióhoz. Egy kezdeti vázlatból indul ki, és fokozatos lépések során egyre tökéletesedik időt hagyva az egyeztetésre és tesztelésre. A funkciók fokozatosan kerülnek bele a programba és esetleg egyre finomodnak.

18

http://msdn.microsoft.com/en-us/vstudio/hh341490.aspx

- 32 -


5.4. ábra Evolúciós fejlesztési minta egyszerű sémája

A felhasználó felület tervezésénél az egyszerűség és az átláthatóság volt a fő cél, az alacsony erőforrás igények mellett, ezért mindenhol a lehető legpuritánabb designet és a legegyszerűbb megoldásokat alkalmaztam.

5.2.5 Tesztelés Egy megbízható software fejlesztése során elengedhetetlen a pontos, precíz tesztelés. Jelen esetben SWEBOK19 tesztelési javaslatát alkalmaztam. A tesztelési lépések során(unit teszt, integritás teszt, system teszt, elfogadási teszt) számos kisebb- nagyobb hiba került felfedezésre, melyek javítva lettek. A teszteket a manuálisan saját magam végeztem minden fejlesztési fázis végén. A unit teszt magának a kódnak a működőképességét és helyességét ellenőrzi. A Visual Studio rendelkezik beépített unit tesztekkel, amelyekkel a tesztelést végeztem. Az Integritás teszt magát a helyes működést teszteli, hogy minden funkció helyesen működik-e. A System teszt a rendszer egészét teszteli működés közben, beleértve a hardware követelményeket és a teljesítmény mutatókat.

19

http://en.wikipedia.org/wiki/SWEBOK ISO/IEC TR 19759:2005

- 33 -


5.2.6 Egyéb eszközök Egy fejlesztéshez nem csak kizárólag IDE-kre van szükség, a modern software fejlesztésben éppúgy figyelmet kell szentelni a pontos tervezésre, dokumentációra, illetve az esetleges prezentációra. Új algoritmus bevezetés lévén fontos, hogy az algoritmust megfelelően lépésről lépésre megismerjük. Ebben sokat segítenek a folyamatábrák. A fejlesztés során a Google Chrome –on keresztül elérhető LucidArt nevű programot használtam, mely egy könnyen elérhető és használható diagramkészítő software számos szolgáltatással és felhő alapú tárolási rendszerrel.

5.5. ábra Lucid Art fejlesztés közben

A dokumentáció elkészítését a Visual Studio beépített lehetőségeivel és a Microsoft Office 2010 program családdal végeztem.

5.3 GeneticProgramming.exe általános bemutatása, rendszerterv Az általam készített program, GeneticProgramming.exe leginkább a logisztikai beszerzés területén felmerülő problémák megoldására készült. Fő funkciója a bemenő, felhasználó által megadott adatok alapján a megrendelés optimálása, illetve a megrendelési lehetőségek és az optimálási folyamat elemzése. Erre különböző mérőszámok és grafikonokon keresztül van lehetőség. Az alkalmazás törekszik az egyszerű és tényszerű felhasználói felület kialakítására. A program .Net keretrendszerben - 34 -

Heurisztikus optimalizálás a logisztikában C# nyelven, „Windows Forms”-ban íródott „Visual Studio 2010 Ultimate x86” fejlesztő környezet segítségével, a Szakdolgozatom keretein belül. A program elkészítése során azért lettek ezek a technológiák választva, mert ezek teszik lehetővé a leghatékonyabb és legkönnyebb fejlesztést, nagyon korszerű technológiák, de ugyanakkor visszafelé kompatibilisek az előző keretrendszerekkel, melyre szükség lehet, hiszen nem mindenhol a legmodernebb futtató környezeteket használják. Emiatt tettem félre a WPF technológiákat és használtam Windows Forms-t.

5.6. ábra Kezdő képernyő

A GeneticProgramming.exe beüzemelése nem okozhat semmilyen problémát. Teljesen portable, azaz semmiféle installációra nincs szükség az elindításához. Továbbá nincsen szükség különböző a .net keretrendszer valamely verzióján kívül semmilyen egyéb más keretrendszerre vagy segéd .dll-re. Egyszerűen felmásoljuk az adott gép merevlemezére, vagy külső adattárolóra és elindítjuk. A program minimális rendszerkövetelményei: az alkalmazásnak viszonylag kicsi a gépigénye, ám az általa alkalmazott evolúciós eljárások megnövelhetik ezeket az igényeket és extrém esetekben nagyon megnövekedhet a futási idő. A teszt gép során hasonló nem fordult elő. A pontos minimális gépigény a következő: 800 MHZ processzor, 256MB belső memória, és a tároláshoz szükséges minimális merevlemez kapacitás, továbbá szükség van egy .Net 2.0 vagy ennél magasabb verzió számú .Net keretrendszerre. - 35 -

Heurisztikus optimalizálás a logisztikában Továbbá mivel az alkalmazás rendelkezik grafikus felülettel, ezért szükség van egy ezt megjeleníteni képes monitorra.

5.7. ábra Adatok felvitele

A program működése is igen egyszerű, indulás után a menü rendszer segítségével a felhasználó kiválasztja a kívánt beállításokat, ezek rendszerint külön ablakba történnek pl.: adatok felvétele, stb… majd az optimálást elindítva rövid időn belül megkapja a kívánt információkat, melyeket grafikonok és különböző mérőszámok pl.: minimális ár, átlagár stb… kiértékelhet.

- 36 -


5.8. ábra Egy Optimálási folyamat végeredménye

A program teljességében egy felhasználós rendszer, így nincs benne authentikáció és jogosultságkezelés. A felhasználásra nincsenek korlátozási szabályok, bárki, aki rendelkezik a programmal, tetszése szerint bármikor használhatja a teljes funkcionalitás készletét. Az

alkalmazás

teljesen

triviális,

nincs

szükség

semmilyen

speciális

számítástechnikai ismeretre az üzemeltetéséhez. Minden egyértelműen jól érhető módon fel van tüntetve, az eredményeket és minden adatot próbál vizuálisan is, grafikonok segítségével reprezentálni. Az eredmények megfelelő kiértékeléséhez azonban lehet, hogy szüksége lesz a felhasználónak minimális matematikai, logisztikai vagy műszaki ismeretekre. A program teljesítménye eléggé változó lehet és erősen problémafüggő a választott optimálási eljárás miatt. A minimális rendszerkövetelmény, melyet javarész a futtatókörnyezet és az eredményes futtatás kíván, 800MHZ-es CPU, 256MB belső memória, és a tároláshoz szükséges merevlemez kapacitás. Az evolúciós algoritmusok gépigénye igen magasra rúghat, ezért mindenféleképpen körültekintően kell megadni a bemenő adatokat és alkalmazni a programba beépített esetleges korlátozásokat.

5.4 Diagramok A fejlesztéshez kötődő alábbi diagramok a Visual Studio generálta. - 37 -

Heurisztikus optimalizálás a logisztikában Az osztály diagram az UML szabvány család egyik legtöbbet használt diagram típusa. Fő feladata az osztályok, azok tagjai illetve az osztályok kapcsolatainak ábrázolása. Tulajdonképpen ez a rendszer statikus modelljének ábrázolása, melyeket különböző absztrakciós szinteken valósíthatunk meg. A különböző absztrakciós szinteket a fejlesztés különböző fázisaiban használjuk. A absztrakciós szintek az analízis elemzés, a tervezés és a megvalósítás. Analízis elemzés absztrakciós szinten az osztályok az alkalmazási szakterület fogalmait reprezentálják. Cél a megértés, számos részlet hiányzik, ezen a szinten implementáció még nem történhet. Tervezés ezen az absztrakciós szinten bővebb reprezentáció történik. Az elemzés során feltárt új részletek kerülnek bele. Bővebb információkat, nem szakterületi osztályokat és implementációs részeket is tartalmaz. Megvalósítás ez a teljes reprezentáció, itt minden részletet tartalmaz a diagramunk, melyek segítségével az választott nyelv eszköztárával leképezhető a programunk. Ebben a fázisban akár automatikusan is generálhatjuk a kódunk a diagramból a megfelelő eszközökkel.

5.9. ábra Osztály Diagram zárt alakban

- 38 -


5.10. ábra Teljes Class Diagram

Depedency diagram vagy függőségi diagram. A függőségi diagram lényegében egy irányított gráf, mely a gráf csúcspontjai között lévő függőségeket reprezentálja a gráf éleivel.

- 39 -


5.11. ábra Alap Dependency diagram

5.12. ábra Depedency diagram egy másik nézete

- 40 -


5.13. ábra Individual osztály depedency diagramja

5.14. ábra Teljes Depedency diagram

5.5 A „genetikus programozás” implementálása A „genetikus programozás” alkalmazás során az egyik legkritikusabb feladat az optimálni kívánt rendszer leképzése az algoritmusunk számára. Ez számos problémát vet fel. Első és legfontosabb feladat magának az optimalizálandó paramétereknek a megfelelő leképzése génekre. Továbbá nagyon fontos az egyedek, és génjeik kiértékeléséhez - 41 -

Heurisztikus optimalizálás a logisztikában szükséges megfelelő fitnesz függvény választása, és az esetleges erőforrás igény megugrást elkerülendő érdemes jó büntető függvényeket is választani, melyek semmiféleképen se gátolja az algoritmus működését vagy esetleges korai leállást. A GeneticProgramming.exe esetében modellezni kívánt rendszer egy beszállítási megrendelés. Ezt a sokváltozós rendszert kell optimálni, szerencsére hiába a sok paraméter, a rendszer könnyen modellezhető, lévén a darabszámok, és árak jól reprezentálhatóak egyszerű számokkal, valamint fitnesz

és büntető függvényeket is

könnyen választhatunk hozzájuk. A számokat pedig a jobb felhasználhatóság és tárolás szempontjából egy egyszerű függvényhívással átalakíthatjuk és tárolhatjuk binárisan.

5.5.1 Paraméterek Jelen esetben a bemenő paraméterek mind egész vagy törtszámok, melyek darabszámokat, árakat, költségeket és százalékokat jelölnek. Az alkalmazásban ezeket az adott névvel ellátott beviteli mezőkben egy külön ablakban adhatjuk meg. Ezek név szerint: Szállítási költség (TransportPrice): a szállítási költség megmutatja, hogy egy szállító eszköz egyszeri útja mennyi költséggel jár. Ez a költség független a szállító jármű fajtájától és az általa szállított árutól. Alapból ezt az értéket Forint/Út ként értjük, de ez természetesen bármely más pénznemben is érthető. Ezt pozitív egész számként kell megadni. A programon belül a TransportPrice nevű int típusú publikus tulajdonság reprezentálja. Szállítási kapacitás (TransportCapacity): a szállítási kapacitás megmutatja, hogy egy úton egy tetszőleges szállítóeszköz hány darabárut képes szállítani. Egy úton, egy egységnyi „szállítási költség” kifizetésével maximálisan ennyi árut lehet beszállítani. Alapból ezt Út/Darabszám ként értelmezi az alkalmazás, ez azonban természetesen akár súlyként is érthető. Ezt pozitív egész számként kell megadni. A programon belül a TransportPrice nevű int típusú publikus tulajdonság reprezentálja. Fajlagos tárolási költség (SpecifiedStoragePrice): a fajlagos tárolási költség megmutatja, hogy egy darab áru tárolása mennyi költséggel jár, ez egy darabra vonatkoztatott fajlagos költség, tehát számolása: tárolási költségek/darabszám. Alapból ez Ft/Darabszám ként értelmezi a program, de természetes bármely pénznemként vagy akár

- 42 -

Heurisztikus optimalizálás a logisztikában Ft/Súlyként is meg lehet adni. Ezt a programon belül egy SpecifiedStoragePrice nevű int típusú tulajdonság reprezentálja. Alapár (BasicPrice): az alapár megmutatja, hogy a termék vásárlása során mennyi az az összeg, amiért megkapunk egy darabárut, ez az ár nagyobb rendelés esetén változhat. Ez alapesetben Ft/Db-ként értendő, de természetesen bármely más pénzformátummal is működik. Az alkalmazásban ez a BasicPrice nevű int típusú tulajdonságként van reprezentálva. Hány darabonként csökken az ár (DecreaesePricePiece): a hány darabonként csökken az ár egy lényegesen hosszú elnevezése ennek a bemenő paraméternek és egyben teljesen le is írja azt. Ez a paraméter megmutatja, hogy a rendelés növelése során hány darabbal kell többet rendelni ahhoz, hogy csökkenjen az ár. Ezt egész számként kell megadni és darabszámot reprezentál. Az alkalmazáson belül ezt a DecrasePricePiece nevű int típusú tulajdonság mutatja. Csökkenés (DecreaesePricePercent): a csökkenés bemenő paraméter megmutatja, hogy ha a rendelés darabszámának növelésével csökken ár, az százalékosan mennyivel csökken. Ezt a programban többféleképpen is megadhatjuk: százalékos formában, ekkor egész számként kell megadni, vagy tizedes tört alakban, ekkor 0,01 tizedes tört formában kell megadni a csökkenés mértékét. A programon belül ez egy DecreasePricePercent nevű double lebegőpontos tulajdonságként van implementálva.

5.5.1.1 Egyéb paraméterek A programban lehetőség van egyéb paraméterek megadására. Ezek magát a program futását szabályozzák és javarészt az extrém erőforrás igények megugrását hivatottak meggátolni. Használatuk opcionális, de nagyban növelik a hatékonyságot, és igen ajánlott a használatuk. Elvárt optimum (ExpectedOptimum): az elvárt optimum egy olyan paraméter mellyel megadhatunk egy általunk már elfogadhatónak tartott optimumot, melyet elérve az optimálási folyamat leáll. Ezt egy egész számként kell megadni és a programon belül egy ExpectedOptimum nevű int tulajdonságban van tárolva. Maximális generáció (MaximumGeneration): a maximális generáció megmutatja, hogy az optimálási folyamat során maximum hány generációt engedjünk létrehozni. Ezt - 43 -

Heurisztikus optimalizálás a logisztikában egy egész számként adhatjuk meg, a programban pedig egy MaximumGeneration nevű int tulajdonság reprezentálja.

5.5.2 Az adatok felvitele és feldolgozása A bemenő adatok feldolgozásáért a SizeDialog osztály felelős. Ez egy egyszerű osztály, a bemenő adatok ideiglenes tárolására és kényelmes felvitelére szolgál. Rendelkezik egy egyszerű „Form”-mal, melyen felvihetjük az adatokat.

5.15. ábra "SizeDialog ablak"

5.5.3 Az egyed implementálása, az Individual osztály A genetikus programozás fő alapegysége az egyed, a programban ezt az Individual osztály reprezentálja. A programban az egyed számos tulajdonsággal rendelkezik, melyek javarészét a bemenő paraméterek adják, de rendelkeznek számolt adattagokkal és a szaporításhoz szükséges adattagokkal.

5.5.3.1 Az Individual osztály adattagjai: TransportPrice: bemenő paraméter int típusú publikus tulajdonság, mely a szállítási költséget reprezentálja. TransportCapacity: bemenő paraméter int típusú publikus tulajdonság, mely a szállítási kapacitást reprezentálja. SpecifiedStoragePrice: bemenő paraméter int típusú publikus tulajdonság, mely az egy

árura

vonatkoztatott

fajlagos

- 44 -

tárolási

költséget

reprezentálja.

Heurisztikus optimalizálás a logisztikában BasicPrice: bemenő paraméter int típusú publikus tulajdonság, mely egy áru alap darab árát reprezentálja DecreasePricePiece: bemenő paraméter int típusú publikus tulajdonság, mely azt hivatott reprezentálni, hogy hány darab vásárlása után csökken az ár. DecreasePricePercent: bemenő paraméter double típusú publikus tulajdonsá,g mely azt hivatott reprezentálni, hogy ha csökken az ár a darabszám miatt, az mennyivel csökken. GenX és GenY: 10 elemű bool tömbök melyek az egyedeket reprezentálják, és ezek segítségével hozhatunk létre új egyre optimálisabb egyedeket. Ezek az adattagok a kezdeti generációban teljesen random szerűen épülnek fel, majd következő generációkban pedig az előző generációk tagjaiból épülnek fel valamely módon. Ezek a tömbök kettes számrendszerben reprezentálnak egy számot. Piece: int típusú publikus tulajdonság mely a GenX és GenY génből a PieceFunction metódus segítségével számolódik úgy, hogy a PieceFunction a GenX és GenY-ből képez egy 20 helyi értékű kettes számrendszerbeli számot és ezt váltja vissza tízes számrendszerbe, és ez a szám lesz a Piece értéke. Ez reprezentálja, hogy hány darabot rendelnék, ha az adott Individual példány lenne az optimális. Fitnesz: int típusú publikus tulajdonság, mely megmutatja, hogy az aktuális egyed mennyire „jó”, ez nagyon fontos az optimálás fő feladata, a konkrét eredményt ez fogja adni. Konkréten egy fajlagos beszerzési költséget takar, mely megmutatja, hogy egy darabra vonatkoztatva mennyi lesz a beszerzési költség, alap értelmezettként Forint/Db, de természetesen bármely más egységben is felfoghatja az elemző. A fitnesz érték matematikai számítása a következő:

5.16. ábra Fitnesz érték számítása

Ezek többsége bemenő adat, kivéve a Darab és az Ár. Ezeket a következő módon számoljuk:

- 45 -


5.17. ábra Darab érték számítása

5.18. ábra A Darabszám függvényében meghatározott ár, kamatos kamat számítás

Ezeket az adatokat az Individual osztály egyik konstruktorával állíthatjuk be a megfelelő konstruktor meghívásával minden érték vagy konstruktor paramétere szerint állítódik, vagy ugyanitt számolódik ki.

5.5.3.2 Az Individual osztály metódusai Az Individual osztály három konstruktorral rendelkezik, attól függően, hogy milyen feltételek közt, a program melyik életszakaszában akarjuk az értékeket beállítani. Az első konstruktor 8 paraméteres, mellyel az osztály összes adattagját beállíthatjuk az új egyed létrehozásakor. Rendelkezik egy egyparaméteres konstruktorral, mellyel primitív, egyszerű egyedeket hozhatunk létre és csak a fitnesz tagját tudjuk létre hozni. Továbbá rendelkezik az osztály a default, paraméter nélküli konstruktorral. PieceFunction: Statikus publikus függvény két bool tömb paraméterrel, visszatérési értéke egy int szám-. Ezzel a funkcióval válthatjuk át a GenX és GenY bool tömböket darabszámra. A metódus lényegében összerakja a két bool tömböt, és azt mint egy 20 hosszúságú kettes számrendszerbeli számot átváltja tízes számrendszerbeli számmá a fenti matematikai képlet alapján. Ezt a számot adja visszatérési értékként. Ez a függvény kizárólag a konstruktoron belül hívódik meg. Mutation: publikus visszatérési érték nélküli egy int paraméterrel rendelkező függvény. Ez a függvény hivatott a mutáció operátor szerepét ellátni. Működése egyszerű: meghívjuk egy Individual példányra és a paraméterként kapott darabszámú gént teljesen véletlenszerűen invertálja. Többek között ezzel a függvénnyel lehet új generációkat létrehozni, ezért az optimálási folyamat fontos része és minden új generáció létrehozásakor kerül használatra. - 46 -

Heurisztikus optimalizálás a logisztikában GenerateRandomIndividual: publikus Individual visszatérési értékű függvény, mely a kezdeti generáció tagjainak a létrehozására szolgál, létrehoz és visszatérési értékként vissza egy Individual példányt, melynek az adatait úgy adja meg, hogy a GenX és GenY pseudo random generált véletlen tömbök, a többi adata pedig a felhasználó által megadott paraméterek, illetve az ezekből számolt értékek. AverageFitness: Egyszerű publikus függvény int visszatérési értékkel, mely megmutatja, hogy egy adott generációban mennyi a tagok átlagos fitnesz értéke, ennek az optimum meghatározás és elemzés során van fontos szerepe minden új generáció létre jöttekor lefut. AveragePiece: Egyszerű publikus függvény int visszatérési értékkel, mely megmutatja, hogy egy adott generációban mennyi a tagok átlagos „Piece”, azaz darabszám értéke. Ennek az optimum meghatározás és elemzés során van fontos szerepe, minden új generáció létrejöttekor lefut. AveragePrice: Egyszerű publikus függvény int visszatérési értékkel, mely megmutatja, hogy egy adott generációban mennyi a tagok átlagos „Price”, azaz árértéke. Ennek az optimum meghatározás és elemzés során van fontos szerepe, minden új generáció létrejöttekor lefut. MinFitness: Egyszerű publikus függvény int visszatérési értékkel, mely megmutatja, hogy egy adott generációban mennyi a legkisebb fitnesz érték. Ennek az optimum meghatározás és az elemzés során van, fontos szerepe, minden új generáció létre jöttekor lefut. MinPrice: Egyszerű publikus függvény int visszatérési értékkel, mely megmutatja, hogy egy adott generációban mennyi a minimális ár értéke. Ennek az optimum meghatározás és az elemzés során van fontos szerepe, minden új generáció létrejöttekor lefut. Injuction: Az egyed létrehozás egyik fontos operátorának, a keresztezésnek a megvalósítása. Visszatérési értéke egy új Individual, mely két Individual-ból áll elő úgy, hogy véletlenszerűen megkapják vagy egyik vagy másik vagy mind két Individual génjeit, és természetesen ez alapján és a bemenő paraméterek alapján beállítódnak az adattagjai is. A géneket úgy választja ki, hogy veszi az összes lehetséges X és Y gén kombinációkat és

- 47 -

Heurisztikus optimalizálás a logisztikában ezek közül egy pseudo random generált random szám segítségével kiválaszt egy lehetőséget és aszerint határozza meg az új géneket. GenerateTemporalyGeneration: két generáció közti úgynevezett köztes generáció létrehozására szolgál, részletesebben a metódus pontos működés 3.2.4-es fejezetben található az optimálási folyamat bemutatása részeként. CompareTo: Az aktuális feladathoz felüldefiniált C# függvén,y mely két Individual példány összehasonlítására alkalmas: ezt úgy teszi, hogy az „nagyobb” amelyiknek kisebb a fitness értéke.

5.5.4 Felhasználó felület és osztályai A felhasználói felület az egyszerűségre és átláthatóságra törekszik, fő funkciója, hogy elősegítse a program megértését és használatát. Mellőz mindenféle komolyabb grafikai látványvilágot, animációkat. A felhasználói felület megtekinthető az 5.7 5.8 és 5.14-es ábrákon. Egyszerű Forms-okat használ. A Forms-ok a Windows.Forms névtérben találhatók. Egy Forms egy felhasználói felületből Form.Designer.cs Form.resx és egy mögöttes kódból Form.cs –ből áll. Ez a három reprezentál egy ablakot, melynek a felhasználó által látható felületén az 5.2 ábrán látható designer módban tudjuk egyszerű módon szerkeszteni. A mögöttes tartalmat pedig a Form.cs-ben írhatjuk meg, ahogy az 5.3-as ábrán láthatjuk

5.5.4.1 Form1 A Form1 a program fő ablaka egyben ez a kezdő képernyő is(5.6 ábra). Egy Az optimális folyamat megkezdéséhez először a megfelelő kezdeti beállításokat kell elvégezni, megadni a szükséges bemenő menürendszerből. Egy fő panelből áll. A menürendszerbe navigálva irányíthatjuk a programunkat egér segítségével. A megfelelő gombokat megnyomva meghívhatjuk a mögöttes funkciót, amely a Form1.cs-ben van implementálva. Form1. Menü rendszerébe a következő menüket találhatjuk két fő menüben(File és Optimálás). A menürendszer szándékosan puritán, későbbi gyors bővíthetőség érdekében.

- 48 -

Heurisztikus optimalizálás a logisztikában A File-on belül az Adatok felvitele gomb megnyomásával példányosítunk egy SizeDialog (5.4.4.2) osztályt, mely választevékenységet szolgáltatva adatot nyújt a Form1nek. A másik menücsoporton belül pedig az Alap Generáció generálása gombbal hívhatjuk meg az optimálási eljárást. Az optimálás gombbal pedig a Panelen jeleníthetjük meg az optimálásunk eredményeit. Form1.cs itt található a mögöttes kód, melyet a felhasználói felület funkció meghívnak. Csak default konstruktorral rendelkezik. A Form1 osztály ugyanolyan adattagokkal rendelkezik, mint az Indivudal(5.4.3) osztály. Erre azért van szükség, mert innen példányosítjuk az Individual osztály tagjait és a legegyszerűbben így . Továbbá minden gomb rendelkezik az osztályon belül egy eseménykezelő metódussal, mely a gombra való kattintásra, vagy egyéb tevékenységre hívódik meg. Ezek rendszerint az Indivudal osztály metódusait hívják meg, vagy példányosítják az osztályt a megfelelő konstruktor segítségével.

5.5.4.2 SizeDialog Az SizeDialog(5.7 ábra) egy egyszerű form mely az adatok felviteléért felelős. A File menü Adatok felvitele megnyomásakor ugrik fel ez az egyszerű ablak, melyen egyszerű textboxok és két gomb található. A gombokat megnyomva választevékenységet váltunk ki a meghíváskor DialogResult formájában. SizeDialog.cs osztály egy egyszerű osztály, mely adatok szolgáltatására hivatott, csupán egyetlen konstruktora van a default. Csupán a felületinicializáló metódussal rendelkezik és az alábbit tulajdonságokkal: „public int TransportPrice { get { return Int32.Parse(transportPriceTextBox.Text); } } public int TransportCapacity { get { return Int32.Parse(transportCapacityTextBox.Text); } } public int SpecificStoragePrice { get { return Int32.Parse(specificStoragePriceTextBox.Text); } } public int BasicPrice { get { return Int32.Parse(priceTextBox.Text); } } public int ExpectedOptimum { get { return Int32.Parse(expectedOptimumTextBox.Text); } } public int DecreasePricePiece { get { return Int32.Parse(decrasePricePieceTextBox.Text); } } public double DecreasePricePercent { get {

- 49 -

Heurisztikus optimalizálás a logisztikában if (double.Parse(decrasePricePercentTextBox.Text) > 1.0) { double a = double.Parse(decrasePricePercentTextBox.Text); return (1 - double.Parse(decrasePricePercentTextBox.Text) / 100); } else { double b = double.Parse(decrasePricePercentTextBox.Text); return (1 - double.Parse(decrasePricePercentTextBox.Text));

};” Ezek az adattagok is csak arra szolgálnak, hogy a textboxokban szereplő adatokat a szolgáltassák.

5.5.5 Az optimálási folyamat bemutatása Az optimális folyamat megkezdéséhez először a megfelelő kezdeti beállításokat kell elvégezni, megadni a szükséges bemenő adatokat és egyéb beállításokat. Ezután a felhasználó elindíthatja az optimálást, mely remélhetőleg rövid időn belül végbe megy és ki lehet értékelni az adatokat. Az optimálás tényleges megkezdése előtt a program elvégez néhány szükséges lépést: első körben beállítja a bemenő adatokat a mínusz egyedik lépésben úgy, hogy a sizedialogban megadott adatokat átadja a szükséges osztályoknak, majd a nulladik lépésben létre hozza a kezdeti generációt, egy 100 elemű Individual tömbbe létre hoz 100 véletlen Individualt a GenerateRandomIndividual függvény segítségével, és a bemenő adatok alapján kiszámolja a még szükséges információkat. Ezután ellenőrzi az adatokat, hogy egyáltalán érdemes-e vagy szükséges-e a kezdeti nulladik generációtól tovább lépni, ha nem, megáll és kiértékelésre adja a kapott értékeket. Amennyiben a kezdeti nulladik generáció során nem teljesülnek azok a feltételek, hogy a program úgy döntsön, nem érdemes tovább futnia, akkor egy ciklusban elkezdi a tényleges optimálást. A ciklus alapesetben a megadott elvárt optimum elérésig fut, de ezt - 50 -

Heurisztikus optimalizálás a logisztikában lehet korlátozni egy maximális generációszám megadásával. Ha nem adunk meg ilyen számot, a program akkor is megáll, de ez rengeteg generációt jelent, továbbá megadható még egy javulási arányon alapuló büntető függvény, mely kilép a programból, ha az utolsó generációk átlag fitnesz értéke nem javult. A nulladik lépés után minden iterációs lépés során létrehoz egy új generációt, az új generáció lépése két lépésben történik. Először létrejön egy sokkal nagyobb úgy nevezett ideiglenes generáció (TemporalyGeneration), mely akár sokszorta nagyobb is lehet, mint az alapgeneráció. A TempolaryGeneration úgy áll elő, hogy vesszük a húsz legjobb fitneszű egyedet az eredeti generációból, ennek a húsz elemnek a teljesen véletlen mutációját, mely nullától tíz gént változtathat meg teljesen véletlenül. Ezután veszünk ötven elemet, melyet keresztezés segítségével állítunk elő oly módon, hogy az i és az i+1edik elem keresztezéséből áll elő, továbbá veszünk további ötven elemet, amelyet szintén keresztezés útján állítunk elő úgy, hogy a generáció két véletlenül választott tagját keresztezzük. Továbbá átkerülnek az ideiglenes generációba az átalagos fitnesz értékűnél jobb fitnesz értékű elemek. Miután létrejött az ideiglenes generáció, az új generációba az ideiglenes generáció legjobb száz fitnesz értékű egyede kerül át. Az új generáció létrejötte után kiértékelésre kerül az új generáció, átlagos fitnesz érték, darabszám, ár, továbbá minimális fitnesz érték, darabszám, ár. Ezek az értékek letárolódnak, hogy a kiértékelés során megvizsgálhassuk, mely generáció során hogy alakultak ezek az értékek. Ha ezek az értékek kielégítik valamely megállási feltételt, akkor a program megáll és megadja a gyűjtött adatokat, ha nem, akkor az eljárás a következő iterációs lépésbe lép és az új generáció lesz, az alapgeneráció melyből folytatja az optimálást.

- 51 -


Összefoglalás Szakdolgozatom témája a heurisztikus optimalizálás a logisztikában. Mikor hozzákezdtem a szakdolgozatom elkészítéshez, számomra új területekkel kellett megismerkednem, melyekről mindaddig nem sok tudással rendelkeztem. Munkám során ezekben elmélyedtem, és lehetőségeimhez mérten sikerült elsajátítanom megfelelő tudást a felmerülő problémák megoldásához. A program elkészültéig hosszú út vezetett, mely során mélyebb ismeretekre tettem szert az optimálás, a logisztika, az algoritmustervezés és implementálás terültén. A software fejlesztésre is másként tekintek ezek után. Elmondhatom, hogy szakmailag számos tapasztalattal gazdagodtam, melyet későbbi munkám során hasznosítani tudok majd. A szakdolgozatom elkészítése során az alap problémafelvetés a beszerzés optimalizálása volt. Ez egy komplex sokváltozós rendszer, így a hagyományos optimálási megoldások szóba se jöhettek. Ezért a heurisztikus algoritmusokat választottam mint az optimálás eszközét. A generikus algoritmust implementáltam munkám során .net keretrendszerbe visual C# nyelven. A kész program képes a bemenő adatok alapján a beszerzési költségek optimálására. A jelenlegi programot mindenféleképpen szeretném továbbfejleszteni, mind a jelenlegi vonalon továbbhaladva, meglévő funkciót bővítve pontosítani. Esetleg a későbbiekben integrálni egy komplex, logisztikát támogató rendszerbe, melynek egyik modulját képezné. Ezeket akár MSc-s diplomamunka keretében.

- 52 -


Irodalomjegyzék 1

dr. Cselényi József – dr. Illés Béla: Anyagáramlási rendszerek tervezése és irányítása

4

2

dr. Prezenszki József: Logisztika I.

4

3

Szegedi Zoltán – Prezenszki József: Logisztika-menedzsment

5

4

Jármai,K. - Iványi,M.: Gazdaságos fémszerkezetek analízise és méretezése. Műegyetemi Kiadó, Budapest,

2001, 230 old. 5

12

Bianchi, Leonora; Marco Dorigo, Luca Maria Gambardella, and Walter J. Gutjahr (2009). "A survey on

metaheuristics for stochastic combinatorial optimization". Natural Computing: an international journal 8 (2): 239–287. doi:10.1007/s11047-008-9098-4 6

15

Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on

Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989)

16

7

17

8

Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. ISBN 0-262-04219-3 http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Aco_branches.svg/400px-

Aco_branches.svg.png 9

17

K.N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal

functions with collective robotics applications. Multi-agent and Grid Systems,2(3):209- 222. 10

18

Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.12. Simulated Annealing

Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8

18

11

19

12

Barricelli, N.A. (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68. Fogel, L.; Owens, A.J.; Walsh, M.J. (1966). Artificial Intelligence through Simulated Evolution.

Wiley. ISBN 0-471-26516-0. 13

19

Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0-

262-08213-6. 14

19

Smith, S.F. (1980). A Learning System Based on Genetic Adaptive Algorithms (PhD Thesis). University of

Pittsburgh.

19

15

http://www.microsoft.com/hun/visualstudio/

29

16

http://msdn.microsoft.com/en-us/magazine/cc188694.aspx

29

- 53 -


Ábrajegyzék 1.1. ábra Logisztika által integrált területek

-6-

1.2.1. ábra Optimálás egyszerű logikai struktúrája

- 13 -

2.3.1. ábra Heurisztikus Algoritmusok egy csoportosítása.

- 16 -

2.3.2. ábra Ant colony működése 2.3 ábra Ant colony működése

- 17 -

2.3.3. ábra Glow worm működése

- 18 -

4.1. ábra Genetikus Algoritmus működés

- 23 -

5.1. ábra A "Visual Stuido New Project" menüje

- 28 -

5.2. ábra Visual Stuido felhasználói felület tervezés közben

- 28 -

5.3. ábra Visual Studio fejlesztés közben

- 29 -

5.4. ábra Evolúciós fejlesztési minta egyszerű sémája

- 33 -

5.5. ábra Lucid Art fejlesztés közben

- 34 -

5.6. ábra Kezdő képernyő

- 35 -

5.7. ábra Adatok felvitele

- 36 -

5.8. ábra Egy Optimálási folyamat végeredménye

- 37 -

5.9. ábra Osztály Diagram zárt alakban

- 38 -

5.10. ábra Teljes Class Diagram

- 39 -

5.11. ábra Alap Dependency diagram

- 40 -

5.12. ábra Depedency diagram egy másik nézete

- 40 -

5.13. ábra Individual osztály depedency diagramja

- 41 -

5.14. ábra Teljes Depedency diagram

- 41 -

5.15. ábra "SizeDialog ablak"

- 44 -

5.16. ábra Fitnesz érték számítása

- 45 - 54 -

Heurisztikus optimalizálás a logisztikában 5.17. ábra Darab érték számítása

- 46 -

5.18. ábra A Darabszám függvényében meghatározott ár, kamatos kamat számítás

- 46 -

- 55 -


SUMMARY The main theme as well as the title of my thesis is Metaheuristic Optimalization in Logistics. Before I started writing my thesis, it was necessary for me to familiarize myself with some fields of logistics and software developing, which were completely new to me. In the course of my work I gained considerable knowledge and I managed to solve all the problems that occurred. It required great perseverance to complete the program but in this way I have gained a deep insight into the fields of logistics, algorithm planning and implementation. Furthermore , my opinion about software developing has also changed.I am convinced that I can use the gained experience in my future work. During my work the base problem was the optimalizaton of supply. This is a complex system with several variables, so the traditional optimalization methods do not work. I have chosen the metaheuristic algorithms to optimalize the system. I implement the genetic algorithm during my work with .net framework in visual C# language. The program can optimalize the supply cost with the input variables. I intend to develop the current version of my program in the future. I want to expand the current functions and also add new functions. In the future I may integrate it into a complex system, which can support logistics.These developments may serve as the base of my MSc thesis.

- 56 -


KÖSZÖNETNYILVÁNÍTÁS Ezúton

szeretnék

köszönetet

mondani

belső

konzulensemnek

és

tervezésvezetőmnek Dr. Bányai Tamásnak (egyetemi docens, ME-Anyagmozgatási és Logisztikai Tanszék) a dolgozat megírásához nyújtott hasznos tanácsaiért, támogatásáért, mellyel nagyban segítette dolgozatom elkészültét. Köszönettel tartozom az Anyagmozgatási és Logisztika tanszék minden dolgozójának a sokéves szakmai felkészítésért, támogatásért és segítségnyújtásért. Továbbá köszönetet mondanék mindazon oktatóknak, akik szakmai vagy egyéb hasznos tanáccsal segítették dolgozatom létrejöttét, támogattak az évek során, illetve Tankör- és Évfolyamtársaimnak az együtt töltött évekért. Utoljára, de nem utolsósorban köszönettel tartozom Szüleimnek támogatásukért, belém vetett hitükért.

- 57 -

Szakdolgozat. Heurisztikus optimalizálás a logisztikában. Anyagmozgatási és Logisztikai tanszék

Recommend Documents