Frank Neumann, Carsten Witt (2010): Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Natural Computing Series, Springer, ISBN 978-3-642-16543-6. Further Information Original publication at Springer (including online access), Amazon.com Author-created final version (free download) Tutorial slides covering selected topic from the book, presented at GECCO 2013 |
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 |
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 |
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 |
A.1 | Probability Distributions |
A.2 | Deviation Inequalities |
A.3 | Other Useful Formulas |
References |