Skip header Section
Skip Bibliometrics Section
Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational ComplexityNovember 2010
- Authors:
- Frank Neumann,
- Carsten Witt
Skip Abstract Section
Abstract
Bioinspired computation methods such as evolutionary algorithms and ant colony optimization are being applied successfully to complex engineering problems and to problems from combinatorial optimization, and with this comes the requirement to more fully understand the computational complexity of these search heuristics. This is the first textbook covering the most important results achieved in this area. The authors study the computational complexity of bioinspired computation and show how runtime behavior can be analyzed in a rigorous way using some of the best-known combinatorial optimization problems -- minimum spanning trees, shortest paths, maximum matching, covering and scheduling problems. A feature of the book is the separate treatment of single- and multiobjective problems, the latter a domain where the development of the underlying theory seems to be lagging practical successes.This book will be very valuable for teaching courses on bioinspired computation and combinatorial optimization. Researchers will also benefit as the presentation of the theory covers the most important developments in the field over the last 10 years. Finally, with a focus on well-studied combinatorial optimization problems rather than toy problems, the book will also be very valuable for practitioners in this field.
Cited By
- Cerf S, Doerr B, Hebras B, Kahane Y and Wietheger S Hot off the Press: The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem Proceedings of the Genetic and Evolutionary Computation Conference Companion, (27-28)
- Doerr B, Echarghaoui A, Jamal M and Krejca M Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations Proceedings of the Genetic and Evolutionary Computation Conference Companion, (35-36)
- Doerr B A Gentle Introduction to Theory (for Non-Theoreticians) Proceedings of the Genetic and Evolutionary Computation Conference Companion, (800-829)
- Antipov D, Doerr B and Ivanova A Already Moderate Population Sizes Provably Yield Strong Robustness to Noise Proceedings of the Genetic and Evolutionary Computation Conference, (1524-1532)
- Doerr B, Knowles J, Neumann A and Neumann F A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis Proceedings of the Genetic and Evolutionary Computation Conference, (493-501)
- Baumann J, Rutter I and Sudholt D Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings Proceedings of the Genetic and Evolutionary Computation Conference, (1533-1541)
- Lv Z, Bian C, Qian C and Sun Y Runtime Analysis of Population-based Evolutionary Neural Architecture Search for a Binary Classification Problem Proceedings of the Genetic and Evolutionary Computation Conference, (358-366)
- Wang S, Zheng W and Doerr B (2024). Choosing the right algorithm with hints from complexity theory, Information and Computation, 296:C, Online publication date: 1-Jan-2024.
- Doerr B, Rajabi A and Witt C (2024). Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem, Algorithmica, 86:1, (64-89), Online publication date: 1-Jan-2024.
- Zheng W and Doerr B (2023). Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II), Artificial Intelligence, 325:C, Online publication date: 1-Dec-2023.
- Wietheger S and Doerr B A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III) Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, (5657-5665)
- Dinot M, Doerr B, Hennebelle U and Will S Runtime analyses of multi-objective evolutionary algorithms in the presence of noise Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, (5549-5557)
- Cerf S, Doerr B, Hebras B, Kahane Y and Wietheger S The first proven performance guarantees for the non-dominated sorting genetic algorithm II (NSGA-II) on a combinatorial optimization problem Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, (5522-5530)
- Doerr B and Qu Z Hot off the Press: A First Runtime Analysis of the NSGA-II on a Multimodal Problem Proceedings of the Companion Conference on Genetic and Evolutionary Computation, (15-16)
- Doerr B A Gentle Introduction to Theory (for Non-Theoreticians) Proceedings of the Companion Conference on Genetic and Evolutionary Computation, (946-975)
- Doerr B, Dremaux A, Lutzeyer J and Stumpf A How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs Proceedings of the Genetic and Evolutionary Computation Conference, (990-999)
- Doerr B and Kelley A Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus Proceedings of the Genetic and Evolutionary Computation Conference, (1555-1564)
- Bossek J and Sudholt D Runtime Analysis of Quality Diversity Algorithms Proceedings of the Genetic and Evolutionary Computation Conference, (1546-1554)
- Bossek J and Sudholt D (2023). Do additional target points speed up evolutionary algorithms?, Theoretical Computer Science, 950:C, Online publication date: 16-Mar-2023.
- Doerr B A gentle introduction to theory (for non-theoreticians) Proceedings of the Genetic and Evolutionary Computation Conference Companion, (890-921)
- Doerr B, Hadri O and Pinard A The (1 + (λ, λ)) global SEMO algorithm Proceedings of the Genetic and Evolutionary Computation Conference, (520-528)
- Zheng W and Doerr B Better approximation guarantees for the NSGA-II by using the current crowding distance Proceedings of the Genetic and Evolutionary Computation Conference, (611-619)
- Doerr B, Rajabi A and Witt C Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem Proceedings of the Genetic and Evolutionary Computation Conference, (1381-1389)
- Neumann F, Sudholt D and Witt C The compact genetic algorithm struggles on Cliff functions Proceedings of the Genetic and Evolutionary Computation Conference, (1426-1433)
- Doerr B, Ghannane Y and Brahim M Towards a stronger theory for permutation-based evolutionary algorithms Proceedings of the Genetic and Evolutionary Computation Conference, (1390-1398)
- Wang H, Vermetten D, Ye F, Doerr C and Bäck T (2022). IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics, ACM Transactions on Evolutionary Learning and Optimization, 2:1, (1-29), Online publication date: 31-Mar-2022.
- Bossek J and Sudholt D Do additional optima speed up evolutionary algorithms? Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, (1-11)
- Zheng W, Chen H and Yao X Analysis of evolutionary algorithms on fitness function with time-linkage property (hot-off-the-press track at GECCO 2021) Proceedings of the Genetic and Evolutionary Computation Conference Companion, (47-48)
- Doerr B Runtime analysis via symmetry arguments Proceedings of the Genetic and Evolutionary Computation Conference Companion, (23-24)
- Doerr B A gentle introduction to theory (for non-theoreticians) Proceedings of the Genetic and Evolutionary Computation Conference Companion, (369-398)
- Bambury H, Bultel A and Doerr B Generalized jump functions Proceedings of the Genetic and Evolutionary Computation Conference, (1124-1132)
- Benbaki R, Benomar Z and Doerr B A rigorous runtime analysis of the 2-MMASib on jump functions Proceedings of the Genetic and Evolutionary Computation Conference, (4-13)
- Huang Z, Chen Z and Zhou Y Analysis on the Efficiency of Multifactorial Evolutionary Algorithms Parallel Problem Solving from Nature – PPSN XVI, (634-647)
- Antipov D, Buzdalov M and Doerr B First Steps Towards a Runtime Analysis When Starting with a Good Solution Parallel Problem Solving from Nature – PPSN XVI, (560-573)
- Rajabi A and Witt C Evolutionary Algorithms with Self-adjusting Asymmetric Mutation Parallel Problem Solving from Nature – PPSN XVI, (664-677)
- Doerr B A gentle introduction to theory (for non-theoreticians) Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, (373-403)
- Antipov D, Buzdalov M and Doerr B Fast mutation in crossover-based algorithms Proceedings of the 2020 Genetic and Evolutionary Computation Conference, (1268-1276)
- Doerr B Does comma selection help to cope with local optima? Proceedings of the 2020 Genetic and Evolutionary Computation Conference, (1304-1313)
- Corus D, Oliveto P and Yazdani D (2019). Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem, Artificial Intelligence, 274:C, (180-196), Online publication date: 1-Sep-2019.
- Neumann F and Sutton A Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, (147-153)
- Doerr B An exponential lower bound for the runtime of the compact genetic algorithm on jump functions Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, (25-33)
- Hevia Fajardo M An empirical evaluation of success-based parameter control mechanisms for evolutionary algorithms Proceedings of the Genetic and Evolutionary Computation Conference, (787-795)
- Antipov D, Doerr B and Yang Q The efficiency threshold for the offspring population size of the (µ, λ) EA Proceedings of the Genetic and Evolutionary Computation Conference, (1461-1469)
- Doerr B, Doerr C and Neumann F Fast re-optimization via structural diversity Proceedings of the Genetic and Evolutionary Computation Conference, (233-241)
- Doerr B Theory for non-theoreticians Proceedings of the Genetic and Evolutionary Computation Conference Companion, (523-549)
- Doerr B, Gieβen C, Witt C and Yang J (2019). The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate, Algorithmica, 81:2, (593-631), Online publication date: 1-Feb-2019.
- Qian C, Bian C, Jiang W and Tang K (2019). Running Time Analysis of the ($$1+1$$1+1)-EA for OneMax and LeadingOnes Under Bit-Wise Noise, Algorithmica, 81:2, (749-795), Online publication date: 1-Feb-2019.
- Doerr B, Doerr C and Kötzing T (2019). Solving Problems with Unknown Solution Length at Almost No Extra Cost, Algorithmica, 81:2, (703-748), Online publication date: 1-Feb-2019.
- Shi F, Schirneck M, Friedrich T, Kötzing T and Neumann F (2019). Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints, Algorithmica, 81:2, (828-857), Online publication date: 1-Feb-2019.
- (2019). The analysis of evolutionary optimisation on the TSP1,2 problem, International Journal of Computational Science and Engineering, 18:3, (261-268), Online publication date: 1-Jan-2019.
- Bian C, Qian C and Tang K A general approach to running time analysis of multi-objective evolutionary algorithms Proceedings of the 27th International Joint Conference on Artificial Intelligence, (1405-1411)
- Doerr B Theory for non-theoreticians Proceedings of the Genetic and Evolutionary Computation Conference Companion, (389-414)
- Qian C, Bian C, Yu Y, Tang K and Yao X Analysis of noisy evolutionary optimization when sampling fails Proceedings of the Genetic and Evolutionary Computation Conference, (1507-1514)
- Shi F, Neumann F and Wang J Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problem Proceedings of the Genetic and Evolutionary Computation Conference, (1515-1522)
- Gieβen C and Witt C (2018). Optimal Mutation Rates for the (1+$$\lambda $$ź) EA on OneMax Through Asymptotically Tight Drift Analysis, Algorithmica, 80:5, (1710-1731), Online publication date: 1-May-2018.
- Doerr B, Doerr C and Kötzing T (2018). Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables, Algorithmica, 80:5, (1732-1768), Online publication date: 1-May-2018.
- Xia X and Zhou Y (2018). On the effectiveness of immune inspired mutation operators in some discrete optimization problems, Information Sciences: an International Journal, 426:C, (87-100), Online publication date: 1-Feb-2018.
- (2018). An order-based algorithm for minimum dominating set with application in graph mining, Information Sciences: an International Journal, 426:C, (101-116), Online publication date: 1-Feb-2018.
- Doerr B Theory for non-theoreticians Proceedings of the Genetic and Evolutionary Computation Conference Companion, (389-412)
- Qian C, Bian C, Jiang W and Tang K Running time analysis of the (1+1)-EA for onemax and leadingones under bit-wise noise Proceedings of the Genetic and Evolutionary Computation Conference, (1399-1406)
- Doerr B, Le H, Makhmara R and Nguyen T Fast genetic algorithms Proceedings of the Genetic and Evolutionary Computation Conference, (777-784)
- Shi F, Schirneck M, Friedrich T, Kötzing T and Neumann F Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints Proceedings of the Genetic and Evolutionary Computation Conference, (1407-1414)
- Sudholt D (2017). How crossover speeds up building block assembly in genetic algorithms, Evolutionary Computation, 25:2, (237-274), Online publication date: 1-Jun-2017.
- Moraglio A and Sudholt D (2017). Principled design and runtime analysis of abstract convex evolutionary search, Evolutionary Computation, 25:2, (205-236), Online publication date: 1-Jun-2017.
- Lissovoi A and Witt C (2017). A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization, Algorithmica, 78:2, (641-659), Online publication date: 1-Jun-2017.
- Gieβen C and Witt C (2017). The Interplay of Population Size and Mutation Probability in the ($$1+\lambda $$1+ź) EA on OneMax, Algorithmica, 78:2, (587-609), Online publication date: 1-Jun-2017.
- Paixão T, Pérez Heredia J, Sudholt D and Trubenová B (2017). Towards a Runtime Comparison of Natural and Artificial Evolution, Algorithmica, 78:2, (681-713), Online publication date: 1-Jun-2017.
- Doerr B, Neumann F and Sutton A (2017). Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas, Algorithmica, 78:2, (561-586), Online publication date: 1-Jun-2017.
- Friedrich T, Kötzing T, Lagodzinski G, Neumann F and Schirneck M Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, (45-54)
- Doerr B and Doerr C Theory for Non-Theoreticians Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, (463-482)
- Doerr B, Doerr C and Koetzing T The Right Mutation Strength for Multi-Valued Decision Variables Proceedings of the Genetic and Evolutionary Computation Conference 2016, (1115-1122)
- Wu J, Polyakovskiy S and Neumann F On the Impact of the Renting Rate for the Unconstrained Nonlinear Knapsack Problem Proceedings of the Genetic and Evolutionary Computation Conference 2016, (413-419)
- Goldman B and Sudholt D Runtime Analysis for the Parameter-less Population Pyramid Proceedings of the Genetic and Evolutionary Computation Conference 2016, (669-676)
- Doerr B, Gao W and Neumann F Runtime Analysis of Evolutionary Diversity Maximization for OneMinMax Proceedings of the Genetic and Evolutionary Computation Conference 2016, (557-564)
- Lissovoi A and Witt C (2016). MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions, Algorithmica, 75:3, (554-576), Online publication date: 1-Jul-2016.
- Dang D and Lehre P (2016). Runtime Analysis of Non-elitist Populations, Algorithmica, 75:3, (428-461), Online publication date: 1-Jul-2016.
- Sutton A (2016). Superpolynomial Lower Bounds for the $$(1+1)$$(1+1) EA on Some Easy Combinatorial Problems, Algorithmica, 75:3, (507-528), Online publication date: 1-Jul-2016.
- Muñoz M, Sun Y, Kirley M and Halgamuge S (2015). Algorithm selection for black-box continuous optimization problems, Information Sciences: an International Journal, 317:C, (224-245), Online publication date: 1-Oct-2015.
- Liu G, Guo W, Li R, Niu Y and Chen G (2015). XGRouter, Frontiers of Computer Science: Selected Publications from Chinese Universities, 9:4, (576-594), Online publication date: 1-Aug-2015.
- Neumann F and Witt C On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling Proceedings of the 24th International Conference on Artificial Intelligence, (3742-3748)
- Qian C, Yu Y and Zhou Z On constrained boolean pareto optimization Proceedings of the 24th International Conference on Artificial Intelligence, (389-395)
- Neumann F and Sutton A Parameterized Complexity Analysis of Evolutionary Algorithms Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, (435-450)
- Paixao T, Pérez Heredia J, Sudholt D and Trubenova B First Steps Towards a Runtime Comparison of Natural and Artificial Evolution Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (1455-1462)
- Gießen C and Witt C Population Size vs. Mutation Strength for the (1+λ) EA on OneMax Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (1439-1446)
- Lissovoi A and Witt C On the Utility of Island Models in Dynamic Optimization Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (1447-1454)
- Doerr B, Doerr C and Kötzing T Solving Problems with Unknown Solution Length at (Almost) No Extra Cost Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (831-838)
- Doerr B, Neumann F and Sutton A Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (1415-1422)
- Pourhassan M and Neumann F On the Impact of Local Search Operators and Variable Neighbourhood Search for the Generalized Travelling Salesperson Problem Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, (465-472)
- Kötzing T, Lissovoi A and Witt C (1+1) EA on Generalized Dynamic OneMax Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, (40-51)
- Oliveto P and Zarges C (2015). Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change, Theoretical Computer Science, 561:PA, (37-56), Online publication date: 4-Jan-2015.
- Lissovoi A and Witt C (2015). Runtime analysis of ant colony optimization on dynamic shortest path problems, Theoretical Computer Science, 561:PA, (73-85), Online publication date: 4-Jan-2015.
- (2015). Optimizing linear functions with the ( 1 + λ ) evolutionary algorithm-Different asymptotic runtimes for different instances, Theoretical Computer Science, 561:PA, (3-23), Online publication date: 4-Jan-2015.
- Lässig J and Sudholt D (2014). Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization, Theoretical Computer Science, 551:C, (66-83), Online publication date: 25-Sep-2014.
- Neumann F and Sutton A Parameterized complexity analysis of evolutionary algorithms Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, (607-622)
- Mambrini A and Manzoni L A comparison between geometric semantic GP and cartesian GP for boolean functions learning Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, (143-144)
- Wei K and Dinneen M Runtime analysis to compare best-improvement and first-improvement in memetic algorithms Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (1439-1446)
- Jansen T and Zarges C Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problem Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (975-982)
- Colin `, Doerr B and Férey G Monotonic functions in EC Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (753-760)
- Nallaperuma S, Neumann F and Sudholt D A fixed budget analysis of randomized search heuristics for the traveling salesperson problem Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (807-814)
- Lissovoi A and Witt C MMAS vs. population-based EA on a family of dynamic fitness functions Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (1399-1406)
- Gao W and Neumann F Runtime analysis for maximizing population diversity in single-objective optimization Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (777-784)
- Witt C Revised analysis of the (1+1) ea for the minimum spanning tree problem Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, (509-516)
- Jansen T and Zarges C Artificial immune systems for optimisation Proceedings of the 15th annual conference companion on Genetic and evolutionary computation, (779-796)
- Neumann F and Witt C Bioinspired computation in combinatorial optimization Proceedings of the 15th annual conference companion on Genetic and evolutionary computation, (567-590)
- Doerr B and Künnemann M How the (1+λ) evolutionary algorithm optimizes linear functions Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1589-1596)
- Lissovoi A and Witt C Runtime analysis of ant colony optimization on dynamic shortest path problems Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1605-1612)
- Oliveto P and Witt C Improved runtime analysis of the simple genetic algorithm Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1621-1628)
- Doerr B, Jansen T, Witt C and Zarges C A method to derive fixed budget results from expected optimisation times Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1581-1588)
- Nguyen A, Sutton A and Neumann F Population size matters Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1613-1620)
- Kempka J, McMinn P and Sudholt D A theoretical runtime and empirical analysis of different alternating variable searches for search-based testing Proceedings of the 15th annual conference on Genetic and evolutionary computation, (1445-1452)
- Oliveto P and Zarges C Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change Proceedings of the 15th annual conference on Genetic and evolutionary computation, (837-844)
- Corus D, Lehre P and Neumann F The generalized minimum spanning tree problem Proceedings of the 15th annual conference on Genetic and evolutionary computation, (519-526)
- Chalupa D An analytical investigation of block-based mutation operators for order-based stochastic clique covering algorithms Proceedings of the 15th annual conference on Genetic and evolutionary computation, (495-502)
- Kratsch S and Neumann F (2013). Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem, Algorithmica, 65:4, (754-771), Online publication date: 1-Apr-2013.
- Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O and Trautmann H A feature-based comparison of local search and the christofides algorithm for the travelling salesperson problem Proceedings of the twelfth workshop on Foundations of genetic algorithms XII, (147-160)
- Moraglio A, Mambrini A and Manzoni L Runtime analysis of mutation-based geometric semantic genetic programming on boolean functions Proceedings of the twelfth workshop on Foundations of genetic algorithms XII, (119-132)
- Lehre P and Özcan E A runtime analysis of simple hyper-heuristics Proceedings of the twelfth workshop on Foundations of genetic algorithms XII, (97-104)
- Jansen T, Oliveto P and Zarges C Approximating vertex cover using edge-based representations Proceedings of the twelfth workshop on Foundations of genetic algorithms XII, (87-96)
- Lehre P and Witt C (2012). Black-Box Search by Unbiased Variation, Algorithmica, 64:4, (623-642), Online publication date: 1-Dec-2012.
- Yao X (2012). Ubiquity symposium: Evolutionary computation and the processes of life, Ubiquity, 2012:September, (1-8), Online publication date: 1-Sep-2012.
- Qian C, Yu Y and Zhou Z On algorithm-dependent boundary case identification for problem classes Proceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part I, (62-71)
- Sutton A and Neumann F A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling Proceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part I, (52-61)
- Wagner M and Neumann F Parsimony pressure versus multi-objective optimization for variable length representations Proceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part I, (133-142)
- Neumann F and Witt C Bioinspired computation in combinatorial optimization Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, (1035-1058)
- Oliveto P and Witt C On the analysis of the simple genetic algorithm Proceedings of the 14th annual conference on Genetic and evolutionary computation, (1341-1348)
- Kötzing T, Sutton A, Neumann F and O'Reilly U The max problem revisited Proceedings of the 14th annual conference on Genetic and evolutionary computation, (1333-1340)
- Minku L, Sudholt D and Yao X Evolutionary algorithms for the project scheduling problem Proceedings of the 14th annual conference on Genetic and evolutionary computation, (1221-1228)
- Neumann F Computational complexity analysis of multi-objective genetic programming Proceedings of the 14th annual conference on Genetic and evolutionary computation, (799-806)
- Moraglio A and Sudholt D Runtime analysis of convex evolutionary search Proceedings of the 14th annual conference on Genetic and evolutionary computation, (649-656)
- Sutton A, Day J and Neumann F A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT Proceedings of the 14th annual conference on Genetic and evolutionary computation, (433-440)
- Chalupa D On the efficiency of an order-based representation in the clique covering problem Proceedings of the 14th annual conference on Genetic and evolutionary computation, (353-360)
- Yao X Unpacking and understanding evolutionary algorithms Proceedings of the 2012 World Congress conference on Advances in Computational Intelligence, (60-76)
- Zhou D, Luo D, Lu R and Han Z (2012). The use of tail inequalities on the probable computational time of randomized search heuristics, Theoretical Computer Science, 436, (106-117), Online publication date: 1-Jun-2012.
- Witt C Theory of randomized search heuristics in combinatorial optimization Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, (1233-1260)
- Kötzing T, Neumann F and Spöhel R PAC learning and genetic programming Proceedings of the 13th annual conference on Genetic and evolutionary computation, (2091-2096)
- Neumann F, Oliveto P, Rudolph G and Sudholt D On the effectiveness of crossover for migration in parallel evolutionary algorithms Proceedings of the 13th annual conference on Genetic and evolutionary computation, (1587-1594)
- Kötzing T, Sudholt D and Theile M How crossover helps in pseudo-boolean optimization Proceedings of the 13th annual conference on Genetic and evolutionary computation, (989-996)
- Doerr B, Lengler J, Kötzing T and Winzen C Black-box complexities of combinatorial problems Proceedings of the 13th annual conference on Genetic and evolutionary computation, (981-988)
- Yang X Metaheuristic optimization Proceedings of the 10th international conference on Experimental algorithms, (21-32)
- Doerr B, Johannsen D and Schmidt M Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, (119-126)
- Durrett G, Neumann F and O'Reilly U Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, (69-80)
- Jansen T and Zarges C Analysis of evolutionary algorithms Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, (1-14)
- Qian H and Yu Y On sampling-and-classification optimization in discrete domains 2016 IEEE Congress on Evolutionary Computation (CEC), (4374-4381)
- Losey D, McDonald C and O'Malley M A bio-inspired algorithm for identifying unknown kinematics from a discrete set of candidate models by using collision detection 2016 6th IEEE International Conference on Biomedical Robotics and Biomechatronics (BioRob), (418-423)
Index Terms
- Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity
Reviews
Manish K Gupta
Biology has long inspired engineering and impacted technology. Recently, in fact, a new branch of natural information and communication technology (ICT) has emerged, thus bridging biology and engineering so that the communication of ideas is possible in both directions. On the one hand, we want to learn the principles of ICT in nature. On the other hand, we want to build useful objects either by using these principles or by applying them to solve problems in various domains of engineering. This book is about nature-inspired algorithms for solving problems in combinatorial optimization. It consists of three parts. Part 1 (chapters 1 through 4) provides an introduction to combinatorial optimization. Chapter 1 gives a short overview of the area, and chapter 2 gives an overview of combinatorial optimization and computational complexity. Chapter 3 introduces two special stochastic search algorithms-namely, evolutionary algorithms and ant colony optimization-that were inspired by nature. Chapter 4 discusses stochastic search algorithms for single-objective optimization. Part 2 (chapters 5 through 9) focuses on single-objective optimization problems, such as minimum spanning trees, maximum matching, makespan scheduling, shortest paths, and Eulerian cycles. These problems are analyzed in light of evolutionary algorithms and ant colony optimization. Part 3 (chapters 10 through 13) focuses on multi-objective optimization for minimum spanning trees, covering problems, and cutting problems. The appendix provides some elementary mathematical material. This timely book will be useful to many researchers and advanced undergraduate and graduate students. The key strength of the book is the complexity analysis of the algorithms for a variety of combinatorial optimization problems on graphs. Furthermore, it provides a comprehensive treatment of evolutionary algorithms and ant colony optimization. The book is recommended to anyone working in the areas of computational complexity, combinatorial optimization, and engineering. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Please enable JavaScript to view thecomments powered by Disqus.
Recommendations
Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationBioinspired computation methods, such as evolutionary algorithms and ant colony optimization, are being applied successfully to complex engineering and combinatorial optimization problems, and it is very important that we understand the computational ...
Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary ComputationBioinspired computation in combinatorial optimization: algorithms and their computational complexity
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation