更改

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

2020年12月15日 (二) 11:25的版本

添加3,266字节、 2020年12月15日 (二) 11:25

无编辑摘要

第483行：第483行：

纳米电子学物理设计中的器件尺寸问题

* Ant colony optimization (ACO) based optimization of 45 nm CMOS-based sense amplifier circuit could converge to optimal solutions in very minimal time.<ref>O. Okobiah, S. P. Mohanty, and E. Kougianos, "[http://www.cse.unt.edu/~smohanty/Publications_Conferences/2012/Mohanty_ISQED2012_Kriging-ACO.pdf Ordinary Kriging Metamodel-Assisted Ant Colony Algorithm for Fast Analog Design Optimization] {{webarchive |url=https://web.archive.org/web/20160304110324/http://www.cse.unt.edu/~smohanty/Publications_Conferences/2012/Mohanty_ISQED2012_Kriging-ACO.pdf |date=March 4, 2016 }}", in Proceedings of the 13th IEEE International Symposium on Quality Electronic Design (ISQED), pp. 458--463, 2012.</ref>

−

基于蚁群优化（ACO）的45 nm ~~CMOS感放电路优化可以在非常短的时间内收敛到最优解~~

+

基于蚁群优化（ACO）的45 nm CMOS感放电路优化可以在非常短的时间内收敛到最优解。

−

~~Loopback vibrators 10×10, synthesized by means of ACO algorithm~~

−

~~采用蚁群算法合成回路振子10 × 10~~

* 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）的可逆电路合成可以显著提高效率 <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~~

第505行：第501行：

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标签, <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标签, <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/>

第513行：第509行：

The ACO algorithm is used in image processing for image edge detection and edge linking.<ref>S. Meshoul and M Batouche, "[https://pdfs.semanticscholar.org/bdd2/61ab1f5a0c90009c6d84dbe4121a87dd4d31.pdf Ant colony system with extremal dynamics for point matching and pose estimation]," Proceedings of the 16th International Conference on Pattern Recognition, vol.3, pp.823-826, 2002.</ref><ref>H. Nezamabadi-pour, S. Saryazdi, and E. Rashedi, "[https://www.researchgate.net/profile/Esmat_Rashedi/publication/220176122_Edge_detection_using_ant_algorithms/links/5743d1ab08ae9ace841b4063.pdf Edge detection using ant algorithms]", Soft Computing, vol. 10, no.7, pp. 623-628, 2006.</ref>

−

~~There are various methods to determine the heuristic matrix. For the below example the heuristic matrix was calculated based on the local statistics:~~

+

在图像处理中，蚁群算法可以用于进行边缘检测与与边缘连接。

−

~~确定启发式矩阵的方法有多种。对于下面的例子，启发式矩阵是根据局部统计数据计算出来的:~~

* '''Edge detection:'''

−

+

The graph here is the 2-D image and the ants traverse from one pixel depositing pheromone. The movement of ants from one pixel to another is directed by the local variation of the image's intensity values. This movement causes the highest density of the pheromone to be deposited at the edges.

这里的图是二维图像,并且蚂蚁从一个像素的沉积信息素遍历。蚂蚁从一个像素移动到另一个是由图像灰度值的局部变化引导的。这样的移动导致最高密度的信息素沉积在边缘上。

+

The following are the steps involved in edge detection using 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>

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

第529行：第525行： −

the ~~local statistics at~~ the ~~pixel position~~ (i,j).

+

''Step1: Initialization: ''Randomly place <math>K</math> ants on the image <math>I_{M_1 M_2}</math> where <math>K= (M_1*M_2)^\tfrac{1}{2}</math> . Pheromone matrix <math>\tau_{(i,j)}</math> are initialized with a random value. The major challenge in the initialization process is determining the heuristic matrix.

+

Step1: Initialization: Randomly place <math>K</math> ants on the image <math>I_{M_1 M_2}</math> where <math>K= (M_1*M_2)^\tfrac{1}{2}</math> . Pheromone matrix <math>\tau_{(i,j)}</math> are initialized with a random value. The major challenge in the initialization process is determining the heuristic matrix.

−

像素(i，j)~~的局部统计数据。~~

+

