Evolutionary Computation in Combinatorial Optimization
11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011, Proceedings
Published on 27. April 2011
XIV, 263 pages
978-3-642-20364-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 11th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2011, held in Torino, Italy, in April 2011. The 22 revised full papers presented were carefully reviewed and selected from 42 submissions. The papers present the latest research and discuss current developments and applications in metaheuristics - a paradigm to effectively solve difficult combinatorial optimization problems appearing in various industrial, economical, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and ant colony optimization.
More details
Other editions
Additional editions
Peter Merz | Jin-Kao Hao
Evolutionary Computation in Combinatorial Optimization
11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011, Proceedings
Book
04/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- A Guided Search Non-dominated Sorting Genetic Algorithm for the Multi-Objective University Course Timetabling Problem
- Introduction
- Description of the MOUCTP
- The Proposed GSNSGA for the MOUCTP
- The LS Schemes (LS1 and LS2)
- Data Structures MEMi (i =1, 2, 3)
- Generating a Child by the Guided Search Strategy
- Experimental Study
- Conclusions and Future Work
- References
- A Hybrid Dual-Population Genetic Algorithm for the Single Machine Maximum Lateness Problem
- Introduction
- Genetic Algorithm
- Data Generation
- Generation of Instances
- Data Analysis
- Computational Experiments
- Parameter Fine-Tuning
- Operator Selection
- Computational Results
- Conclusions
- References
- A Kolmogorov-Type Stability Measure for Evolutionary Algorithms
- Introduction
- An Example of an EA, Problem and Parameters
- The Problem and EA Parameters
- EA Sensitivity
- The EA as a Black Box
- Setup
- The Distance and Neighbourhood Structure on Parameter Sets
- An Example of Neighbourhood Enumeration for =6
- EA Kolmogorov Stability
- Kolmogorov Distance
- Estimation of Distribution of Kolmogorov Distances over N(p)
- Experiment 1
- Experiment 2
- Experiment 3
- Discussion
- Conclusion
- References
- A Matheuristic Approach for the Total Completion Time Two-Machines Permutation Flow Shop Problem
- Introduction
- Basic Model and Matheuristic Approach
- Computational Results
- Concluding Remarks
- References
- Connectedness and Local Search for Bicriteria Knapsack Problems
- Introduction
- The Bicriteria Unconstrained Optimization Problem
- Problem Definition
- Connectedness Analysis
- Local Search for BUOP
- The Bicriteria Knapsack Problem with Bounded Cardinality
- Problem Definition
- Connectedness Analysis
- Local Search for BKP-BC
- Concluding Remarks
- References
- Cutting Graphs Using Competing Ant Colonies and an Edge Clustering Heuristic
- Introduction
- Theoretical Background
- Graph Cuts
- Ant Colony Optimization
- The Algorithm
- Heuristic Information
- Stop Conditions
- Validation
- Parameter Tuning
- Comparison to a Baseline Algorithm
- Complexity
- Comparison to State-of-the-Art Cuts
- Conclusion and Suggestions for Further Research
- References
- Effective Variable Fixing and Scoring Strategies for Binary Quadratic Programming
- Introduction
- The TS Variable Fixing and Scoring Algorithm
- Definitions
- Tabu Search
- Reference Solutions
- Variable Fixing Procedure
- Variable Freeing Procedure
- Variable Scoring and Fixing Strategies
- Variable Scoring Strategy
- Variable Fixing Strategy
- Four Derived Algorithms
- Experimental Results
- Instances and Experimental Protocol
- Computational Results
- Discussion and Analysis
- Variable Fixing Errors
- Fitness Distance Correlation Analysis
- Conclusions
- References
- Evolutionary Multiobjective Route Planning in Dynamic Multi-hop Ridesharing
- Introduction
- Preliminaries
- Modeling Drivers' Offers for Route Planning in Multi-hop Dynamic Ridesharing
- Related Work
- Evolutionary Multiobjective Route Planning
- Solution Representation and Population Initialization
- Genetic Operators
- Evaluation Function
- Experiments
- Experiment Description
- Quality Indicators
- Experimentation Results and Discussion
- Conclusions and Future Work
- References
- Experiments in Parallel Constraint-Based Local Search
- Introduction
- Local Search and Parallelism
- The Adaptive Search Algorithm
- Parallel Performance Analysis
- Discussion
- Conclusion and Future Work
- References
- Fitness-Probability Cloud and a Measure of Problem Hardness for Evolutionary Algorithms
- Introduction
- Evolvability and Its Characterisations
- Fitness-Probability Cloud
- Escape Probability
- Fitness-Probability Cloud
- Accumulated Escape Probability
- Methodology for Generating fpc
- Test Problems
- Invertible Functions of Unitation
- Subset Sum Problem
- Experimental Results
- Conclusion
- References
- Frequency Distribution Based Hyper-Heuristic for the Bin-Packing Problem
- Introduction
- Related Work
- Combination of LLHs
- Bin-Packing Problem
- LLHs
- Simulated Annealing Hyper-Heuristic
- Frequency Distribution
- Pair Frequency and Frequency Matrix
- Frequency Distribution Analysis
- Frequency Distribution Based Hyper-Heuristic
- Reverse-Frequency Matrix
- Frequency Based Simulated Annealing Hyper-Heuristic
- Framework
- Experimental Results
- Conclusion and Future Work
- References
- From Adaptive to More Dynamic Control in Evolutionary Algorithms
- Introduction
- Adaptive Operator Selection
- Quality and Diversity Management
- The Trade-off Hypothesis
- Towards a More Dynamic Control
- Operators Management
- Conclusion
- References
- Geometric Generalisation of Surrogate Model Based Optimisation to Combinatorial Spaces
- Introduction
- Radial Basis Function Networks
- Classic RBFNs
- Generalisation of RBFNs to Arbitrary Representations
- Experiments
- Conclusions and Future Work
- References
- GPU-Based Approaches for Multiobjective Local Search Algorithms. A Case Study: The Flowshop Scheduling Problem
- Introduction
- Parallel Multiobjective Local Search Algorithms
- Multiobjective Local Search Algorithms
- Parallel Models of Local Search Algorithms
- GPU Computing for Metaheuristics
- General GPU Model
- Parallelism Control: GPU Threads Model
- Memory Management: Kernel Management
- The Proposed GPU-Based Algorithm
- Neighborhood Generation and Memory Management
- Efficient Mappings of Neighborhood Structures on GPU
- Memory Management of Local Search Algorithms on GPU
- Application to the Flowshop Scheduling Problem
- Configuration
- Aggregated Tabu Search
- Pareto Local Search Algorithms
- Discussion and Conclusion
- References
- Local Search for Mixed-Integer Nonlinear Optimization: A Methodology and an Application
- Presentation of the Problem
- Methodology and Outcomes
- General Heuristic
- Moves
- Evaluation Machinery
- Combinatorial Part
- Continuous Part
- Numerical Experiments
- References
- Multi-start Heuristics for the Two-Echelon Vehicle Routing Problem
- Introduction
- Problem Definition
- Literature Review
- Heuristics for the 2E-VRP
- First Clustering
- Clustering Improvement
- Multi-start Heuristic
- Computational Tests
- Comparison with State-Of-The-Art Algorithms
- Conclusions
- References
- NILS: A Neutrality-Based Iterated Local Search and Its Application to Flowshop Scheduling
- Motivations
- Background
- The Permutation Flowshop Scheduling Problem
- Neighborhood and Local Search
- Neutral Fitness Landscape
- Neutrality in the PFSP
- Iterated Local Search
- Neutrality-Based Iterated Local Search
- Local Search: First-Improving Hill-Climbing
- Perturbation: Neutral Walk-Based Perturbation
- NILS: A Neutrality-Based ILS
- Neutrality-Based Iterated Local Search for the Permutation Flowshop Scheduling Problem
- Experimental Design
- Experimental Results
- Influence of the MNS Parameter
- Benefits and Costs of Neutral Moves
- Conclusion and Future Works
- References
- Off-line and On-line Tuning: A Study on Operator Selection for a Memetic Algorithm Applied to the QAP
- Introduction
- The Algorithms Implemented
- Parameter Tuning
- Experimental Setup
- Experimental Results
- Conclusions
- References
- On Complexity of the Optimal Recombination for the Travelling Salesman Problem
- Introduction
- NP-Hardness of Optimal Recombination
- Symmetric Case
- The General Case
- Transformation of the ORP into TSP on Graphs With Bounded Vertex Degree
- General Case
- Symmetric Case
- Conclusions
- References
- Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives
- Motivations
- Local Search for Multiobjective Combinatorial Optimization
- Multiobjective Combinatorial Optimization
- Local Search
- MNK-Landscapes: Multiobjective NK-Landscapes with Objective Correlation
- NK- and MNK-Landscapes
- MNK-Landscapes
- Study of Pareto Local Optima
- Number of Pareto Local Optima
- Estimating the Cardinality of the Pareto Optimal Set?
- Adaptive Walk
- Properties vs. Multi-modality for Large-Size Problems
- Discussion
- References
- Quick-ACO: Accelerating Ant Decisions and Pheromone Updates in ACO
- Introduction
- The Standard ACO Algorithm
- The Quick-ACO Algorithm
- Initialization
- Solution Construction
- Updating Pheromone Matrix and Prefix Sum Matrix
- Experimental Result
- Examining Impact of Parameters k and L
- Comparison with Standard ACO
- Conclusion
- References
- Two Iterative Metaheuristic Approaches to Dynamic Memory Allocation for Embedded Systems
- Introduction
- Modeling the Problem
- ILP Formulation for Dy-MemExplorer Problem
- Example
- Iterative Metaheuristic Approaches
- Long-Term Approach
- Short-Term Approach
- Computational Results
- Conclusion
- References
- Author Index
