Cover
Natural Computing Series
Bioinspired Computation
in Combinatorial Optimization
Copyright
9783642165436
Foreword
Preface
Contents
Part I - Basics
1
Introduction
2
Combinatorial Optimization and
Computational Complexity
2.1 Combinatorial Optimization
2.2 Computational Complexity
2.3 Approximation Versus Exact Optimization
2.4 Multi-objective Optimization
3
Stochastic Search Algorithms
3.1 Evolutionary Algorithms
3.2 Ant Colony Optimization
3.3 Other Stochastic Search Algorithms
4
Analyzing Stochastic Search Algorithms
4.1 Simple Stochastic Search Algorithms
4.2 Basic Methods for the Analysis
Part II - Single-objective Optimization
5
Minimum Spanning Trees
5.1 Representation for Evolutionary Algorithms
5.2 Properties of Local Changes
5.3 Analysis of Evolutionary Algorithms
5.4 Analysis of Ant Colony Optimization
6
Maximum Matchings
6.1 Representations and Underlying Concepts
6.2 Approximation Quality for General Graphs
6.3 Upper Bounds for Simple Graph Classes
6.4 A Worst-Case Result
7
Makespan Scheduling
7.1 Representations and Neighborhood Structure
7.2 Worst-Case Analysis
7.3 Average-Case Analysis
8
Shortest Paths
8.1 Single Source Shortest Paths
8.2 All Pairs Shortest Paths
8.3 Analysis of Ant Colony Optimization
9
Eulerian Cycles
9.1 Edge Permutations
9.2 Adjacency List Matchings
Part III - Multi-objective Optimization
10
Multi-objective Minimum Spanning Trees
10.1 Representation
10.2 Extremal Points of the Convex Hull
10.3 Analysis of GSEMO
11
Minimum Spanning Trees Made Easier
11.1 A Two-Objective Model
11.2 Analysis of the Expected Optimization Time
11.3 Experimental Results
12
Covering Problems
12.1 Problem Formulation and Representation
12.2 Single-objective Optimization
12.3 Multi-objective Optimization
13
Cutting Problems
13.1 Single-objective Approaches
13.2 Multi-objective Model for the Multicut Problem
Appendix
A.1 Probability Distributions
A.2 Deviation Inequalities
A.3 Other Useful Formulas
References