W monografii przedstawiono sposoby adaptacji wybranych algorytmów stadnych do rozwiązania problemów szeregowania zadań, przydziału z kwadratowym wskaźnikiem jakości, komiwojażera oraz optymalizacji systemów i sieci kolejkowych. (...) Główna część pracy dotyczy przeprowadzenia badań nad zastosowaniem algorytmów stadnych w optymalizacji dyskretnej i kombinatorycznej, propozycji modyfikacji tych algorytmów oraz przebadania mechanizmów w nich stosowanych w celu intensyfikacji i eksploracji przestrzeni rozwiązań, a także zbadania wydajności zaprojektowanych algorytmów na podstawie bibliotek testowych dla wybranych zagadnień. Rezultaty prowadzonych badań potwierdziły możliwości zastosowania oraz efektywność algorytmów stadnych w rozwiązaniu problemów NP-trudnych i wspomaganiu decyzji dotyczących optymalnej struktury i likwidacji kolejki w modelach kolejkowych.
- Spis treści
-
Streszczenie 9
Summary 11
Wykaz symboli i skrótów 13
Wprowadzenie 15
1. Podstawowe zagadnienia dotyczące algorytmów stadnych 19
1.1. Ogólne zasady działania algorytmów opartych na grupowych zachowaniach występujących w naturze 19
1.2. Charakterystyka wybranych algorytmów 22
1.2.1. Algorytm optymalizacji kolonią mrówek 23
1.2.2. Algorytm optymalizacji rojem cząstek 26
1.2.3. Algorytm pszczeli 28
1.2.4. Algorytm świetlika 30
1.2.5. Algorytm kukułki 32
1.2.6. Algorytm optymalizacji kolonią karaluchów 34
1.3. Algorytmy stadne na tle różnych metaheurystyk 35
1.4. Kierunki badawcze 37
1.5. Problem zbieżności 38
1.6. Krajobrazy przestrzeni rozwiązań 39
1.7. Teoria NFL 40
1.8. Podsumowanie 41
2. Elementy projektowania algorytmów stadnych w problemach optymalizacji 43
2.1. Dobre praktyki projektowania algorytmów 43
2.2. Adaptacja algorytmów do zagadnień permutacyjnych 44
2.2.1. Reprezentacja rozwiązania 45
2.2.2. Sposoby dyskretyzacji przestrzeni 45
2.2.3. Sąsiedztwo, odległość, ruch 46
2.3. Problem doboru parametrów algorytmu 47
2.3.1. Wybrane metody sterowania parametrami w algorytmach stadnych 50
2.3.2. Parametry podlegające procedurom doboru 50
2.4. Hybrydyzacja algorytmów 51
2.5. Podsumowanie 53
3. Zastosowanie algorytmów pszczelego, świetlika i optymalizacji kolonią karaluchów do rozwiązania przepływowego problemu szeregowania 54
3.1. Permutacyjny problem szeregowania typu flow shop 55
3.1.1. Założenia 56
3.1.2. Model matematyczny 56
3.2. Realizacja i wyniki badań algorytmów pszczelego, świetlika i optymalizacji kolonią karaluchów 57
3.2.1. Algorytm pszczeli – reprezentacja rozwiązania i sposób adaptacji 58
3.2.2. Reprezentacja rozwiązania w algorytmach świetlika i optymalizacji kolonią karaluchów 58
3.2.3. Adaptacja algorytmu świetlika 59
3.2.4. Adaptacja algorytmu optymalizacji kolonią karaluchów 61
3.2.5. Eksperymenty obliczeniowe 63
3.2.5.1. Badanie efektywności algorytmu pszczelego 64
3.2.5.2. Badanie efektywności algorytmów świetlika i optymalizacji kolonią karaluchów 67
3.2.6. Porównanie wyników i wnioski z przeprowadzonych badań 69
4. Zastosowanie algorytmów mrówkowych, z optymalizacji rojem cząstek i pszczelego do rozwiązania kwadratowego problemu przydziału 72
4.1. Model matematyczny kwadratowego problemu przydziału 72
4.2. Adaptacja algorytmów mrówkowych 73
4.2.1. System mrówkowy 73
4.2.2. System mrówkowy ze strategią max-min 74
4.2.3. Przeszukiwanie lokalne 75
4.3. Adaptacja algorytmu optymalizacji rojem cząstek 76
4.4. Adaptacja algorytmu pszczelego 79
4.5. Analiza efektywności algorytmów 79
4.5.1. Metodyka badań 80
4.5.2. Wpływ parametrów systemu mrówkowego ze strategią max-min na jakość rozwiązań 80
4.5.3. Wpływ parametrów algorytmu optymalizacji rojem cząstek na jakość rozwiązań 83
4.5.4. Wpływ parametrów algorytmu pszczelego na jakość rozwiązań 85
4.5.5. Podsumowanie eksperymentów 88
5. Optymalizacja problemu komiwojażera za pomocą algorytmów stadnych 90
5.1. Model matematyczny problemu komiwojażera 90
5.2. Możliwości modyfikacji algorytmów 91
5.3. Adaptacja algorytmu świetlika 92
5.4. Adaptacja algorytmu optymalizacji kolonią karaluchów 93
5.5. Eksperymenty obliczeniowe 96
5.5.1. Badanie efektywności algorytmu świetlika 96
5.5.2. Badanie efektywności algorytmu optymalizacji kolonią karaluchów 98
5.6. Podsumowanie 100
6. Algorytmy stadne w wybranych problemach optymalizacji systemów i sieci kolejkowych 102
6.1. Systemy kolejkowe i ich optymalizacja 103
6.1.1. Wybrane modele systemów kolejkowych 103
6.1.1.1. System ze stratami M/M/m/-/m 104
6.1.1.2. System kolejkowy M/M/m/FIFO/m+N ze skończoną pojemnością i niecierpliwymi zgłoszeniami 104
6.1.1.3. System zamknięty M/M/m/FIFO/N/F 105
6.1.2. Optymalizacja systemów kolejkowych 106
6.1.2.1. Funkcje kosztów w problemach optymalizacji systemów kolejkowych 106
6.1.2.2. Analiza porównawcza algorytmów świetlika i optymalizacji kolonią karaluchów 107
6.2. Sieci kolejkowe i ich optymalizacja 109
6.2.1. Sieci kolejkowe wieloklasowe BCMP 110
6.2.1.1. Algorytm aproksymacji SUM 111
6.2.1.2. Dodatkowe mechanizmy w sieciach kolejkowych 113
6.2.2. Możliwości zastosowania sieci kolejkowych 114
6.2.3. Modelowanie w służbie zdrowia – proces chemioterapii 114
6.2.4. Problemy optymalizacji sieci kolejkowych 117
6.2.5. Optymalizacja strukturalna sieci kolejkowych 117
6.2.5.1. Sformułowanie problemu optymalizacji sieci kolejkowych 117
6.2.5.2. Optymalizacja sieci z wykorzystaniem algorytmu kukułki 118
6.2.5.3. Wyniki badań 120
6.2.5.4. Wnioski z przeprowadzonych eksperymentów 121
6.3. Algorytm świetlika w problemie szeregowania zgłoszeń w węzłach budujących strukturę sieciową 122
6.3.1. Adaptacja algorytmu świetlika 123
6.3.2. Wyniki przeprowadzonych eksperymentów 125
6.3.3. Podsumowanie wyników 127
Zakończenie 129
Literatura 133