更改

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

2021年1月24日 (日) 23:28的版本

添加52字节、 2021年1月24日 (日) 23:28

无编辑摘要

第8行：第8行： −

在计算机科学和运筹学中， 蚁群优化算法 ant colony optimization algorithm~~（ACO）是一种解决计算问题的概率化方法，它可以简化为通过~~[[图 Graph]]来寻找最优路径。人工蚁群代表了受真实蚂蚁行为启发的多主体方法。

+

在计算机科学和运筹学中，''' 蚁群优化算法 ant colony optimization algorithm（ACO）'''是一种解决计算问题的概率化方法，它可以简化为通过[[图 Graph]]来寻找最优路径。人工蚁群代表了受真实蚂蚁行为启发的多主体方法。

−

基于信息素的蚂蚁通信方法常被作为一种典型范式<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>。人工蚁群和局部搜索算法的组合已经是许多优化任务的一种求解方法，这些优化任务往往涉及某种，例如车辆路径 vehicle routing和互联网路由 internet routing的问题。这一领域的蓬勃发展催生了专门讨论人工蚂蚁的学术会议，以及诸如 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>。人工蚁群和局部搜索算法的组合已经是许多优化任务的一种求解方法，这些优化任务往往涉及某种，例如'''车辆路径 vehicle routing'''和'''互联网路由 internet routing'''的问题。这一领域的蓬勃发展催生了专门讨论人工蚂蚁的学术会议，以及诸如 AntOptima 等专业公司的大量商业应用。

−

以蚁群算法<ref>{{cite journal|last = Dorigo, Gambardella |first = M, L.M. |title = Learning Approach to the Traveling Salesman Problem |publisher = IEEE Transactions on Evolutionary Computation, 1 (1) |page=214 |year = 1997}}</ref>为例，它是一种模拟蚁群行为的优化算法。人造”蚂蚁“（例如:仿真模拟的主体）通过在代表所有可能解的参数空间移动来求取最优解。真实蚂蚁们在探索环境时，会产生信息素 pheromone来指引彼此寻找资源。模拟的“蚂蚁”会类似地记录它们的位置和求解结果的好坏，以便在随后的仿真迭代计算中有更多的蚂蚁找到更好的解。<ref>Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004.</ref>蚁群算法的一个变种是蜜蜂算法，它更类似于另一种社会性昆虫——蜜蜂的觅食模式。

+

以蚁群算法<ref>{{cite journal|last = Dorigo, Gambardella |first = M, L.M. |title = Learning Approach to the Traveling Salesman Problem |publisher = IEEE Transactions on Evolutionary Computation, 1 (1) |page=214 |year = 1997}}</ref>为例，它是一种模拟蚁群行为的优化算法。人造”蚂蚁“（例如:仿真模拟的主体）通过在代表所有可能解的参数空间移动来求取最优解。真实蚂蚁们在探索环境时，会产生'''信息素 pheromone'''来指引彼此寻找资源。模拟的“蚂蚁”会类似地记录它们的位置和求解结果的好坏，以便在随后的仿真迭代计算中有更多的蚂蚁找到更好的解。<ref>Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 2004.</ref>蚁群算法的一个变种是蜜蜂算法，它更类似于另一种社会性昆虫——蜜蜂的觅食模式。

−

在~~群智能~~ swarm intelligence方法中,这个算法是蚁群算法家族的一员。它构成了某些元启发式 metaheuristic的优化。第一个蚁群算法最初由 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}}</ref> ，并与'''分布估计算法 estimation of distribution algorithm'''具有一定的相似性。

+

在'''群体智能 swarm intelligence'''方法中,这个算法是蚁群算法家族的一员。它构成了某些'''元启发式 metaheuristic'''的优化。第一个蚁群算法最初由 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}}</ref> ，并与'''分布估计算法 estimation of distribution algorithm'''具有一定的相似性。

第65行：第65行：

===边的选择 Edge selection===

−

