Optimization Techniques for Solving Complex Problems

Real-world problems and modern optimization techniques to solve them Here, a team of international experts brings together core ideas for solving complex problems in optimization across a wide variety of real-world settings, including computer science, engineering, transportation, telecommunications, and bioinformatics. Part One—covers methodologies for complex problem solving including genetic programming, neural networks, genetic algorithms, hybrid evolutionary algorithms, and more. Part Two—delves into applications including DNA sequencing and reconstruction, location of antennae in telecommunication networks, metaheuristics, FPGAs, problems arising in telecommunication networks, image processing, time series prediction, and more. All chapters contain examples that illustrate the applications themselves as well as the actual performance of the algorithms.?Optimization Techniques for Solving Complex Problems is a valuable resource for practitioners and researchers who work with optimization in real-world settings.

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