Step1: 初始化: 在图像<math>I_{M_1 M_2}</math>上随机放置蚂蚁<math>k</math >，其中<math>k=(m_1*m_2)^tfrac{1}</math> 。信息素矩阵<math>tau_{(i，j)}</math>由一个随机值初始化。在初始化过程中的主要困难是确定启发式矩阵。

−

~~The graph here is the 2-D image and the ants traverse from one pixel depositing pheromone. The movement of ants from one pixel~~ to ~~another is directed by the local variation of~~ the ~~image's intensity values~~. ~~This movement causes~~ the ~~highest density of~~ the ~~pheromone to be deposited at~~ the ~~edges.~~

+

There are various methods to determine the heuristic matrix. For the below example the heuristic matrix was calculated based on the local statistics:

+

There are various methods to determine the heuristic matrix. For the below example the heuristic matrix was calculated based on the local statistics:

−

~~<math>\eta_{(i,j)}= \tfrac{1}{Z}*Vc*I_{(i,j)}</math>~~

+

确定启发式矩阵的方法有多种。对于下面的例子，启发式矩阵是根据局部统计数据计算出来的:

+

the local statistics at the pixel position (i,j).

−

~~The following are~~ the ~~steps involved in edge detection using 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>~~

+

the local statistics at the pixel position (i,j).

+

像素(i，j)的局部统计数据。

+

<math>\eta_{(i,j)}= \tfrac{1}{Z}*Vc*I_{(i,j)}</math>

Where <math>I</math> is the image of size <math>M_1*M_2</math>

+

其中 <math>I</math> 是尺寸为 <math>M_1*M_2</math>的图像

−

大小<math>M_1*M_2</math>~~的图像~~<math>I</math> ~~在哪里~~

+

<math>Z =\sum_{i=1:M_1} \sum_{j=1:M_2} Vc(I_{i,j})</math>, which is a normalization factor

+

<math>Z =\sum_{i=1:M_1} \sum_{j=1:M_2} Vc(I_{i,j})</math>, 是一个归一化因子

−

''Step1: Initialization: ''Randomly place <math>K</math> ants on the image <math>I_{M_1 M_2}</math> where <math>K= (M_1*M_2)^\tfrac{1}{2}</math> . Pheromone matrix <math>\tau_{(i,j)}</math> are initialized with a random value. The major challenge in the initialization process is determining the heuristic matrix.

−

Step1: Initialization: Randomly place <math>K</math> ants on the image <math>I_{M_1 M_2}</math> where <math>K= (M_1*M_2)^\tfrac{1}{2}</math> . Pheromone matrix <math>\tau_{(i,j)}</math> are initialized with a random value. The major challenge in the initialization process is determining the heuristic matrix.

−

Step1: 初始化: 在图像<math>I_{M_1 M_2}</math> 上随机放置蚂蚁 < math > k </math >，其中 < math > k = (m _ 1 * m _ 2) ^ tfrac {1} </math > 。信息素矩阵 < math > tau _ {(i，j)} </math > 由一个随机值初始化。在初始化过程中的主要困难是确定启发式矩阵。

−

~~There are various methods to determine the heuristic matrix. For the below example the heuristic matrix was calculated based on the local statistics:~~

−

~~the local statistics at the pixel position (i,j).~~

−

~~<math>\eta_{(i,j)}= \tfrac{1}{Z}*Vc*I_{(i,j)}</math>~~

−

~~Where <math>I</math> is the image of size <math>M_1*M_2</math> ~~

−

~~<math>Z =\sum_{i=1:M_1} \sum_{j=1:M_2} Vc(I_{i,j})</math>, which is a normalization factor 是一个归一化因子~~

