Optimization Techniques for Solving Complex Problems

ENRIQUE ALBA is a Professor of Data Communications and Evolutionary Algorithms at the University of Málaga, Spain. CHRISTIAN BLUM is a Research Fellow at the ALBCOM research group of the Universitat Politècnica de Catalunya, Spain. PEDRO ISASI??is a Professor of Artificial Intelligence at the University Carlos III of Madrid, Spain. COROMOTO LEÓN is a Professor of Language Processors and Distributed Programming at the University of La Laguna, Spain. JUAN ANTONIO??GÓMEZ is a Professor of Computer Architecture and Reconfigurable Computing at the University of Extremadura, Spain.??

• Contributors xvForeword xixPreface xxiPart I Methodologies for Complex Problem Solving 11 Generating Automatic Projections by Means of Genetic Programming 3C. Estébanez and R. Aler1.1 Introduction 31.2 Background 41.3 Domains 61.4 Algorithmic Proposal 61.5 Experimental Analysis 91.6 Conclusions 11References 132 Neural Lazy Local Learning 15J. M. Valls, I. M. Galván, and P. Isasi2.1 Introduction 152.2 Lazy Radial Basis Neural Networks 172.3 Experimental Analysis 222.4 Conclusions 28References 303 Optimization Using Genetic Algorithms with Micropopulations 31Y. Sáez3.1 Introduction 313.2 Algorithmic Proposal 333.3 Experimental Analysis: The Rastrigin Function 403.4 Conclusions 44References 454 Analyzing Parallel Cellular Genetic Algorithms 49G. Luque, E. Alba, and B. Dorronsoro4.1 Introduction 494.2 Cellular Genetic Algorithms 504.3 Parallel Models for cGAs 514.4 Brief Survey of Parallel cGAs 524.5 Experimental Analysis 554.6 Conclusions 59References 595 Evaluating New Advanced Multiobjective Metaheuristics 63A. J. Nebro, J. J. Durillo, F. Luna, and E. Alba5.1 Introduction 635.2 Background 655.3 Description of the Metaheuristics 675.4 Experimental Methodology 695.5 Experimental Analysis 725.6 Conclusions 79References 806 Canonical Metaheuristics for Dynamic Optimization Problems 83G. Leguizamón, G. Ordóñez, S. Molina, and E. Alba6.1 Introduction 836.2 Dynamic Optimization Problems 846.3 Canonical MHs for DOPs 886.4 Benchmarks 926.5 Metrics 936.6 Conclusions 95References 967 Solving Constrained Optimization Problems with Hybrid Evolutionary Algorithms 101C. Cotta and A. J. Fernández7.1 Introduction 1017.2 Strategies for Solving CCOPs with HEAs 1037.3 Study Cases 1057.4 Conclusions 114References 1158 Optimization of Time Series Using Parallel, Adaptive, and Neural Techniques 123J. A. Gómez, M. D. Jaraiz, M. A. Vega, and J. M. Sánchez8.1 Introduction 1238.2 Time Series Identification 1248.3 Optimization Problem 1258.4 Algorithmic Proposal 1308.5 Experimental Analysis 1328.6 Conclusions 136References 1369 Using Reconfigurable Computing for the Optimization of Cryptographic Algorithms 139J. M. Granado, M. A. Vega, J. M. Sánchez, and J. A. Gómez9.1 Introduction 1399.2 Description of the Cryptographic Algorithms 1409.3 Implementation Proposal 1449.4 Expermental Analysis 1539.5 Conclusions 154References 15510 Genetic Algorithms, Parallelism, and Reconfigurable Hardware 159J. M. Sánchez, M. Rubio, M. A. Vega, and J. A. Gómez10.1 Introduction 15910.2 State of the Art 16110.3 FPGA Problem Description and Solution 16210.4 Algorithmic Proposal 16910.5 Experimental Analysis 17210.6 Conclusions 177References 17711 Divide and Conquer: Advanced Techniques 179C. León, G. Miranda, and C. Rodríguez11.1 Introduction 17911.2 Algorithm of the Skeleton 18011.3 Experimental Analysis 18511.4 Conclusions 189References 19012 Tools for Tree Searches: Branch-and-Bound and A∗ Algorithms 193C. León, G. Miranda, and C. Rodríguez12.1 Introduction 19312.2 Background 19512.3 Algorithmic Skeleton for Tree Searches 19612.4 Experimentation Methodology 19912.5 Experimental Results 20212.6 Conclusions 205References 20613 Tools for Tree Searches: Dynamic Programming 209C. León, G. Miranda, and C. Rodríguez13.1 Introduction 20913.2 Top-Down Approach 21013.3 Bottom-Up Approach 21213.4 Automata Theory and Dynamic Programming 21513.5 Parallel Algorithms 22313.6 Dynamic Programming Heuristics 22513.7 Conclusions 228References 229Part II Applications 23114 Automatic Search of Behavior Strategies in Auctions 233D. Quintana and A. Mochón14.1 Introduction 23314.2 Evolutionary Techniques in Auctions 23414.3 Theoretical Framework: The Ausubel Auction 23814.4 Algorithmic Proposal 24114.5 Experimental Analysis 24314.6 Conclusions 246References 24715 Evolving Rules for Local Time Series Prediction 249C. Luque, J. M. Valls, and P. Isasi15.1 Introduction 24915.2 Evolutionary Algorithms for Generating Prediction Rules 25015.3 Experimental Methodology 25015.4 Experiments 25615.5 Conclusions 262References 26316 Metaheuristics in Bioinformatics: DNA Sequencing and Reconstruction 265C. Cotta, A. J. Fernández, J. E. Gallardo, G. Luque, and E. Alba16.1 Introduction 26516.2 Metaheuristics and Bioinformatics 26616.3 DNA Fragment Assembly Problem 27016.4 Shortest Common Supersequence Problem 27816.5 Conclusions 282References 28317 Optimal Location of Antennas in Telecommunication Networks 287G. Molina, F. Chicano, and E. Alba17.1 Introduction 28717.2 State of the Art 28817.3 Radio Network Design Problem 29217.4 Optimization Algorithms 29417.5 Basic Problems 29717.6 Advanced Problem 30317.7 Conclusions 305References 30618 Optimization of Image-Processing Algorithms Using FPGAs 309M. A. Vega, A. Gómez, J. A. Gómez, and J. M. Sánchez18.1 Introduction 30918.2 Background 31018.3 Main Features of FPGA-Based Image Processing 31118.4 Advanced Details 31218.5 Experimental Analysis: Software Versus FPGA 32118.6 Conclusions 322References 32319 Application of Cellular Automata Algorithms to the Parallel Simulation of Laser Dynamics 325J. L. Guisado, F. Jiménez-Morales, J. M. Guerra, and F. Fernández19.1 Introduction 32519.2 Background 32619.3 Laser Dynamics Problem 32819.4 Algorithmic Proposal 32919.5 Experimental Analysis 33119.6 Parallel Implementation of the Algorithm 33619.7 Conclusions 344References 34420 Dense Stereo Disparity from an Artificial Life Standpoint 347G. Olague, F. Fernández, C. B. Pérez, and E. Lutton20.1 Introduction 34720.2 Infection Algorithm with an Evolutionary Approach 35120.3 Experimental Analysis 36020.4 Conclusions 363References 36321 Exact, Metaheuristic, and Hybrid Approaches to Multidimensional Knapsack Problems 365J. E. Gallardo, C. Cotta, and A. J. Fernández21.1 Introduction 36521.2 Multidimensional Knapsack Problem 37021.3 Hybrid Models 37221.4 Experimental Analysis 37721.5 Conclusions 379References 38022 Greedy Seeding and Problem-Specific Operators for Gas Solution of Strip Packing Problems 385C. Salto, J. M. Molina, and E. Alba22.1 Introduction 38522.2 Background 38622.3 Hybrid GA for the 2SPP 38722.4 Genetic Operators for Solving the 2SPP 38822.5 Initial Seeding 39022.6 Implementation of the Algorithms 39122.7 Experimental Analysis 39222.8 Conclusions 403References 40423 Solving the KCT Problem: Large-Scale Neighborhood Search and Solution Merging 407C. Blum and M. J. Blesa23.1 Introduction 40723.2 Hybrid Algorithms for the KCT Problem 40923.3 Experimental Analysis 41523.4 Conclusions 416References 41924 Experimental Study of GA-Based Schedulers in Dynamic Distributed Computing Environments 423F. Xhafa and J. Carretero24.1 Introduction 42324.2 Related Work 42524.3 Independent Job Scheduling Problem 42624.4 Genetic Algorithms for Scheduling in Grid Systems 42824.5 Grid Simulator 42924.6 Interface for Using a GA-Based Scheduler with the Grid Simulator 43224.7 Experimental Analysis 43324.8 Conclusions 438References 43925 Remote Optimization Service 443J. García-Nieto, F. Chicano, and E. Alba25.1 Introduction 44325.2 Background and State of the Art 44425.3 ROS Architecture 44625.4 Information Exchange in ROS 44825.5 XML in ROS 44925.6 Wrappers 45025.7 Evaluation of ROS 45125.8 Conclusions 454References 45526 Remote Services for Advanced Problem Optimization 457J. A. Gómez, M. A. Vega, J. M. Sánchez, J. L. Guisado, D. Lombraña, and F. Fernández26.1 Introduction 45726.2 SIRVA 45826.3 MOSET and TIDESI 46226.4 ABACUS 465References 470Index 473