Evolutionary Computation in Combinatorial Optimization

Name: Evolutionary Computation in Combinatorial Optimization | 11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011, Proceedings

Peter Merz Jin-Kao Hao(Herausgeber*in)

Springer (Verlag)

Erschienen am 27. April 2011

XIV, 263 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-20364-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken