Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
复制标题
DOI：
10.1145/2464576.2466738
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
F. Neumann;C. Witt
中科院分区：
文献类型：
--
作者：
F. Neumann;C. Witt
受生物启发的计算方法，例如进化算法和蚁群优化算法，正成功地应用于复杂的工程和组合优化问题，而且我们理解这些算法的计算复杂性是非常重要的。本教程讲解了在该领域所取得的最重要的成果。授课者展示了如何以严谨的方式分析运行时行为，尤其是针对组合优化问题。他们介绍了一些著名的问题，比如最小生成树、最短路径、最大匹配以及覆盖和调度问题。首先研究了经典的单目标优化。然后他们研究了应用于所考虑的组合优化问题的多目标变体的受生物启发的计算的计算复杂性，并且特别展示了多目标优化如何有助于加快针对单目标优化问题的受生物启发的计算。本教程基于作者所写的同名书籍。关于该书的更多信息可在www.bioinspiredcomputation.com找到。
Bioinspired 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 complexity of these algorithms. This tutorials explains the most important results achieved in this area. The presenters show how runtime behavior can be analyzed in a rigorous way, in particular for combinatorial optimization. They present well-known problems such as minimum spanning trees, shortest paths, maximum matching, and covering and scheduling problems. Classical single objective optimization is examined first. They then investigate the computational complexity of bioinspired computation applied to multiobjective variants of the considered combinatorial optimization problems, and in particular they show how multiobjective optimization can help to speed up bioinspired computation for single-objective optimization problems. The tutorial is based on a book written by the authors with the same title. Further information about the book can be found at www.bioinspiredcomputation.com.