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 Experimental 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
С. 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 Тор-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 .......................................... 380
21.2 Multidimensional Knapsack Problem ..................... 370
21.3 Hybrid Models ......................................... 372
21.4 Experimental Analysis ................................. 377
21.5 Conclusions ........................................... 379
References
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
|