每个蚂蚁都需要构造一个解来遍历图。为了在遍历过程中选择下一条边，蚂蚁将考虑从其当前位置可以获得的每条边的长度，以及相应的信息素水平。在算法的每一步，每一个蚂蚁都从状态<math>x</math>移动到状态<math>y</math>，状态<math>y</math>对应一个更完整的中间解。因此，每个蚂蚁<math>k</math> 在每次迭代中计算一组可行展开式集合<math>A_k(x)</math>，并以一定概率移动到其中一个。对于蚂蚁<math>k</math>，从状态<math>x</math>移动到状态<math>y</math>的概率<math>p_{xy}^k</math>取决于两个值的组合，即移动的吸引力<math>\eta_{xy}</math>，这是由某种启发式计算得出的，表示移动的先验期望值和本次移动的信息素踪迹浓度等级<math>\tau_{xy}</math>，这表明它在过去进行该特定移动的熟练程度。踪迹浓度等级代表了本次移动期望的后验指标。

+

每个蚂蚁都需要构造一个解来遍历图。为了在遍历过程中选择下一条边，蚂蚁将考虑从其当前位置可以获得的每条边的长度，以及相应的信息素水平。在算法的每一步，每一个蚂蚁都从状态<math>x</math>移动到状态<math>y</math>，状态<math>y</math>对应一个更完整的中间解。因此，每个蚂蚁<math>k</math> 在每次迭代中计算一组可行展开式集合<math>A_k(x)</math>，并以一定概率移动到其中一个。对于蚂蚁<math>k</math>，从状态<math>x</math>移动到状态<math>y</math>的概率<math>p_{xy}^k</math>取决于两个值的组合，'''即移动的吸引力<math>\eta_{xy}</math>，这是由某种启发式计算得出的，表示移动的先验期望值和本次移动的信息素踪迹浓度等级<math>\tau_{xy}</math>，这表明它在过去进行该特定移动的熟练程度。踪迹浓度等级代表了本次移动期望的后验指标。'''

第75行：第75行：

{ \sum_{z\in \mathrm{allowed}_x} (\tau_{xz}^{\alpha}) (\eta_{xz}^{\beta}) }</math>

−

其中,<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>代表了其他可能的状态转移的轨迹浓度等级和吸引力

+

其中,<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>代表了其他可能的状态转移的轨迹浓度等级和吸引力'''

第133行：第133行：

===连续正交蚁群 Continuous Orthogonal Ant Colony (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>

+

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>

第139行：第139行：

===递归蚁群优化 Recursive Ant Colony Optimization===

−

它是蚂蚁系统的一种递归 recursive形式，将整个搜索域划分为若干子域，并在这些子域上求解。<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>

+

它是蚂蚁系统的一种'''递归 recursive'''形式，将整个搜索域划分为若干子域，并在这些子域上求解。<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>

第239行：第239行：

[[File:ANT antenna 2.jpg|thumb|Unloopback vibrators 10×10, synthesized by means of ACO algorithm<ref name=slyusarant1/>]]

−

~~为了优化天线的结构，可以使用蚁群算法。例如，可以考虑基于蚁群算法（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>10×10的回送和卸载振动器<ref name=slyusarant1/>

+

为了优化天线的结构，可以使用蚁群算法。例如，可以考虑基于蚁群算法（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>10×10的回送和卸载振动器<ref name=slyusarant1/>

第392行：第392行： −

在实践中，蚂蚁之间通过环境交换信息（称为“[[stigmergy]]”的原理）被认为足以使算法属于蚁群算法。基于这种“合作性”的分类原则，作者提出了一些“合作式”的分类和运输方式。<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006. </ref>

+

'''在实践中，蚂蚁之间通过环境交换信息（称为“[[stigmergy]]”的原理）被认为足以使算法属于蚁群算法。基于这种“合作性”的分类原则，作者提出了一些“合作式”的分类和运输方式。'''<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006. </ref>

−

实际上，通过蚂蚁之间通过环境交换信息的行为(被称为“stigmergy”原理)足以使一种算法属于蚁群算法的一类。这一原则促使一些作者创造“价值”这个词来组织基于寻找食物，幼虫分类，分工和合作运输的方法和行为。<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006.</ref>

+

'''实际上，通过蚂蚁之间通过环境交换信息的行为(被称为“stigmergy”原理)足以使一种算法属于蚁群算法的一类。这一原则促使一些作者创造“价值”这个词来组织基于寻找食物，幼虫分类，分工和合作运输的方法和行为。'''<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006.</ref>

薄荷

7,129

个编辑