Cellular Genetic Algorithms
Buku ini diterbitkan tahun 2008 oleh Springer Science+Business Media, LLC. New York. Buku ini buku edisi Pertama.
Judul: Cellular Genetic Algorithms
Oleh: Enrique Alba, et al
Penerbit: Springer Science+Business Media, LLC. New York
Tahun: 2008
Jumlah Halaman: 247 hal.
Penulis:
Enrique Alba
Universidad de Málaga
Málaga, Spain
eat@lcc.uma.es
Bernabé Dorronsoro
Universidad de Málaga
Málaga, Spain
bernabe@lcc.uma.es
Lingkup Pembahasan:
Buku ini merupakan hasil dari upaya untuk membuat algoritma pencarian yang sangat efisien
dengan biaya terikat dalam kinerja mereka dan pelaksanaannya. Memecahkan optimasi dan masalah di akademi dan industri belajar adalah sangat penting saat ini, tidak hanya dalam ilmu komputer, tetapi juga dalam riset operasi, matematika, dan di hampir semua domain dalam kehidupan sehari-hari: logistik, bioinformatika, ekonomi, telekomunikasi.
Pembahasan buku ini mencakup Bagian I Pendahuluan meliputi 1) Pengantar Seluler Algoritma Genetik dan 2) Seni Seluler di Evolusi Algoritma. Bagian II karakteristik Seluler Algoritma Genetik mencakup 3) Pengaruh Penataan Penduduk dan 4) Beberapa Teori: Sebuah Seleksi Tekanan Studi cGAs. Bagian III Model algorithmic dan Ekstensi membahas 5) Algorithmic dan Eksperimental Desain, 6) Desain cGAs Self-adaptif, 7) Desain Seluler memetic Algoritma, 8) Desain Paralel Algoritma Genetik Seluler, 9) Merancang Seluler Algoritma Genetik untuk Optimasi Multi-tujuan, 10) Model Seluler Lain, dan 11) Software untuk cGAs: The JCell Kerangka. Bagian IV Aplikasi cGAs meliputi 12) Optimasi berkelanjutan, 13) Logistik: The Vehicle Routing Masalah, 14) Telekomunikasi: Optimalisasi Proses Penyiaran di MANETs, dan 15) Bioinformatika: Masalah DNA Fragmen.
Daftar Isi:
Part I Introduction
1 Introduction to Cellular Genetic Algorithms 3
1.1 Optimization and Advanced Algorithms 4
1.2 Solving Problems Using Metaheuristics 6
1.3 Evolutionary Algorithms 7
1.4 Decentralized Evolutionary Algorithms 11
1.5 Cellular Evolutionary Algorithms 13
1.5.1 Synchronous and Asynchronous cEAs 16
1.5.2 Formal Characterization of the Population in cEAs 17
1.6 Cellular Genetic Algorithms 18
1.7 Conclusions 20
2 The State of the Art in Cellular Evolutionary Algorithms 21
2.1 Cellular EAs: a New Algorithmic Model 21
2.2 The Research in the Theory of the Cellular Models 22
2.2.1 Characterizing the Behavior of cEAs 24
2.2.2 The Influence of the Ratio 26
2.3 Empirical Studies on the Behavior of cEAs 26
2.4 Algorithmic Improvements to the Canonical Model 29
2.5 Parallel Models of cEAs 31
2.6 Conclusions 34
Part II Characterizing Cellular Genetic Algorithms
3 On the Effects of Structuring the Population 37
3.1 Non-decentralized GAs 37
3.1.1 Steady State GA 38
3.1.2 Generational GA 38
3.2 Decentralized GAs 39
3.3 Experimental Comparison 40
3.3.1 Cellular versus Panmictic GAs 41
3.3.2 Cellular versus Distributed GAs 43
3.4 Conclusions 46
4 Some Theory: A Selection Pressure Study on cGAs 47
4.1 The Selection Pressure 48
4.2 Theoretical Study 50
4.2.1 Approach to the Deterministic Model 50
4.2.2 A Probabilistic Model for Approaching the Selection Pressure Curve 52
4.2.3 Comparison of the Main Existing Mathematical Models 57
4.3 Validation of the Theoretical Models 60
4.3.1 Validation on Combinatorial Optimization 61
4.3.2 Validation on Continuous Optimization 65
4.4 Conclusions 68
Part III Algorithmic Models and Extensions
5 Algorithmic and Experimental Design 73
5.1 Proposal of New Efficient Models 73
5.2 Evaluation of the Results 76
5.2.1 The Mono-objective Case 77
5.2.2 The Multi-objective Case 78
5.2.3 Some Additional Definitions 80
5.3 Conclusions 82
6 Design of Self-adaptive cGAs 83
6.1 Introduction 83
6.2 Description of Algorithms 84
6.2.1 Static and Pre-Programmed Algorithms 86
6.2.2 Self-Adaptive Algorithms 87
6.3 Experimentation 90
6.3.1 Parameterization 91
6.3.2 Experimental Results 92
6.3.3 Additional Discussion 95
6.4 Conclusions 99
7 Design of Cellular Memetic Algorithms 101
7.1 Cellular Memetic Algorithms 102
7.2 Simple and Advanced Components in Cellular MAs 103
7.2.1 Three Basic Local Search Techniques for SAT 103
7.2.2 Cellular Memetic GAs 106
7.3 Computational Analysis 107
7.3.1 Effects of Combining a Structured Population and an Adaptive Fitness Function
(SAW) 107
7.3.2 Results: Non Memetic Procedures for SAT 109
7.3.3 Results: Cellular Memetic Algorithms 110
7.3.4 Comparison Versus Other Algorithms in the Literature 113
7.4 Conclusions 114
8 Design of Parallel Cellular Genetic Algorithms 115
8.1 The Meta-cellular Genetic Algorithm 116
8.1.1 Parameterization 117
8.1.2 Analysis of Results 117
8.2 The Distributed Cellular Genetic Algorithm 119
8.2.1 Parameterization 120
8.2.2 Analysis of Results 123
8.3 Conclusions 125
9 Designing Cellular Genetic Algorithms for Multi-objective Optimization 127 9.1 Background on Multi-objective Optimization 129
9.2 The MOCell Algorithm 130
9.2.1 Extensions to MOCell 132
9.3 Experimental Analysis 133
9.4 Conclusions 138
10 Other Cellular Models 139
10.1 Hierarchical cGAs 139
10.1.1 Hierarchy 140
10.1.2 Dissimilarity Selection 141
10.1.3 First Theoretical Results: Takeover Times 142
10.1.4 Computational Experiments 143
10.2 Cellular Estimation of Distribution Algorithms 146
10.2.1 First Theoretical Results: Takeover Times 149
10.2.2 Computational Experiments 149
10.3 Conclusions 152
11 Software for cGAs: The JCell Framework 153
11.1 The JCell Framework 153
11.2 Using JCell 158
11.3 Conclusions 163
Part IV Applications of cGAs
12 Continuous Optimization 167
12.1 Introduction 167
12.2 Experimentation 168
12.2.1 Tuning the Algorithm 169
12.2.2 Comparison with Other Algorithms 171
12.3 Conclusions 174
13 Logistics: The Vehicle Routing Problem 175
13.1 The Vehicle Routing Problem 177
13.2 Proposed Algorithms 178
13.2.1 Problem Representation 179
13.2.2 Recombination 180
13.2.3 Mutation 181
13.2.4 Local Search 182
13.3 Solving CVRP with JCell2o1i 184
13.4 New Solutions to CVRP 185
13.5 Conclusions 186
14 Telecommunications: Optimization of the Broadcasting Process in MANETs 187
14.1 The Problem 188
14.1.1 Metropolitan Mobile Ad Hoc Networks. The Madhoc Simulator 188
14.1.2 Delayed Flooding with Cumulative Neighborhood 191
14.1.3 MOPs Definition 192
14.2 A Multi-objective cGA: cMOGA. 193
14.2.1 Dealing with Constraints 194
14.3 Experiments 194
14.3.1 Parameterization of cMOGA 195
14.3.2 Madhoc Configuration 196
14.3.3 Results for DFCNT 198
14.4 Comparing cMOGA Against NSGA-II 200
14.4.1 Parameterization of NSGA-II 200
14.4.2 Discussion 201
14.5 Conclusions 202
15 Bioinformatics: The DNA Fragment Assembly Problem 203
15.1 The DNA Fragment Assembly Problem 204
15.2 A cMA for DNA Fragment Assembly Problem 206
15.3 Results 208
15.4 Conclusions 210
Part V Appendix
A Definition of the Benchmark Problems 213
A.1 Combinatorial Optimization Problems 213
A.1.1 COUNTSAT Problem 213
A.1.2 Error Correcting Codes Design Problem – ECC 214
A.1.3 Frequency Modulation Sounds – FMS 215
A.1.4 IsoPeak Problem 215
A.1.5 Maximum Cut of a Graph – MAXCUT 216
A.1.6 Massively Multimodal Deceptive Problem – MMDP 216
A.1.7 Minimum Tardy Task Problem – MTTP 217
A.1.8 OneMax Problem 218
A.1.9 Plateau Problem 218
A.1.10 P-PEAKS Problem 218
A.1.11 Satisfiability Problem – SAT 219
A.2 Continuous Optimization Problems 220
A.2.1 Academic Problems 220
A.2.2 Real World Problems 222
A.3 Multi-objective Optimization Problems 223
References 225
Index 243
Berminat?
Email: zanetapm@gmail.com
0 comments:
Post a Comment