<math>\begin{align}Vc(I_{i,j}) = &f \left( \left\vert I_{(i-2,j-1)} - I_{(i+2,j+1)} \right\vert + \left\vert I_{(i-2,j+1)} - I_{(i+2,j-1)} \right\vert \right. \\

第579行：第569行：

0, & \text{else}\end{cases}</math>

−

The parameter <math>\lambda</math> in each of above functions adjusts the functions’ respective shapes. Step 2 Construction process: The ant's movement is based on 4-connected pixels or 8-connected pixels. The probability with which the ant moves is given by the probability equation <math>P_{x,y}</math> Step 3 and Step 5 Update process: The pheromone matrix is updated twice. in step 3 the trail of the ant (given by <math>\tau_{(x,y)}</math> ) is updated where as in step 5 the evaporation rate of the trail is updated which is given by the below equation. <math>

+

The parameter <math>\lambda</math> in each of above functions adjusts the functions’ respective shapes.

+

上面每个函数中的参数<math>\lambda</math>用来调整函数各自的形状。

+

Step 2 Construction process: The ant's movement is based on 4-connected pixels or 8-connected pixels. The probability with which the ant moves is given by the probability equation <math>P_{x,y}</math> Step 3 and Step 5 Update process: The pheromone matrix is updated twice. in step 3 the trail of the ant (given by <math>\tau_{(x,y)}</math> ) is updated where as in step 5 the evaporation rate of the trail is updated which is given by the below equation. <math>

−

~~上面每个函数中的参数<math>lambda</math>用来调整函数各自的形状。 ~~ 步骤2构建过程: 蚂蚁的移动是在4个连接的像素或8个连接的像素进行的。根据概率方程<math>P_{x,y}</math>给出蚂蚁移动的概率 步骤3与步骤5更新过程 信息素矩阵更新两次。在步骤3中，蚂蚁(由<math>\tau_{(x,y)}</math>给出)的踪迹被更新，就像在步骤5中，蚂蚁的踪迹蒸发率由下面的方程进行更新。

+

步骤2构建过程:

+

蚂蚁的移动是在4个连接的像素或8个连接的像素进行的。根据概率方程<math>P_{x,y}</math>给出蚂蚁移动的概率

+

步骤3与步骤5更新过程 信息素矩阵更新两次。在步骤3中，蚂蚁(由<math>\tau_{(x,y)}</math>给出)的踪迹被更新，就像在步骤5中，蚂蚁的踪迹蒸发率由下面的方程进行更新。

<math>

\tau_{new} \leftarrow

第587行：第582行：

</math>, where <math>\psi</math> is the pheromone decay coefficient <math>0< \tau <1</math>

−

~~这里是信息素衰减系数。~~

+

<math>

−

+

\tau_{new} \leftarrow

+

(1-\psi)\tau_{old} + \psi \tau_{0}

+

</math>, 其中 <math>\psi</math> 是信息素衰减系数 <math>0< \tau <1</math>

Step 7 Decision Process: Once the K ants have moved a fixed distance L for N iteration, the decision whether it is an edge or not is based on the threshold T on the pheromone matrix τ. Threshold for the below example is calculated based on Otsu's method.

第596行：第593行：

Image Edge detected using ACO: The images below are generated using different functions given by the equation (1) to (4).<ref>{{cite web|title=File Exchange {{ndash}} Ant Colony Optimization (ACO)|website=[[MATLAB]] Central|url=http://www.mathworks.com/matlabcentral/fileexchange/32009-ant-colony-optimization--aco-}}</ref>

+

使用 ACO 检测图像边缘: 下面的图像是使用方程(1)至(4)给出的不同函数生成的。<ref>{{cite web|title=File Exchange {{ndash}} Ant Colony Optimization (ACO)|website=[[MATLAB]] Central|url=http://www.mathworks.com/matlabcentral/fileexchange/32009-ant-colony-optimization--aco-}}</ref>

[[File:(a)Original Image (b)Image Generated using equation(1) (c)Image generated using equation(2) (d) Image generated using equation(3) (e)Image generated using equation(4).jpg|none|thumb]]

−

~~使用 ACO 检测图像边缘: 下面的图像是使用方程(1)至(4)给出的不同函数生成的。~~

+

* '''Edge linking:'''<ref>{{cite book|last1 = Jevtić|first1 = A.|title = 2009 35th Annual Conference of IEEE Industrial Electronics|last2 = Melgar|first2 = I.|last3 = Andina|first3 = D.|pages = 3353–3358|year = 2009|location = 35th Annual Conference of IEEE Industrial Electronics, 2009. IECON '09.|doi = 10.1109/IECON.2009.5415195|isbn = 978-1-4244-4648-3|s2cid = 34664559}}</ref> ACO has also been proven effective in edge linking algorithms too.

+

边缘连接：<ref>{{cite book|last1 = Jevtić|first1 = A.|title = 2009 35th Annual Conference of IEEE Industrial Electronics|last2 = Melgar|first2 = I.|last3 = Andina|first3 = D.|pages = 3353–3358|year = 2009|location = 35th Annual Conference of IEEE Industrial Electronics, 2009. IECON '09.|doi = 10.1109/IECON.2009.5415195|isbn = 978-1-4244-4648-3|s2cid = 34664559}}</ref>

+

ACO算法在边缘连接算法中也是证明有效的。

−

* '''Edge linking:'''<ref>{{cite book|last1 = Jevtić|first1 = A.|title = 2009 35th Annual Conference of IEEE Industrial Electronics|last2 = Melgar|first2 = I.|last3 = Andina|first3 = D.|pages = 3353–3358|year = 2009|location = 35th Annual Conference of IEEE Industrial Electronics, 2009. IECON '09.|doi = 10.1109/IECON.2009.5415195|isbn = 978-1-4244-4648-3|s2cid = 34664559}}</ref> ACO has also been proven effective in edge linking algorithms too.

=== Other applications ===

第626行：第626行：

* [[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">~~

+

* Energy and electricity network design

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

{{cite conference

第666行：第666行：

==Definition difficulty==

定义困难

+

[[File:Aco shortpath.svg|thumb]]

+

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>

−

~~[[File~~:~~Aco shortpath~~.~~svg|thumb]]~~

+

With an ACO algorithm, the shortest path in a graph, between two points A and B, is built from a combination of several paths. 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 populated metaheuristics with each solution represented by an ant moving in the search space. 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. In their versions for combinatorial problems, they use an iterative construction of solutions. 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".

−

~~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>

+

采用蚁群优化算法，图中两点 a 和 b 之间的最短路径是由多条路径组合建立的。<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>要准确定义算法是不是蚁群算法并不容易，因为其定义可能因作者和用途而有所不同。广义地说，蚁群算法被认为是一种填充的元启发式算法，每个解由一个在搜索空间中移动的蚂蚁表示。<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>蚂蚁标记最优解，并考虑到以前的标记来优化搜索。它们可以被看作是概率化多智能体算法，使用概率分布进行每次迭代之间的转换。<ref>http://www.multiagent.fr/extensions/ICAPManager/pdf/LauriCharpillet2006.pdf</ref> 在用于解决组合问题的蚁群算法版本中，使用了一种解的迭代构造方法。<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>

+

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

−

With an ACO algorithm, the shortest path in a graph, between two points A and B, is built from a combination of several paths. 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 populated metaheuristics with each solution represented by an ant moving in the search space. 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. In their versions for combinatorial problems, they use an iterative construction of solutions. 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", In practice, the use of an exchange of information between ants via the environment (a principle called "stigmergy") is deemed enough for an algorithm to belong to the class of ant colony algorithms. This principle has led some authors to create the term "value" to organize methods and behavior based on search of food, sorting larvae, division of labour and cooperative transportation.

−

采用蚁群优化算法，图中两点 a 和 b 之间的最短路径是由多条路径组合建立的。要准确定义算法是不是蚁群算法并不容易，因为其定义可能因作者和用途而有所不同。广义地说，蚁群算法被认为是一种填充的元启发式算法，每个解由一个在搜索空间中移动的蚂蚁表示。蚂蚁标记最优解，并考虑到以前的标记来优化搜索。它们可以被看作是概率化多智能体算法，使用概率分布进行每次迭代之间的转换。在用于解决组合问题的蚁群算法版本中，使用了一种解的迭代构造方法。根据一些作者的观点，蚁群算法区别于其他相关算法(比如估计分布的算法或粒子群优化算法)的是蚁群算法的建设性方面。在组合问题中，即使没有蚂蚁被证明是有效的，最终可能会找到最好的解。因此，在旅行商问题的例子中，蚂蚁实际上并不需要走最短的路线: 最短的路线可以从最优解中最强的部分建立起来。然而，在实变量中没有“相邻”这样的结构存在，所以这一定义在实变量问题的情况下可能是有问题的。群居昆虫的集体行为仍然是研究人员的灵感来源。在生物系统中寻找自我组织的各种算法(无论是优化还是非优化)促进了“群体智能”的概念，实际上，利用蚂蚁之间通过环境交换信息的行为(一个被称为“暂时能力”的原则)被认为足以使算法属于蚁群算法的一类。这一原则促使一些作者创造了“价值”这个词来组织基于寻找食物，幼虫分类，分工和合作运输的方法和行为。

==Stigmergy algorithms==

Stigmergy算法

−

There is in practice a large number of algorithms claiming to be "ant colonies", without always sharing the general framework of optimization by canonical ant colonies.<ref>Santpal Singh Dhillon , ''Ant Routing, Searching and Topology Estimation Algorithms for Ad Hoc Networks'', [https://books.google.com/books?id=j5fOJqhwcJoC&pg=PA33&dq=Stigmergy+algorithms&hl=fr&sa=X&ved=0ahUKEwjwjfaAtOrTAhWnLsAKHVPkCjYQ6AEIKTAB#v=onepage&q=Stigmergy%20algorithms&f=false], IOS Press, (2008)</ref> In practice, the use of an exchange of information between ants via the environment (a principle called "[[stigmergy]]") is deemed enough for an algorithm to belong to the class of ant colony algorithms. This principle has led some authors to create the term "value" to organize methods and behavior based on search of food, sorting larvae, division of labour and cooperative transportation.<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006. {{ISBN|978-3-540-34689-0}}</ref>

+

There is in practice a large number of algorithms claiming to be "ant colonies", without always sharing the general framework of optimization by canonical ant colonies.<ref>Santpal Singh Dhillon , ''Ant Routing, Searching and Topology Estimation Algorithms for Ad Hoc Networks'', [https://books.google.com/books?id=j5fOJqhwcJoC&pg=PA33&dq=Stigmergy+algorithms&hl=fr&sa=X&ved=0ahUKEwjwjfaAtOrTAhWnLsAKHVPkCjYQ6AEIKTAB#v=onepage&q=Stigmergy%20algorithms&f=false], IOS Press, (2008)</ref>

−

在实践中，蚂蚁之间通过环境交换信息（称为“[[stigmergy]]”的原理）被认为足以使算法属于蚁群算法。基于这种“合作性”的分类原则，作者提出了一些“合作式”的分类和运输方式。

+

在实践中，有大量的算法声称是“蚁群”，但并不总是拥有典型蚁群优化的一般框架。<ref>Santpal Singh Dhillon , ''Ant Routing, Searching and Topology Estimation Algorithms for Ad Hoc Networks'', [https://books.google.com/books?id=j5fOJqhwcJoC&pg=PA33&dq=Stigmergy+algorithms&hl=fr&sa=X&ved=0ahUKEwjwjfaAtOrTAhWnLsAKHVPkCjYQ6AEIKTAB#v=onepage&q=Stigmergy%20algorithms&f=false], IOS Press, (2008)</ref>

+

In practice, the use of an exchange of information between ants via the environment (a principle called "[[stigmergy]]") is deemed enough for an algorithm to belong to the class of ant colony algorithms. This principle has led some authors to create the term "value" to organize methods and behavior based on search of food, sorting larvae, division of labour and cooperative transportation.<ref>A. Ajith; G. Crina; R. Vitorino (éditeurs), ''Stigmergic Optimization'', Studies in Computational Intelligence , volume 31, 299 pages, 2006. {{ISBN|978-3-540-34689-0}}</ref>

+

In practice, the use of an exchange of information between ants via the environment (a principle called "stigmergy") is deemed enough for an algorithm to belong to the class of ant colony algorithms. This principle has led some authors to create the term "value" to organize methods and behavior based on search of food, sorting larvae, division of labour and cooperative transportation.

+

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

+

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

==Related methods==

第686行：第696行：

*[[Genetic algorithm]]s (GA) maintain a pool of solutions rather than just one. The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded.

−

基因算法（GA）维护一个解决方案池，而不仅仅是一个。寻找更好的解决方案的过程模仿了进化的过程，解决方案被组合或变异以改变解决方案池，劣质的解决方案被丢弃。

+

基因算法（GA）维护不是一个而是一组解。寻找更好的解的过程模仿了进化的过程，解被组合或变异以改变解空间，较差的解被丢弃。

+

* An [[estimation of distribution algorithm]] (EDA) is an [[evolutionary algorithm]] that substitutes traditional reproduction operators by model-guided operators. Such models are learned from the population by employing machine learning techniques and represented as probabilistic graphical models, from which new solutions can be sampled<ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|title=Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms|date=2005|publisher=Springer|location=Berlin [u.a.]|isbn=978-3-540-23774-7|edition=1st}}</ref> or generated from guided-crossover.<ref>{{cite book|last1=Thierens|first1=Dirk|s2cid=28648829|chapter=The Linkage Tree Genetic Algorithm|journal=Parallel Problem Solving from Nature, PPSN XI|date=11 September 2010|pages=264–273|doi=10.1007/978-3-642-15844-5_27|language=en|isbn=978-3-642-15843-8}}</ref><ref>{{cite journal|last1=Martins|first1=Jean P.|last2=Fonseca|first2=Carlos M.|last3=Delbem|first3=Alexandre C. B.|title=On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem|journal=Neurocomputing|date=25 December 2014|volume=146|pages=17–29|doi=10.1016/j.neucom.2014.04.069}}</ref>

+

An [[estimation of distribution algorithm]] (EDA) is an [[evolutionary algorithm]] that substitutes traditional reproduction operators by model-guided operators. Such models are learned from the population by employing machine learning techniques and represented as probabilistic graphical models, from which new solutions can be sampled or generated from guided-crossover.

+

分布估计算法（EDA）是一种进化算法，它用模型引导的算子代替传统的复制算子。这类模型通过机器学习技术从群体中学习，并以概率图形模型表示，从中可以通过抽样或引导交叉生成新的解。

+

*[[Simulated annealing]] (SA) is a related global optimization technique which traverses the search space by generating neighboring solutions of the current solution. A superior neighbor is always accepted. An inferior neighbor is accepted probabilistically based on the difference in quality and a temperature parameter. The temperature parameter is modified as the algorithm progresses to alter the nature of the search.

第697行：第713行：

*[[Tabu search]] (TS) is similar to simulated annealing in that both traverse the solution space by testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest fitness of those generated. To prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions. It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.

−

[[塔布研究]]（TS）类似于模拟退火，两者都通过测试单个解的突变来遍历解空间。模拟退火只产生一个变异解，禁忌搜索则产生许多变异解，并移到适应度最低的解。为了防止循环并鼓励在解决方案空间中进行更大的移动，禁忌列表保留了部分或完整解决方案。禁止移动到包含禁忌列表元素的解，该列表会随着解遍历解空间而更新

+

塔布搜索（TS）类似于模拟退火，两者都通过测试单个解的突变来遍历解空间。模拟退火只产生一个变异解，塔布搜索则产生许多变异解，并转移到适应度最低的解。为了防止循环并鼓励在解空间中进行更大的移动，塔布列表保留了部分或完整的解。禁止移动到包含塔布列表元素的解，该列表会随着解遍历解空间而更新

*[[Artificial immune system]] (AIS) algorithms are modeled on vertebrate immune systems.

−

~~[[人工免疫系统]]（AIS）算法是以脊椎动物免疫系统为模型的。~~

+

人工免疫系统（AIS）算法是以脊椎动物免疫系统为模型的。

BackgroundColors = canvas:fond

−

*[[Particle swarm optimization]] (PSO), a [[swarm intelligence]] method

+

粒子群优化，一种群智能方法。

*[[Intelligent Water Drops|Intelligent water drops]] (IWD), a swarm-based optimization algorithm based on natural water drops flowing in rivers

+

智能水滴（IWD），一种基于自然水滴在河流中流动的群优化算法

+

* [[Stochastic diffusion search]] (SDS), an agent-based probabilistic global search and optimization technique best suited to problems where the objective function can be decomposed into multiple independent partial-functions

+

随机扩散搜索（SDS），一种基于主体的概率全局搜索和优化技术，最适合于目标函数可分解为多个独立的部分函数的问题

Lincent

19

个编辑

更改

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

2020年12月15日 (二) 11:25的版本

导航菜单

搜索