Algorytmy genetyczne. Kompendium, t. 1

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

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