Genetinio algoritmo lyginimas su kitais euristiniais optimizavimo metodais keliaujančio pirklio uždaviniui spręsti

Ištrauka

Genetinio algoritmo lyginimas su kitais euristiniais
optimizavimo metodais keliaujančio pirklio uždaviniui spręsti

Turinys
Įvadas 4
Apibrėžimai 6
1. Euristinių algoritmų literatūros analizė 7
1.1. Keliaujančio pirklio uždavinys 7
1.1.1. Uždavinio formuluotė 7
1.1.2. Sudėtingumas 7
1.2. Genetiniai algoritmai 8
1.2.1. Veikimo principas 8
1.2.2. Populiacijos dydis 8
1.2.3. Tinkamumo rodiklis 9
1.2.4. Genetinių algoritmų operatoriai 9
1.2.4.1. Atrankos operatorius 9
1.2.4.2. Kryžminimo operatorius 11
1.2.4.3. Mutacijos operatorius 12
1.2.5. Elitizmas 13
1.3. Skruzdėlių kolonijos algoritmas 13
1.3.1. Sekančio miesto pasirinkimas 14
1.3.2. Feromonų atnaujinimas 14
1.3.3. Alfa () ir Beta () parametrai 14
1.4. Atkaitinimo modeliavimas 14
1.4.1. Veikimo principas 15
1.4.2. Kandidatų sprendimų generavimas 16
1.4.3. Aušinimo grafikas 16
2. Eksperimento planas ir konfigūracijos nustatymas 16
2.1. Genetinio algoritmo konfigūracija 17
2.1.1. Populiacijos dydžio pasirinkimas 17
2.1.2. Elitizmo dydžio pasirinkimas 18
2.1.3. Mutacijos dažnis 20
2.1.4. Kryžminimo dažnis 21
2.2. Skruzdėlių kolonijos algoritmo konfigūracija 22
2.2.1. Skruzdėlių skaičiaus pasirinkimas 22
2.2.2. Išgaravimo rodiklio pasirinkimas 23
2.2.3. Beta parametro pasirinkimas 24
2.2.4. Alfa parametro pasirinkimas 25
2.3. Atkaitinimo modeliavimo konfigūracija 27
2.3.1. Geriausia parametrų kombinacija 27
3. Eksperimentas 29
3.1. Algoritmų palyginimas 29
3.1.1. Trumpiausio atstumo palyginimas 29
3.1.2. Vykdymo laiko palyginimas 30
Rezultatai ir išvados 31
Conclusions 33
Literatūros sąrašas 34

Įvadas
Euristiniai algoritmai yra stiprūs įrankiai spręsti sudėtingas optimizavimo problemas, jų
dėka galima rasti apytikslį užduoties sprendimą, kai tikslūs algoritmai gali šlubuoti [Wil20].
Euristiniai algoritmai dažnu atveju remiasi gamtinėmis idėjomis, stochastiniu pagrindu,
simuliacijomis. Šie algoritmai yra lankstūs ir gali būti taikomi sprendžiant įvairias problemas
su skirtingais problemų dydžiais. Didžiausias šių optimizavimo algoritmų pranašumas prieš
tradicinius sprendimo metodus yra laikas [Wil20]. Skirtingai nei tradiciniai, tikslūs algoritmai,
kurie dažnai apima visus galimus sprendimus, euristiniai metodai geba pateikti sprendimus
per žymiai trumpesnį laiką, nes efektyviai ir greitai mažina paieškos sprendimo erdvę. Tai
ypatingai matosi tada, kai sprendžiamos sudėtingos problemos su dideliais duomenų kiekiais.
Vienas iš sudėtingų uždavinių dėl savo eksponentinio sprendimo erdvės augimo, kuris
priklauso NP sudėtingumo klasei yra keliaujančio pirklio uždavinys (KPU) (angl. Travelling
Salesman problem (TSP)). Tai yra klasikinė problema kompiuterių moksle. Praktikoje šis
uždavinys padeda rasti atsakymus į įvairius planavimo, logistikos ir išteklių paskirstymo
klausimus. Šis, iš pažiūros, paprastas uždavinys tampa per sudėtingas didėjant miestų skaičiui,
todėl tai yra puikus iššūkis euristiniams algoritmams. Šiame darbe ir bus analizuojami
euristiniai algoritmai, tokie kaip genetinis algoritmas (angl. Genetic Algorithm (GA)),
skruzdėlių kolonijos optimizavimas (angl. Ant Colony Optimization (ACO)) bei atkaitinimo
modeliavimas (angl. Simulated Anealling (SA)), sprendžiant įvairių duomenų dydžių
keliaujančio pirklio uždavinius.
Genetiniai algoritmai yra prisitaikantys, euristinės metodikos paieškos algoritmai. Jie
paremti natūraliosios atrankos procesu, kas reiškia, kad išgyventi ir daugintis gali tik tos
rūšys, kurios prisitaiko prie tam tikrų pokyčių. Genetinis algoritmas pradeda savo darbą
sugeneruodamas atsitiktinę galimų sprendimų populiaciją, tada pakartotinai naudojant tris
operatorius, atranką, kryžminimą ir mutaciją yra sukuriamos naujos kartos. Šis procesas
evoliucionuoja sprendimus, artėjant prie geriausio užduoties sprendimo.
Skruzdėlių kolonijos optimizavimo idėja yra ta, kad naudojamos skruzdėlės, kurios eina
sprendimų erdvėje ir kiekvienos skruzdėlės nueitas kelias yra išreikštas kaip problemos
sprendimas. Skruzdėlės, eidamos savo keliu išskiria feromonus, kurie padeda kitos kartos
skruzdėlėms žinoti, kuris kelias yra daugiau einamas, trumpiausias.
Atkaitinimo modeliavimas yra algoritmas, kurio idėja remiasi medžiagos kaitinimu ir
palaipsniniu aušinimu, gerinant medžiagos savybes [Sar15]. Algoritmas leidžia pasiremti ir
blogesniais sprendimais, išvengiant lokalių optimalumų.
Šio bakalauro baigiamojo darbo tikslas yra išanalizuoti genetinius algoritmus
keliaujančio pirklio uždavinyje ir jų veikimą lemiančius operatorius ir parametrus bei šį
sprendimo būdą palyginti su kitais euristiniais optimizavimo metodais: gaunamų sprendimo
optimalumo ir sprendimo gavimo laiko atžvilgiu. Kad šį tikslą būtų galima įgyvendinti,
galima išsikelti uždavinius:
1.Apžvelgti literatūrą susijusią su euristiniais algoritmais ir jų taikymą...