Cover    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),
Author-created final version (free download)

Tutorial slides covering selected topic from the book, presented at GECCO 2013

Table of Contents

Part I: Basics

2Combinatorial Optimization and Computational Complexity
2.1Combinatorial Optimization
2.2Computational Complexity
2.3Approximation Versus Exact Optimization
2.4Multi-objective Optimization
3Stochastic Search Algorithms
3.1Evolutionary Algorithms
3.2Ant Colony Optimization
3.3Other Stochastic Search Algorithms
4Analyzing Stochastic Search Algorithms
4.1Simple 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

10Multi-objective Minimum Spanning Trees
10.2Extremal Points of the Convex Hull
10.3Analysis of GSEMO
11 Minimum Spanning Trees Made Easier
11.1A Two-Objective Model
11.2Analysis of the Expected Optimization Time
11.3Experimental Results
12Covering Problems
12.1Problem Formulation and Representation
12.2Single-objective Optimization
12.3Multi-objective Optimization
13Cutting Problems
13.1Single-objective Approaches
13.2 Multi-objective Model for the Multicut Problem


A.1 Probability Distributions
A.2 Deviation Inequalities
A.3   Other Useful Formulas