更改

蚁群优化算法 (查看源代码)

2020年12月1日 (二) 10:13的版本

添加24,319字节、 2020年12月1日 (二) 10:13

无编辑摘要

第106行：第106行：

Nature offers several examples of how minuscule organisms, if they all follow the same basic rule, can create a form of collective intelligence on the macroscopic level. Colonies of social insects perfectly illustrate this model which greatly differs from human societies. This model is based on the co-operation of independent units with simple and unpredictable behavior. They move through their surrounding area to carry out certain tasks and only possess a very limited amount of information to do so. A colony of ants, for example, represents numerous qualities that can also be applied to a network of ambient objects. Colonies of ants have a very high capacity to adapt themselves to changes in the environment as well as an enormous strength in dealing with situations where one individual fails to carry out a given task. This kind of flexibility would also be very useful for mobile networks of objects which are perpetually developing. Parcels of information that move from a computer to a digital object behave in the same way as ants would do. They move through the network and pass from one knot to the next with the objective of arriving at their final destination as quickly as possible.

−

大自然中存在很多例子，说明了微小的生物体如果都遵循同样的基本规则，是如何创造出一种宏观层面的集体智慧的。社会性昆虫的群落完美地说明了这个与人类社会有很大不同的模型。该模型基于具有简单和不可预测行为的独立单元之间的合作。他们穿过周围地区执行某些任务，但只掌握了非常有限的信息。例如，一群蚂蚁代表了许多可以应用到环境对象的网络中的特性。蚂蚁群体具有很高的适应环境变化的能力，并且在处理某项个体无法完成的任务时具有很大的能力。这种灵活性对于不断发展的移动网络也是非常有用的。从一台计算机到一个数字化对象的信息包和蚂蚁的行为一样。它们穿过网络并从一个节点传到下一个节点，目的是尽快到达终点。

+

