Dane szczegółowe książki
Algorytmy genetyczne i ich zastosowania / Goldberg, David E. (1953-); Grygiel, Kazimierz
Tytuł
Algorytmy genetyczne i ich zastosowania
Tytuł oryginału
Genetic algorithms in search, optimization and machine learning
Wydawnictwo
Warszawa: Wydawnictwa Naukowo-Techniczne, 1998
Numer wydania
2
ISBN
8320422728
Hasła przedmiotowe
Spis treści
pokaż spis treści
Rozdział 1. Wprowadzenie dla niewtajemniczonych
Co to są algorytmy genetyczne? ______________________
Odporność tradycyjnych metod optymalizacji i poszukiwania . Cele optymalizacji__________________________________
Czym różnią się algorytmy genetyczne od tradycyjnych metod? Elementarny algorytm genetyczny_________________________
1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8.
1.9. Nieco żargonu
1.10. Podsumowanie
1.11. Zadania _____
Algorytmy genetyczne w działaniu - symulacja odręczna____
Ziarno optymalizacyjnego mtyna - podobieństwa strukturalne Schematy _________________________________________
1.12. Ćwiczenia komputerowe
.17
_17
_22
_23
_26
.32
_36
_39 _41 _42
Rozdział 2. Podstawy matematyczne algorytmów genetycznych
2.1. 2.2. 2.3. 2.4. 2.5. 2.6.
2.7. 2.8.
Kto przetrwa, a kto zginie? Podstawowe twierdzenie_____________
Przetwarzanie schematów na żywo: symulacja odręczna po raz wtóry . Zagadnienia dwu- i ^-ramiennego bandyty______________________
Ile schematów bierze efektywny udział w przetwarzaniu? Hipoteza cegiełek________________________________
Minimalny problem zwodniczy 2.6.1. MDP: analiza_________
2.6.2. MDP: wyniki symulacyjne _____________________________
Jeszcze o schematach: wzorce podobieństwa jako hiperpłaszczyzny . Podsumowanie ___________________________________________
_44
_45 _50 _53 _57 _59 _63 _66 _68 _70 _71
#12
2.9. Zadania ____________
2.10. Ćwiczenia komputerowe
_72 _73
Rozdział 3. Implementacja komputerowa algorytmu genetycznego
3.1. Struktury danych _________________________________
_75
Reprodukcja, krzyżowanie, mutacja . Czas reprodukcji, czas krzyżowania . Program główny ______________
3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8.
3.9. Standardowa metoda kodowania dla zadań wieloparametrycznych
3.10. Dyskretyzacja _______________________________________
3.11. Problem więzów______________________________________
3.12. Podsumowanie ______________________________________
3.13. Zadania ___________________________________________.
3.14. Ćwiczenia komputerowe ________________________________
Czy wszystko działa jak należy?_______________
Przekształcenie funkcji celu w funkcję przystosowania .
Skalowanie przystosowania ___________________
Metody kodowania __________________________
_76 _78 _81 _83 _84 _90 _91 _94 _97 _99 _100 _101 .102 _103
Rozdział 4. Niektóre zastosowania algorytmów genetycznych
4.1. Powstanie algorytmów genetycznych_______________
.104
_104
4.2.
Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych 107
4.2.1. Bagley i adaptacyjny program gry w sześć pionków____________107
Rosenberg i symulacja żywej komórki___________________
Cavicchio i rozpoznawanie postaci ____________________
4.2.2. 4.2.3. 4.2.4.
108 110
Weinberg, symulacja komórki i algorytm genetyczny
4.3. 4.4. 4.5. 7 metapr)7inmu 113
4 ? F, Hnllstifin i nptymali7aqa funknji 114
4,?. R, Frant? i efekt pn7ynyjny 11fi
4.?. 7. Bnfiwnrth, Fnn i 7eigler - geny n r7er7ywiste" 117
4 9 R Rnv i planowanie ewolucyjne 11ft
4 9 P Inno ewolucyjne techniki nptymali7anji 190
42 10 Fogel, Owens i Walsh - Programowanie ewolucyjne 190
De .long i optymali7arja funknji 199
l lr(nskr>na lenia terhnir:7ne 13fi
441 Alternatywne metnrly selekrji 13fi
449 Merhani7imy skalowania 138
4 4 3 Nadawanie rang 14f>
Aktualne 7astnsnwania algnrytmńw genetycznych 141
451 Ontvmali/a<^Ha nirnriąnn naynwenn 144
4.5.2. Optymalizacja strukturalna konstrukcji przy użyciu algorytmu genetycznego ___________________________________
.151
4.5.3. Obróbka medycznych obrazów rentgenowskich za pomocą algorytmu
genetycznego _________________________________________153
Spis treści
4.5.4. lterowany dylemat więźnia
4.6. Podsumowanie ______________
4.7. Zadania_____________________
4.8. Ćwiczenia komputerowe
_ 13
.155 _157 _158 _160
Rozdział 5. Techniki i operacje zaawansowane
.161
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
5.2.
5.3.
5.4.
5.5. 5.6.
_162
5.1.1. Diploidalność i dominowanie w algorytmach genetycznych -zarys historyczny ___________________________________________
.164
5.1.2. Analiza diploidalności i dominowania w algorytmach genetycznych__172
5.1.3. Implementacja modelu triallelicznego_________________________176
Inwersja i inne operacje rekonfiguracji_____________________________178
5.2.1. Operacje rekonfiguracji w algorytmach genetycznych. Zarys
historyczny _________________________________________
5.2.2. Teoria operacji rekonfigurujących Inne mikrooperacje__________________
5.3.1. Segregacja, translokacja i s*ruktury wielochromosomowe .
5.3.2. Duplikacja i delecja _____________________________
5.3.3. Determinacja płci i zróżnicowanie płciowe Nisze i specjacja_________________________
5.4.1. Teoria nisz i gatunków_________________________
5.4.2. Metody niszowe w poszukiwaniach genetycznych____
5.4.3. Bariery reprodukcyjne w poszukiwaniach genetycznych .
Optymalizacja wielokryterialna_________________________
Techniki oparte na wiedzy ___________________________
5.6.1. Hybrydyzacja _________________________________
_182 _190 _194 _194 _195 _196 _200 _202 _205
5.6.2. Operacje wzbogacone wiedzą.
5.6.3. Metody aproksymacyjne ____
_212 _217 _218 _220
5.7. 5.8. 5.9. 5.10. Ćwiczenia komputerowe
Algorytmy genetyczne a architektura równoległa .
Podsumowanie _________________________
Zadania_________________________________
_224 _228 _229 _231
Rozdział 6. Wprowadzenie do genetycznych systemów uczących się
_232
6.1. 6.2. 6.3. 6.4. 6.5. 6.6.
Skąd wzięty się systemy GBMI___________
Czym jest system klasyfikujący?_________
Układ przetwarzania komunikatów_______
Układ oceniający: Algorytm bucket brigade . Algorytm genetyczny__________________
_233
_236
System klasyfikujący w Pascalu___
6.6.1. Strukturydanych___________
6.6.2. Układ wykonawczy_________
6.6.3. Algorytm przyznawania ocen
_240 _245 _246 _246 _248 _249
14
Spis treści
6.6.4. Poszukiwanie genetyczne w systemie klasyfikującym .
6.6.5. A więc gdzie problem?_______________________
6.6.6. Odczytaj komunikat, podejmij działanie .
6.6.7. Zwycięzca bierze wszystko _________
6.6.8. Program główny__________________
6.7. Wyniki eksperymentów z systemem SCS
6.7.1. Parametry środowiska i systemu__
6.7.2. Reguty idealne i ,,dywersanci"____
6.7.3. Hierarchia domniemań _________
6.7.4. Start od zera: Model Tabula rasa
Podsumowanie ____________________
Zadania___________________________
6.8. 6.9. 6.10. Ćwiczenia komputerowe
_252 _255 _258 _260 _261 _262 _262 _262 _265 _271 _273 _274 _276
Rozdział 7. Zastosowania genetycznych systemów uczących się
7.1. Początki systemów GBML ______________________
_277
7.1.1. Schematy i ich procesory .
7.1.2. Język przekazu _______
7.2.
7.3.
7.4.
Pierwszy system klasyfikujący CS-1
7.2.1. System CS-1 w działaniu___
Program pokerowy Smitha _______
7.3.1. Wyniki osiągnięte przez program LS-1 Inne wczesne próby z systemami GBMI_____
7.4.1. Poszukiwanie pożywienia i unikanie trucizn
7.4.2. Koordynacja systemu EYE-EYE_________
7.4.3. System klasyfikujący ANIMAT___________
7.5.
7.4.4. System klasyfikujący do sterowania gazociągiem Przegląd wybranych zastosowań __________________
_277
_278 _279 _281 _283 _286
_290 _292 _292 _297 _300 _304 _308
7.5.1. BOOLE: System klasyfikujący uczy się trudnej funkcji boolowskiej_________________________________
7.5.2. Równoległe sieci semantyczne na bazie klasyfikatorów: system CL-ONE _______________________________
7.6. 7.7. 7.8.
7.5.3. Przetwarzanie genetyczne programów sekwencyjnych: JB i TB
Podsumowanie .___________________________________________
Zadania__________________________________________________
Ćwiczenia komputerowe ____________________________________
_308
_312 _317 _320 _322 _323
Rozdział 8. Rzut oka wstecz i przed siebie
_324
Dodatek A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa
____________________________
A.1. Reguła iloczynu
A.2. Permutacje ___
A.3. Kombinacje ___
.329
_329 _330 _331
#15
A.4. Wzór dwumianowy.
A.5. Zdarzenia_______
A.6. A.7. A.8. A.9.
Aksjomaty prawdopodobieństwa _ Przypadek jednakowych szans _ Prawdopodobieństwo warunkowe Rozbicia zdarzeń ____________
A.10. Reguła Bayesa __________________
A.11. Zdarzenia niezależne _____________
A.12. Rozkład dwumianowy _____________
A.13. Wartość oczekiwana zmiennej losowej
A.14. Twierdzenia graniczne _____________
A.15. Podsumowanie __________________
A.16. Zadania _______________________
_332 _333 _334 _336 _337 _338 _339 _339 _340 _340 _341 _341 _341
Dodatek B Dodatek C Dodatek D
Program SGA
Program SCS
_343 _352
Transformacja współczynników partycyjnych i jej zastosowanie w problemie doboru kodu
_______________________________375
D.1. Transformacja współczynników partycyjnych
D.2. Przykład: f(x) = x2 na trzech bitach _______
D.3. Interpretacja współczynników partycyjnych __
D.4. Zastosowanie współczynników partycyjnych do analizy problemów
D.5. Konstruowanie problemów AG-zwodniczych za pomocąwspółczynników
_376 _377 _378
_379
D.6.
D.7. Zadania .
D.8. Ćwiczenia
_380 _381 _381 _382
Bibliografia
Skorowidz
Skorowidz identyfikatorów
rzeczowy
_383 _404 _407
Co to są algorytmy genetyczne? ______________________
Odporność tradycyjnych metod optymalizacji i poszukiwania . Cele optymalizacji__________________________________
Czym różnią się algorytmy genetyczne od tradycyjnych metod? Elementarny algorytm genetyczny_________________________
1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8.
1.9. Nieco żargonu
1.10. Podsumowanie
1.11. Zadania _____
Algorytmy genetyczne w działaniu - symulacja odręczna____
Ziarno optymalizacyjnego mtyna - podobieństwa strukturalne Schematy _________________________________________
1.12. Ćwiczenia komputerowe
.17
_17
_22
_23
_26
.32
_36
_39 _41 _42
Rozdział 2. Podstawy matematyczne algorytmów genetycznych
2.1. 2.2. 2.3. 2.4. 2.5. 2.6.
2.7. 2.8.
Kto przetrwa, a kto zginie? Podstawowe twierdzenie_____________
Przetwarzanie schematów na żywo: symulacja odręczna po raz wtóry . Zagadnienia dwu- i ^-ramiennego bandyty______________________
Ile schematów bierze efektywny udział w przetwarzaniu? Hipoteza cegiełek________________________________
Minimalny problem zwodniczy 2.6.1. MDP: analiza_________
2.6.2. MDP: wyniki symulacyjne _____________________________
Jeszcze o schematach: wzorce podobieństwa jako hiperpłaszczyzny . Podsumowanie ___________________________________________
_44
_45 _50 _53 _57 _59 _63 _66 _68 _70 _71
#12
2.9. Zadania ____________
2.10. Ćwiczenia komputerowe
_72 _73
Rozdział 3. Implementacja komputerowa algorytmu genetycznego
3.1. Struktury danych _________________________________
_75
Reprodukcja, krzyżowanie, mutacja . Czas reprodukcji, czas krzyżowania . Program główny ______________
3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8.
3.9. Standardowa metoda kodowania dla zadań wieloparametrycznych
3.10. Dyskretyzacja _______________________________________
3.11. Problem więzów______________________________________
3.12. Podsumowanie ______________________________________
3.13. Zadania ___________________________________________.
3.14. Ćwiczenia komputerowe ________________________________
Czy wszystko działa jak należy?_______________
Przekształcenie funkcji celu w funkcję przystosowania .
Skalowanie przystosowania ___________________
Metody kodowania __________________________
_76 _78 _81 _83 _84 _90 _91 _94 _97 _99 _100 _101 .102 _103
Rozdział 4. Niektóre zastosowania algorytmów genetycznych
4.1. Powstanie algorytmów genetycznych_______________
.104
_104
4.2.
Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych 107
4.2.1. Bagley i adaptacyjny program gry w sześć pionków____________107
Rosenberg i symulacja żywej komórki___________________
Cavicchio i rozpoznawanie postaci ____________________
4.2.2. 4.2.3. 4.2.4.
108 110
Weinberg, symulacja komórki i algorytm genetyczny
4.3. 4.4. 4.5. 7 metapr)7inmu 113
4 ? F, Hnllstifin i nptymali7aqa funknji 114
4,?. R, Frant? i efekt pn7ynyjny 11fi
4.?. 7. Bnfiwnrth, Fnn i 7eigler - geny n r7er7ywiste" 117
4 9 R Rnv i planowanie ewolucyjne 11ft
4 9 P Inno ewolucyjne techniki nptymali7anji 190
42 10 Fogel, Owens i Walsh - Programowanie ewolucyjne 190
De .long i optymali7arja funknji 199
l lr(nskr>na lenia terhnir:7ne 13fi
441 Alternatywne metnrly selekrji 13fi
449 Merhani7imy skalowania 138
4 4 3 Nadawanie rang 14f>
Aktualne 7astnsnwania algnrytmńw genetycznych 141
451 Ontvmali/a<^Ha nirnriąnn naynwenn 144
4.5.2. Optymalizacja strukturalna konstrukcji przy użyciu algorytmu genetycznego ___________________________________
.151
4.5.3. Obróbka medycznych obrazów rentgenowskich za pomocą algorytmu
genetycznego _________________________________________153
Spis treści
4.5.4. lterowany dylemat więźnia
4.6. Podsumowanie ______________
4.7. Zadania_____________________
4.8. Ćwiczenia komputerowe
_ 13
.155 _157 _158 _160
Rozdział 5. Techniki i operacje zaawansowane
.161
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
5.2.
5.3.
5.4.
5.5. 5.6.
_162
5.1.1. Diploidalność i dominowanie w algorytmach genetycznych -zarys historyczny ___________________________________________
.164
5.1.2. Analiza diploidalności i dominowania w algorytmach genetycznych__172
5.1.3. Implementacja modelu triallelicznego_________________________176
Inwersja i inne operacje rekonfiguracji_____________________________178
5.2.1. Operacje rekonfiguracji w algorytmach genetycznych. Zarys
historyczny _________________________________________
5.2.2. Teoria operacji rekonfigurujących Inne mikrooperacje__________________
5.3.1. Segregacja, translokacja i s*ruktury wielochromosomowe .
5.3.2. Duplikacja i delecja _____________________________
5.3.3. Determinacja płci i zróżnicowanie płciowe Nisze i specjacja_________________________
5.4.1. Teoria nisz i gatunków_________________________
5.4.2. Metody niszowe w poszukiwaniach genetycznych____
5.4.3. Bariery reprodukcyjne w poszukiwaniach genetycznych .
Optymalizacja wielokryterialna_________________________
Techniki oparte na wiedzy ___________________________
5.6.1. Hybrydyzacja _________________________________
_182 _190 _194 _194 _195 _196 _200 _202 _205
5.6.2. Operacje wzbogacone wiedzą.
5.6.3. Metody aproksymacyjne ____
_212 _217 _218 _220
5.7. 5.8. 5.9. 5.10. Ćwiczenia komputerowe
Algorytmy genetyczne a architektura równoległa .
Podsumowanie _________________________
Zadania_________________________________
_224 _228 _229 _231
Rozdział 6. Wprowadzenie do genetycznych systemów uczących się
_232
6.1. 6.2. 6.3. 6.4. 6.5. 6.6.
Skąd wzięty się systemy GBMI___________
Czym jest system klasyfikujący?_________
Układ przetwarzania komunikatów_______
Układ oceniający: Algorytm bucket brigade . Algorytm genetyczny__________________
_233
_236
System klasyfikujący w Pascalu___
6.6.1. Strukturydanych___________
6.6.2. Układ wykonawczy_________
6.6.3. Algorytm przyznawania ocen
_240 _245 _246 _246 _248 _249
14
Spis treści
6.6.4. Poszukiwanie genetyczne w systemie klasyfikującym .
6.6.5. A więc gdzie problem?_______________________
6.6.6. Odczytaj komunikat, podejmij działanie .
6.6.7. Zwycięzca bierze wszystko _________
6.6.8. Program główny__________________
6.7. Wyniki eksperymentów z systemem SCS
6.7.1. Parametry środowiska i systemu__
6.7.2. Reguty idealne i ,,dywersanci"____
6.7.3. Hierarchia domniemań _________
6.7.4. Start od zera: Model Tabula rasa
Podsumowanie ____________________
Zadania___________________________
6.8. 6.9. 6.10. Ćwiczenia komputerowe
_252 _255 _258 _260 _261 _262 _262 _262 _265 _271 _273 _274 _276
Rozdział 7. Zastosowania genetycznych systemów uczących się
7.1. Początki systemów GBML ______________________
_277
7.1.1. Schematy i ich procesory .
7.1.2. Język przekazu _______
7.2.
7.3.
7.4.
Pierwszy system klasyfikujący CS-1
7.2.1. System CS-1 w działaniu___
Program pokerowy Smitha _______
7.3.1. Wyniki osiągnięte przez program LS-1 Inne wczesne próby z systemami GBMI_____
7.4.1. Poszukiwanie pożywienia i unikanie trucizn
7.4.2. Koordynacja systemu EYE-EYE_________
7.4.3. System klasyfikujący ANIMAT___________
7.5.
7.4.4. System klasyfikujący do sterowania gazociągiem Przegląd wybranych zastosowań __________________
_277
_278 _279 _281 _283 _286
_290 _292 _292 _297 _300 _304 _308
7.5.1. BOOLE: System klasyfikujący uczy się trudnej funkcji boolowskiej_________________________________
7.5.2. Równoległe sieci semantyczne na bazie klasyfikatorów: system CL-ONE _______________________________
7.6. 7.7. 7.8.
7.5.3. Przetwarzanie genetyczne programów sekwencyjnych: JB i TB
Podsumowanie .___________________________________________
Zadania__________________________________________________
Ćwiczenia komputerowe ____________________________________
_308
_312 _317 _320 _322 _323
Rozdział 8. Rzut oka wstecz i przed siebie
_324
Dodatek A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa
____________________________
A.1. Reguła iloczynu
A.2. Permutacje ___
A.3. Kombinacje ___
.329
_329 _330 _331
#15
A.4. Wzór dwumianowy.
A.5. Zdarzenia_______
A.6. A.7. A.8. A.9.
Aksjomaty prawdopodobieństwa _ Przypadek jednakowych szans _ Prawdopodobieństwo warunkowe Rozbicia zdarzeń ____________
A.10. Reguła Bayesa __________________
A.11. Zdarzenia niezależne _____________
A.12. Rozkład dwumianowy _____________
A.13. Wartość oczekiwana zmiennej losowej
A.14. Twierdzenia graniczne _____________
A.15. Podsumowanie __________________
A.16. Zadania _______________________
_332 _333 _334 _336 _337 _338 _339 _339 _340 _340 _341 _341 _341
Dodatek B Dodatek C Dodatek D
Program SGA
Program SCS
_343 _352
Transformacja współczynników partycyjnych i jej zastosowanie w problemie doboru kodu
_______________________________375
D.1. Transformacja współczynników partycyjnych
D.2. Przykład: f(x) = x2 na trzech bitach _______
D.3. Interpretacja współczynników partycyjnych __
D.4. Zastosowanie współczynników partycyjnych do analizy problemów
D.5. Konstruowanie problemów AG-zwodniczych za pomocąwspółczynników
_376 _377 _378
_379
D.6.
D.7. Zadania .
D.8. Ćwiczenia
_380 _381 _381 _382
Bibliografia
Skorowidz
Skorowidz identyfikatorów
rzeczowy
_383 _404 _407