HÁLÓZATSZERŰEN MŰKÖDŐ LOGISZTIKÁVAL INTEGRÁLT TERMELÉSÜTEMEZÉS MEGOLDÁSA GENETIKUS ALGORITMUS ALKALMAZÁSÁVAL
OLÁH Béla
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A TERMELÉSÜTEMEZÉS MEGFOGALMAZÁSA
gép
Flow shop: adott n számú termék, melyeken m számú különböző munkafolyamatot kell elvégezni. A technológiai útvonal (az összes termékre azonos), és a műveleti idők adottak. Meg kell határozni a termékek sorrendjét a gépeken, mely C
A
célfüggvények
állásidő p1=4
p2=10
p3=6
p4=7
p5=1
holtidő
5 p1=9
B 4
p2=3 1
13
p4=6
6 p2=10
p3=2
1
16
p4=14
4
p5=9
5 p1=7
D
p5=8
3
p1=3
C
p3=7
p2=7
p3=5
4
p4=4 8
átfutási idő = 67
p5=11 5
idő
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
MEGOLDÁSI VÁLTOZATOK KIÉRTÉKELÉSE reprezentálás
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
HOLTIDŐK ÉS ÁLLÁSIDŐK KIÉRTÉKELÉSE
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
SORREND-MEGHATÁROZÁS MÓDSZEREI NP-teljes probléma
heurisztikus eljárások
Az utóbbi évtizedekben más megközelítési módok (összefoglaló néven természetes számítások) is elterjedtek: Neurális hálózatok (NN), Genetikus algoritmusok (GA), Membrán-rendszerek (PS), Molekuláris számítások (MC), Kvantumszámítógépek (QC).
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A GENETIKUS ALGORITMUS FOLYAMATÁBRÁJA
Induló populáció generálása
Kiértékelő függvény
További optimalizálás igen
nem
Legjobb egyed eredmény
Start
Új populáció generálása alkalmazott kódolás, egyed, populáció, alkalmasság
Mutáció
Kiválasztás
Klónozás
Keresztezés
A GA lényege, hogy rendelkezik a lehetséges megoldások egy populációjával, a populáción értelmezett a kiválasztási folyamat - mely az egyedek alkalmasságán alapul - és értelmezett néhány genetikus operátor.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
FELHASZNÁLÓI FELÜLET
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A GENETIKUS ALGORITMUS ÁLTAL SZOLGÁLTATOTT HOLTIDŐÉRTÉKEK AZ ITERÁCIÓSZÁM FÜGGVÉNYÉBEN
4550 4450 4350 4250 4150 4050
1000
750
600
500
425
350
300
250
200
175
150
125
100
75
50
25
10
5
3950
Ugyanazon (20 gépes, 25 termékes) feladatra 30-szor lefuttatott genetikus algoritmus által szolgáltatott holtidő értékek átlagai a populáció méretének (150) változatlanul hagyása mellett a legjobb kiválasztási stratégiát, valamint 4%-os klónozást, 16%-os mutációt és 80%-os keresztezést használva.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A GENETIKUS ALGORITMUS ÁLTAL SZOLGÁLTATOTT HOLTIDŐÉRTÉKEK A POPULÁCIÓMÉRET FÜGGVÉNYÉBEN
4325 4275
holtidő
4225 4175 4125 4075 4025 3975 0
250
500
750
1000
1250
1500
populáció-méret
Ugyanarra a 25 termékes feladatra elvégezve a vizsgálatot 30 futtatás utáni holtidő értékek átlagai a populáció méretének függvényében az iteráció-szám változatlanul hagyása mellett a korábbi beállítási lehetőségeket megtartva, hasonló jellegű görbét adtak.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A KIVÁLASZTÁSI STRATÉGIÁK ÖSSZEHASONLÍTÁSA A HOLTIDŐ ÉS ITERÁCIÓ-SZÁM FÜGGVÉNYÉBEN 4550 4450 holtidő
4350 random 4250 4150 rulett
best
4050 3950 0
100
200
300
400
500
600
700
800
900
1000
iterációszám
Megállapítható, hogy a véletlen kiválasztás adja a leggyengébb eredményeket, míg a rulett-kerék szelekció kicsivel (közel 1 %-kal) mindig jobb megoldásokat szolgáltat ugyanannyi iterációt követően. Kijelenthető, hogy a best kiválasztódás eredményezi a legjobb megoldásokat a leggyorsabban.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
HOLTIDŐ-ÉRTÉKEK A POPULÁCIÓMÉRET ÉS TERMÉKSZÁM
FÜGGVÉNYÉBEN AZONOS FUTÁSIDŐ ALATT 7025 6670 6315 5960 job99
5605 idle time
Ugyanazon 20 gépes feladatra a GA által 30 futtatás után szolgáltatott holtidőértékek átlagai a populáció méretének és a termékszám függvényében ugyanakkora futásidő alatt a legjobb kiválasztási stratégiát, 4%-os klónozást, 16%-os mutációt és 80%-os keresztezést használva. Az azonos futásidő úgy érhető el, hogy az alkalmazott populáció mérete és az iteráció szorzata állandó (ez esetben 15.000), azaz ugyanannyi individuumot vonok be a vizsgálatba. Látható – kék vonallal be is jelölve –, hogy a feladat méreteinek növekedésével nem a várt növekedés, hanem csökkenés mutatkozik az optimális populációnagyságra vonatkozóan ugyanakkora futásidőt feltételezve.
job75 job50
5250
job25 job10
4895 4540 4185 3830 3475 1500 1000 750 500 375 250 150 100 population size
75
50
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A KLÓNOZÁS ÉS A MUTÁCIÓ ARÁNYÁNAK VIZSGÁLATA A HOLTIDŐK SZEMPONTJÁBÓL
4400 4300 4200 4100 4000 3900 3800 1
2
4
5 10 15 20 25 30 33 40 50 60 75 80 85 90 95
A genetikus algoritmus a klónozás operátor 10 és 60 % közötti értéke esetén eredményezte a legkisebb holtidő értékeket csak mutációt használva. A minimumot a 30 %-os másolás (és ezáltal 70 %-os mutáció) jelentette.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A KLÓNOZÁS ÉS A KERESZTEZÉS ARÁNYÁNAK VIZSGÁLATA A HOLTIDŐ-ÉRTÉKEK FÜGGVÉNYÉBEN
4500 4450
gépi holtidők
4400 4350 4300 4250 4200 4150 4100 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
keresztezés [%]
A genetikus algoritmus a klónozás operátor 25 és 85 % közötti értéke esetén eredményezte a legkisebb holtidő értékeket csak keresztezést használva. A minimumot ugyan a 75 %-os másolás (és ezáltal 25 %-os keresztezés) jelentette.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A MUTÁCIÓ ÉS A KERESZTEZÉS ARÁNYÁNAK VIZSGÁLATA 10%-OS KLÓNOZÁSNÁL A HOLTIDŐK SZEMPONTJÁBÓL
4200 4175 4150 4125 4100 4075 4050 4025 0
1
2
4
5 10 15 20 23 25 30 33 40 50 57 60 65 67 70 75 80 85 86 88 89 90
A mutáció arányának 57 %-ig történő növelésével folyamatosan javulnak a GA által szolgáltatott holtidő-értékek, ezután viszont folyamatos, igaz csekély mértékű gyengülés következik be.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
KERESZTEZŐ OPERÁTOROK ÉRZÉKENYSÉGVIZSGÁLATA A GA által szolgáltatott holtidő-értékek vegyes, csak Cycle-Crossover (CX) és csak OrderCrossover (OX) keresztező operátorok használatakor. 4500 4450
gépi holtidők
4400 4350 4300 4250 4200 4150 4100 99 98 96
4500
4500
4450
4450
4400
4400
4350 4300 4250
95 90 85 80 75 70 67 60 50
40 33 25 20 15 10
5
4
2
5
4
2
keresztezés [%]
gépi holtidők
gépi holtidők
A CX operátor átlag 2%-kal gyengébb eredményeket szolgáltat a mindkét szisztémát egyformán használó keresztezéshez képest. Az OX keresztező operátor átlag 1,1%-kal még a CX keresztezésnél is rosszabb. Meglepő, hogy amikor fele-fele arányban van alkalmazva a két operátor az átlagos fitnesz-érték mégis jobban közelíti az optimális értéket, mint külön-külön bármelyiknél. Konkrét feladatnál tehát érdemes a keresztező eljárások széles skáláját használni.
4350 4300 4250
4200
4200
4150
4150 4100
4100 99 98 96 95 90
85 80
75 70
67 60 50
40 33
keresztezés [%]
25 20 15 10
5
4
2
99 98 96 95 90 85 80 75 70 67
60 50 40 33 25
keresztezés [%]
20 15 10
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
MUTÁCIÓ OPERÁTOROK ÉRZÉKENYSÉGVIZSGÁLATA A GA által szolgáltatott holtidő-értékek különböző mutáció operátorok használata esetén 4675 4600 gépi holtidők
4525 vegyes
4450
simple inversion
4375
reciprocal exchange
4300
swap
4225
displacement
4150 4075 4000 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10 5 4 2 mutáció [%] A négy mutáció operátor közül kettő sokkal jobb eredményeket szolgáltat a másik kettőnél. A legjobb megoldásokat a reciprocal exchange mutáció alkalmazása adja, de alig marad el tőle a simple inversion operátor, ami csak átlag 2,5%-kal generál gyengébb célfüggvény-értékeket. Ezzel szemben a swap mutáció már közel 9,5%-kal rosszabb, mint a reciprocal exchange, míg a displacement operátor több mint 12%-kal, így kijelenthető, hogy ez utóbbi mutáció használata eredményezi a legnagyobb holtidőket. A keresztező operátorok vizsgálatával ellentétben, nem mondható el, hogy a mutációs eljárások együttes alkalmazásakor kapnánk a legjobb eredményeket, bár az operátorokat egyenlő arányban alkalmazó vegyes megoldás grafikonja szinte teljesen egyezik a legkisebb értékeket felvonultató reciprocal exchange mutációéval.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
ÖSSZEHASONLÍTÁS AZ ÁTFUTÁSI IDŐ SZEMPONTJÁBÓL 1600
1500 Genetic
1400
Dannenbring Palmer
1300
Ad hoc
1200
49
46
43
40
37
34
31
28
25
22
19
16
13
10
7
4
1
1100
A Dannenbring és a Palmer módszer közelítése között átlagban (~1345) szinte semmi eltérés sincs. A genetikus algoritmus viszont már az első iterációban az ad hoc sorrend (~1469) eredményeihez közeli értéket produkál, 3-4 iteráció után pedig a heurisztikus módszereknél is jobb megoldást készít, továbbá 100 iteráció befejeztével (~1228) közel 20%-ot javít az ad hoc sorrenden, szemben a többi heurisztikus módszer 8%-val.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A HOLTIDŐK SZEMPONTJÁBÓL
13000 12000 11000
Genetikus Ad hoc
10000
Dannenbring Palmer
9000 8000
19
17
15
13
11
9
7
5
3
1
7000
Ha a gépek holtideje, illetve a termékek állásideje célfüggvények szempontjából hasonlítjuk össze a genetikus algoritmus hatékonyságát a többi heurisztikus módszerrel, még megdöbbentőbb eredményhez jutunk. Ami nem is annyira meglepő, ugyanis jelen heurisztikus módszereket csak az átfutási idő optimalizálására fejlesztették ki. A holtidők minimalizálása tekintetében a Dannenbring és a Palmer módszer átlagban szintén 8%-ot javít az ad hoc sorrenden, de óriási a szórása a két módszernek. A GA viszont több mint 25%-kal jobb az ad hoc sorrendnél 100 iterációt követően.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A TERMÉKEK ÁLLÁSIDEJÉNEK SZEMPONTJÁBÓL 13000 12000 11000 Genetikus 10000
Ad hoc Dannenbring
9000
Palmer 8000 7000
19
17
15
13
11
9
7
5
3
1
6000
A termékek állásidejének optimalizálása esetén még nagyobb az eltérés a genetikus algoritmus javára. A GA közel 35%-kal jobban közelíti az optimális megoldást, mint az ad hoc sorrend! Meglepően jól szerepelnek a heurisztikus módszerek is, a Dannenbring 16%-ot, a Palmer 13%-ot javít az ad hoc sorrend eredményein.
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
ÖSSZEFOGLALÁS • A genetikus algoritmusra és az ismert heurisztikus módszerekre épülő software készítése • A genetikus algoritmus összehasonlító elemzése a heurisztikus módszerekkel logisztikai célfüggvények figyelembevételével • Kiválasztási stratégiák és az operátorok hatékonyságának vizsgálata • A genetikus operátorok arányának optimálása
Továbbfejlesztési lehetőségek ismertetése • A módszer kidolgozása job-shop és open-shop típusú ütemezési feladatokra • A feladat kiterjesztése hálózatszerűen működő termelés esetére • A genetikus algoritmus összehasonlítása más természetes számításon alapuló módszerekkel: – – – –
Ant colony algorithm Megerősítéses tanulás Neurális hálózatok Molekuláris számítások
• Új keresztező és mutáció operátorok megalkotása • stb.
KÖSZÖNÖM A FIGYELMET!
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
A JOB-SHOP ÜTEMEZÉSI FELADAT (JSSP)
A job-shop ütemezési feladatban j munka (job) és m gép (machine) van. Minden egyes munka feladatok halmazából áll, melyek mindegyikét 1. gép különböző gépen kell megmunkálni különböző 2. gép megmunkálási idővel, egy előre megadott munka- 3. gép függő sorrendben.
p1=3
p2=8
p4=5
p4=5
p3=5 p1=1
p6=3
p2=5
p3=4
4. gép
p3=9
p1=6
p5=9
p5=3
p3=8
0
p5=3
p3=1
p6=1
p4=3
p2=10
6. gép
p2=10
p4=5
p6=3
5. gép
p6=10
p5=5
p6=9
p1=7
p3=7
p2=10
p2=4 p5=1
p4=8
p5=4
p6=4
p1=3
p1=6
p4=9
55 idő
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
AZ OPEN-SHOP ÜTEMEZÉSI FELADAT (JSSP) Az open-shop ütemezési feladat (OSSP) hasonló a job-shop problémához, azzal a kivétellel, hogy nincs prioritási sorrendje a műveleteknek egy terméken belül. 1. gép
p2=7
p2=68
p3=1 p2=14 p5=15
p4=13
0
p2=18
p3=74
p3=70
p3=60
3. gép
5. gép
p1=64
p1=66
2. gép
4. gép
p4=54
p5=45
p5=10
p2=69
p4=45
p4=98
p4=76
p5=91
p5=80
p1=31
p1=85
p1=44
p3=90
300 idő
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
HÁLÓZATSZERŰEN MŰKÖDŐ ÖSSZESZERELŐ RENDSZER
beszállítók
alapanyag elosztó raktárak
összeszerelő üzemek
késztermék elosztó raktárak
felhasználók
B1
...
Bi
...
Bx
AER1
...
AERj
...
AERm
Ü1
...
Üλ
...
Ün
KER1
...
KERκ
...
KERr
F1
...
Fµ
...
Fw
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
GA VS. MEGERŐSÍTÉSES TANULÁS (HOLTIDŐK SZEMPONTJÁBÓL) 6000 5500 5000
Boltzmann
4500
GA
4000
Dannenbring Palmer
3500 3000 2500 3 5
7 9 11 13 15 17 19 21 23 25 27 29
Számszerűsítve az eredményeket a genetikus algoritmus átlagban közel 8%-kal eredményezett jobb megoldást, mint a megerősítéses tanulás, de ahogy a 2. ábrán is látható a berajzolt trendfüggvény a termékek számának növekedésével közel exponenciálisan növekszik (25-30 termékes feladatoknál már 10-12 százalék a különbség)! Persze ez nem fokozható a végtelenségig, de az megállapítható, hogy a GA nagyobb termékszám esetében sokkal jobban közelíti az optimális megoldást, mint a megerősítéses tanulás. A genetikus algoritmus általában már a 20. iterációt követően előállt olyan eredménnyel, ami már jobb volt, mint a szimulált hűtéssel kombinált megerősítéses tanulás által adott eredmény.
14 12 10 %
1
Ha a genetikus algoritmus hatékonyságát hasonlítjuk össze a szimulált hűtéssel kombinált megerősítéses tanulás eredményeivel a gépek holtidejének minimalizálása érdekében (30 különböző húszgépes esetben a termékek számát egytől harmincig növelve) azt tapasztalhatjuk, hogy a genetikus algoritmus eleinte azonos eredményt produkál a megerősítéses tanulással (úgy kb. tíztermékes esetig), majd a termékek számának növelésével egyre inkább kiütközik a két módszer közötti különbség természetesen a GA javára.
GA %-os javítása a megerősítéses tanuláshoz képest
8 6 4 2 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 termékek száma
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 A KERESZTEZŐ ÉS MUTÁCIÓ „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán” OPERÁTOROK ISMERTETÉSE
DIA CÍMSOR
TÁMOP-4.2.2.B-15/1/KONV-2015-0015 „Tehetséggondozási kutatóműhelyek fejlesztése a Szolnoki Főiskolán”
