Dane szczegółowe książki
Wykłady z algorytmów ewolucyjnych / Arabas, Jarosław; Tenniel, John (1820-1914)
Tytuł
Wykłady z algorytmów ewolucyjnych
Wydawnictwo
Warszawa: Wydawnictwa Naukowo-Techniczne, 2001
ISBN
8320426049
Hasła przedmiotowe
Spis treści
pokaż spis treści
Wprowadzenie 15
CZĘŚĆ I 27
WYKŁAD 1. W poszukiwaniu optimum. 29
1.1. Wstęp. 29
1.2. Rodzaje zadari 30
1.2.1. Właściwości funkcji celu. 31
1.2.2. Ograniczenia funkcji celu 36
1.2.3. Znaczenie liczby wymiarów 38
1.3. Metody optymalizacji. 40
1.4. Jak oceniać algorytmy optymalizacji. 43
1.4.1. Dokładność przybliżenia rozwiązania 43
1.4.2. Odporność 44
1.4.3. Koszt symulacji. 45
1.5. Metody eliminowania ograniczeń funkcyjnych 46
1.5.1. Metody transformacji zmiennych niezależnych. 47
1.5.2. Metody funkcji kary. 50
1.6. Zadania wielokryteriame. 55
1.6.1. Sformułowanie zadania 55
1.6.2. Skalaryzacja zadania 56
1.7. Środowisko dynamiczne. 60
1.7.1. Kryteria oceny algorytmu. 61
1.7.2. Rodzaje zmian środowiska. 61
1.7.3. Adaptacja do zmian środowiska 62
1.8. Uwagi bibliograficzne 62
1.9. Pytania i ćwiczenia 63
WYKŁAD 2. Podstawowe typy algorytmów ewolucyjnych 65
2.1. Algorytmy genetyczne. 65
2.1.1. Prosty algorytm genetyczny. 65
2.1.2. Schematy 72
2.1.3. Symulacja działania algorytmu genetycznego. 76
2.2. Strategie ewolucyjne. 83
2.2.1. Strategia (1+1) 83
2.2.2. Strategia (fj, + A) 85
2.2.3. Strategia (p,, A) 87
2.2.4. Analiza działania strategii. 88
2.2.5. Symulacja działania strategii 90
2.3. Programowanie ewolucyjne 92
2.3.1. Schemat programowania. 94
2.3.2. Operatory mutacji. 95
2.4. Programowanie genetyczne 96
2.4.1. Programy, które powstają samoczynnie 96
2.4.2. Kodowanie drzewiaste. 97
2.4.3. Operatory genetyczne. 98
2.5. Uwagi bibliograficzne 101
2.6. Pytania i ćwiczenia 102
CZĘŚĆ II 103
WYKŁAD 3. Zarządzanie populacją 105
3.1. Ogólny schemat algorytmu ewolucyjnego 105
3.2. Eksploracja i eksploatacja. 107
3.2.1. Nacisk selektywny w prostej metodzie poszukiwań losowych 108
3.3. Jak oceniać algorytmy ewolucyjne. 112
3.3.1. Metoda testowania i sposób prezentacji wyników. 112
3.4. Metody selekcji 114
3.4.1. Reprodukcja i sukcesja 114
K. 3.4.2. Reprodukcja proporcjonalna (ruletkowa). 114
3.4.3. Zmodyfikowana reprodukcja proporcjonalna. 117
3.4.4. Reprodukcja rangowa 120
3.4.5. Reprodukcja turniejowa. 123
3.4.6. Reprodukcja progowa 127
3.4.7. Sukcesja z całkowitym zastępowaniem. 129
3.4.8. Sukcesja z częściowym zastępowaniem. 129
3.4.9. Sukcesja elitarna 130
3.5. Kryteria zatrzymania algorytmu. 135
3.5.1. Monitorowanie rozwiązań generowanych przez algorytm 136
3.5.2. Monitorowanie zdolności eksploracyjnych 139
3.6. Uwagi bibliograficzne 142
3.7. Pytania i ćwiczenia 143
WYKŁAD 4. Kodowanie i operatory genetyczne 145
4.1. Rola kodowania i operatorów genetycznych 145
4.2. Jak dobierać kodowanie i operatory genetyczne 146
4.2.1. Pożądane cechy kodowania chromosomów 146
4.2.2. Metryki w przestrzeni genotypu i fenotypu. 147
4.2.3. Pożądane cechy operatorów genetycznych 149
4.3. Warianty operatorów krzyżowania. 151
4.4. Przegląd metod krzyżowania. 153
4.4.1. Operatory krzyżowania wymieniającego 153
4.4.2. Operatory krzyżowania uśredniającego. 157
4.4.3. Różnice między operatorami krzyżowania wymieniającego i uśredniającego. 159
4.5. Operator inwersji 160
4.6. Operatory mutacji. 163
4.6.1. Mutacja dla kodowania binarnego. 163
4.6.2. Mutacje przeznaczone do optymalizacji w Rn 163
4.7. Eksploracja i eksploatacja a operatory genetyczne. 165
4.7.1. Czy ważniejszym operatoremjest krzyżowanie, czy mutacja? 165
4.7.2. Zasięg operatorów. 166
4.8. Metody modyfikacji zasięgu operatorów genetycznych 169
4.8.1. Modyfikacje zasięgu mutacji. 169
4.8.2. Modyfikacje zasięgu krzyżowania 174
4.9. Krzyżowanie wieloosobnicze. 177
4.10. Zarządzaniewielomaoperatoramigenetycznymi. 181
4.11. Czy warto stosować kodowanie binarne problemów numerycznych? 185
4.12. Uwagi bibliograficzne 190
4.13. Pytania i ćwiczenia 191
CZĘŚĆ III 193
WYKŁAD 5. Zapobieganie przedwczesnej zbieżności. 195
5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych 195
5.1.1. Efekt Baldwina i ewolucja lamarkowska 197
5.2. Czas życia osobników w populacji bazowej. 200
5.2.1. Limitowanie maksymalnego czasu życia 200
5.2.2. Selekcja sterowana czasem życia. 202
5.3. Optymalizacja wielomodalna 208
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej 209
5.4.1. Wprowadzanie dodatkowego czynnika losowego 210
5.4.2. Osłabianie konkurencyjności w ramach selekcji. 211
5.4.3. Ograniczanie zasięgu selekcji. 213
5.4.4. Preselekcja 216
''' 5.4.5. Deformacje funkcji przystosowania w otoczeniu maksimum lokalnego 218
5.5. Inicjacja populacji bazowej 220
.11.
. 12 - Spis treści
5.5.1. Posiew nierównomierny 224
5.5.2. Znaczenie generatora liczb pseudolosowych 225
5.6. Znaczenie liczności populacji bazowej 227
5.7. Równoległość w algorytmach ewolucyjnych 231
5.7.1. Implementacje równolegle. 232
5.7.2. Algorytmy koewolucyjne. 236
5.8. Uwagi bibliograficzne 239
5.9. Pytania i ćwiczenia 241
WYKŁAD 6. Uwzględnianie specyfiki problemu. 243
6.1. Wykorzystanie skomplikowanych struktur danych 243
6.1.1. Zadania o ustalonej liczbie parametrów 243
6.1.2. Zadania o nieustalonej liczbie parametrów. 250
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń 255
6.2.1. Kodowanie specjalizowane i operatory genetyczne 255
6.2.2. Algorytmy naprawy. 257
6.3. Modyfikacje algorytmu ewolucyjnego uwzględniające zadania wielokryterialne. 258
6.3.1. Reprodukcja oparta na dominacji 259
6.3.2. Podejście koewolucyjne 260
6.4. Algorytm ewolucyjny w środowisku dynamicznym. 261
6.4.1. Informacja o zajściu zmiany. 262
6.4.2. Metody adaptacji. 262
6.4.3. Pamięć na poziomie populacji. 263
6.4.4. Pamięć na poziomie osobnika 263
6.5. Uwagi bibliograficzne 265
6.6. Pytania i ćwiczenia 266
Uwagi końcowe. 267
DODATEK A. Oznaczenia i symbole. 269
A.1. Symbole łacińskie. 269
W j A.2. Symbole greckie. 270
A.3. Oznaczenia inne. 270
A.4. Zasady indeksowania i doboru czcionek 271
DODATEK B. Niektóre funkcje testowe 273
B.1. Zadania ciągłe. 273
B.2. Zadania dyskretne. 274
DODATEK C. Wartości parametrów uznawane za optymalne. 277
DODATEK D. Elementy matematyki. 279
D.1. Miary różnorodności. 279
D.2. Rozkłady zmiennych losowych. 281
#13.
DODATEK E. Oprogramowanie gabi . 283
E.1. Założenia ogólne. 283
E.2. Opis funkcjonalny oprogramowania 284
E.3. Sposób implementacji 285
E.4. Pliki konfiguracyjne 286
E.5. Sposób działania oprogramowania 287
E.5.1. Funkcja main 287
E.5.2. Funkcja petlaGlowna 287
E.5.3. Funkcja genetyka 288
E.5.4. Funkcja reprodukcja 289
E.6. Rozbudowa oprogramowania. 289
E.6.1. Plik algorytm.c. 289
E.6.2. Plik genetyka.c. 290
E.6.3. Plik glowny.c. 291
E.6.4. Plik losowe. c. 291
E.6.5. Plik monitor.c 291
E.6.6. Plik ogranicz. c. 292
E.6.7. Plik osobnik.c 292
E.6.8. Plik pop. c. 292
E.6.9. Płik raporty.c 292
E.6.10. Plik selekcja.c. 293
E.6.11. Plik stop. c 293
E.6.12. Plik wewy.c 293
E.6.13. Plik zadanie. c 293
Literatura 295
Skorowidz 301
CZĘŚĆ I 27
WYKŁAD 1. W poszukiwaniu optimum. 29
1.1. Wstęp. 29
1.2. Rodzaje zadari 30
1.2.1. Właściwości funkcji celu. 31
1.2.2. Ograniczenia funkcji celu 36
1.2.3. Znaczenie liczby wymiarów 38
1.3. Metody optymalizacji. 40
1.4. Jak oceniać algorytmy optymalizacji. 43
1.4.1. Dokładność przybliżenia rozwiązania 43
1.4.2. Odporność 44
1.4.3. Koszt symulacji. 45
1.5. Metody eliminowania ograniczeń funkcyjnych 46
1.5.1. Metody transformacji zmiennych niezależnych. 47
1.5.2. Metody funkcji kary. 50
1.6. Zadania wielokryteriame. 55
1.6.1. Sformułowanie zadania 55
1.6.2. Skalaryzacja zadania 56
1.7. Środowisko dynamiczne. 60
1.7.1. Kryteria oceny algorytmu. 61
1.7.2. Rodzaje zmian środowiska. 61
1.7.3. Adaptacja do zmian środowiska 62
1.8. Uwagi bibliograficzne 62
1.9. Pytania i ćwiczenia 63
WYKŁAD 2. Podstawowe typy algorytmów ewolucyjnych 65
2.1. Algorytmy genetyczne. 65
2.1.1. Prosty algorytm genetyczny. 65
2.1.2. Schematy 72
2.1.3. Symulacja działania algorytmu genetycznego. 76
2.2. Strategie ewolucyjne. 83
2.2.1. Strategia (1+1) 83
2.2.2. Strategia (fj, + A) 85
2.2.3. Strategia (p,, A) 87
2.2.4. Analiza działania strategii. 88
2.2.5. Symulacja działania strategii 90
2.3. Programowanie ewolucyjne 92
2.3.1. Schemat programowania. 94
2.3.2. Operatory mutacji. 95
2.4. Programowanie genetyczne 96
2.4.1. Programy, które powstają samoczynnie 96
2.4.2. Kodowanie drzewiaste. 97
2.4.3. Operatory genetyczne. 98
2.5. Uwagi bibliograficzne 101
2.6. Pytania i ćwiczenia 102
CZĘŚĆ II 103
WYKŁAD 3. Zarządzanie populacją 105
3.1. Ogólny schemat algorytmu ewolucyjnego 105
3.2. Eksploracja i eksploatacja. 107
3.2.1. Nacisk selektywny w prostej metodzie poszukiwań losowych 108
3.3. Jak oceniać algorytmy ewolucyjne. 112
3.3.1. Metoda testowania i sposób prezentacji wyników. 112
3.4. Metody selekcji 114
3.4.1. Reprodukcja i sukcesja 114
K. 3.4.2. Reprodukcja proporcjonalna (ruletkowa). 114
3.4.3. Zmodyfikowana reprodukcja proporcjonalna. 117
3.4.4. Reprodukcja rangowa 120
3.4.5. Reprodukcja turniejowa. 123
3.4.6. Reprodukcja progowa 127
3.4.7. Sukcesja z całkowitym zastępowaniem. 129
3.4.8. Sukcesja z częściowym zastępowaniem. 129
3.4.9. Sukcesja elitarna 130
3.5. Kryteria zatrzymania algorytmu. 135
3.5.1. Monitorowanie rozwiązań generowanych przez algorytm 136
3.5.2. Monitorowanie zdolności eksploracyjnych 139
3.6. Uwagi bibliograficzne 142
3.7. Pytania i ćwiczenia 143
WYKŁAD 4. Kodowanie i operatory genetyczne 145
4.1. Rola kodowania i operatorów genetycznych 145
4.2. Jak dobierać kodowanie i operatory genetyczne 146
4.2.1. Pożądane cechy kodowania chromosomów 146
4.2.2. Metryki w przestrzeni genotypu i fenotypu. 147
4.2.3. Pożądane cechy operatorów genetycznych 149
4.3. Warianty operatorów krzyżowania. 151
4.4. Przegląd metod krzyżowania. 153
4.4.1. Operatory krzyżowania wymieniającego 153
4.4.2. Operatory krzyżowania uśredniającego. 157
4.4.3. Różnice między operatorami krzyżowania wymieniającego i uśredniającego. 159
4.5. Operator inwersji 160
4.6. Operatory mutacji. 163
4.6.1. Mutacja dla kodowania binarnego. 163
4.6.2. Mutacje przeznaczone do optymalizacji w Rn 163
4.7. Eksploracja i eksploatacja a operatory genetyczne. 165
4.7.1. Czy ważniejszym operatoremjest krzyżowanie, czy mutacja? 165
4.7.2. Zasięg operatorów. 166
4.8. Metody modyfikacji zasięgu operatorów genetycznych 169
4.8.1. Modyfikacje zasięgu mutacji. 169
4.8.2. Modyfikacje zasięgu krzyżowania 174
4.9. Krzyżowanie wieloosobnicze. 177
4.10. Zarządzaniewielomaoperatoramigenetycznymi. 181
4.11. Czy warto stosować kodowanie binarne problemów numerycznych? 185
4.12. Uwagi bibliograficzne 190
4.13. Pytania i ćwiczenia 191
CZĘŚĆ III 193
WYKŁAD 5. Zapobieganie przedwczesnej zbieżności. 195
5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych 195
5.1.1. Efekt Baldwina i ewolucja lamarkowska 197
5.2. Czas życia osobników w populacji bazowej. 200
5.2.1. Limitowanie maksymalnego czasu życia 200
5.2.2. Selekcja sterowana czasem życia. 202
5.3. Optymalizacja wielomodalna 208
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej 209
5.4.1. Wprowadzanie dodatkowego czynnika losowego 210
5.4.2. Osłabianie konkurencyjności w ramach selekcji. 211
5.4.3. Ograniczanie zasięgu selekcji. 213
5.4.4. Preselekcja 216
''' 5.4.5. Deformacje funkcji przystosowania w otoczeniu maksimum lokalnego 218
5.5. Inicjacja populacji bazowej 220
.11.
. 12 - Spis treści
5.5.1. Posiew nierównomierny 224
5.5.2. Znaczenie generatora liczb pseudolosowych 225
5.6. Znaczenie liczności populacji bazowej 227
5.7. Równoległość w algorytmach ewolucyjnych 231
5.7.1. Implementacje równolegle. 232
5.7.2. Algorytmy koewolucyjne. 236
5.8. Uwagi bibliograficzne 239
5.9. Pytania i ćwiczenia 241
WYKŁAD 6. Uwzględnianie specyfiki problemu. 243
6.1. Wykorzystanie skomplikowanych struktur danych 243
6.1.1. Zadania o ustalonej liczbie parametrów 243
6.1.2. Zadania o nieustalonej liczbie parametrów. 250
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń 255
6.2.1. Kodowanie specjalizowane i operatory genetyczne 255
6.2.2. Algorytmy naprawy. 257
6.3. Modyfikacje algorytmu ewolucyjnego uwzględniające zadania wielokryterialne. 258
6.3.1. Reprodukcja oparta na dominacji 259
6.3.2. Podejście koewolucyjne 260
6.4. Algorytm ewolucyjny w środowisku dynamicznym. 261
6.4.1. Informacja o zajściu zmiany. 262
6.4.2. Metody adaptacji. 262
6.4.3. Pamięć na poziomie populacji. 263
6.4.4. Pamięć na poziomie osobnika 263
6.5. Uwagi bibliograficzne 265
6.6. Pytania i ćwiczenia 266
Uwagi końcowe. 267
DODATEK A. Oznaczenia i symbole. 269
A.1. Symbole łacińskie. 269
W j A.2. Symbole greckie. 270
A.3. Oznaczenia inne. 270
A.4. Zasady indeksowania i doboru czcionek 271
DODATEK B. Niektóre funkcje testowe 273
B.1. Zadania ciągłe. 273
B.2. Zadania dyskretne. 274
DODATEK C. Wartości parametrów uznawane za optymalne. 277
DODATEK D. Elementy matematyki. 279
D.1. Miary różnorodności. 279
D.2. Rozkłady zmiennych losowych. 281
#13.
DODATEK E. Oprogramowanie gabi . 283
E.1. Założenia ogólne. 283
E.2. Opis funkcjonalny oprogramowania 284
E.3. Sposób implementacji 285
E.4. Pliki konfiguracyjne 286
E.5. Sposób działania oprogramowania 287
E.5.1. Funkcja main 287
E.5.2. Funkcja petlaGlowna 287
E.5.3. Funkcja genetyka 288
E.5.4. Funkcja reprodukcja 289
E.6. Rozbudowa oprogramowania. 289
E.6.1. Plik algorytm.c. 289
E.6.2. Plik genetyka.c. 290
E.6.3. Plik glowny.c. 291
E.6.4. Plik losowe. c. 291
E.6.5. Plik monitor.c 291
E.6.6. Plik ogranicz. c. 292
E.6.7. Plik osobnik.c 292
E.6.8. Plik pop. c. 292
E.6.9. Płik raporty.c 292
E.6.10. Plik selekcja.c. 293
E.6.11. Plik stop. c 293
E.6.12. Plik wewy.c 293
E.6.13. Plik zadanie. c 293
Literatura 295
Skorowidz 301