Optimization Techniques for Solving Complex Problems Book

Contributors xv

Foreword xix

Preface xxi

Part I Methodologies for Complex Problem Solving 1

1 Generating Automatic Projections by Means of Genetic Programming C. Estébanez R. Aler 3

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 J. M. Valls I. M. Galván P. Isasi 15

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 Y. Sáez 31

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 G. Luque E. Alba B. Dorronsoro 49

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 A. J. Nebro J. J. Durillo F. Luna E. Alba 63

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 G. Leguizamón G. Ordóñez S. Molina E. Alba 83

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 HybridEvolutionary Algorithms C. Cotta A. J. Fernández 101

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 J. A. Gómez M. D. Jaraiz M. A. Vega J. M. Sánchez 123

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 J. M. Granado M. A. Vega J. M. Sánchez J. A. Gómez 139

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 J. M. Sánchez M. Rubio M. A. Vega J. A. Gómez 159

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 C. León G. Miranda C. Rodríguez 179

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 C. León G. Miranda C. Rodríguez 193

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 C. León G. Miranda C. Rodríguez 209

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 D. Quintana A. Mochón 233

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 C. Luque J. M. Valls P. Isasi 249

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 C. Cotta A. J. Fernández J. E. Gallardo G. Luque E. Alba 265

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 G. Molina F. Chicano E. Alba 287

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 M. A. Vega A. Gómez J. A. Gómez J. M. Sánchez 309

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 J. L. Guisado F. Jiménez-Morales J. M. Guerra F. Fernández 325

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 G. Olague F. Fernández C. B. Pérez E. Lutton 347

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 J. E. Gallardo C. Cotta A. J. Fernández 365

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 C. Salto J. M. Molina E. Alba 385

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 C. Blum M. J. Blesa 407

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 F. Xhafa J. Carretero 423

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 J. García-Nieto F. Chicano E. Alba 443

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 J. A. Gómez M. A. Vega J. M. Sánchez J. L. Guisado D. Lombraña F. Fernández 457

26.1 Introduction 457

26.2 SIRVA 458

26.3 MOSET and TIDESI 462

26.4 ABACUS 465

References 470

Index 473