Ant Colony Optimization
Ant Colony Optimization
复制标题
DOI：
10.1007/978-3-540-39930-8_5
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
V. Maniezzo;L. Gambardella;Fabio de Luigi
中科院分区：
文献类型：
--
作者：
V. Maniezzo;L. Gambardella;Fabio de Luigi
蚁群优化算法是一种设计求解组合优化问题的元启发式算法的范例。第一个可以在这个框架内分类的算法是在1991年提出的[21，13]，从那时起，文献中报道了基本原理的许多不同变体。蚁群算法的基本特点是结合了先验信息的结构，一个有前途的解决方案与后验信息的结构，以前获得的好的解决方案。元启发式算法是为了逃离局部最优而驱动一些基本启发式的算法：从空解开始并添加元素以构建良好的完整解的构造性启发式，或者从完整解开始并迭代修改其一些元素以实现更好的局部搜索启发式。元启发式部分允许低级启发式获得比它单独实现的更好的解决方案，即使迭代。通常，控制机制是通过约束或随机化局部相邻解的集合来实现的，以在局部搜索中考虑（如模拟退火[46]或禁忌搜索[33]的情况），或者通过组合不同解所采用的元素（如进化策略[11]和遗传[40]或生物学[56]算法的情况）。ACO算法的特点是显式地使用以前解的元素。事实上，他们驱动一个建设性的低级解决方案，就像GRASP [30]一样，但将其包含在人口框架中，并以蒙特卡洛方式随机构建。遗传算法[40]也提出了不同解元素的Monte Carlo组合，但在ACO的情况下，概率分布由先前获得的解分量明确定义。定义组件和相关概率的特定方式是特定于问题的，并且可以以不同的方式设计，面临用于条件化的信息的特异性与在有效地偏置概率分布之前需要构建的解决方案的数量之间的权衡。
Ant Colony Optimization (ACO) is a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. The first algorithm which can be classified within this framework was presented in 1991 [21, 13] and, since then, many diverse variants of the basic principle have been reported in the literature. The essential trait of ACO algorithms is the combination of a priori information about the structure of a promising solution with a posteriori information about the structure of previously obtained good solutions. Metaheuristic algorithms are algorithms which, in order to escape from local optima, drive some basic heuristic: either a constructive heuristic starting from a null solution and adding elements to build a good complete one, or a local search heuristic starting from a complete solution and iteratively modifying some of its elements in order to achieve a better one. The metaheuristic part permits the lowlevel heuristic to obtain solutions better than those it could have achieved alone, even if iterated. Usually, the controlling mechanism is achieved either by constraining or by randomizing the set of local neighbor solutions to consider in local search (as is the case of simulated annealing [46] or tabu search [33]), or by combining elements taken by different solutions (as is the case of evolution strategies [11] and genetic [40] or bionomic [56] algorithms). The characteristic of ACO algorithms is their explicit use of elements of previous solutions. In fact, they drive a constructive low-level solution, as GRASP [30] does, but including it in a population framework and randomizing the construction in a Monte Carlo way. A Monte Carlo combination of different solution elements is suggested also by Genetic Algorithms [40], but in the case of ACO the probability distribution is explicitly defined by previously obtained solution components. The particular way of defining components and associated probabilities is problem-specific, and can be designed in different ways, facing a trade-off between the specificity of the information used for the conditioning and the number of solutions which need to be constructed before effectively biasing the probability dis-