Cellular genetic algorithms / Enrique Alba and Bernabé Dorronsoro.

Format:

Book

Author/Creator:

Alba, Enrique.

Contributor:

Dorronsoro, Bernabé.

Anne and Joseph Trachtman Memorial Book Fund.

Series:

Operations research/computer science interfaces series ; ORCS 42.

Operations research/computer science interfaces series ; ORCS 42

Language:

English

Subjects (All):

Nonlinear programming.

Genetic algorithms.

Physical Description:

xiii, 245 pages : illustrations ; 24 cm.

Place of Publication:

Berlin : Springer, [2008]

Summary:

Cellular Genetic Algorithms defines a new class of optimization algorithms based on the concepts of structured populations and Genetic Algorithms (GAs). The authors explain and demonstrate the validity of these cellular genetic algorithms throughout the book. This class of genetic algorithms is shown to produce impressive results on a whole range of domains, including complex problems that are epistatic, multi-modal, deceptive, discrete, continuous, multi-objective, and random in nature. The focus of this book is twofold. On the one hand, the authors present new algorithmic models and extensions to the basic class of Cellular GAs in order to tackle complex problems more efficiently. On the other hand, practical real world tasks are successfully faced by applying Cellular GA methodologies to produce workable solutions of real-world applications. These methods can include local search (memetic algorithms), cooperation, parallelism, multi-objective, estimations of distributions, and self-adaptive ideas to extend their applicability.

The methods are benchmarked against well-known metaheutistics like Genetic Algorithms, Tabu Search, heterogeneous GAs, Estimation of Distribution Algorithms, etc. Also, a publicly available software tool is offered to reduce the learning curve in applying these techniques. The three final chapters will use the classic problem of "vehicle routing" and the hot topics of "ad-hoc mobile networks" and "DNA genome sequencing" to clearly illustrate and demonstrate the power and utility of these algorithms.

Contents:

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

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

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

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

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

6 Design of Self-adaptive cGAs 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

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

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

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

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

11 Software for cGAs: The JCell Framework 153

11.1 The JCell Framework 153

11.2 Using JCell 158

Part IV Applications of cGAs

12 Continuous Optimization 167

12.2 Experimentation 168

12.2.1 Tuning the Algorithm 169

12.2.2 Comparison with Other Algorithms 171

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

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

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

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.

Notes:

Includes bibliographical references (pages [225]-242) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Anne and Joseph Trachtman Memorial Book Fund.

ISBN:

0387776095

9780387776095

OCLC:

212327911