集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

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

2020年12月8日 (二) 13:53的版本

删除826字节 、 2020年12月8日 (二) 13:53
→‎Applications
第356行： 第356行：  
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.
 
它还被用于产生[[旅行商问题]]的近似最优解。在图形动态变化的情况下，蚁群算法具有类似问题的[[模拟退火]]和[[遗传算法]]方法的优势；蚁群算法可以连续运行，实时适应变化。这对[[网络路由]]和城市交通系统很有意义  
 
它还被用于产生[[旅行商问题]]的近似最优解。在图形动态变化的情况下，蚁群算法具有类似问题的[[模拟退火]]和[[遗传算法]]方法的优势；蚁群算法可以连续运行，实时适应变化。这对[[网络路由]]和城市交通系统很有意义  
−
It must visit each city exactly once;
+
:1.It must visit each city exactly once;
    
它必须每个城市只到达一次;
 
它必须每个城市只到达一次;
   −
 
+
:2.A distant city has less chance of being chosen (the visibility);
−
 
  −
A distant city has less chance of being chosen (the visibility);
      
较远的城市被选中的机会较少(可见度) ;
 
较远的城市被选中的机会较少(可见度) ;
第368行： 第366行：  
The first ACO algorithm was called the ant system<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> 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:
 
The first ACO algorithm was called the ant system<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> 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:
   −
The more intense the pheromone trail laid out on an edge between two cities, the greater the probability that that edge will be chosen;
+
:3.The more intense the pheromone trail laid out on an edge between two cities, the greater the probability that that edge will be chosen;
    
在两个城市之间的边上留下的信息素踪迹越强烈，这条边被选择的概率就越大;
 
在两个城市之间的边上留下的信息素踪迹越强烈，这条边被选择的概率就越大;
   −
# It must visit each city exactly once;
+
:4.Having completed its journey, the ant deposits more pheromones on all edges it traversed, if the journey is short;
−
它必须访问每座城市一次
  −
Having completed its journey, the ant deposits more pheromones on all edges it traversed, if the journey is short;
      
旅程结束后，如果旅程很短，蚂蚁会在所经过的所有边上释放更多的信息素;
 
旅程结束后，如果旅程很短，蚂蚁会在所经过的所有边上释放更多的信息素;
   −
# A distant city has less chance of being chosen (the visibility);
+
:5.After each iteration, trails of pheromones evaporate.
−
远的城市只有很小的机会被选中（可视性）
  −
After each iteration, trails of pheromones evaporate.
      
每次迭代后，信息素踪迹会蒸发。
 
每次迭代后，信息素踪迹会蒸发。
   −
# The more intense the pheromone trail laid out on an edge between two cities, the greater the probability that that edge will be chosen;
  −
在两个城市之间的边上，信息素的踪迹越密集，被选中的可能性就越大
  −
# Having completed its journey, the ant deposits more pheromones on all edges it traversed, if the journey is short;
  −
蚂蚁完成了它的旅程，如果旅程很短的话，它会在经过的所有边缘上沉积更多的信息素
  −
center
  −
  −
中心
  −
  −
# After each iteration, trails of pheromones evaporate.
  −
  −
每次迭代后，信息素轨迹蒸发
      
[[File:Aco TSP.svg|thumb|600px|center]]
 
[[File:Aco TSP.svg|thumb|600px|center]]
第430行： 第413行：  
具有序列依赖设置时间的单机总延迟问题 <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>
+
*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, 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>
+
具有序列依赖设置/转换时间的多级流车间调度问题 <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,, pp.111-138, 2008.</ref>
      第1,089行： 第1,072行：  
2016年，首次应用于肽序列设计。  
 
2016年，首次应用于肽序列设计。  
 
* 2017, successful integration of the multi-criteria decision-making method PROMETHEE into the ACO algorithm ([[HUMANT (HUManoid ANT) algorithm|HUMANT algorithm]]).<ref>{{cite journal|last1=Mladineo|first1=Marko|last2=Veza|first2=Ivica|last3=Gjeldum|first3=Nikola|title=Solving partner selection problem in cyber-physical production networks using the HUMANT algorithm|journal=International Journal of Production Research|date=2017|volume=55|issue=9|pages=2506–2521|doi=10.1080/00207543.2016.1234084|s2cid=114390939}}</ref>
 
* 2017, successful integration of the multi-criteria decision-making method PROMETHEE into the ACO algorithm ([[HUMANT (HUManoid ANT) algorithm|HUMANT algorithm]]).<ref>{{cite journal|last1=Mladineo|first1=Marko|last2=Veza|first2=Ivica|last3=Gjeldum|first3=Nikola|title=Solving partner selection problem in cyber-physical production networks using the HUMANT algorithm|journal=International Journal of Production Research|date=2017|volume=55|issue=9|pages=2506–2521|doi=10.1080/00207543.2016.1234084|s2cid=114390939}}</ref>
−
2017年，多准则决策方法PROMETHEE成功集成到ACO算法中  
+
2017年，多准则决策方法PROMETHEE成功集成到ACO算法中
    
==References==
 
==References==
薄荷
7,129

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/19795”