Wykłady z algorytmów ewolucyjnych

Jarosław Arabas

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

83-204-2970-6

DOI:

Wydawnictwo:

Wydawnictwo WNT

Rok wydania:

2004

Liczba stron:

286

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Arabas, Jarosław. Wykłady z algorytmów ewolucyjnych. Red. . Warszawa: Wydawnictwo WNT, 2004, 286 s. ISBN 83-204-2970-6

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Arabas, J.

T1 Wykłady z algorytmów ewolucyjnych

PB Wydawnictwo WNT

PP Warszawa

YR 2004

SN 83-204-2970-6

Bibliografia BibTex:

@Book{ 438, author = "Arabas, Jarosław", editor = "", title = "Wykłady z algorytmów ewolucyjnych", publisher = "Wydawnictwo WNT", year = "2004", address = "Warszawa", isbn = "83-204-2970-6" }

Bibliografia endNote:

TY - BOOK

AU - Arabas, Jarosław

ED -

TI - Wykłady z algorytmów ewolucyjnych

PB - Wydawnictwo WNT

CY - Warszawa

PY - 2004

SN - 83-204-2970-6

ER -

Netografia (standard APA):

Arabas, Jarosław. Wykłady z algorytmów ewolucyjnych [baza danych online] Warszawa: Wydawnictwo WNT, 2004 [dostęp: 05 05 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/wyklady-z-algorytmow-ewolucyjnych-jaroslaw-arabas-438.

programowanie

Książka jest poświęcona algorytmom ewolucyjnym, czyli technikom przeszukiwania inspirowanym przyrodą. Składa się z trzech części. W pierwszej autor wprowadza czytelnika w krąg podstawowych schematów algorytmów ewolucyjnych: algorytmów genetycznych...

Więcej

ISBN/ISSN:

83-204-2970-6

DOI:

Wydawnictwo:

Wydawnictwo WNT

Rok wydania:

2004

Liczba stron:

286

XML:ISBN/ISSN:

ONIX MARC21

Wprowadzenie10
WYKŁAD 1. W poszukiwaniu optimum21
1.1. Wstęp21
1.2. Rodzaje zadań22
1.2.1. Właściwości funkcji celu23
1.2.2. Ograniczenia funkcji celu28
1.2.3. Znaczeni liczby wymiarów30
1.3. Metody optymalizacji32
1.4. Jak oceniać algorytmy optymalizacji35
1.4.1. Dokładność przybliżenia rozwiązania35
1.4.2. Odporność36
1.4.3. Koszt symulacji37
1.5. Metody eliminowania ograniczeń funkcyjnych38
1.5.1. Metody transformacji zmiennych niezależnych39
1.5.2. Metody funkcji kary42
1.6. Zadania wielokryterialne47
1.6.1. Sformułowanie zadania47
1.6.2. Skalaryzacja zadania48
1.7. Środowisko dynamiczne52
1.7.1. Kryteria oceny algorytmu53
1.7.2. Rodzaje zmian środowiska53
1.8. Uwagi bibliograficzne54
1.7.3. Adaptacja do zmian środowiska54
1.9. Pytania i ćwiczenia55
WYKŁAD 2. Podstawowe typy algorytmów ewolucyjnych57
2.1. Algorytmy genetyczne57
2.1.1. Prosty algorytm genetyczny57
2.1.2. Schematy64
2.1.3. Symulacja działania algorytmu genetycznego68
2.2. Strategie ewolucyjne75
2.2.1. Strategia (1+1)75
2.2.2. Strategia (u + ?)77
2.2.3. Strategia (u, ?)79
2.2.4. Analiza działania strategii80
2.2.5. Symulacja działania strategii82
2.3. Programowanie ewolucyjne84
2.3.1. Schemat programowania86
2.3.2. Operatory mutacji87
2.4. Programowanie genetyczne88
2.4.1. Programy, które powstają samoczynnie88
2.4.2. Kodowanie drzewiaste89
2.4.3. Operatory genetyczne90
2.5. Uwagi bibliograficzne93
2.6. Pytania i ćwiczenia94
WYKŁAD 3. Zarządzanie populacją95
3.1. Ogólny schemat algorytmu ewolucyjnego95
3.2. Eksploracja i eksploatacja97
3.2.1. Nacisk selektywny w prostej metodzie poszukiwań losowych98
3.3. Jak oceniać algorytmy ewolucyjne102
3.3.1. Metoda testowania i sposób prezentacji wyników102
3.4. Metody selekcji104
3.4.1. Reprodukcja i sukcesja104
3.4.2. Reprodukcja proporcjonalna (ruletkowa)104
3.4.3. Zmodyfikowana reprodukcja proporcjonalna107
3.4.4. Reprodukcja rangowa110
3.4.5. Reprodukcja turniejowa113
3.4.6. Reprodukcja progowa117
3.4.7. Sukcesja z całkowitym zastępowaniem119
3.4.8. Sukcesja z częściowym zastępowaniem119
3.4.9. Sukcesja elitarna120
3.5. Kryteria zatrzymania algorytmu125
3.5.1. Monitorowanie rozwiązań generowanych przez algorytm126
3.5.2. Monitorowanie zdolności eksploracyjnych129
3.6. Uwagi bibliograficzne132
3.7. Pytania i ćwiczenia133
WYKŁAD 4. Kodowanie i operatory genetyczne134
4.1. Rola kodowania i operatorów genetycznych134
4.2. Jak dobierać kodowanie i operatory genetyczne135
4.2.1. Pożądane cechy kodowania chromosomów135
4.2.2. Metryki w przestrzeni genotypu i fenotypu136
4.8. Metody modyfikacji zasięgu operatorów genetycznych138
4.2.3. Pożądane cechy operatorów genetycznych138
4.3. Warianty operatorów krzyżowania140
4.4. Przegląd metod krzyżowania142
4.4.1. Operatory krzyżowania wymieniającego142
4.4.2. Operatory krzyżowania uśredniającego146
4.4.3. Różnice między operatorami krzyżowania wymieniającego i uśredniającego148
4.5. Operator inwersji149
4.6. Operatory mutacji152
4.6.1. Mutacja dla kodowania binarnego152
4.6.2. Mutacje przeznaczone do optymalizacji w Rn152
4.7. Eksploracja i eksploatacja a operatory genetyczne154
4.7.1. Czy ważniejszym operatorem jest krzyżowanie, czy mutacja?154
4.7.2. Zasięg operatorów155
4.8.1. Modyfikacje zasięgu mutacji158
DODATEK B. Niektóre funkcje testowe159
4.8.2. Modyfikacje zasięgu krzyżowania163
4.9. Krzyżowanie wieloosobnicze166
4.10. Zarządzanie wieloma operatorami genetycznymi170
4.11. Czy warto stosować kodowanie binarne problemów numerycznych?174
4.12.Uwagi bibliograficzne179
4.13.Pytania i ćwiczenia180
WYKŁAD 5. Zapobieganie przedwczesnej zbieżności182
5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych182
5.1.1. Efekt Baldwina i ewolucja lamarkowska184
5.2. Czas życia osobników w populacji bazowej187
5.2.1. Limitowanie maksymalnego czasu życia187
5.2.2. Selekcja sterowana czasem życia189
5.3. Optymalizacja wielomodalna195
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej196
5.4.1. Wprowadzanie dodatkowego czynnika losowego197
5.4.2. Osłabianie konkurencyjności w ramach selekcji198
5.4.3. Ograniczanie zasięgu selekcji200
5.4.4. Preselekcja203
5.4.5. Deformacje funkcji przystosowania w otoczeniu maksimum lokalnego205
5.5. Inicjacja populacji bazowej207
5.5.1. Posiew nierównomierny211
5.5.2. Znaczenie generatora liczb pseudolosowych212
5.6. Znaczenie liczności populacji bazowej213
5.7. Równoległość w algorytmach ewolucyjnych218
5.7.1. Implementacje równoległe219
5.7.2. Algorytmy koewolucyjne223
5.8. Uwagi bibliograficzne226
5.9. Pytania i ćwiczenia228
WYKŁAD 6. Uwzględnianie specyfki problemu230
6.1. Wykorzystanie skomplikowanych struktur danych230
6.1.1. Zadania o ustalonej liczbie parametrów230
6.1.2. Zadania o nie ustalonej liczbie parametrów237
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń242
6.2.1. Kodowanie specjalizowane i operatory genetyczne242
6.2.2. Algorytmy naprawy244
6.3. Modyfikacje algorytmu ewolucyjnego uwzględniające zadania wielokryterialne245
6.3.1. Reprodukcja oparta na dominacji246
6.3.2. Podejście koewolucyjne247
6.4. Algorytm ewolucyjny w środowisku dynamicznym248
6.4.1. Informacja o zajściu zmiany249
6.4.2. Metody adaptacji249
6.4.3. Pamięć na poziomie populacji250
6.4.4. Pamięć na poziomie osobnika250
6.5. Uwagi bibliograficzne252
Uwagi końcowe254
DODATEK A. Oznaczenia i symbole256
A.1. Symbole łacińskie256
A.2. Symbole greckie257
A.3. Oznaczenia inne257
A.4. Zasady indeksowania i doboru czcionek258
B.1. Zadania ciągłe259
B.2. Zadania dyskretne260
DODATEK C. Wartości parametrów uznawane za optymalne262
DODATEK D. Elementy matematyki264
D.1. Miary różnorodności264
D.2. Rozkłady zmiennych losowych266
DODATEK E. Oprogramowanie gabi267
E.1. Założenia ogólne267
E.2. Opis funkcjonalny oprogramowania268
E.3. Sposób implementacji269
E.4. Pliki konfiguracyjne270
E.5. Sposób działania oprogramowania271
E.5.1. Funkcja main271
E.5.2. Funkcja petlaGlowna271
E.5.3. Funkcja genetyka272
E.5.4. Funkcja reprodukcja273
E.6. Rozbudowa oprogramowania273
E.6.1. Plik algorytm.c273
E.6.2. Plik genetyka.c274
E.6.3. Plik główny.c275
E.6.4. Plik losowe.c275
E.6.5. Plik monitor.c275
E.6.6. Plik ogranicz.c276
E.6.7. plik osobnik.c276
E.6.8. Plik pop.c276
E.6.9. Plik raporty.c276
E.6.10. Plik selekcja.c277
E.6.11. Plik stop.c277
E.6.12. Plik wewy.c277
E.6.13. Plik zadanie.c277
Literatura278
Skorowidz284

J.Arabas"Wykładyzalgorytmówewolucyjnych",Warszawa2004,wyd.II,ISBN83-204-2970-6©byWNT

1.Wposzukiwaniuoptimum...

Zadaniaoptymalizacjimogąbyćrozwiązywanemetodami

analitycznymilubnumerycznymi.Wykorzystaniemetodpierw-

szegorodzajujestjednakmożliwetylkowprzypadkuklasyfunkcji

przedstawionychanalitycznie.Najczęściejjednakrzeczywistepro-

blemysąnatyleskomplikowane,żealboanalitycznapostaćunie-

możliwialubznacznieutrudniaznalezienieminimum,albofunk-

cjacelujestwynikiemsymulacjikomputerowej,takwięczada-

niemożebyćrozwiązywanenumeryczniepoprzezprzeszukiwanie

zbiorudopuszczalnegowposzukiwaniujaknajlepszegopunktu.

1.2.Rodzajezadań

Wzależnościodprzestrzeniposzukiwań,mówimyoróżnychro-

dzajachoptymalizacji.

Woptymalizacjiparametrycznejzakładasię,żepunkt

x∈Ujestwektoremzmiennychniezależnych,zktórychkażda

przyjmujepewnąwartość.Oznaczato,żeprzestrzeńprzeszuki-

wańjestiloczynemkartezjańskimzbiorówwartościzmiennych

niezależnych.Wzależnościodtyputychzbiorów,dokonujesię

klasyﬁkacjizadańoptymalizacjiparametrycznej.

Zadaniaciągłecharakteryzująsiętym,żeprzestrzeńprze-

szukiwańjestiloczynemkartezjańskimzbioruliczbrzeczywistych

U=Rn.Wśródzadańoptymalizacjiciągłejwyróżniasięzada-

niawypukłe(gdyzbiórdopuszczalnyifunkcjacelusąwypu-

kłe)izadaniaoptymalizacjiglobalnej(niewypukłafunkcja

celulubzbiórdopuszczalny)*.Ooptymalizacjidyskretnejmó-

wimy,gdywartościzmiennychniezależnychxinależądozbioru

dyskretnego(skończonegolubprzeliczalnego)U=Zn.Wza-

daniachoptymalizacjikombinatorycznejkażdazezmiennych

niezależnychprzyjmujewartośćlogiczną—prawdaalbofałsz,

czyliU=Zn

2.Sąteżprzypadkimieszane—częśćzmiennychnie-

zależnychprzyjmujewartościzezbioruliczbrzeczywistych,część

zaś—całkowitych.

Zbiór(obszar)dopuszczalnyDmożebyćtożsamyzprze-

strzeniąprzeszukiwańU—mówisięwówczasooptymalizacjibez

ograniczeń,wprzeciwnymprzypadku—ooptymalizacjizogra-

niczeniami.

Niewszystkiezadaniasąjednakowotrudne.Stopieńskom-

plikowaniazadaniazależyzarównoodpostacifunkcjicelu,jak

równieżodkształtuzbiorudopuszczalnego.Poniżejscharaktery-

*Zagadnieniaoptymalizacji

zowanokilkanajczęściejwykorzystywanychwłaściwościfunkcji

globalnejomówionowdal-

szejczęściwykładu.

celuizbiorudopuszczalnego.

Brak wyników

Wykłady z algorytmów ewolucyjnych

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra