ebook Algorytmy genetyczne. Kompendium, t. 1 Tomasz Dominik Gwiazda

Wydawca: Wydawnictwo Naukowe PWN

Rok wydania: 2009

Tom 1, który zapoczątkowuje serię Algorytmy Genetyczne, przedstawia najbardziej istotny dla AG operator – operator krzyżowania. Autor prezentuje w nim ponad 180 operatorów dla problemów kodowanych liczbami binarnymi i rzeczywistymi. Każdy z operatorów przedstawiony jest wedle tego samego, następującego schematu:

¦ Słowa kluczowe – mają pomóc w przeszukiwaniu książki i wzajemnym kojarzeniu prezentowanych w niej operatorów.

¦ Motywacja – wskazanie motywacji leżącej u podstaw opracowania danego operatora.

¦ Źródło – tekst źródłowy wraz ze wskazaniem adresu URL skąd można ten tekst pobrać.

¦ Czytaj także – zalecane dodatkowe teksty wraz z URL’ami, których tematyka jest bezpośrednio związana z omawianym operatorem.

¦ Patrz także – inne operatory, z którymi warto się zapoznać w kontekście danego operatora.

¦ Algorytm – prezentuje w formie pseudokodu omawiany operator, nierzadko w kilku wariantach, ta forma prezentacji operatora w większości przypadków umożliwia natychmiastowe zastosowanie operatora w praktyce.

¦ Komentarze – komentarze do algorytmu lub opis prezentowanego operatora.

¦ Funkcje testowe – lista standardowych funkcji lub problemów testowych, o ile takowe zostały zastosowane w toku eksperymentów z zastosowaniem omawianego operatora.

¦ Porównano z – lista innych operatorów krzyżowania, z którymi porównywany był (w tekście źródłowym) prezentowany operator.

Internetowy serwis autora (www.tomaszgwiazda.pl) oferuje więcej szczegółów, w tym pierwsze 40 stron tomu 1 do pobrania jako dokument PDF.

Spis treści ebooka Algorytmy genetyczne. Kompendium, t. 1

1. Wstęp 9
2. Krótko o algorytmach genetycznych 13
Historia 13
Kanoniczna postać AG 14
Generowanie populacji początkowej 15
Ocena populacji 18
Selekcja rodziców 21
Operatory genetyczne 23
Kreowanie nowej populacji 27
Pełna postać kanonicznego AG 31
Literatura 39
3. Standardowe operatory krzyżowania 41
Krzyżowanie jednopunktowe (1-Point Crossover ) 41
Krzyżowanie wielopunktowe (k-Point Crossover) 41
Krzyżowanie tasujące (Shuffle Crossover) 43
Krzyżowanie zastępujące (Reduced Surrogate Crossover) 44
Krzyżowanie równomierne (Uniform Crossover ) 45
Krzyżowanie niszczące (Heuristic Uniform Crossover/Highly Disruptive Crossover) 46
Krzyżowanie uśredniające (Average Crossover) 47
Krzyżowanie ziarniste (Discrete Crossover) 48
Krzyżowanie płaskie (Flat Crossover) 48
Krzyżowanie heurystyczne-1 (Heuristic Crossover /Intermediate Crossover) 49
Krzyżowanie mieszające (Blend Crossover) 50
4. Operatory krzyżowania dla problemów kodowanych liczbami binarnymi 53
Krzyżowanie powielające podobieństwa (Random Respectful Crossover) 53
Krzyżowanie oparte na dominacji (Masked Crossover) 55
Krzyżowanie wyboru operatora (1bit Adaptation Crossover) 57
Krzyżowanie wielowymiarowe (Multivariate Crossover) 61
Krzyżowanie homologiczne (Homologous Crossover) 63
Krzyżowanie zliczające-1 (Count-preserving Crossover-1) 65
Krzyżowanie elitarne (Elitist Crossover) 67
Krzyżowanie skanujące (Scanning Crossover) 68
Krzyżowanie częściowe (Partial Copy Crossover) 71
Krzyżowanie nierównomierne oparte na wiedzy (Knowledge-Based Nonuniform Crossover) 72
Krzyżowanie średnicą (Circle-ring Crossover) 74
Wystarczająca wymiana (Sufficient Exchanging) 75
Ewolucja powiązań (Linkage Evolving Genetic Operator) 77
Krzyżowanie łańcuchami-1 (2N-parent Parameter Wise Crossover) 79
Krzyżowanie diagonalne (Diagonal Crossover) 81
Krzyżowanie pulą genów-1 (Gene Pool Crossover-1) 83
Krzyżowanie hierarchiczne (Hierarchical Crossover) 84
Krzyżowanie iloczynem/sumą logiczną (Randomized and/or Crossover) 88
Krzyżowanie jednokierunkowe (Simple Conjugation Operator) 89
Strategia wyboru operatora-1 (Adaptive Strategies of Mixing Crossovers) 91
Krzyżowanie ortogonalne-1 (Orthogonal Crossover) 93
Krzyżowanie mikrobiologiczne (Microbial Crossover) 95
Krzyżowanie selektywne-1 (Selective Crossover-1) 98
Krzyżowanie powiązań (Exchange Crossover/ Linkage Crossover) 100
Krzyżowanie skanujące wielopłciowe (Multi Sexual Scanning Crossover) 101
Krzyżowanie różnicami (Differences-Based Crossover) 103
Krzyżowanie kumulujące (Fusion Crossover) 105
Krzyżowanie wielochromosomowe (Multiple Chromosomes Crossover) 106
Krzyżowanie ograniczone (Restricted Crossover) 108
Krzyżowanie selektywne-2 (Selective Crossover-2) 110
Samokrzyżowanie (Self Crossover) 112
Krzyżowanie tnące (Multi-cut Crossover) 115
Transpozycja (Transposition Operator) 116
Transpozycja z selekcją turniejową (Tournament Based Transposition Operator) 120
Dominujący splot (Dominant Splice/Symbiotic Combination) 126
Krzyżowanie zdysocjowane (Dissociated Crossover) 127
Krzyżowanie spontaniczne (Spontaneous Crossover) 129
Krzyżowanie metodą bisekcji (Binary Search Point Crossover) 131
Krzyżowanie stabilne (Fixed Crossover) 134
Powielanie z lokalnym dostrajaniem (Common Features/Random Sample Climbing Crossover) 135
Transpozycja bezpłciowa (Asexual Transposition) 137
Krzyżowanie różnic (Disrespectful Crossover) 141
Krzyżowanie dwupunktowe asymetryczne-1 (Asymmetric Two-point Crossover) 143
Krzyżowanie dwupunktowe asymetryczne-2 (Variation of Asymmetric Two-point Crossover) 145
Najlepsza kombinacja (Best Combinatorial Crossover) 147
Związki mieszane (Hybridization Crossover) 148
Strategia wyboru operatora-2 (Mixed Crossover) 149
Krzyżowanie łańcuchami-2 (Direct Design Variable Exchange Crossover) 151
Poszukiwanie schematów (Best Schema Crossover) 153
Krzyżowanie chromosomów o zmiennej długości (Variable Length Genomes Crossover) 155
Krzyżowanie trójosobnicze (Three-Parent Crossover) 159
Krzyżowanie częściowo mieszające (Partially Randomized Crossover) 161
Krzyżowanie nierównomierne oparte na statystykach (Statistic-Based Adaptive Non-Uniform Crossover) 162
Krzyżowanie zbiorem operatorów-1 (Multiple Crossover Operators-1) 164
Krzyżowanie z decydentem (Half Sibling and a Clone) 167
Adaptacja liczby punktów krzyżowania i mutacji (Adaptive Number of Crossover Points) 168
Kooperacja/rywalizacja płci (Sexual Selection Crossover) 170
Tasowanie chromosomów (Chromosome Shuffling) 172
Krzyżowanie ortogonalne-2 (Orthogonal Latin Mutli-Parent Crossover) 174
Krzyżowanie z punktową mutacją (Different Location Crossover) 176
Strategia wyboru operatora-3 (Combined Balanced Crossover) 177
Krzyżowanie wielokrotne-1 (Hybrid 1-Point Crossover) 180
Krzyżowanie zliczające-2 (Count-preserving Crossover-2) 182
Krzyżowanie ważone przystosowaniem-1 (Fitness Weighted Crossover (Binary)) 185
Adaptacja prawdopodobieństwa-1 (Adaptive Probability Crossover-1) 187
Maksymalizacja podobieństw (Schema-Based Crossover) 189
5. Operatory krzyżowania dla problemów kodowanych liczbami rzeczywistymi 193
Krzyżowanie linearne-1 (Linear Crossover) 193
Krzyżowanie heurystyczne-2 (Heuristic Crossover2) 194
Krzyżowanie proste (Simple Crossover) 196
Krzyżowanie pojedyncze arytmetyczne (Single Arithmetical Crossover) 197
Krzyżowanie arytmetyczne (Arithmetical Crossover, Intermediate Crossover2, Linear Crossover, Guaranteed Average Crossover, Convex Crossover ) 199
Krzyżowanie wstawiające (Injection Crossover) 201
Adaptacja prawdopodobieństwa-2 (Adaptive Probability Crossover-2) 203
Krzyżowanie linearne-2 (Linear BGA Crossover) 205
Krzyżowanie z simpleksem-1 (Simplex Crossover) 207
Krzyżowanie linearne-3 (Simulated Binary Crossover) 209
Krzyżowanie ze zbiorami rozmytymi-1 (Fuzzy Crossover) 211
Krzyżowanie ze zbiorami rozmytymi-2 (Fuzzy Connectives Based Crossover) 213
Krzyżowanie z wspinaczką-1 (Crossover Hillclimbing) 215
Krzyżowanie przypadkowe (Random Crossover) 217
Krzyżowanie łańcuchami-3 (Variable Length Segments Crossover) 218
Krzyżowanie uśredniające zaburzone (Unfair Average Crossover) 221
Krzyżowanie równomierne ciągłe (Continuous Uniform Crossover) 223
Krzyżowanie geometryczne (Geometrical Crossover) 225
Krzyżowanie sferyczne (Sphere Crossover) 227
Krzyżowanie z wektorem różnic (Differential Evolution Crossover) 229
Krzyżowanie z simpleksem-2 (Simplex Crossover-2) 231
Krzyżowanie wielokrotne-2 (Multiple Crossover Per Couple) 233
Krzyżowanie pulą genów-2 (Gene-Pooling Crossover-2) 235
Krzyżowanie środkiem masy-1 (Center of Mass Crossover) 237
Krzyżowanie wieloosobniczne-1 (Multi-parent Feature-wise Crossover) 238
Krzyżowanie z przystosowaniem częściowo separowalnym (Partially Separable Crossover) 240
Krzyżowanie drążące (Seed Crossover) 242
Niewypukła wieloosobnicza kombinacja liniowa (Non-convex Linear Combination of Multiple Parents) 243
Krzyżowanie kierunkowe (Direction-Based Crossover) 244
Krzyżowanie z pochodną (Derivative-Based Crossover) 246
Krzyżowanie z rankingiem (Rank Based Crossover) 247
Krzyżowanie paraboliczne-1 (Parabolic Crossover) 249
Krzyżowanie kierowane (Guided Crossover) 251
Krzyżowanie wielokrotne-3 (Multiple Crossover on Multiple Parents) 253
Krzyżowanie z simpleksem-3 (Simplex Crossover-3) 255
Krzyżowanie jednorodne (Uniform Design Crossover) 257
Krzyżowanie środkiem grawitacji (Center of Gravity Crossover) 258
Krzyżowanie jednopunktowe uśrednione (1-point Average Crossover) 260
Krzyżowanie dwupunktowe uśrednione (Messy Average Crossover) 261
Adaptacja prawdopodobieństwa-3 (Adaptive Probability Crossover-3) 263
Krzyżowanie z wspinaczką-2 (Site-Specific Crossover) 264
Krzyżowanie z przystosowaniem nieseparowalnym (BLX Principal Component Analysis and Independent Component Analysis) 269
Krzyżowanie ortogonalne z kwantyzacją (Orthogonal Crossover with Quantization) 271
Krzyżowanie równomierne gaussowskie (Gaussian Uniform Crossover) 272
Krzyżowanie pulą genów-3 (Set-Oriented Crossover) 274
Adaptacja prawdopodobieństwa-4 (Adaptive Probability Crossover-4) 275
Adaptacja prawdopodobieństwa-5 (Adaptive Probability Crossover-5) 278
Krzyżowanie pozycyjne (Position Crossover) 281
Krzyżowanie najlepszy-najlepszy (Best-Best Crossover) 283
Adaptywne krzyżowanie w losowej liczbie punktów (Adaptive Q-rand Point Crossover) 285
Krzyżowanie w losowej liczbie punktów (Q-rand Point Crossover) 286
Krzyżowanie wielokrotne-4 (Multiple Crossover) 289
Krzyżowanie arytmetyczne poprawione-1 (Improved Arithmetical Crossover) 291
Translokacja wzajemna (Reciprocal Translocation Operator) 293
Krzyżowanie arytmetyczne poprawione-2 (Hybrid Arithmetical Crossover) 298
Krzyżowanie wielokrotne-5 (Generation of Multiple Descendants and Selection of the Two Best) 300
Krzyżowanie w otoczeniu-1 (Adaptive Neighborhood-based Multi-parent Crossover) 302
Krzyżowanie ułomne (Imperfect Crossover) 304
Adaptacja prawdopodobieństwa-6 (Adaptive Probability Crossover-6) 307
Krzyżowanie zbiorem operatorów-2 (Multiple Crossover Operators-2) 309
Krzyżowanie samoadaptacyjne (Heuristic-Based Self -Adapting Crossover) 311
Krzyżowanie ze zmiennymi typami danych (Mixed Variable Crossover) 315
Krzyżowanie cylindryczne (Curved Cylinder Crossover) 319
Krzyżowanie wymienne (Exchanging Information Crossover) 322
Krzyżowanie arytmetyczne poprawione-3 (Real-Biased Crossover) 323
Krzyżowanie Taguchiego-1 (Taguchi Crossover/Main Effect Orthogonal Crossover) 325
Krzyżowanie ortogonalne z interakcją (Interaction Effect Orthogonal Crossover) 328
Krzyżowanie różnorodne (Diverse Crossover) 331
Krzyżowanie w otoczeniu-2 (Parent Centric BLX-? Crossover) 333
Krzyżowanie Taguchiego-2 (Taguchi Crossover-2) 335
Krzyżowanie w grupie (Extended GA Crossover) 337
Krzyżowanie jednogenowe (Single Gene Crossover) 339
Krzyżowanie ważone przystosowaniem-2 (Fitness Weighted Crossover (Real)) 341
Krzyżowanie zależności (Inheritance Crossover) 343
Adaptacja prawdopodobieństwa dla genu (Adaptive Probability of Gene Crossover) 345
Adaptacja prawdopodobieństwa-7 (Adaptive Probability Crossover-7) 346
Krzyżowanie ze znormalizowanym dystansem przystosowania (Normalized Fitness Crossover) 348
Krzyżowanie z kontrolą zawartości (Controlled Content Crossover) 350
Krzyżowanie środkiem masy-2 (Center of Mass Crossover-2) 353
Krzyżowanie różnicujące (Parent Differentiation Crossover) 355
Metoda przełączająca (Improved Crossover and Mutation) 356
Adaptacja prawdopodobieństwa-8 (Adaptive Probability Crossover-8) 358
Krzyżowanie królewskie (King Strategy Crossover) 361
Krzyżowanie pulą genów-4 (Gene-Pooling Crossover-4) 362
Krzyżowanie sterowane przystosowaniem (Fitness Guided Crossover) 364
Krzyżowanie w otoczeniu-3 (Continuous Adaptive Culture Model Crossover) 365
Krzyżowanie paraboliczne-2 (Fitness-Based Parabolic Crossover) 367
Krzyżowanie wieloosobnicze-2 (Hybrid Panmictic (multi-parent) Crossover) 368
6. Operatory statystyczne 371
UNDX – Unimodal Normal Distribution Crossover 371
MM-B – Factorized Distribution Method 372
PCX – Parent-Centric Crossover 372
MM-B – Marginal Histogram-Based Method 372
EDX – Extrapolation Directed Crossover 373
TDX – Trimodal Distribution Crossover 373
CIXL2 – Confidence Interval Based Crossover 373
GAQPR – Quantum Probability Representation-Based Method 374
LUNDX-m – Latent Variable Crossover 374
Indeks słów kluczowych, autorów i funkcji testowych 375