Algorytmy genetyczne. Kompendium, t. 1

Tomasz Dominik Gwiazda

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-15168-3

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2009

Liczba stron:

384

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Gwiazda, Tomasz Dominik. Algorytmy genetyczne. Kompendium, t. 1. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2009, 384 s. ISBN 978-83-01-15168-3

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Gwiazda, T.D.

T1 Algorytmy genetyczne. Kompendium, t. 1

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2009

SN 978-83-01-15168-3

Bibliografia BibTex:

@Book{ 521, author = "Gwiazda, Tomasz Dominik", editor = "", title = "Algorytmy genetyczne. Kompendium, t. 1", publisher = "Wydawnictwo Naukowe PWN", year = "2009", address = "Warszawa", isbn = "978-83-01-15168-3" }

Bibliografia endNote:

TY - BOOK

AU - Gwiazda, Tomasz Dominik

ED -

TI - Algorytmy genetyczne. Kompendium, t. 1

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2009

SN - 978-83-01-15168-3

ER -

Netografia (standard APA):

Gwiazda, Tomasz Dominik. Algorytmy genetyczne. Kompendium, t. 1 [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2009 [dostęp: 03 07 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/algorytmy-genetyczne-kompendium-t-1-tomasz-dominik-gwiazda-521.

informatyka, programowanie, algorytmy ewolucyjne, algorytmy genetyczne

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 ...

Więcej

ISBN/ISSN:

978-83-01-15168-3

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2009

Liczba stron:

384

XML:ISBN/ISSN:

ONIX MARC21

1. Wstęp10
2. Krótko o algorytmach genetycznych14
Historia14
Kanoniczna postać AG15
Generowanie populacji początkowej16
Ocena populacji19
Selekcja rodziców22
Operatory genetyczne24
Kreowanie nowej populacji28
Pełna postać kanonicznego AG32
Literatura40
3. Standardowe operatory krzyżowania42
Krzyżowanie jednopunktowe (1-Point Crossover )42
Krzyżowanie wielopunktowe (k-Point Crossover)42
Krzyżowanie tasujące (Shuffle Crossover)44
Krzyżowanie zastępujące (Reduced Surrogate Crossover)45
Krzyżowanie równomierne (Uniform Crossover )46
Krzyżowanie niszczące (Heuristic Uniform Crossover/Highly Disruptive Crossover)47
Krzyżowanie uśredniające (Average Crossover)48
Krzyżowanie płaskie (Flat Crossover)49
Krzyżowanie ziarniste (Discrete Crossover)49
Krzyżowanie heurystyczne-1 (Heuristic Crossover /Intermediate Crossover)50
Krzyżowanie mieszające (Blend Crossover)51
4. Operatory krzyżowania dla problemów kodowanych liczbami binarnymi54
Krzyżowanie powielające podobieństwa (Random Respectful Crossover)54
Krzyżowanie oparte na dominacji (Masked Crossover)56
Krzyżowanie wyboru operatora (1bit Adaptation Crossover)58
Krzyżowanie wielowymiarowe (Multivariate Crossover)62
Krzyżowanie homologiczne (Homologous Crossover)64
Krzyżowanie zliczające-1 (Count-preserving Crossover-1)66
Krzyżowanie elitarne (Elitist Crossover)68
Krzyżowanie skanujące (Scanning Crossover)69
Krzyżowanie częściowe (Partial Copy Crossover)72
Krzyżowanie nierównomierne oparte na wiedzy (Knowledge-Based Nonuniform Crossover)73
Krzyżowanie średnicą (Circle-ring Crossover)75
Wystarczająca wymiana (Sufficient Exchanging)76
Ewolucja powiązań (Linkage Evolving Genetic Operator)78
Krzyżowanie łańcuchami-1 (2N-parent Parameter Wise Crossover)80
Krzyżowanie diagonalne (Diagonal Crossover)82
Krzyżowanie pulą genów-1 (Gene Pool Crossover-1)84
Krzyżowanie hierarchiczne (Hierarchical Crossover)85
Krzyżowanie iloczynem/sumą logiczną (Randomized and/or Crossover)89
Krzyżowanie jednokierunkowe (Simple Conjugation Operator)90
Strategia wyboru operatora-1 (Adaptive Strategies of Mixing Crossovers)92
Krzyżowanie ortogonalne-1 (Orthogonal Crossover)94
Krzyżowanie mikrobiologiczne (Microbial Crossover)96
Krzyżowanie selektywne-1 (Selective Crossover-1)99
Krzyżowanie powiązań (Exchange Crossover/ Linkage Crossover)101
Krzyżowanie skanujące wielopłciowe (Multi Sexual Scanning Crossover)102
Krzyżowanie różnicami (Differences-Based Crossover)104
Krzyżowanie kumulujące (Fusion Crossover)106
Krzyżowanie wielochromosomowe (Multiple Chromosomes Crossover)107
Krzyżowanie ograniczone (Restricted Crossover)109
Krzyżowanie selektywne-2 (Selective Crossover-2)111
Samokrzyżowanie (Self Crossover)113
Krzyżowanie tnące (Multi-cut Crossover)116
Transpozycja (Transposition Operator)117
Transpozycja z selekcją turniejową (Tournament Based Transposition Operator)121
Dominujący splot (Dominant Splice/Symbiotic Combination)127
Krzyżowanie zdysocjowane (Dissociated Crossover)128
Krzyżowanie spontaniczne (Spontaneous Crossover)130
Krzyżowanie metodą bisekcji (Binary Search Point Crossover)132
Krzyżowanie stabilne (Fixed Crossover)135
Powielanie z lokalnym dostrajaniem (Common Features/Random Sample Climbing Crossover)136
Transpozycja bezpłciowa (Asexual Transposition)138
Krzyżowanie różnic (Disrespectful Crossover)142
Krzyżowanie dwupunktowe asymetryczne-1 (Asymmetric Two-point Crossover)144
Krzyżowanie dwupunktowe asymetryczne-2 (Variation of Asymmetric Two-point Crossover)146
Najlepsza kombinacja (Best Combinatorial Crossover)148
Związki mieszane (Hybridization Crossover)149
Strategia wyboru operatora-2 (Mixed Crossover)150
Krzyżowanie łańcuchami-2 (Direct Design Variable Exchange Crossover)152
Poszukiwanie schematów (Best Schema Crossover)154
Krzyżowanie chromosomów o zmiennej długości (Variable Length Genomes Crossover)156
Krzyżowanie trójosobnicze (Three-Parent Crossover)160
Krzyżowanie częściowo mieszające (Partially Randomized Crossover)162
Krzyżowanie nierównomierne oparte na statystykach (Statistic-Based Adaptive Non-Uniform Crossover)163
Krzyżowanie zbiorem operatorów-1 (Multiple Crossover Operators-1)165
Krzyżowanie z decydentem (Half Sibling and a Clone)168
Adaptacja liczby punktów krzyżowania i mutacji (Adaptive Number of Crossover Points)169
Kooperacja/rywalizacja płci (Sexual Selection Crossover)171
Tasowanie chromosomów (Chromosome Shuffling)173
Krzyżowanie ortogonalne-2 (Orthogonal Latin Mutli-Parent Crossover)175
Krzyżowanie z punktową mutacją (Different Location Crossover)177
Strategia wyboru operatora-3 (Combined Balanced Crossover)178
Krzyżowanie wielokrotne-1 (Hybrid 1-Point Crossover)181
Krzyżowanie zliczające-2 (Count-preserving Crossover-2)183
Krzyżowanie ważone przystosowaniem-1 (Fitness Weighted Crossover (Binary))186
Adaptacja prawdopodobieństwa-1 (Adaptive Probability Crossover-1)188
Maksymalizacja podobieństw (Schema-Based Crossover)190
5. Operatory krzyżowania dla problemów kodowanych liczbami rzeczywistymi194
Krzyżowanie linearne-1 (Linear Crossover)194
Krzyżowanie heurystyczne-2 (Heuristic Crossover2)195
Krzyżowanie proste (Simple Crossover)197
Krzyżowanie pojedyncze arytmetyczne (Single Arithmetical Crossover)198
Krzyżowanie arytmetyczne (Arithmetical Crossover, Intermediate Crossover2, Linear Crossover, Guaranteed Average Crossover, Convex Crossover )200
Krzyżowanie wstawiające (Injection Crossover)202
Adaptacja prawdopodobieństwa-2 (Adaptive Probability Crossover-2)204
Krzyżowanie linearne-2 (Linear BGA Crossover)206
Krzyżowanie z simpleksem-1 (Simplex Crossover)208
Krzyżowanie linearne-3 (Simulated Binary Crossover)210
Krzyżowanie ze zbiorami rozmytymi-1 (Fuzzy Crossover)212
Krzyżowanie ze zbiorami rozmytymi-2 (Fuzzy Connectives Based Crossover)214
Krzyżowanie z wspinaczką-1 (Crossover Hillclimbing)216
Krzyżowanie przypadkowe (Random Crossover)218
Krzyżowanie łańcuchami-3 (Variable Length Segments Crossover)219
Krzyżowanie uśredniające zaburzone (Unfair Average Crossover)222
Krzyżowanie równomierne ciągłe (Continuous Uniform Crossover)224
Krzyżowanie geometryczne (Geometrical Crossover)226
Krzyżowanie sferyczne (Sphere Crossover)228
Krzyżowanie z wektorem różnic (Differential Evolution Crossover)230
Krzyżowanie z simpleksem-2 (Simplex Crossover-2)232
Krzyżowanie wielokrotne-2 (Multiple Crossover Per Couple)234
Krzyżowanie pulą genów-2 (Gene-Pooling Crossover-2)236
Krzyżowanie środkiem masy-1 (Center of Mass Crossover)238
Krzyżowanie wieloosobniczne-1 (Multi-parent Feature-wise Crossover)239
Krzyżowanie z przystosowaniem częściowo separowalnym (Partially Separable Crossover)241
Krzyżowanie drążące (Seed Crossover)243
Niewypukła wieloosobnicza kombinacja liniowa (Non-convex Linear Combination of Multiple Parents)244
Krzyżowanie kierunkowe (Direction-Based Crossover)245
Krzyżowanie z pochodną (Derivative-Based Crossover)247
Krzyżowanie z rankingiem (Rank Based Crossover)248
Krzyżowanie paraboliczne-1 (Parabolic Crossover)250
Krzyżowanie kierowane (Guided Crossover)252
Krzyżowanie wielokrotne-3 (Multiple Crossover on Multiple Parents)254
Krzyżowanie z simpleksem-3 (Simplex Crossover-3)256
Krzyżowanie jednorodne (Uniform Design Crossover)258
Krzyżowanie środkiem grawitacji (Center of Gravity Crossover)259
Krzyżowanie jednopunktowe uśrednione (1-point Average Crossover)261
Krzyżowanie dwupunktowe uśrednione (Messy Average Crossover)262
Adaptacja prawdopodobieństwa-3 (Adaptive Probability Crossover-3)264
Krzyżowanie z wspinaczką-2 (Site-Specific Crossover)265
Krzyżowanie z przystosowaniem nieseparowalnym (BLX Principal Component Analysis and Independent Component Analysis)270
Krzyżowanie ortogonalne z kwantyzacją (Orthogonal Crossover with Quantization)272
Krzyżowanie równomierne gaussowskie (Gaussian Uniform Crossover)273
Krzyżowanie pulą genów-3 (Set-Oriented Crossover)275
Adaptacja prawdopodobieństwa-4 (Adaptive Probability Crossover-4)276
Adaptacja prawdopodobieństwa-5 (Adaptive Probability Crossover-5)279
Krzyżowanie pozycyjne (Position Crossover)282
Krzyżowanie najlepszy-najlepszy (Best-Best Crossover)284
Adaptywne krzyżowanie w losowej liczbie punktów (Adaptive Q-rand Point Crossover)286
Krzyżowanie w losowej liczbie punktów (Q-rand Point Crossover)287
Krzyżowanie wielokrotne-4 (Multiple Crossover)290
Krzyżowanie arytmetyczne poprawione-1 (Improved Arithmetical Crossover)292
Translokacja wzajemna (Reciprocal Translocation Operator)294
Krzyżowanie arytmetyczne poprawione-2 (Hybrid Arithmetical Crossover)299
Krzyżowanie wielokrotne-5 (Generation of Multiple Descendants and Selection of the Two Best)301
Krzyżowanie w otoczeniu-1 (Adaptive Neighborhood-based Multi-parent Crossover)303
Krzyżowanie ułomne (Imperfect Crossover)305
Adaptacja prawdopodobieństwa-6 (Adaptive Probability Crossover-6)308
Krzyżowanie zbiorem operatorów-2 (Multiple Crossover Operators-2)310
Krzyżowanie samoadaptacyjne (Heuristic-Based Self -Adapting Crossover)312
Krzyżowanie ze zmiennymi typami danych (Mixed Variable Crossover)316
Krzyżowanie cylindryczne (Curved Cylinder Crossover)320
Krzyżowanie wymienne (Exchanging Information Crossover)323
Krzyżowanie arytmetyczne poprawione-3 (Real-Biased Crossover)324
Krzyżowanie Taguchiego-1 (Taguchi Crossover/Main Effect Orthogonal Crossover)326
Krzyżowanie ortogonalne z interakcją (Interaction Effect Orthogonal Crossover)329
Krzyżowanie różnorodne (Diverse Crossover)332
Krzyżowanie w otoczeniu-2 (Parent Centric BLX-? Crossover)334
Krzyżowanie Taguchiego-2 (Taguchi Crossover-2)336
Krzyżowanie w grupie (Extended GA Crossover)338
Krzyżowanie jednogenowe (Single Gene Crossover)340
Krzyżowanie ważone przystosowaniem-2 (Fitness Weighted Crossover (Real))342
Krzyżowanie zależności (Inheritance Crossover)344
Adaptacja prawdopodobieństwa dla genu (Adaptive Probability of Gene Crossover)346
Adaptacja prawdopodobieństwa-7 (Adaptive Probability Crossover-7)347
Krzyżowanie ze znormalizowanym dystansem przystosowania (Normalized Fitness Crossover)349
Krzyżowanie z kontrolą zawartości (Controlled Content Crossover)351
Krzyżowanie środkiem masy-2 (Center of Mass Crossover-2)354
Krzyżowanie różnicujące (Parent Differentiation Crossover)356
Metoda przełączająca (Improved Crossover and Mutation)357
Adaptacja prawdopodobieństwa-8 (Adaptive Probability Crossover-8)359
Krzyżowanie królewskie (King Strategy Crossover)362
Krzyżowanie pulą genów-4 (Gene-Pooling Crossover-4)363
Krzyżowanie sterowane przystosowaniem (Fitness Guided Crossover)365
Krzyżowanie w otoczeniu-3 (Continuous Adaptive Culture Model Crossover)366
Krzyżowanie paraboliczne-2 (Fitness-Based Parabolic Crossover)368
Krzyżowanie wieloosobnicze-2 (Hybrid Panmictic (multi-parent) Crossover)369
6. Operatory statystyczne372
UNDX – Unimodal Normal Distribution Crossover372
MM-B – Factorized Distribution Method373
MM-B – Marginal Histogram-Based Method373
PCX – Parent-Centric Crossover373
CIXL2 – Confidence Interval Based Crossover374
EDX – Extrapolation Directed Crossover374
TDX – Trimodal Distribution Crossover374
GAQPR – Quantum Probability Representation-Based Method375
LUNDX-m – Latent Variable Crossover375
Indeks słów kluczowych, autorów i funkcji testowych376

Wstęp

•

innychoperatorówideowoznimzwiązanych;zalecanymtekstomtakżetowarzyszą

adresyserwisów,skądmożnajepobrać.

Patrztakże-inneoperatory,zktórymiwmojejopiniiwartosięzapoznaćwkontekście

danegooperatora.

Algorytm-prezentujewformiepseudokoduomawianyoperator,nierzadkowkilku

wariantach;zdecydowałemsięnatęformęprezentacjioperatora,ponieważ

wwiększościprzypadkówumożliwiaonanatychmiastowezastosowanieoperatora

wpraktyce,zdrugiejzaśstronyniechciałemstosowaćkonkretnegojęzykaprogramo-

wania,ponieważdodatkowopojawiającesięwkodzieelementywynikającezgrama-

tykijęzykamogłybyutrudnićzrozumieniedemonstrowanegooperatora.Prezentowany

algorytmczęstomożeodbiegaćodswejoryginalnejpostaciprzedstawionejwtekście

źródłowym.Dziejesiętakwtedy,gdypostaćtamiałaścisłyzwiązekzproblemem,dla

któregooperatorzostałopracowany,jednakwkażdymwypadkukluczowaideaopera-

torazostałatuzaprezentowana.

Komentarze-komentarzelubopisprezentowanegooperatora,zależnieodtego,czy

wmojejopiniipseudokodalgorytmustanowiwystarczającyopisoperatora,czynie.

Funkcjetestowe-listastandardowychfunkcjilubproblemówtestowych,oiletakowe

zostałyzastosowanewtokueksperymentówzużyciemomawianegooperatora.

Porównanoz-listainnychoperatorówkrzyżowania,zktórymiporównywanybył

(wtekścieźródłowym)prezentowanyoperator.

Aczkolwiekmożetosięspotkaćzdezaprobatą,wtokucałegotekstutraktujęjako

synonimytakieparypojęć,jak„rekombinacja-krzyżowanie”,„wektorrozwiązania

-chromosom”,„gen-zmienna”,„generacja-iteracja”.Ponadto,oileniezostanieexplicite

wskazane,żejestinaczej,wtokucałegotekstustosujęnastępująceoznaczenia:

t-licznikgeneracji(iteracji,numerupopulacji)

M-maksymalnaliczbageneracji(iteracji)algorytmu

P()-populacjawektorówrozwiązania(chromosomów)

P(0)-początkowapopulacja

P(t)-bieżącapopulacja(populacjarodziców)

P(t+1)-następnapopulacja(populacjapotomków)

L_p-licznośćpopulacji(rozmiarpopulacji)

pcross,pc-prawdopodobieństwokrzyżowania

pm-prawdopodobieństwomutacji

n-długośćwektorarozwiązania(chromosomu)

Rnd–losowa(orozkładzierównomiernym)liczbarzeczywista,Rnd∈<0,1>;jeżeliRnd

występujewpętlialgorytmu,wtedywkażymkrokutejpętlijejwartośćwyznaczanajest

ponownie

Brak wyników

Algorytmy genetyczne. Kompendium, t. 1

Treść książki

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