Table of Contents
Contributors xv
Foreword xix
Preface xxi
Part I Methodologies for Complex Problem Solving 1
1 Generating Automatic Projections by Means of Genetic Programming 3
C. Estébanez and R. Aler
1.1 Introduction 3
1.2 Background 4
1.3 Domains 6
1.4 Algorithmic Proposal 6
1.5 Experimental Analysis 9
1.6 Conclusions 11
References 13
2 Neural Lazy Local Learning 15
J. M. Valls, I. M. Galván, and P. Isasi
2.1 Introduction 15
2.2 Lazy Radial Basis Neural Networks 17
2.3 Experimental Analysis 22
2.4 Conclusions 28
References 30
3 Optimization Using Genetic Algorithms with Micropopulations 31
Y. Sáez
3.1 Introduction 31
3.2 Algorithmic Proposal 33
3.3 Experimental Analysis: The Rastrigin Function 40
3.4 Conclusions 44
References 45
4 Analyzing Parallel Cellular Genetic Algorithms 49
G. Luque, E. Alba, and B. Dorronsoro
4.1 Introduction 49
4.2 Cellular Genetic Algorithms 50
4.3 Parallel Models for cGAs 51
4.4 Brief Survey of Parallel cGAs 52
4.5 Experimental Analysis 55
4.6 Conclusions 59
References 59
5 Evaluating New Advanced Multiobjective Metaheuristics 63
A. J. Nebro, J. J. Durillo, F. Luna, and E. Alba
5.1 Introduction 63
5.2 Background 65
5.3 Description of the Metaheuristics 67
5.4 Experimental Methodology 69
5.5 Experimental Analysis 72
5.6 Conclusions 79
References 80
6 Canonical Metaheuristics for Dynamic Optimization Problems 83
G. Leguizamón, G. Ordóñez, S. Molina, and E. Alba
6.1 Introduction 83
6.2 Dynamic Optimization Problems 84
6.3 Canonical MHs for DOPs 88
6.4 Benchmarks 92
6.5 Metrics 93
6.6 Conclusions 95
References 96
7 Solving Constrained Optimization Problems with Hybrid Evolutionary Algorithms 101
C. Cotta and A. J. Fernández
7.1 Introduction 101
7.2 Strategies for Solving CCOPs with HEAs 103
7.3 Study Cases 105
7.4 Conclusions 114
References 115
8 Optimization of Time Series Using Parallel, Adaptive, and Neural Techniques 123
J. A. Gómez, M. D. Jaraiz, M. A. Vega, and J. M. Sánchez
8.1 Introduction 123
8.2 Time Series Identification 124
8.3 Optimization Problem 125
8.4 Algorithmic Proposal 130
8.5 Experimental Analysis 132
8.6 Conclusions 136
References 136
9 Using Reconfigurable Computing for the Optimization of Cryptographic Algorithms 139
J. M. Granado, M. A. Vega, J. M. Sánchez, and J. A. Gómez
9.1 Introduction 139
9.2 Description of the Cryptographic Algorithms 140
9.3 Implementation Proposal 144
9.4 Expermental Analysis 153
9.5 Conclusions 154
References 155
10 Genetic Algorithms, Parallelism, and Reconfigurable Hardware 159
J. M. Sánchez, M. Rubio, M. A. Vega, and J. A. Gómez
10.1 Introduction 159
10.2 State of the Art 161
10.3 FPGA Problem Description and Solution 162
10.4 Algorithmic Proposal 169
10.5 Experimental Analysis 172
10.6 Conclusions 177
References 177
11 Divide and Conquer: Advanced Techniques 179
C. León, G. Miranda, and C. Rodríguez
11.1 Introduction 179
11.2 Algorithm of the Skeleton 180
11.3 Experimental Analysis 185
11.4 Conclusions 189
References 190
12 Tools for Tree Searches: Branch-and-Bound and A∗ Algorithms 193
C. León, G. Miranda, and C. Rodríguez
12.1 Introduction 193
12.2 Background 195
12.3 Algorithmic Skeleton for Tree Searches 196
12.4 Experimentation Methodology 199
12.5 Experimental Results 202
12.6 Conclusions 205
References 206
13 Tools for Tree Searches: Dynamic Programming 209
C. León, G. Miranda, and C. Rodríguez
13.1 Introduction 209
13.2 Top-Down Approach 210
13.3 Bottom-Up Approach 212
13.4 Automata Theory and Dynamic Programming 215
13.5 Parallel Algorithms 223
13.6 Dynamic Programming Heuristics 225
13.7 Conclusions 228
References 229
Part II Applications 231
14 Automatic Search of Behavior Strategies in Auctions 233
D. Quintana and A. Mochón
14.1 Introduction 233
14.2 Evolutionary Techniques in Auctions 234
14.3 Theoretical Framework: The Ausubel Auction 238
14.4 Algorithmic Proposal 241
14.5 Experimental Analysis 243
14.6 Conclusions 246
References 247
15 Evolving Rules for Local Time Series Prediction 249
C. Luque, J. M. Valls, and P. Isasi
15.1 Introduction 249
15.2 Evolutionary Algorithms for Generating Prediction Rules 250
15.3 Experimental Methodology 250
15.4 Experiments 256
15.5 Conclusions 262
References 263
16 Metaheuristics in Bioinformatics: DNA Sequencing and Reconstruction 265
C. Cotta, A. J. Fernández, J. E. Gallardo, G. Luque, and E. Alba
16.1 Introduction 265
16.2 Metaheuristics and Bioinformatics 266
16.3 DNA Fragment Assembly Problem 270
16.4 Shortest Common Supersequence Problem 278
16.5 Conclusions 282
References 283
17 Optimal Location of Antennas in Telecommunication Networks 287
G. Molina, F. Chicano, and E. Alba
17.1 Introduction 287
17.2 State of the Art 288
17.3 Radio Network Design Problem 292
17.4 Optimization Algorithms 294
17.5 Basic Problems 297
17.6 Advanced Problem 303
17.7 Conclusions 305
References 306
18 Optimization of Image-Processing Algorithms Using FPGAs 309
M. A. Vega, A. Gómez, J. A. Gómez, and J. M. Sánchez
18.1 Introduction 309
18.2 Background 310
18.3 Main Features of FPGA-Based Image Processing 311
18.4 Advanced Details 312
18.5 Experimental Analysis: Software Versus FPGA 321
18.6 Conclusions 322
References 323
19 Application of Cellular Automata Algorithms to the Parallel Simulation of Laser Dynamics 325
J. L. Guisado, F. Jiménez-Morales, J. M. Guerra, and F. Fernández
19.1 Introduction 325
19.2 Background 326
19.3 Laser Dynamics Problem 328
19.4 Algorithmic Proposal 329
19.5 Experimental Analysis 331
19.6 Parallel Implementation of the Algorithm 336
19.7 Conclusions 344
References 344
20 Dense Stereo Disparity from an Artificial Life Standpoint 347
G. Olague, F. Fernández, C. B. Pérez, and E. Lutton
20.1 Introduction 347
20.2 Infection Algorithm with an Evolutionary Approach 351
20.3 Experimental Analysis 360
20.4 Conclusions 363
References 363
21 Exact, Metaheuristic, and Hybrid Approaches to Multidimensional Knapsack Problems 365
J. E. Gallardo, C. Cotta, and A. J. Fernández
21.1 Introduction 365
21.2 Multidimensional Knapsack Problem 370
21.3 Hybrid Models 372
21.4 Experimental Analysis 377
21.5 Conclusions 379
References 380
22 Greedy Seeding and Problem-Specific Operators for Gas Solution of Strip Packing Problems 385
C. Salto, J. M. Molina, and E. Alba
22.1 Introduction 385
22.2 Background 386
22.3 Hybrid GA for the 2SPP 387
22.4 Genetic Operators for Solving the 2SPP 388
22.5 Initial Seeding 390
22.6 Implementation of the Algorithms 391
22.7 Experimental Analysis 392
22.8 Conclusions 403
References 404
23 Solving the KCT Problem: Large-Scale Neighborhood Search and Solution Merging 407
C. Blum and M. J. Blesa
23.1 Introduction 407
23.2 Hybrid Algorithms for the KCT Problem 409
23.3 Experimental Analysis 415
23.4 Conclusions 416
References 419
24 Experimental Study of GA-Based Schedulers in Dynamic Distributed Computing Environments 423
F. Xhafa and J. Carretero
24.1 Introduction 423
24.2 Related Work 425
24.3 Independent Job Scheduling Problem 426
24.4 Genetic Algorithms for Scheduling in Grid Systems 428
24.5 Grid Simulator 429
24.6 Interface for Using a GA-Based Scheduler with the Grid Simulator 432
24.7 Experimental Analysis 433
24.8 Conclusions 438
References 439
25 Remote Optimization Service 443
J. García-Nieto, F. Chicano, and E. Alba
25.1 Introduction 443
25.2 Background and State of the Art 444
25.3 ROS Architecture 446
25.4 Information Exchange in ROS 448
25.5 XML in ROS 449
25.6 Wrappers 450
25.7 Evaluation of ROS 451
25.8 Conclusions 454
References 455
26 Remote Services for Advanced Problem Optimization 457
J. A. Gómez, M. A. Vega, J. M. Sánchez, J. L. Guisado, D. Lombraña, and F. Fernández
26.1 Introduction 457
26.2 SIRVA 458
26.3 MOSET and TIDESI 462
26.4 ABACUS 465
References 470
Index 473
