19
个编辑
更改
无编辑摘要
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial Ants stand for multi-agent methods inspired by the behavior of real ants.
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial Ants stand for multi-agent methods inspired by the behavior of real ants.
在计算机科学和运筹学中，<font color="#ff8000"> 蚁群优化算法 ant colony optimization algorithm</font>(ACO)是一种基于概率解决计算问题的技术，它可以简化为通过图来寻找最优路径。人工蚂蚁代表了受真蚂蚁行为启发的多智能体方法。
在计算机科学和运筹学中，<font color="#ff8000"> 蚁群优化算法 ant colony optimization algorithm</font>(ACO)是一种基于<font color="#ff8000"> 概率</font>解决计算问题的技术，它可以简化为通过<font color="#ff8000">图</font>来寻找最优路径。人工蚂蚁代表了受真蚂蚁行为启发的多智能体方法。
The pheromone-based communication of biological [[ant]]s is often the predominant paradigm used.<ref>{{cite book |last = Monmarché Nicolas, Guinand Frédéric and Siarry Patrick |title = Artificial Ants |publisher = Wiley-ISTE |year = 2010 |isbn = 978-1-84821-194-0}}</ref> Combinations of Artificial Ants and [[local search (optimization)|local search]] algorithms have become a method of choice for numerous optimization tasks involving some sort of [[Graph (discrete mathematics)|graph]], e.g., [[vehicle routing problem|vehicle routing]] and internet [[routing]]. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as [[AntOptima]].
The pheromone-based communication of biological [[ant]]s is often the predominant paradigm used.<ref>{{cite book |last = Monmarché Nicolas, Guinand Frédéric and Siarry Patrick |title = Artificial Ants |publisher = Wiley-ISTE |year = 2010 |isbn = 978-1-84821-194-0}}</ref> Combinations of Artificial Ants and [[local search (optimization)|local search]] algorithms have become a method of choice for numerous optimization tasks involving some sort of [[Graph (discrete mathematics)|graph]], e.g., [[vehicle routing problem|vehicle routing]] and internet [[routing]]. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as [[AntOptima]].
The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of Artificial Ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as AntOptima.
The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of Artificial Ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as AntOptima.
基于信息素的蚂蚁通信被用来作为非常典型的范例<ref>{{cite book |last = Monmarché Nicolas, Guinand Frédéric and Siarry Patrick |title = Artificial Ants |publisher = Wiley-ISTE |year = 2010 |isbn = 978-1-84821-194-0}}</ref>。人工蚁群和局部搜索算法的组合已经是许多优化任务的一种求解方法，这些优化任务往往涉及某种图，例如车辆路径和互联网路由的问题。这一领域的蓬勃发展催生了专门讨论人工蚂蚁的学术会议，以及诸如 AntOptima 等专业公司的大量商业用途。
基于信息素的蚂蚁通信被用来作为非常典型的范例<ref>{{cite book |last = Monmarché Nicolas, Guinand Frédéric and Siarry Patrick |title = Artificial Ants |publisher = Wiley-ISTE |year = 2010 |isbn = 978-1-84821-194-0}}</ref>。人工蚁群和局部搜索算法的组合已经是许多优化任务的一种求解方法，这些优化任务往往涉及某种<font color="#ff8000">图</font>，例如<font color="#ff8000">车辆路径</font>和<font color="#ff8000">互联网</font>路由的问题。这一领域的蓬勃发展催生了专门讨论人工蚂蚁的学术会议，以及诸如 AntOptima 等专业公司的大量商业用途。
As an example, Ant colony optimization is a class of optimization algorithms modeled on the actions of an ant colony. Artificial 'ants' (e.g. simulation agents) locate optimal solutions by moving through a parameter space representing all possible solutions. Real ants lay down pheromones directing each other to resources while exploring their environment. The simulated 'ants' similarly record their positions and the quality of their solutions, so that in later simulation iterations more ants locate better solutions. One variation on this approach is the bees algorithm, which is more analogous to the foraging patterns of the honey bee, another social insect.
As an example, Ant colony optimization is a class of optimization algorithms modeled on the actions of an ant colony. Artificial 'ants' (e.g. simulation agents) locate optimal solutions by moving through a parameter space representing all possible solutions. Real ants lay down pheromones directing each other to resources while exploring their environment. The simulated 'ants' similarly record their positions and the quality of their solutions, so that in later simulation iterations more ants locate better solutions. One variation on this approach is the bees algorithm, which is more analogous to the foraging patterns of the honey bee, another social insect.
以蚁群算法<ref>{{cite journal|last = Dorigo, Gambardella |first = M, L.M. |authorlink = M. Dorigo & L. M. Gambardella |title = Learning Approach to the Traveling Salesman Problem |publisher = IEEE Transactions on Evolutionary Computation, 1 (1) |page=214 |year = 1997}}</ref>为例，它是一种模拟蚁群行为的优化算法。人造「蚂蚁」(例如:模拟仿真代替)通过在代表所有可能解的参数空间移动来求取最优解。真实蚂蚁们在探索环境时，会产生信息素来指引彼此寻找资源。模拟的“蚂蚁”会类似地记录它们的位置和求解结果的好坏，以便在随后的模拟迭代计算中有更多的蚂蚁找到更好的解。<ref>Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. {{ISBN|0-262-04219-3}}</ref>蚁群算法的一个变种是蜜蜂算法，它更类似于另一种社会性昆虫————蜜蜂的觅食模式。
以蚁群算法<ref>{{cite journal|last = Dorigo, Gambardella |first = M, L.M. |authorlink = M. Dorigo & L. M. Gambardella |title = Learning Approach to the Traveling Salesman Problem |publisher = IEEE Transactions on Evolutionary Computation, 1 (1) |page=214 |year = 1997}}</ref>为例，它是一种模拟蚁群行为的优化算法。人造「蚂蚁」(例如:模拟仿真代替)通过在代表所有可能解的参数空间移动来求取最优解。真实蚂蚁们在探索环境时，会产生<font color="#ff8000">信息素</font>来指引彼此寻找资源。模拟的“蚂蚁”会类似地记录它们的位置和求解结果的好坏，以便在随后的模拟迭代计算中有更多的蚂蚁找到更好的解。<ref>Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004. {{ISBN|0-262-04219-3}}</ref>蚁群算法的一个变种是蜜蜂算法，它更类似于另一种社会性昆虫————蜜蜂的觅食模式。
This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis, the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. From a broader perspective, ACO performs a model-based search and shares some similarities with estimation of distribution algorithms.
This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis, the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. From a broader perspective, ACO performs a model-based search and shares some similarities with estimation of distribution algorithms.
这个算法是蚁群算法家族的一员，在<font color="#ff8000">群体智能</font>方法中，它构成了一些<font color="#ff8000">元启发式</font>的优化。最初由 Marco Dorigo 在1992年的博士论文中提出<ref>A. Colorni, M. Dorigo et V. Maniezzo, ''Distributed Optimization by Ant Colonies'', actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.</ref><ref name="M. Dorigo, Optimization, Learning and Natural Algorithms">M. Dorigo, ''Optimization, Learning and Natural Algorithms'', PhD thesis, Politecnico di Milano, Italy, 1992.</ref>，第一个蚁群算法的目的是基于蚂蚁在它们的聚居地和食物之间寻找一条路径的行为，在一张图中寻找最佳路径。借鉴了蚂蚁行为的各个方面，最初的蚁群算法已经变得多样以解决更多类型的数值问题，并且也出现了一些问题。从更高的角度来看，蚁群算法实现了基于模型的搜索<ref>{{cite journal|last1=Zlochin|first1=Mark|last2=Birattari|first2=Mauro|last3=Meuleau|first3=Nicolas|last4=Dorigo|first4=Marco|title=Model-Based Search for Combinatorial Optimization: A Critical Survey|journal=Annals of Operations Research|date=1 October 2004|volume=131|issue=1–4|pages=373–395|doi=10.1023/B:ANOR.0000039526.52305.af|language=en|issn=0254-5330|citeseerx=10.1.1.3.427|s2cid=63137}}</ref> ，并与分布估计算法具有一定的相似性。
New concepts are required since “intelligence” is no longer centralized but can be found throughout all minuscule objects. Anthropocentric concepts have been known to lead to the production of IT systems in which data processing, control units and calculating forces are centralized. These centralized units have continually increased their performance and can be compared to the human brain. The model of the brain has become the ultimate vision of computers. Ambient networks of intelligent objects and, sooner or later, a new generation of information systems which are even more diffused and based on nanotechnology, will profoundly change this concept. Small devices that can be compared to insects do not dispose of a high intelligence on their own. Indeed, their intelligence can be classed as fairly limited. It is, for example, impossible to integrate a high performance calculator with the power to solve any kind of mathematical problem into a biochip that is implanted into the human body or integrated in an intelligent tag which is designed to trace commercial articles. However, once those objects are interconnected they dispose of a form of intelligence that can be compared to a colony of ants or bees. In the case of certain problems, this type of intelligence can be superior to the reasoning of a centralized system similar to the brain.
New concepts are required since “intelligence” is no longer centralized but can be found throughout all minuscule objects. Anthropocentric concepts have been known to lead to the production of IT systems in which data processing, control units and calculating forces are centralized. These centralized units have continually increased their performance and can be compared to the human brain. The model of the brain has become the ultimate vision of computers. Ambient networks of intelligent objects and, sooner or later, a new generation of information systems which are even more diffused and based on nanotechnology, will profoundly change this concept. Small devices that can be compared to insects do not dispose of a high intelligence on their own. Indeed, their intelligence can be classed as fairly limited. It is, for example, impossible to integrate a high performance calculator with the power to solve any kind of mathematical problem into a biochip that is implanted into the human body or integrated in an intelligent tag which is designed to trace commercial articles. However, once those objects are interconnected they dispose of a form of intelligence that can be compared to a colony of ants or bees. In the case of certain problems, this type of intelligence can be superior to the reasoning of a centralized system similar to the brain.
因为“智能”不再是中心化的而可以在所有微小的物体中找到，所以需要一些新的概念来描述。以人为中心的概念被认为引导了 IT 系统的产生，其中数据处理、控制单元和计算力量是集中的。这些集中的单元功能不断地提高，并可以与人类的大脑相比较。大脑模型已经成为计算机的终极愿景。由智能物体构成的环境的网络，以及基于纳米技术的新一代信息系统，迟早会深刻地改变这种概念。可以与昆虫相比较的小型设备本身并不具备高智能。事实上，他们的智能程度相当有限。例如，不可能把一个能解决任何数学问题的高性能计算器集成到可以植入人体的生物芯片中，或者集成到一个用于跟踪商品的智能标签中。然而，一旦这些物体互相连接起来，它们就拥有了可以与一群蚂蚁或蜜蜂相提并论的智慧。在某些问题下，这种类型的智能可能优于类似大脑的集中系统的推理<ref name="Waldner 2008 214">{{cite book |last = Waldner |first = Jean-Baptiste |authorlink = Jean-Baptiste Waldner |title = Nanocomputers and Swarm Intelligence |publisher = [[ISTE Ltd|ISTE]] John Wiley & Sons |place = London |year = 2008 |isbn = 978-1-84704-002-2 | page = 214}}</ref>。
因为“智能”不再是中心化的而可以在所有微小的物体中找到，所以需要一些新的概念来描述。以人为中心的概念被认为引导了 IT 系统的产生，其中数据处理、控制单元和计算力量是集中的。这些集中的单元功能不断地提高，并可以与人类的大脑相比较。大脑模型已经成为计算机的终极愿景。由智能物体构成的环境网络，以及基于<font color="#ff8000">纳米技术</font>的新一代信息系统，迟早会深刻地改变这种概念。可以与昆虫相比较的小型设备本身并不具备高智能。事实上，他们的智能程度相当有限。例如，不可能把一个能解决任何数学问题的高性能计算器集成到可以植入人体的生物芯片中，或者集成到一个用于跟踪商品的智能标签中。然而，一旦这些物体互相连接起来，它们就拥有了可以与一群蚂蚁或蜜蜂相提并论的智慧。在某些问题下，这种类型的智能可能优于类似大脑的集中系统的推理<ref name="Waldner 2008 214">{{cite book |last = Waldner |first = Jean-Baptiste |authorlink = Jean-Baptiste Waldner |title = Nanocomputers and Swarm Intelligence |publisher = [[ISTE Ltd|ISTE]] John Wiley & Sons |place = London |year = 2008 |isbn = 978-1-84704-002-2 | page = 214}}</ref>。
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.
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.
它是蚂蚁系统的一种<font color="#ff8000">递归</font>形式，将整个搜索域划分为若干子域，并在这些子域上求解。<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>
Ant colony optimization algorithms have been applied to many combinatorial optimization problems, ranging from quadratic assignment to protein folding or routing vehicles and a lot of derived methods have been adapted to dynamic problems in real variables, stochastic problems, multi-targets and parallel implementations.
Ant colony optimization algorithms have been applied to many combinatorial optimization problems, ranging from quadratic assignment to protein folding or routing vehicles and a lot of derived methods have been adapted to dynamic problems in real variables, stochastic problems, multi-targets and parallel implementations.
蚁群算法已经被应用于许多组合优化问题，从<font color="#ff8000">二次分配</font>到<font color="#ff8000">蛋白质折叠</font>或<font color="#ff8000">路径选择</font>问题，以及许多派生方法已经被应用于实变量的动态问题、随机问题、多目标和并行方法。
==Applications==
==Applications==
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.
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.
它也被用来产生<font color="#ff8000">旅行商问题</font>的近似最优解。当图形可能发生动态变化时，它们比<font color="#ff8000">模拟退火算法</font>和<font color="#ff8000">遗传算法</font>具有优势; 蚁群算法可以连续运行并实时适应变化。这是网络路由和城市交通系统中很感兴趣的内容。
[[File:Knapsack ants.svg|thumb|[[Knapsack problem]]: The ants prefer the smaller drop of honey over the more abundant, but less nutritious, sugar]]
[[File:Knapsack ants.svg|thumb|[[Knapsack problem]]: The ants prefer the smaller drop of honey over the more abundant, but less nutritious, sugar]]
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/>
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）的天线<font color="#ff8000">RFID</font>标签, <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/>
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.
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算法与其他相关算法（如<font color="#ff8000">分布估计算法</font>或<font color="#ff8000">粒子群优化算法</font>）的区别正是它们的建设性方面。在组合问题中，即使没有蚂蚁被证明是有效的，也有可能最终找到最佳解。因此，在旅行商问题的例子中，蚂蚁实际上并不需要走最短的路线：最短的路线可以从最佳解的最强部分建立起来。然而，在实际变量中存在问题的情况下，这个定义可能会有问题，因为不存在“邻居”的结构。社会性昆虫的集体行为仍然是研究人员灵感的源泉。生物系统中寻求自组织的各种各样的算法（无论是优化还是非优化）导致了“群体智能”的概念
PlotArea = width:170 height:280 left:40 bottom:10
PlotArea = width:170 height:280 left:40 bottom:10