更改

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

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

{{cite conference

{{cite conference

  | last1 = Warner | first1 = Lars

  | last1 = Warner | first1 = Lars

  | last2 = Vogel | first2 = Ute

  | last2 = Vogel | first2 = Ute

  | title = Optimization of energy supply networks using ant colony optimization

  | title = Optimization of energy supply networks using ant colony optimization

  | date = 2008

  | date = 2008

  | conference = Environmental Informatics and Industrial Ecology — 22nd International Conference on Informatics for Environmental Protection

  | conference = Environmental Informatics and Industrial Ecology — 22nd International Conference on Informatics for Environmental Protection

  | publisher = Shaker Verlag

  | publisher = Shaker Verlag

  | location = Aachen, Germany

  | location = Aachen, Germany

  | isbn = 978-3-8322-7313-2

  | isbn = 978-3-8322-7313-2

  | url = http://enviroinfo.eu/sites/default/files/pdfs/vol119/0327.pdf

  | url = http://enviroinfo.eu/sites/default/files/pdfs/vol119/0327.pdf

  | access-date = 2018-10-09

  | access-date = 2018-10-09

}}

}}

</ref>

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

系统辨识<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>

==Definition difficulty==

==Definition difficulty==

<timeline>

<timeline>

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

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

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

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

 

==Stigmergy algorithms==

==Stigmergy algorithms==

Stigmergy算法  

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

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

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

==Related methods==

==Related methods==

*[[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.

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

*[[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.

*[[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.

模拟退火（SA）是一种相关的全局优化技术，它通过生成当前解的相邻解来遍历搜索空间。更好的的相邻解总是被接受的。根据质量和温度参数的差异概率地接受较差的相邻解。随着算法的进行，温度参数会被修改，以改变搜索的性质。

模拟退火（SA）是一种相关的全局优化技术，它通过生成当前解的相邻解来遍历搜索空间。更好的的相邻解总是被接受的。根据质量和温度参数的差异概率地接受较差的相邻解。随着算法的进行，温度参数会被修改，以改变搜索的性质。

* Reactive search optimization focuses on combining machine learning with optimization, by adding an internal feedback loop to self-tune the free parameters of an algorithm to the characteristics of the problem, of the instance, and of the local situation around the current solution.

* Reactive search optimization focuses on combining machine learning with optimization, by adding an internal feedback loop to self-tune the free parameters of an algorithm to the characteristics of the problem, of the instance, and of the local situation around the current solution.

反应式搜索优化是将机器学习与优化相结合，通过添加一个内部反馈回路，根据问题、实例和当前解周围的局部情况，对算法的自由参数进行自调整。  

反应式搜索优化是将机器学习与优化相结合，通过添加一个内部反馈回路，根据问题、实例和当前解周围的局部情况，对算法的自由参数进行自调整。  

*[[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.

*[[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.

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

BackgroundColors = canvas:fond

BackgroundColors = canvas:fond

 

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

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

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

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

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

==History==

==History==

历史

历史

The inventors are [[Frans Moyson]] and [[Bernard Manderick]]. Pioneers of the field include [[Marco Dorigo]], [[Luca Maria Gambardella]].<ref>{{cite journal|last = Manderick, Moyson |first = Bernard, Frans |authorlink = Manderick, Bernard, and Moyson, Frans |title = The collective behavior of ants: An example of self-organization in massive parallelism.  |publisher = Proceedings of the AAAI Spring Symposium on Parallel Models of Intelligence |place = Stanford |year = 1988}}</ref>

The inventors are [[Frans Moyson]] and [[Bernard Manderick]]. Pioneers of the field include [[Marco Dorigo]], [[Luca Maria Gambardella]].<ref>{{cite journal|last = Manderick, Moyson |first = Bernard, Frans |authorlink = Manderick, Bernard, and Moyson, Frans |title = The collective behavior of ants: An example of self-organization in massive parallelism.  |publisher = Proceedings of the AAAI Spring Symposium on Parallel Models of Intelligence |place = Stanford |year = 1988}}</ref>

 

    

 

   from:1989  till:1989 shift:($dx,$dy)    text:studies of collective behavior

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Chronology of ant colony optimization algorithms.

Chronology of ant colony optimization algorithms.

蚁群优化算法年表  

蚁群优化算法年表