大自然中存在很多例子，说明了微小的生物体如果都遵循同样的基本规则，是如何创造出一种宏观层面的集体智慧的。社会性昆虫的群落完美地说明了这个与人类社会有很大不同的模型。该模型基于具有简单和不可预测行为的独立单元之间的合作。<ref>{{cite book|last = Waldner |first = Jean-Baptiste |authorlink = Jean-Baptiste Waldner |title = Inventer l'Ordinateur du XXIème Siècle |publisher = [[Hermes Science]] |place = London |year = 2007 | pages = 259–265 |isbn = 978-2-7462-1516-0}}</ref> 他们穿过周围地区执行某些任务，但只掌握了非常有限的信息。例如，一群蚂蚁代表了许多可以应用到环境对象的网络中的特性。蚂蚁群体具有很高的适应环境变化的能力，并且在处理某项个体无法完成的任务时具有很大的能力。这种灵活性对于不断发展的移动网络也是非常有用的。从一台计算机到一个数字化对象的信息包和蚂蚁的行为一样。它们穿过网络并从一个节点传到下一个节点，目的是尽快到达终点。<ref>{{cite book |last = Waldner |first = Jean-Baptiste |authorlink = Jean-Baptiste Waldner |title = Nanocomputers and Swarm Intelligence |publisher = ISTE John Wiley & Sons |place = London |year = 2008 |isbn = 978-1-84704-002-2 | page = 215}}</ref>

第122行：第122行：

bees, ants and termites; both for inter-agent and agent-swarm communications. Due to its feasibility, artificial pheromones have been adopted in multi-robot and swarm robotic systems. Pheromone-based communication was implemented by different means such as chemical or physical (RFID tags, light, sound) ways. However, those implementations were not able to replicate all the aspects of pheromones as seen in nature.

−

蜜蜂、蚂蚁和白蚁; 既用于主体之间的通信也用于主体与群体之间的通信。由于其可行性，人工信息素已被应用于多机器人和群机器人系统中。基于信息素的通信是通过化学或物理(~~RFID标签、光、声~~)方式实现的。然而，这些方式并不能复制信息素在自然中呈现的所有方面。

+

蜜蜂、蚂蚁和白蚁; 既用于主体之间的通信也用于主体与群体之间的通信。由于其可行性，人工信息素已被应用于多机器人和群机器人系统中。基于信息素的通信是通过化学<ref>Lima, Danielli A., and Gina MB Oliveira. "[https://doi.org/10.1016/j.apm.2017.03.021 A cellular automata ant memory model of foraging in a swarm of robots]." Applied Mathematical Modelling 47, 2017: 551-572.</ref><ref>Russell, R. Andrew. "[https://ieeexplore.ieee.org/abstract/document/774005/ Ant trails-an example for robots to follow?]." Robotics and Automation, 1999. Proceedings. 1999 IEEE International Conference on. Vol. 4. IEEE, 1999.</ref><ref>Fujisawa, Ryusuke, et al. "[https://www.researchgate.net/profile/Shigeto_Dobata/publication/265053113_Designing_pheromone_communication_in_swarm_robotics_Group_foraging_behavior_mediated_by_chemical_substance/links/551500f60cf260a7cb2e39eb.pdf Designing pheromone communication in swarm robotics: Group foraging behavior mediated by chemical substance]." Swarm Intelligence 8.3 (2014): 227-246.</ref>或物理(RFID标签<ref>Sakakibara, Toshiki, and Daisuke Kurabayashi. "[https://link.springer.com/article/10.1016/S1672-6529(07)60038-9 Artificial pheromone system using rfid for navigation of autonomous robots]." Journal of Bionic Engineering 4.4 (2007): 245-253.</ref>、光<ref>Arvin, Farshad, et al. "[http://eprints.lincoln.ac.uk/22466/7/Aggregation-Final.pdf Investigation of cue-based aggregation in static and dynamic environments with a mobile robot swarm]." Adaptive Behavior (2016): 1-17.</ref><ref>Farshad Arvin, et al. "[https://www.researchgate.net/profile/Masoud_Bekravi/publication/241683938_Imitation_of_Honeybee_Aggregation_with_Collective_Behavior_of_Swarm_Robots/links/546518320cf25b85d17d2587/Imitation-of-Honeybee-Aggregation-with-Collective-Behavior-of-Swarm-Robots.pdf Imitation of honeybee aggregation with collective behavior of swarm robots]." International Journal of Computational Intelligence Systems 4.4 (2011): 739-748.</ref><ref>Schmickl, Thomas, et al. "[http://swarmrobot.org/publications/Get_in_touch.pdf Get in touch: cooperative decision making based on robot-to-robot collisions]." Autonomous Agents and Multi-Agent Systems 18.1 (2009): 133-155.</ref><ref>Garnier, Simon, et al. "[http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1002903 Do ants need to estimate the geometrical properties of trail bifurcations to find an efficient route? A swarm robotics test bed.]" PLoS Comput Biol 9.3 (2013): e1002903.</ref>、声<ref>Arvin, Farshad, et al. "[https://www.researchgate.net/profile/Farshad_Arvin/publication/273892103_Cue-based_aggregation_with_a_mobile_robot_swarm_A_novel_fuzzy-based_method/links/55e4b97a08ae6abe6e9031be/Cue-based-aggregation-with-a-mobile-robot-swarm-A-novel-fuzzy-based-method.pdf Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method]." Adaptive Behavior 22.3 (2014): 189-206.</ref>)方式实现的。然而，这些方式并不能复制信息素在自然中呈现的所有方面。

第130行：第130行：

Using projected light was presented in an 2007 IEEE paper by Garnier, Simon, et al. as an experimental setup to study pheromone-based communication with micro autonomous robots. Another study that proposed a novel pheromone communication method, COSΦ, for a swarm robotic system is based on precise and fast visual localization.

−

2007年，Garnier，Simon 等人在一篇IEEE论文中提出了使用投射光作为研究基于信息素的微型自主机器人通信的实验装置。另一项针对群机器人系统的研究提出了一种新颖的信息素通信方法 cosφ，该方法基于精确快速的视觉定位。

+

2007年，Garnier，Simon 等人在一篇IEEE论文<ref>Garnier, Simon, et al. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.716.1460&rep=rep1&type=pdf Alice in pheromone land: An experimental setup for the study of ant-like robots]." 2007 IEEE Swarm Intelligence Symposium. IEEE, 2007.</ref> 中提出了使用投射光作为研究基于信息素的微型自主机器人通信的实验装置。另一项针对群机器人系统的研究提出了一种新颖的信息素通信方法 cosφ<ref>Farshad Arvin et al. "[http://eprints.lincoln.ac.uk/17957/1/APH-colias.pdf COSΦ: artificial pheromone system for robotic swarms research]." IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2015.</ref>，该方法基于精确快速的视觉定位。<ref>Krajník, Tomáš, et al. "[http://eprints.lincoln.ac.uk/13653/1/jint_2014_public.pdf A practical multirobot localization system]." Journal of Intelligent & Robotic Systems 76.3-4 (2014): 539-562.</ref>

The system allows simulation of a virtually unlimited number of different pheromones and provides the result of their interaction as a gray-scale image on a horizontal LCD screen that the robots move on. In order to demonstrate the pheromone communication method, Colias autonomous micro robot was deployed as the swarm robotic platform.{{Citation needed|date=December 2019|reason=removed citation to predatory publisher content}}

第257行：第257行：

<math>\tau_{xy}</math> is the amount of pheromone deposited for transition from state <math>x</math> to <math>y</math>, 0 ≤ <math>\alpha</math> is a parameter to control the influence of <math>\tau_{xy}</math>, <math>\eta_{xy}</math> is the desirability of state transition <math>xy</math> (a priori knowledge, typically <math>1/d_{xy}</math>, where <math>d</math> is the distance) and <math>\beta</math> ≥ 1 is a parameter to control the influence of <math>\eta_{xy}</math>. <math>\tau_{xz}</math> and <math>\eta_{xz}</math> represent the trail level and attractiveness for the other possible state transitions.

−

~~τxy是从状态x到y的信息素积累量，0≤α是控制τxy影响的参数，ηxy是状态转换xy的期望值（一种先验信息，通常为1~~/~~dxy，其中d是距离），β≥1是控制ηxy影响的参数。τxz和ηxz代表了其他可能的状态转移的轨迹浓度等级和吸引力~~

+

<math>\tau_{xy}</math> 是从状态<math>x</math> 到<math>y</math> 的信息素积累量，0 ≤ <math>\alpha</math>是控制<math>\tau_{xy}</math> 影响的参数，<math>\eta_{xy}</math> 是状态转换<math>xy</math> 的期望值（一种先验信息，通常为<math>1/d_{xy}</math>，其中d是距离），<math>\beta</math>≥1是控制<math>\eta_{xy}</math>影响的参数。<math>\tau_{xz}</math>和<math>\eta_{xz}</math>代表了其他可能的状态转移的轨迹浓度等级和吸引力

第299行：第299行：

where <math>\tau_{xy}</math> is the amount of pheromone deposited for a state transition <math>xy</math>, <math>\rho</math> is the pheromone evaporation coefficient and <math>\Delta \tau^{k}_{xy}</math> is the amount of pheromone deposited by <math>k</math>th ant, typically given for a TSP problem (with moves corresponding to arcs of the graph) by

−

~~式中，τxy是状态转换xy的信息素沉积量，ρ是信息素蒸发系数，Δτkxy是第k只蚂蚁沉积的信息素量，通常针对TSP问题（移动对应于图的弧）给出：~~

+

式中，<math>\tau_{xy}</math>是状态转换<math>xy</math>的信息素沉积量，<math>\rho</math>是信息素蒸发系数，<math>\Delta \tau^{k}_{xy}</math>是第<math>k</math>只蚂蚁沉积的信息素量，通常针对TSP问题（移动对应于图的弧）给出：

第364行：第364行：

The Ant System is the first ACO algorithm. This algorithm corresponds to the one presented above. It was developed by Dorigo.

−

蚂蚁系统是第一种蚁群算法。此算法与前述算法相对应。它是由 Dorigo 开发的。

+

蚂蚁系统是第一种蚁群算法。此算法与前述算法相对应。它是由 Dorigo 开发的。<ref name="Ant system" />

+

第375行：第376行：

In the Ant Colony System algorithm, the original Ant System was modified in three aspects: (i) the edge selection is biased towards exploitation (i.e. favoring the probability of selecting the shortest edges with a large amount of pheromone); (ii) while building a solution, ants change the pheromone level of the edges they are selecting by applying a local pheromone updating rule; (iii) at the end of each iteration, only the best ant is allowed to update the trails by applying a modified global pheromone updating rule.

−

在蚁群系统算法中，原来的蚁群算法在三个方面进行了改进：（一）边的选择偏向于'''开发'''。（即偏向具有大量信息素的最短边的概率）；（二）在求解过程中，蚂蚁通过应用局部信息素更新规则来改变所选边的信息素水平；（iii）在每次迭代结束时，只允许最优的蚂蚁通过改进的全局信息素更新规则来更新路径。

+

在蚁群系统算法中，原来的蚁群算法在三个方面进行了改进：（一）边的选择偏向于'''开发'''。（即偏向具有大量信息素的最短边的概率）；（二）在求解过程中，蚂蚁通过应用局部信息素更新规则来改变所选边的信息素水平；（iii）在每次迭代结束时，只允许最优的蚂蚁通过改进的全局信息素更新规则来更新路径。<ref name="M. Dorigo et L.M. Gambardella">M. Dorigo et L.M. Gambardella, ''[http://www.idsia.ch/~luca/acs-ec97.pdf Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem]'', IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.</ref>

第390行：第391行：

This algorithm controls the maximum and minimum pheromone amounts on each trail. Only the global best tour or the iteration best tour are allowed to add pheromone to its trail. To avoid stagnation of the search algorithm, the range of possible pheromone amounts on each trail is limited to an interval [τmax,τmin]. All edges are initialized to τmax to force a higher exploration of solutions. The trails are reinitialized to τmax when nearing stagnation.

−

该算法控制每条路线上信息素的最大和最小数量。只有全局最优或迭代最优才允许在其路线中添加信息素。为了避免搜索算法的停滞不前，每条路径上可能的信息素数量范围被限制在一个区间[~~τmax~~,~~τmin~~]~~。所有边都被初始化为τmax，以进行最多的求解。当算法接近停滞状态时，路线被重新初始化为τmax~~ 。

+

该算法控制每条路线上信息素的最大和最小数量。只有全局最优或迭代最优才允许在其路线中添加信息素。为了避免搜索算法的停滞不前，每条路径上可能的信息素数量范围被限制在一个区间[τmax,τmin]。所有边都被初始化为τmax，以进行最多的求解。当算法接近停滞状态时，路线被重新初始化为τmax。<ref name="T. Stützle et H.H. Hoos">T. Stützle et H.H. Hoos, ''MAX MIN Ant System'', Future Generation Computer Systems, volume 16, pages 889-914, 2000</ref>

+

第409行：第411行：

The pheromone deposit mechanism of COAC is to enable ants to search for solutions collaboratively and effectively. By using an orthogonal design method, ants in the feasible domain can explore their chosen regions rapidly and efficiently, with enhanced global search capability and accuracy. The orthogonal design method and the adaptive radius adjustment method can also be extended to other optimization algorithms for delivering wider advantages in solving practical problems.

−

COAC的信息素沉积机制使蚂蚁能够协同有效地寻找解决方案。利用正交化设计法，可行域中的蚂蚁可以快速有效地搜索所选区域，提高了全局搜索能力和准确性。正交设计法和自适应半径调整法也可以推广到其他优化算法中，在解决实际问题时具有更广泛的优势。

+

COAC的信息素沉积机制使蚂蚁能够协同有效地寻找解决方案。利用正交化设计法，可行域中的蚂蚁可以快速有效地搜索所选区域，提高了全局搜索能力和准确性。正交设计法和自适应半径调整法也可以推广到其他优化算法中，在解决实际问题时具有更广泛的优势。<ref>[http://eprints.gla.ac.uk/3894/ X Hu, J Zhang, and Y Li (2008). Orthogonal methods based ant colony search for solving continuous optimization problems. ''Journal of Computer Science and Technology'', 23(1), pp.2-18.]</ref>

第419行：第421行：

It is a recursive form of ant system which divides the whole search domain into several sub-domains and solves the objective on these subdomains. The results from all the subdomains are compared and the best few of them are promoted for the next level. The subdomains corresponding to the selected results are further subdivided and the process is repeated until an output of desired precision is obtained. This method has been tested on ill-posed geophysical inversion problems and works well.

−

它是蚂蚁系统的一种递归形式，将整个搜索域划分为若干子域，并在这些子域上求解。对所有子域的结果进行比较，并将其中最好的几个子域提升到下一个等级。与选定结果相对应的子区域被进一步细分，并重复这个过程，直到获得所需精度的输出。该方法在不适定地球物理反演问题中得到了验证，效果良好。

+

它是蚂蚁系统的一种递归形式，将整个搜索域划分为若干子域，并在这些子域上求解。<ref>Gupta, D.K.; Arora, Y.; Singh, U.K.; Gupta, J.P., "Recursive Ant Colony Optimization for estimation of parameters of a function," Recent Advances in Information Technology (RAIT), 2012 1st International Conference on , vol., no., pp.448-454, 15–17 March 2012</ref>对所有子域的结果进行比较，并将其中最好的几个子域提升到下一个等级。与选定结果相对应的子区域被进一步细分，并重复这个过程，直到获得所需精度的输出。该方法在不适定地球物理反演问题中得到了验证，效果良好。<ref>Gupta, D.K.; Gupta, J.P.; Arora, Y.; Shankar, U., "[http://nsg.eage.org/publication/download/?publication=68286 Recursive ant colony optimization: a new technique for the estimation of function parameters from geophysical field data]," Near Surface Geophysics , vol. 11, no. 3, pp.325-339</ref>

第429行：第431行：

For some versions of the algorithm, it is possible to prove that it is convergent (i.e., it is able to find the global optimum in finite time). The first evidence of convergence for an ant colony algorithm was made in 2000, the graph-based ant system algorithm, and later on for the ACS and MMAS algorithms. Like most metaheuristics, it is very difficult to estimate the theoretical speed of convergence. A performance analysis of a continuous ant colony algorithm with respect to its various parameters (edge selection strategy, distance measure metric, and pheromone evaporation rate) showed that its performance and rate of convergence are sensitive to the chosen parameter values, and especially to the value of the pheromone evaporation rate. In 2004, Zlochin and his colleagues showed that COAC-type algorithms could be assimilated methods of stochastic gradient descent, on the cross-entropy and estimation of distribution algorithm. They proposed these metaheuristics as a "research-based model".

−

对于某些版本的算法，可以证明它是收敛的(也就是说，它能在有限时间内找到全局最优解)。蚁群算法的收敛性在2000年首次得到证实，然后是基于图的蚂蚁系统算法，以及后来的 ACS 和 MMAS 算法。和大多数启发式算法一样，很难估计理论上的收敛速度。对连续蚁群算法相关各参数(边的选择策略、距离测度方法和信息素蒸发率)的性能分析表明，蚁群算法的性能和收敛速度对参数值，特别是信息素蒸发率的参数选择非常敏感。在2004年，Zlochin 和他的同事们展示了COAC类型的算法在交叉熵和分布估计算法中可以同化为随机梯度下降方法。他们提出这些元启发式算法作为一个“基于研究的模型”。

+

对于某些版本的算法，可以证明它是收敛的(也就是说，它能在有限时间内找到全局最优解)。蚁群算法的收敛性在2000年首次得到证实，然后是基于图的蚂蚁系统算法，以及后来的 ACS 和 MMAS 算法。和大多数启发式算法一样，很难估计理论上的收敛速度。对连续蚁群算法相关各参数(边的选择策略、距离测度方法和信息素蒸发率)的性能分析表明，蚁群算法的性能和收敛速度对参数值，特别是信息素蒸发率的参数选择非常敏感。<ref>V.K.Ojha, A. Abraham and V. Snasel, [https://arxiv.org/abs/1707.01812 ACO for Continuous Function Optimization: A Performance Analysis], 14th International Conference on Intelligent Systems Design and Applications (ISDA), Japan, Page 145 - 150, 2017, 978-1-4799-7938-7/14 2014 IEEE.</ref> 在2004年，Zlochin 和他的同事<ref name="Zlochin model-based search">M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, ''Model-based search for combinatorial optimization: A critical survey'', Annals of Operations Research, vol. 131, pp. 373-395, 2004.</ref>们展示了COAC类型的算法在交叉熵和分布估计算法中可以同化为随机梯度下降方法。他们提出这些元启发式算法作为一个“基于研究的模型”。

第459行：第461行：

The first ACO algorithm was called the ant system and it was aimed to solve the travelling salesman problem, in which the goal is to find the shortest round-trip to link a series of cities. The general algorithm is relatively simple and based on a set of ants, each making one of the possible round-trips along the cities. At each stage, the ant chooses to move from one city to another according to some rules:

−

第一个蚁群算法被称为蚂蚁系统，它的目标是解决旅行商问题，其中的目标是找到最短的往返路线连接一系列城市。一般的算法相对简单，可以基于一组蚂蚁，每个蚂蚁沿着城市进行一次可能的往返旅行。在每个阶段，蚂蚁都会根据一些规则从一个城市迁移到另一个城市:

+

第一个蚁群算法被称为蚂蚁系统<ref name="Ant system">M. Dorigo, V. Maniezzo, et A. Colorni, ''[http://www.cs.unibo.it/babaoglu/courses/cas05-06/tutorials/Ant_Colony_Optimization.pdf Ant system: optimization by a colony of cooperating agents]'', IEEE Transactions on Systems, Man, and Cybernetics--Part B , volume 26, numéro 1, pages 29-41, 1996.</ref>，它的目标是解决旅行商问题，其中的目标是找到最短的往返路线连接一系列城市。一般的算法相对简单，可以基于一组蚂蚁，每个蚂蚁沿着城市进行一次可能的往返旅行。在每个阶段，蚂蚁都会根据一些规则从一个城市迁移到另一个城市:

It has also been used to produce near-optimal solutions to the [[travelling salesman problem]]. They have an advantage over [[simulated annealing]] and [[genetic algorithm]] approaches of similar problems when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in [[network routing]] and urban transportation systems.

第509行：第511行：

===Scheduling problem===

规划难题

+

*[[Sequential Ordering Problem]] (SOP) <ref> L.M. Gambardella, M. Dorigo, "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem", INFORMS Journal on Computing, vol.12(3), pp. 237-255, 2000.</ref>

−

顺序排序问题

+

顺序排序问题 <ref> L.M. Gambardella, M. Dorigo, "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem", INFORMS Journal on Computing, vol.12(3), pp. 237-255, 2000.</ref>

−

*[[Job-shop scheduling]] problem (JSP)<ref>D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, ''[https://ieeexplore.ieee.org/abstract/document/4336122/ Classification with Ant Colony Optimization]'', IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.

+

−

工序车间调度问题

+

*[[Job-shop scheduling]] problem (JSP)<ref>D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, ''[https://ieeexplore.ieee.org/abstract/document/4336122/ Classification with Ant Colony Optimization]'', IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.</ref>

−

</ref>

+

工序车间调度问题<ref>D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, ''[https://ieeexplore.ieee.org/abstract/document/4336122/ Classification with Ant Colony Optimization]'', IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.</ref>

*[[Open-shop scheduling]] problem (OSP)<ref>B. Pfahring, "Multi-agent search for open scheduling: adapting the Ant-Q formalism," Technical report TR-96-09, 1996.</ref><ref>C. Blem, "[http://lia.disi.unibo.it/Courses/SistInt/articoli/beam-aco.pdf Beam-ACO, Hybridizing ant colony optimization with beam search. An application to open shop scheduling]," Technical report TR/IRIDIA/2003-17, 2003.</ref>

−

开放车间调度问题

+

开放车间调度问题<ref>B. Pfahring, "Multi-agent search for open scheduling: adapting the Ant-Q formalism," Technical report TR-96-09, 1996.</ref><ref>C. Blem, "[http://lia.disi.unibo.it/Courses/SistInt/articoli/beam-aco.pdf Beam-ACO, Hybridizing ant colony optimization with beam search. An application to open shop scheduling]," Technical report TR/IRIDIA/2003-17, 2003.</ref>

+

*Permutation flow shop problem (PFSP)<ref>T. Stützle, "An ant approach to the flow shop problem," Technical report AIDA-97-07, 1997.</ref>

−

排列流车间问题

+

排列流车间问题 <ref>T. Stützle, "An ant approach to the flow shop problem," Technical report AIDA-97-07, 1997.</ref>

+

*Single machine total tardiness problem (SMTTP)<ref>A. Bauer, B. Bullnheimer, R. F. Hartl and C. Strauss, "Minimizing total tardiness on a single machine using ant colony optimization," Central European Journal for Operations Research and Economics, vol.8, no.2, pp.125-141, 2000.</ref>

−

单机总延迟问题

+

单机总延迟问题 ref>A. Bauer, B. Bullnheimer, R. F. Hartl and C. Strauss, "Minimizing total tardiness on a single machine using ant colony optimization," Central European Journal for Operations Research and Economics, vol.8, no.2, pp.125-141, 2000.</ref>

+

*Single machine total weighted tardiness problem (SMTWTP)<ref>M. den Besten, "Ants for the single machine total weighted tardiness problem," Master's thesis, University of Amsterdam, 2000.</ref><ref>M, den Bseten, T. Stützle and M. Dorigo, "Ant colony optimization for the total weighted tardiness problem," Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, vol. 1917 of [[Lecture Notes in Computer Science]], pp.611-620, 2000.</ref><ref>D. Merkle and M. Middendorf, "[http://www.ccas.ru/orsot/library/An%20Ant%20Algorithm%20with%20a%20New%20Pheromone%20Evaluation%20Rule%20for%20Total%20Tardiness%20Problems.pdf An ant algorithm with a new pheromone evaluation rule for total tardiness problems]," Real World Applications of Evolutionary Computing, vol. 1803 of Lecture Notes in Computer Science, pp.287-296, 2000.</ref>

−

单机总加权延迟调度问题

+

单机总加权延迟调度问题 <ref>M. den Besten, "Ants for the single machine total weighted tardiness problem," Master's thesis, University of Amsterdam, 2000.</ref><ref>M, den Bseten, T. Stützle and M. Dorigo, "Ant colony optimization for the total weighted tardiness problem," Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, vol. 1917 of [[Lecture Notes in Computer Science]], pp.611-620, 2000.</ref><ref>D. Merkle and M. Middendorf, "[http://www.ccas.ru/orsot/library/An%20Ant%20Algorithm%20with%20a%20New%20Pheromone%20Evaluation%20Rule%20for%20Total%20Tardiness%20Problems.pdf An ant algorithm with a new pheromone evaluation rule for total tardiness problems]," Real World Applications of Evolutionary Computing, vol. 1803 of Lecture Notes in Computer Science, pp.287-296, 2000.</ref>

+

*Resource-constrained project scheduling problem (RCPSP)<ref>D. Merkle, M. Middendorf and H. Schmeck, "Ant colony optimization for resource-constrained project scheduling," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), pp.893-900, 2000.</ref>

−

资源受限的项目调度问题

+

资源受限的项目调度问题<ref>D. Merkle, M. Middendorf and H. Schmeck, "Ant colony optimization for resource-constrained project scheduling," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), pp.893-900, 2000.</ref>

+

*Group-shop scheduling problem (GSP)<ref>C. Blum, "[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Ant%20Algorithms,%203%20conf.,%20ANTS%202002(LNCS2463,%20Springer,%202002)(ISBN%203540441468)(318s).pdf#page=28 ACO applied to group shop scheduling: a case study on intensification and diversification]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Proceedings of ANTS 2002, vol. 2463 of Lecture Notes in Computer Science, pp.14-27, 2002.</ref>

−

组车间调度问题

+

组车间调度问题<ref>C. Blum, "[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Ant%20Algorithms,%203%20conf.,%20ANTS%202002(LNCS2463,%20Springer,%202002)(ISBN%203540441468)(318s).pdf#page=28 ACO applied to group shop scheduling: a case study on intensification and diversification]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Proceedings of ANTS 2002, vol. 2463 of Lecture Notes in Computer Science, pp.14-27, 2002.</ref>

+

*Single-machine total tardiness problem with sequence dependent setup times (SMTTPDST)<ref>C. Gagné, W. L. Price and M. Gravel, "[https://link.springer.com/article/10.1057/palgrave.jors.2601390 Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times]," Journal of the Operational Research Society, vol.53, pp.895-906, 2002.</ref>

−

具有序列依赖设置时间的单机总延迟问题

+

具有序列依赖设置时间的单机总延迟问题 <ref>C. Gagné, W. L. Price and M. Gravel, "[https://link.springer.com/article/10.1057/palgrave.jors.2601390 Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times]," Journal of the Operational Research Society, vol.53, pp.895-906, 2002.</ref>

+

*Multistage flowshop scheduling problem (MFSP) with sequence dependent setup/changeover times<ref>A. V. Donati, V. Darley, B. Ramachandran, "An Ant-Bidding Algorithm for Multistage Flowshop Scheduling Problem: Optimization and Phase Transitions", book chapter in Advances in Metaheuristics for Hard Optimization, Springer, {{ISBN|978-3-540-72959-4}}, pp.111-138, 2008.</ref>

−

具有序列依赖设置/转换时间的多级流车间调度问题

+

具有序列依赖设置/转换时间的多级流车间调度问题 <ref>A. V. Donati, V. Darley, B. Ramachandran, "An Ant-Bidding Algorithm for Multistage Flowshop Scheduling Problem: Optimization and Phase Transitions", book chapter in Advances in Metaheuristics for Hard Optimization, Springer, {{ISBN|978-3-540-72959-4}}, pp.111-138, 2008.</ref>

第536行：第546行：

车辆路线问题

*Capacitated vehicle routing problem (CVRP)<ref>{{Cite journal |doi = 10.1016/S0166-218X(01)00351-1|title = Models, relaxations and exact approaches for the capacitated vehicle routing problem|journal = Discrete Applied Mathematics|volume = 123|issue = 1–3|pages = 487–512|year = 2002|last1 = Toth|first1 = Paolo|last2 = Vigo|first2 = Daniele}}</ref><ref>J. M. Belenguer, and E. Benavent, "A cutting plane algorithm for capacitated arc routing problem," Computers & Operations Research, vol.30, no.5, pp.705-728, 2003.</ref><ref>T. K. Ralphs, "Parallel branch and cut for capacitated vehicle routing," Parallel Computing, vol.29, pp.607-629, 2003.</ref>

−

容量受限车辆路径问题

+

容量受限车辆路径问题 <ref>{{Cite journal |doi = 10.1016/S0166-218X(01)00351-1|title = Models, relaxations and exact approaches for the capacitated vehicle routing problem|journal = Discrete Applied Mathematics|volume = 123|issue = 1–3|pages = 487–512|year = 2002|last1 = Toth|first1 = Paolo|last2 = Vigo|first2 = Daniele}}</ref><ref>J. M. Belenguer, and E. Benavent, "A cutting plane algorithm for capacitated arc routing problem," Computers & Operations Research, vol.30, no.5, pp.705-728, 2003.</ref><ref>T. K. Ralphs, "Parallel branch and cut for capacitated vehicle routing," Parallel Computing, vol.29, pp.607-629, 2003.</ref>

+

*Multi-depot vehicle routing problem (MDVRP)<ref>{{Cite journal |doi = 10.1016/S0377-2217(96)00253-6|title = A multi-level composite heuristic for the multi-depot vehicle fleet mix problem|journal = European Journal of Operational Research|volume = 103|pages = 95–112|year = 1997|last1 = Salhi|first1 = S.|last2 = Sari|first2 = M.}}</ref>

−

多基地车辆路径问题

+

多基地车辆路径问题<ref>{{Cite journal |doi = 10.1016/S0377-2217(96)00253-6|title = A multi-level composite heuristic for the multi-depot vehicle fleet mix problem|journal = European Journal of Operational Research|volume = 103|pages = 95–112|year = 1997|last1 = Salhi|first1 = S.|last2 = Sari|first2 = M.}}</ref>

+

*Period vehicle routing problem (PVRP)<ref>{{Cite journal |doi = 10.1016/S0377-2217(01)00206-5|title = The periodic vehicle routing problem with intermediate facilities|journal = European Journal of Operational Research|volume = 137|issue = 2|pages = 233–247|year = 2002|last1 = Angelelli|first1 = Enrico|last2 = Speranza|first2 = Maria Grazia|author2-link= M. Grazia Speranza}}</ref>

−

周期车辆路径问题

+

周期车辆路径问题 <ref>{{Cite journal |doi = 10.1016/S0377-2217(01)00206-5|title = The periodic vehicle routing problem with intermediate facilities|journal = European Journal of Operational Research|volume = 137|issue = 2|pages = 233–247|year = 2002|last1 = Angelelli|first1 = Enrico|last2 = Speranza|first2 = Maria Grazia|author2-link= M. Grazia Speranza}}</ref>

+

*Split delivery vehicle routing problem (SDVRP)<ref>{{Cite journal |citeseerx = 10.1.1.8.7096|title = A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries|journal = Computers and Operations Research|volume = 31|issue = 12|pages = 1947–1964|year = 2002|last1 = Ho|first1 = Sin C.|last2 = Haugland|first2 = Dag|doi = 10.1016/S0305-0548(03)00155-2}}</ref>

−

分批配送车辆路径问题

+

分批配送车辆路径问题<ref>{{Cite journal |citeseerx = 10.1.1.8.7096|title = A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries|journal = Computers and Operations Research|volume = 31|issue = 12|pages = 1947–1964|year = 2002|last1 = Ho|first1 = Sin C.|last2 = Haugland|first2 = Dag|doi = 10.1016/S0305-0548(03)00155-2}}</ref>

+

*Stochastic vehicle routing problem (SVRP)<ref>{{Cite journal |citeseerx = 10.1.1.392.4034|title = Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands|journal = Computers & Operations Research|pages = 2000|last1 = Secomandi|first1 = Nicola}}</ref>

−

随机车辆路径问题

+

随机车辆路径问题 <ref>{{Cite journal |citeseerx = 10.1.1.392.4034|title = Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands|journal = Computers & Operations Research|pages = 2000|last1 = Secomandi|first1 = Nicola}}</ref>

+

*Vehicle routing problem with pick-up and delivery (VRPPD)<ref>W. P. Nanry and J. W. Barnes, "[https://pdfs.semanticscholar.org/f5a3/fffdfb26ead53680a5f9d3334e556181317b.pdf Solving the pickup and delivery problem with time windows using reactive tabu search]," Transportation Research Part B, vol.34, no. 2, pp.107-121, 2000.</ref><ref>R. Bent and P.V. Hentenryck, "[https://pdfs.semanticscholar.org/3952/105ddd7477f04ab1225cf2821021fefeab50.pdf A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows]," Computers & Operations Research, vol.33, no.4, pp.875-893, 2003.</ref>

−

带取送的车辆路径问题

+

带取送的车辆路径问题 <ref>W. P. Nanry and J. W. Barnes, "[https://pdfs.semanticscholar.org/f5a3/fffdfb26ead53680a5f9d3334e556181317b.pdf Solving the pickup and delivery problem with time windows using reactive tabu search]," Transportation Research Part B, vol.34, no. 2, pp.107-121, 2000.</ref><ref>R. Bent and P.V. Hentenryck, "[https://pdfs.semanticscholar.org/3952/105ddd7477f04ab1225cf2821021fefeab50.pdf A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows]," Computers & Operations Research, vol.33, no.4, pp.875-893, 2003.</ref>

+

*Vehicle routing problem with time windows (VRPTW)<ref> L.M. Gambardella, E. Taillard, G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows", In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, London, UK, pp. 63-76, 1999.</ref><ref>{{Cite journal |doi = 10.1016/0166-218X(95)00027-O|title = The simulated trading heuristic for solving vehicle routing problems|journal = Discrete Applied Mathematics|volume = 65|issue = 1–3|pages = 47–72|year = 1996|last1 = Bachem|first1 = A.|last2 = Hochstättler|first2 = W.|last3 = Malich|first3 = M.}}</ref><ref>{{Cite journal |doi = 10.1016/S0925-5273(98)00250-3|title = A heuristic for bi-objective vehicle routing with time window constraints|journal = International Journal of Production Economics|volume = 62|issue = 3|pages = 249–258|year = 1999|last1 = Hong|first1 = Sung-Chul|last2 = Park|first2 = Yang-Byung}}</ref><ref>{{Cite journal |doi = 10.1016/j.ejor.2004.08.018|title = Scatter search for the vehicle routing problem with time windows|journal = European Journal of Operational Research|volume = 169|issue = 2|pages = 606–622|year = 2006|last1 = Russell|first1 = Robert A.|last2 = Chiang|first2 = Wen-Chyuan}}</ref>

−

带时间窗的车辆路径问题

+

带时间窗的车辆路径问题 <ref> L.M. Gambardella, E. Taillard, G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows", In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, London, UK, pp. 63-76, 1999.</ref><ref>{{Cite journal |doi = 10.1016/0166-218X(95)00027-O|title = The simulated trading heuristic for solving vehicle routing problems|journal = Discrete Applied Mathematics|volume = 65|issue = 1–3|pages = 47–72|year = 1996|last1 = Bachem|first1 = A.|last2 = Hochstättler|first2 = W.|last3 = Malich|first3 = M.}}</ref><ref>{{Cite journal |doi = 10.1016/S0925-5273(98)00250-3|title = A heuristic for bi-objective vehicle routing with time window constraints|journal = International Journal of Production Economics|volume = 62|issue = 3|pages = 249–258|year = 1999|last1 = Hong|first1 = Sung-Chul|last2 = Park|first2 = Yang-Byung}}</ref><ref>{{Cite journal |doi = 10.1016/j.ejor.2004.08.018|title = Scatter search for the vehicle routing problem with time windows|journal = European Journal of Operational Research|volume = 169|issue = 2|pages = 606–622|year = 2006|last1 = Russell|first1 = Robert A.|last2 = Chiang|first2 = Wen-Chyuan}}</ref>

+

*Time dependent vehicle routing problem with time windows (TDVRPTW)<ref>A. V. Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli, L. M. Gambardella, "[ftp://ftp.idsia.ch/pub/andrea/ASP_Aprile07/EJOR2007.pdf Time Dependent Vehicle Routing Problem with a Multi Ant Colony System]", European Journal of Operational Research, vol.185, no.3, pp.1174–1191, 2008.</ref>

−

带时间窗的时间相关的车辆路径问题

+

带时间窗的时间相关的车辆路径问题<ref>A. V. Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli, L. M. Gambardella, "[ftp://ftp.idsia.ch/pub/andrea/ASP_Aprile07/EJOR2007.pdf Time Dependent Vehicle Routing Problem with a Multi Ant Colony System]", European Journal of Operational Research, vol.185, no.3, pp.1174–1191, 2008.</ref>

+

*Vehicle routing problem with time windows and multiple service workers (VRPTWMS)

带时间窗和多个服务工人的车辆路径问题

第558行：第576行：

分配问题

*[[Quadratic assignment problem]] (QAP)<ref>{{Cite journal |citeseerx = 10.1.1.47.5167|title = MAX-MIN Ant System for Quadratic Assignment Problems|year = 1997}}</ref>

−

二次分配问题

+

二次分配问题<ref>{{Cite journal |citeseerx = 10.1.1.47.5167|title = MAX-MIN Ant System for Quadratic Assignment Problems|year = 1997}}</ref>

+

*[[Generalized assignment problem]] (GAP)<ref>R. Lourenço and D. Serra "[https://upcommons.upc.edu/bitstream/handle/2099/3627/4-ramalhinho.pdf Adaptive search heuristics for the generalized assignment problem]," Mathware & soft computing, vol.9, no.2-3, 2002.</ref><ref>M. Yagiura, T. Ibaraki and F. Glover, "[http://leeds-faculty.colorado.edu/glover/Publications/TS%20-%20PR%20-%20GAP%20in%20INFORMS%20JOC.pdf An ejection chain approach for the generalized assignment problem]," INFORMS Journal on Computing, vol. 16, no. 2, pp. 133–151, 2004.</ref>

−

广义分配问题

+

广义分配问题<ref>R. Lourenço and D. Serra "[https://upcommons.upc.edu/bitstream/handle/2099/3627/4-ramalhinho.pdf Adaptive search heuristics for the generalized assignment problem]," Mathware & soft computing, vol.9, no.2-3, 2002.</ref><ref>M. Yagiura, T. Ibaraki and F. Glover, "[http://leeds-faculty.colorado.edu/glover/Publications/TS%20-%20PR%20-%20GAP%20in%20INFORMS%20JOC.pdf An ejection chain approach for the generalized assignment problem]," INFORMS Journal on Computing, vol. 16, no. 2, pp. 133–151, 2004.</ref>

+

*[[Frequency assignment problem]] (FAP)<ref>K. I. Aardal, [[S. P. M. van Hoesel]], A. M. C. A. Koster, C. Mannino and Antonio. Sassano, "Models and solution techniques for the frequency assignment problem," A Quarterly Journal of Operations Research, vol.1, no.4, pp.261-317, 2001.</ref>

−

频率分配问题

+

频率分配问题 <ref>K. I. Aardal, [[S. P. M. van Hoesel]], A. M. C. A. Koster, C. Mannino and Antonio. Sassano, "Models and solution techniques for the frequency assignment problem," A Quarterly Journal of Operations Research, vol.1, no.4, pp.261-317, 2001.</ref>

+

*[[Redundancy allocation problem]] (RAP)<ref>Y. C. Liang and A. E. Smith, "[http://www.eng.auburn.edu/sites/personal/aesmith/files/antcolonyIEEETrRel%20paper.pdf An ant colony optimization algorithm for the redundancy allocation problem (RAP)]{{Dead link|date=September 2019 |bot=InternetArchiveBot |fix-attempted=yes }}," IEEE Transactions on Reliability, vol.53, no.3, pp.417-423, 2004.</ref>

−

冗余分配问题

+

冗余分配问题 <ref>Y. C. Liang and A. E. Smith, "[http://www.eng.auburn.edu/sites/personal/aesmith/files/antcolonyIEEETrRel%20paper.pdf An ant colony optimization algorithm for the redundancy allocation problem (RAP)]{{Dead link|date=September 2019 |bot=InternetArchiveBot |fix-attempted=yes }}," IEEE Transactions on Reliability, vol.53, no.3, pp.417-423, 2004.</ref>

+

第570行：第592行：

集合问题

*[[Set cover problem]] (SCP)<ref>G. Leguizamon and Z. Michalewicz, "[https://cs.adelaide.edu.au/users/zbyszek/Papers/as4.pdf A new version of ant system for subset problems]," Proceedings of the 1999 Congress on Evolutionary Computation(CEC 99), vol.2, pp.1458-1464, 1999.</ref><ref>R. Hadji, M. Rahoual, E. Talbi and V. Bachelet "Ant colonies for the set covering problem," Abstract proceedings of ANTS2000, pp.63-66, 2000.</ref>

−

集合覆盖问题

+

集合覆盖问题 <ref>G. Leguizamon and Z. Michalewicz, "[https://cs.adelaide.edu.au/users/zbyszek/Papers/as4.pdf A new version of ant system for subset problems]," Proceedings of the 1999 Congress on Evolutionary Computation(CEC 99), vol.2, pp.1458-1464, 1999.</ref><ref>R. Hadji, M. Rahoual, E. Talbi and V. Bachelet "Ant colonies for the set covering problem," Abstract proceedings of ANTS2000, pp.63-66, 2000.</ref>

+

*[[Partition problem]] (SPP)<ref>V Maniezzo and M Milandri, "[https://link.springer.com/chapter/10.1007/3-540-45724-0_19 An ant-based framework for very strongly constrained problems]," Proceedings of ANTS2000, pp.222-227, 2002.</ref>

−

划分问题

+

划分问题 <ref>V Maniezzo and M Milandri, "[https://link.springer.com/chapter/10.1007/3-540-45724-0_19 An ant-based framework for very strongly constrained problems]," Proceedings of ANTS2000, pp.222-227, 2002.</ref>

+

*Weight constrained graph tree partition problem (WCGTPP)<ref>R. Cordone and F. Maffioli,"[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/A/Applications%20of%20Evolutionary%20Computing,%20EvoWorkshops%202001..%20EvoCOP(LNCS2037,%20Springer,%202001)(ISBN%203540419209)(529s)_CsLn_.pdf#page=74 Colored Ant System and local search to design local telecommunication networks]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Applications of Evolutionary Computing: Proceedings of Evo Workshops, vol.2037, pp.60-69, 2001.</ref>

−

权约束的图树划分问题

+

权约束的图树划分问题 <ref>R. Cordone and F. Maffioli,"[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/A/Applications%20of%20Evolutionary%20Computing,%20EvoWorkshops%202001..%20EvoCOP(LNCS2037,%20Springer,%202001)(ISBN%203540419209)(529s)_CsLn_.pdf#page=74 Colored Ant System and local search to design local telecommunication networks]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Applications of Evolutionary Computing: Proceedings of Evo Workshops, vol.2037, pp.60-69, 2001.</ref>

+

*Arc-weighted l-cardinality tree problem (AWlCTP)<ref>C. Blum and M.J. Blesa, "[https://upcommons.upc.edu/bitstream/handle/2117/97393/R03-1.ps Metaheuristics for the edge-weighted k-cardinality tree problem]," Technical Report TR/IRIDIA/2003-02, IRIDIA, 2003.</ref>

−

弧加权l-基数树问题

+

弧加权l-基数树问题 <ref>C. Blum and M.J. Blesa, "[https://upcommons.upc.edu/bitstream/handle/2117/97393/R03-1.ps Metaheuristics for the edge-weighted k-cardinality tree problem]," Technical Report TR/IRIDIA/2003-02, IRIDIA, 2003.</ref>

+

*Multiple knapsack problem (MKP)<ref>[http://parallel.bas.bg/~stefka/heuristic.ps S. Fidanova, "ACO algorithm for MKP using various heuristic information"], Numerical Methods and Applications, vol.2542, pp.438-444, 2003.</ref>

−

多重背包问题

+

多重背包问题 <ref>[http://parallel.bas.bg/~stefka/heuristic.ps S. Fidanova, "ACO algorithm for MKP using various heuristic information"], Numerical Methods and Applications, vol.2542, pp.438-444, 2003.</ref>

+

*Maximum independent set problem (MIS)<ref>G. Leguizamon, Z. Michalewicz and Martin Schutz, "[http://sedici.unlp.edu.ar/bitstream/handle/10915/23384/Documento_completo.pdf?sequence=1 An ant system for the maximum independent set problem]," Proceedings of the 2001 Argentinian Congress on Computer Science, vol.2, pp.1027-1040, 2001.</ref>

−

最大独立集问题

+

最大独立集问题<ref>G. Leguizamon, Z. Michalewicz and Martin Schutz, "[http://sedici.unlp.edu.ar/bitstream/handle/10915/23384/Documento_completo.pdf?sequence=1 An ant system for the maximum independent set problem]," Proceedings of the 2001 Argentinian Congress on Computer Science, vol.2, pp.1027-1040, 2001.</ref>

第592行：第619行：

* Ant colony optimization (ACO) based reversible circuit synthesis could improve efficiency significantly.<ref>M. Sarkar, P. Ghosal, and S. P. Mohanty, "[http://www.cse.unt.edu/~smohanty/Publications_Conferences/2013/Mohanty_MWSCAS2013_Reversible-Circuit.pdf Reversible Circuit Synthesis Using ACO and SA based Quinne-McCluskey Method] {{webarchive |url=https://web.archive.org/web/20140729081848/http://www.cse.unt.edu/~smohanty/Publications_Conferences/2013/Mohanty_MWSCAS2013_Reversible-Circuit.pdf |date=July 29, 2014 }}", in Proceedings of the 56th IEEE International Midwest Symposium on Circuits & Systems (MWSCAS), 2013, pp. 416--419.</ref>

−

基于蚁群优化（ACO）的可逆电路合成可以显著提高效率

+

基于蚁群优化（ACO）的可逆电路合成可以显著提高效率 <ref>M. Sarkar, P. Ghosal, and S. P. Mohanty, "[http://www.cse.unt.edu/~smohanty/Publications_Conferences/2013/Mohanty_MWSCAS2013_Reversible-Circuit.pdf Reversible Circuit Synthesis Using ACO and SA based Quinne-McCluskey Method] {{webarchive |url=https://web.archive.org/web/20140729081848/http://www.cse.unt.edu/~smohanty/Publications_Conferences/2013/Mohanty_MWSCAS2013_Reversible-Circuit.pdf |date=July 29, 2014 }}", in Proceedings of the 56th IEEE International Midwest Symposium on Circuits & Systems (MWSCAS), 2013, pp. 416--419.</ref>

+

[[File:ANT antenna 2.jpg|thumb|Unloopback vibrators 10×10, synthesized by means of ACO algorithm loopback and unloopback vibrators 10×10

第611行：第639行：

The following are the steps involved in edge detection using ACO:

−

以下是使用 ACO 进行边缘检测的步骤:

+

以下是使用 ACO 进行边缘检测的步骤:<ref>{{cite book|last1=Tian|first1=Jing|title=2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence)|pages=751–756|last2=Yu|first2=Weiyu|last3=Xie|first3=Shengli|doi=10.1109/CEC.2008.4630880|year=2008|isbn=978-1-4244-1822-0|s2cid=1782195}}</ref><ref>{{cite web|last1=Gupta|first1=Charu|last2=Gupta|first2=Sunanda|title=Edge Detection of an Image based on Ant ColonyOptimization Technique|url=https://www.academia.edu/4688002}}</ref><ref>{{Cite book|title = Edge detection using ant colony search algorithm and multiscale contrast enhancement|journal = IEEE International Conference on Systems, Man and Cybernetics, 2009. SMC 2009|pages = 2193–2198|doi = 10.1109/ICSMC.2009.5345922|first1 = A.|last1 = Jevtić|first2 = J.|last2 = Quintanilla-Dominguez|first3 = M.G.|last3 = Cortina-Januchs|first4 = D.|last4 = Andina|year = 2009|isbn = 978-1-4244-2793-2|s2cid = 11654036}}</ref>

To optimize the form of antennas, ant colony algorithms can be used. As example can be considered antennas RFID-tags based on ant colony algorithms (ACO),<ref>Marcus Randall, Andrew Lewis, Amir Galehdar, David Thiel. Using Ant Colony Optimisation to Improve the Efficiency of Small Meander Line RFID Antennas.// In 3rd IEEE International e-Science and Grid Computing Conference [http://www98.griffith.edu.au/dspace/bitstream/10072/17063/1/47523_1.pdf], 2007</ref> loopback and unloopback vibrators 10×10<ref name=slyusarant1/>

−

~~为了优化天线的形状，可以使用蚁群算法。例如，可以考虑基于蚁群算法（ACO）的天线RFID标签~~

+

为了优化天线的结构，可以使用蚁群算法。例如，可以考虑基于蚁群算法（ACO）的天线RFID标签, <ref>Marcus Randall, Andrew Lewis, Amir Galehdar, David Thiel. Using Ant Colony Optimisation to Improve the Efficiency of Small Meander Line RFID Antennas.// In 3rd IEEE International e-Science and Grid Computing Conference [http://www98.griffith.edu.au/dspace/bitstream/10072/17063/1/47523_1.pdf], 2007</ref>loopback and unloopback vibrators 10×10<ref name=slyusarant1/>

第804行：第833行：

* [[Bankruptcy prediction]]<ref>{{cite journal|last1=Zhang|first1=Y.|title=A Rule-Based Model for Bankruptcy Prediction Based on an Improved Genetic Ant Colony Algorithm|journal=Mathematical Problems in Engineering|date=2013|volume=2013|page=753251|doi=10.1155/2013/753251|doi-access=free}}</ref>

−

破产预测

+

破产预测<ref>{{cite journal|last1=Zhang|first1=Y.|title=A Rule-Based Model for Bankruptcy Prediction Based on an Improved Genetic Ant Colony Algorithm|journal=Mathematical Problems in Engineering|date=2013|volume=2013|page=753251|doi=10.1155/2013/753251|doi-access=free}}</ref>

+

* [[Classification]]<ref name="D. Martens, M pages 651">D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, "[https://ieeexplore.ieee.org/abstract/document/4336122/ Classification with Ant Colony Optimization]", IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.</ref>

−

分类

+

分类<ref name="D. Martens, M pages 651">D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, "[https://ieeexplore.ieee.org/abstract/document/4336122/ Classification with Ant Colony Optimization]", IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.</ref>

+

* Connection-oriented [[network routing]]<ref>G. D. Caro and M. Dorigo, "Extending AntNet for best-effort quality-of-service routing," Proceedings of the First International Workshop on Ant Colony Optimization (ANTS’98), 1998.</ref>

−

面向连接的网络路由

+

面向连接的网络路由<ref>G. D. Caro and M. Dorigo, "Extending AntNet for best-effort quality-of-service routing," Proceedings of the First International Workshop on Ant Colony Optimization (ANTS’98), 1998.</ref>

+

* Connectionless network routing<ref>G.D. Caro and M. Dorigo "[http://www.idsia.ch/~gianni/Papers/tech-rep-iridia-97-12.pdf AntNet: a mobile agents approach to adaptive routing]," Proceedings of the Thirty-First Hawaii International Conference on System Science, vol.7, pp.74-83, 1998.</ref><ref>G. D. Caro and M. Dorigo, "[https://www.researchgate.net/profile/Gianni_Di_Caro/publication/2328604_Two_Ant_Colony_Algorithms_For_Best-Effort_Routing_In_Datagram_Networks/links/0deec52909f32c7e6d000000/Two-Ant-Colony-Algorithms-For-Best-Effort-Routing-In-Datagram-Networks.pdf Two ant colony algorithms for best-effort routing in datagram networks]," Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’98), pp.541-546, 1998.</ref>

−

无连接网络路由

+

无连接网络路由 <ref>G.D. Caro and M. Dorigo "[http://www.idsia.ch/~gianni/Papers/tech-rep-iridia-97-12.pdf AntNet: a mobile agents approach to adaptive routing]," Proceedings of the Thirty-First Hawaii International Conference on System Science, vol.7, pp.74-83, 1998.</ref><ref>G. D. Caro and M. Dorigo, "[https://www.researchgate.net/profile/Gianni_Di_Caro/publication/2328604_Two_Ant_Colony_Algorithms_For_Best-Effort_Routing_In_Datagram_Networks/links/0deec52909f32c7e6d000000/Two-Ant-Colony-Algorithms-For-Best-Effort-Routing-In-Datagram-Networks.pdf Two ant colony algorithms for best-effort routing in datagram networks]," Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’98), pp.541-546, 1998.</ref>

+

* [[Data mining]]<ref name="D. Martens, M pages 651"/><ref>D. Martens, B. Baesens, T. Fawcett "[https://link.springer.com/content/pdf/10.1007/s10994-010-5216-5.pdf Editorial Survey: Swarm Intelligence for Data Mining]," Machine Learning, volume 82, number 1, pp. 1-42, 2011</ref><ref>R. S. Parpinelli, H. S. Lopes and A. A Freitas, "[http://neuro.bstu.by/ai/To-dom/My_research/Paper-0-again/For-courses/Ants/heuristic-dm-bk.pdf An ant colony algorithm for classification rule discovery]," Data Mining: A heuristic Approach, pp.191-209, 2002.</ref><ref>R. S. Parpinelli, H. S. Lopes and A. A Freitas, "[https://www.academia.edu/download/31181466/datamining070.pdf Data mining with an ant colony optimization algorithm]," IEEE Transactions on Evolutionary Computation, vol.6, no.4, pp.321-332, 2002.</ref>

−

数据挖掘

+

数据挖掘<ref name="D. Martens, M pages 651"/><ref>D. Martens, B. Baesens, T. Fawcett "[https://link.springer.com/content/pdf/10.1007/s10994-010-5216-5.pdf Editorial Survey: Swarm Intelligence for Data Mining]," Machine Learning, volume 82, number 1, pp. 1-42, 2011</ref><ref>R. S. Parpinelli, H. S. Lopes and A. A Freitas, "[http://neuro.bstu.by/ai/To-dom/My_research/Paper-0-again/For-courses/Ants/heuristic-dm-bk.pdf An ant colony algorithm for classification rule discovery]," Data Mining: A heuristic Approach, pp.191-209, 2002.</ref><ref>R. S. Parpinelli, H. S. Lopes and A. A Freitas, "[https://www.academia.edu/download/31181466/datamining070.pdf Data mining with an ant colony optimization algorithm]," IEEE Transactions on Evolutionary Computation, vol.6, no.4, pp.321-332, 2002.</ref>

+

* Discounted cash flows in project scheduling<ref>W. N. Chen, J. ZHANG and H. Chung, "[http://webdelprofesor.ula.ve/economia/gsfran/Asignaturas/EvaluacionFinEconProyec/2%20OptimizingDiscounted.pdf Optimizing Discounted Cash Flows in Project Scheduling--An Ant Colony Optimization Approach]", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews Vol.40 No.5 pp.64-77, Jan. 2010.</ref>

−

项目调度中的折现现金流

+

项目调度中的折现现金流 <ref>W. N. Chen, J. ZHANG and H. Chung, "[http://webdelprofesor.ula.ve/economia/gsfran/Asignaturas/EvaluacionFinEconProyec/2%20OptimizingDiscounted.pdf Optimizing Discounted Cash Flows in Project Scheduling--An Ant Colony Optimization Approach]", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews Vol.40 No.5 pp.64-77, Jan. 2010.</ref>

* [[distributed computing|Distributed]] [[information retrieval]]<ref>D. Picard, A. Revel, M. Cord, "An Application of Swarm Intelligence to Distributed Image Retrieval", Information Sciences, 2010</ref><ref>D. Picard, M. Cord, A. Revel, "[http://hal.upmc.fr/docs/00/65/63/63/PDF/manuscript.pdf Image Retrieval over Networks : Active Learning using Ant Algorithm]", IEEE Transactions on Multimedia, vol. 10, no. 7, pp. 1356--1365 - nov 2008</ref>

−

分布式计算

+

分布式计算 <ref>D. Picard, A. Revel, M. Cord, "An Application of Swarm Intelligence to Distributed Image Retrieval", Information Sciences, 2010</ref><ref>D. Picard, M. Cord, A. Revel, "[http://hal.upmc.fr/docs/00/65/63/63/PDF/manuscript.pdf Image Retrieval over Networks : Active Learning using Ant Algorithm]", IEEE Transactions on Multimedia, vol. 10, no. 7, pp. 1356--1365 - nov 2008</ref>

* Energy and electricity network design<ref name="warner-and-vogel-2008">

−

能源与电力网络设计

+

能源与电力网络设计 <ref name="warner-and-vogel-2008">

{{cite conference

第854行：第888行：

* Grid workflow scheduling problem<ref>W. N. Chen and J. ZHANG "Ant Colony Optimization Approach to Grid Workflow Scheduling Problem with Various QoS Requirements", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews, Vol. 31, No. 1,pp.29-43,Jan 2009.</ref>

−

网格工作流调度问题

+

网格工作流调度问题 <ref>W. N. Chen and J. ZHANG "Ant Colony Optimization Approach to Grid Workflow Scheduling Problem with Various QoS Requirements", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews, Vol. 31, No. 1,pp.29-43,Jan 2009.</ref>

+

* Inhibitory peptide design for [[protein protein interaction]]s<ref name=":0">{{Cite journal|last1=Zaidman|first1=Daniel|last2=Wolfson|first2=Haim J.|date=2016-08-01|title=PinaColada: peptide–inhibitor ant colony ad-hoc design algorithm|journal=Bioinformatics|volume=32|issue=15|pages=2289–2296|doi=10.1093/bioinformatics/btw133|pmid=27153578|issn=1367-4803|doi-access=free}}</ref>

−

蛋白质-蛋白质相互作用的抑制肽设计

+

蛋白质-蛋白质相互作用的抑制肽设计<ref name=":0">{{Cite journal|last1=Zaidman|first1=Daniel|last2=Wolfson|first2=Haim J.|date=2016-08-01|title=PinaColada: peptide–inhibitor ant colony ad-hoc design algorithm|journal=Bioinformatics|volume=32|issue=15|pages=2289–2296|doi=10.1093/bioinformatics/btw133|pmid=27153578|issn=1367-4803|doi-access=free}}</ref>

+

* Intelligent testing system<ref>Xiao. M.Hu, J. ZHANG, and H. Chung, "[https://ieeexplore.ieee.org/abstract/document/5061647/ An Intelligent Testing System Embedded with an Ant Colony Optimization Based Test Composition Method]", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews, Vol. 39, No. 6, pp. 659-669, Dec 2009.</ref>

−

智能测试系统

+

智能测试系统 <ref>Xiao. M.Hu, J. ZHANG, and H. Chung, "[https://ieeexplore.ieee.org/abstract/document/5061647/ An Intelligent Testing System Embedded with an Ant Colony Optimization Based Test Composition Method]", IEEE Transactions on Systems, Man, and Cybernetics--Part C: Applications and Reviews, Vol. 39, No. 6, pp. 659-669, Dec 2009.</ref>

* Power [[electronic circuit design]]<ref>J. ZHANG, H. Chung, W. L. Lo, and T. Huang, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4340&rep=rep1&type=pdf Extended Ant Colony Optimization Algorithm for Power Electronic Circuit Design]", IEEE Transactions on Power Electronic. Vol.24,No.1, pp.147-162, Jan 2009.</ref>

−

电源电子电路设计

+

电源电子电路设计 <ref>J. ZHANG, H. Chung, W. L. Lo, and T. Huang, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4340&rep=rep1&type=pdf Extended Ant Colony Optimization Algorithm for Power Electronic Circuit Design]", IEEE Transactions on Power Electronic. Vol.24,No.1, pp.147-162, Jan 2009.</ref>

+

* [[Protein folding]]<ref>X. M. Hu, J. ZHANG，J. Xiao and Y. Li, "[http://eprints.gla.ac.uk/5306/1/5306.pdf Protein Folding in Hydrophobic-Polar Lattice Model: A Flexible Ant- Colony Optimization Approach] ", Protein and Peptide Letters, Volume 15, Number 5, 2008, Pp. 469-477.</ref><ref>A. Shmygelska, R. A. Hernández and H. H. Hoos, "[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Ant%20Algorithms,%203%20conf.,%20ANTS%202002(LNCS2463,%20Springer,%202002)(ISBN%203540441468)(318s).pdf#page=54 An ant colony optimization algorithm for the 2D HP protein folding problem]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Proceedings of the 3rd International Workshop on Ant Algorithms/ANTS 2002, Lecture Notes in Computer Science, vol.2463, pp.40-52, 2002.</ref><ref>{{cite book |author1=M. Nardelli |author2=L. Tedesco |author3=A. Bechini |title= Cross-lattice behavior of general ACO folding for proteins in the HP model |journal= Proc. Of ACM SAC 2013|year=2013|pages=1320–1327 |doi= 10.1145/2480362.2480611|isbn=9781450316569 |s2cid=1216890 |url=https://zenodo.org/record/3445092 }}</ref>

−

蛋白质折叠

+

蛋白质折叠<ref>X. M. Hu, J. ZHANG，J. Xiao and Y. Li, "[http://eprints.gla.ac.uk/5306/1/5306.pdf Protein Folding in Hydrophobic-Polar Lattice Model: A Flexible Ant- Colony Optimization Approach] ", Protein and Peptide Letters, Volume 15, Number 5, 2008, Pp. 469-477.</ref><ref>A. Shmygelska, R. A. Hernández and H. H. Hoos, "[ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Ant%20Algorithms,%203%20conf.,%20ANTS%202002(LNCS2463,%20Springer,%202002)(ISBN%203540441468)(318s).pdf#page=54 An ant colony optimization algorithm for the 2D HP protein folding problem]{{Dead link|date=June 2020 |bot=InternetArchiveBot |fix-attempted=yes }}," Proceedings of the 3rd International Workshop on Ant Algorithms/ANTS 2002, Lecture Notes in Computer Science, vol.2463, pp.40-52, 2002.</ref><ref>{{cite book |author1=M. Nardelli |author2=L. Tedesco |author3=A. Bechini |title= Cross-lattice behavior of general ACO folding for proteins in the HP model |journal= Proc. Of ACM SAC 2013|year=2013|pages=1320–1327 |doi= 10.1145/2480362.2480611|isbn=9781450316569 |s2cid=1216890 |url=https://zenodo.org/record/3445092 }}</ref>

+

The inventors are Frans Moyson and Bernard Manderick. Pioneers of the field include Marco Dorigo, Luca Maria Gambardella.

第868行：第906行：

* System identification<ref>L. Wang and Q. D. Wu, "Linear system parameters identification based on ant system algorithm," Proceedings of the IEEE Conference on Control Applications, pp. 401-406, 2001.</ref><ref>K. C. Abbaspour, R. Schulin, M. T. Van Genuchten, "[https://www.ars.usda.gov/arsuserfiles/20360500/pdf_pubs/P1797.pdf Estimating unsaturated soil hydraulic parameters using ant colony optimization]," Advances In Water Resources, vol. 24, no. 8, pp. 827-841, 2001.</ref>

−

系统辨识

+

系统辨识<ref>L. Wang and Q. D. Wu, "Linear system parameters identification based on ant system algorithm," Proceedings of the IEEE Conference on Control Applications, pp. 401-406, 2001.</ref><ref>K. C. Abbaspour, R. Schulin, M. T. Van Genuchten, "[https://www.ars.usda.gov/arsuserfiles/20360500/pdf_pubs/P1797.pdf Estimating unsaturated soil hydraulic parameters using ant colony optimization]," Advances In Water Resources, vol. 24, no. 8, pp. 827-841, 2001.</ref>

第887行：第925行：

210 height: 300

−

With an ACO algorithm, the shortest path in a graph, between two points A and B, is built from a combination of several paths.<ref>{{Cite journal | doi=10.1186/1471-2105-6-30| pmid=15710037| pmc=555464|year = 2005|last1 = Shmygelska|first1 = Alena| title=An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem| journal=BMC Bioinformatics| volume=6| pages=30| last2=Hoos| first2=Holger H.}}</ref> It is not easy to give a precise definition of what algorithm is or is not an ant colony, because the definition may vary according to the authors and uses. Broadly speaking, ant colony algorithms are regarded as [[people|populated]] [[metaheuristics]] with each solution represented by an ant moving in the search space.<ref>Fred W. Glover,Gary A. Kochenberger, ''Handbook of Metaheuristics'', [https://books.google.com/books?id=P-HpBwAAQBAJ&pg=PA276&lpg=PA276&dq=aco+algorithms+with+guaranteed+convergence+to+the+optimal+solution+metaheuristics&source=bl&ots=4kyU_bZLpg&sig=zSrzu89MRED00H8QWjixBMkw11k&hl=fr&sa=X&ved=0ahUKEwjm4_2ysurTAhUHZ1AKHabGAZIQ6AEIODAE#v=onepage&q=aco%20algorithms%20with%20guaranteed%20convergence%20to%20the%20optimal%20solution%20metaheuristics&f=false], Springer (2003)</ref> Ants mark the best solutions and take account of previous markings to optimize their search. They can be seen as [[probabilistic]] [[multi-agent]] algorithms using a [[probability distribution]] to make the transition between each [[iteration]].<ref>http://www.multiagent.fr/extensions/ICAPManager/pdf/LauriCharpillet2006.pdf</ref> In their versions for combinatorial problems, they use an iterative construction of solutions.<ref>WJ Gutjahr , ''ACO algorithms with guaranteed convergence to the optimal solution'', [https://homes.di.unimi.it/cordone/courses/2016-ae/Lez07-Materiali/ACOAlgoithmsWithGuaranteedConvergenceToTheOptimalSolution.pdf], (2002)</ref> According to some authors, the thing which distinguishes ACO algorithms from other relatives (such as algorithms to estimate the distribution or particle swarm optimization) is precisely their constructive aspect. In combinatorial problems, it is possible that the best solution eventually be found, even though no ant would prove effective. Thus, in the example of the Travelling salesman problem, it is not necessary that an ant actually travels the shortest route: the shortest route can be built from the strongest segments of the best solutions. However, this definition can be problematic in the case of problems in real variables, where no structure of 'neighbours' exists. The collective behaviour of [[social insects]] remains a source of inspiration for researchers. The wide variety of algorithms (for optimization or not) seeking self-organization in biological systems has led to the concept of "[[swarm intelligence]]",<ref name="Waldner 2008 214"/> which is a very general framework in which ant colony algorithms fit.

+

With an ACO algorithm, the shortest path in a graph, between two points A and B, is built from a combination of several paths.<ref>{{Cite journal | doi=10.1186/1471-2105-6-30| pmid=15710037| pmc=555464|year = 2005|last1 = Shmygelska|first1 = Alena| title=An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem| journal=BMC Bioinformatics| volume=6| pages=30| last2=Hoos| first2=Holger H.}}</ref> It is not easy to give a precise definition of what algorithm is or is not an ant colony, because the definition may vary according to the authors and uses. Broadly speaking, ant colony algorithms are regarded as [[people|populated]] [[metaheuristics]] with each solution represented by an ant moving in the search space.<ref>Fred W. Glover,Gary A. Kochenberger, ''Handbook of Metaheuristics'', [https://books.google.com/books?id=P-HpBwAAQBAJ&pg=PA276&lpg=PA276&dq=aco+algorithms+with+guaranteed+convergence+to+the+optimal+solution+metaheuristics&source=bl&ots=4kyU_bZLpg&sig=zSrzu89MRED00H8QWjixBMkw11k&hl=fr&sa=X&ved=0ahUKEwjm4_2ysurTAhUHZ1AKHabGAZIQ6AEIODAE#v=onepage&q=aco%20algorithms%20with%20guaranteed%20convergence%20to%20the%20optimal%20solution%20metaheuristics&f=false], Springer (2003)</ref> Ants mark the best solutions and take account of previous markings to optimize their search. They can be seen as [[probabilistic]] [[multi-agent]] algorithms using a [[probability distribution]] to make the transition between each [[iteration]].<ref>http://www.multiagent.fr/extensions/ICAPManager/pdf/LauriCharpillet2006.pdf</ref> In their versions for combinatorial problems, they use an iterative construction of solutions.<ref>WJ Gutjahr , ''ACO algorithms with guaranteed convergence to the optimal solution'', [https://homes.di.unimi.it/cordone/courses/2016-ae/Lez07-Materiali/ACOAlgoithmsWithGuaranteedConvergenceToTheOptimalSolution.pdf], (2002)</ref>

+

According to some authors, the thing which distinguishes ACO algorithms from other relatives (such as algorithms to estimate the distribution or particle swarm optimization) is precisely their constructive aspect. In combinatorial problems, it is possible that the best solution eventually be found, even though no ant would prove effective. Thus, in the example of the Travelling salesman problem, it is not necessary that an ant actually travels the shortest route: the shortest route can be built from the strongest segments of the best solutions. However, this definition can be problematic in the case of problems in real variables, where no structure of 'neighbours' exists. The collective behaviour of [[social insects]] remains a source of inspiration for researchers. The wide variety of algorithms (for optimization or not) seeking self-organization in biological systems has led to the concept of "[[swarm intelligence]]",<ref name="Waldner 2008 214"/> which is a very general framework in which ant colony algorithms fit.

根据一些作者的观点，ACO算法与其他相关算法（如分布估计算法或粒子群优化算法）的区别正是它们的建设性方面。在组合问题中，即使没有蚂蚁被证明是有效的，也有可能最终找到最佳解。因此，在旅行商问题的例子中，蚂蚁实际上并不需要走最短的路线：最短的路线可以从最佳解的最强部分建立起来。然而，在实际变量中存在问题的情况下，这个定义可能会有问题，因为不存在“邻居”的结构。[[群居昆虫]的集体行为仍然是研究人员灵感的源泉。生物系统中寻求自组织的各种各样的算法（无论是优化还是非优化）导致了“群体智能”的概念

PlotArea = width:170 height:280 left:40 bottom:10

Lincent

19

个编辑

更改

蚁群优化算法 (查看源代码)

2020年12月1日 (二) 10:13的版本

导航菜单

搜索