一种简单蚁群算法的实现

Question

在this paper中，描述了一个非常简单的模型来说明蚁群算法是如何工作的。简而言之，它假设两个节点通过两条链路连接，其中一条链路较短。然后，给定一个信息素增量和信息素蒸发动力学，我们期望所有蚂蚁最终选择较短的路径

现在，我尝试复制本文的模拟，对应于上面的场景，其结果应该（或多或少）如下

这是我的一个实现（采用与上述测试相同的规范）

import random
import matplotlib.pyplot as plt

N = 10
l1 = 1
l2 = 2
ru = 0.5
Q = 1
tau1 = 0.5
tau2 = 0.5

epochs = 150

success = [0 for x in range(epochs)]

def compute_probability(tau1, tau2):
    return tau1/(tau1 + tau2), tau2/(tau1 + tau2)

def select_path(prob1, prob2):
    if prob1 > prob2:
        return 1
    if prob1 < prob2:
        return 2
    if prob1 == prob2:
        return random.choice([1,2])

def update_accumulation(link_id):
    global tau1
    global tau2
    if link_id == 1:
        tau1 += Q / l1
        return tau1
    if link_id == 2:
        tau2 += Q / l2
        return tau2

def update_evapuration():
    global tau1
    global tau2
    tau1 *= (1-ru)
    tau2 *= (1-ru)
    return tau1, tau2

def report_results(success):
    plt.plot(success)
    plt.show()

for epoch in range(epochs-1):
    temp = 0
    for ant in range(N-1):
        prob1, prob2 = compute_probability(tau1, tau2)
        selected_path = select_path(prob1,prob2)
        if selected_path == 1:
            temp += 1
        update_accumulation(selected_path)
        update_evapuration()
    success[epoch] = temp

report_results(success)

然而，我得到的是相当奇怪的如下

看来我对信息素应该如何更新的理解是有缺陷的

那么，能否解决我在这个实现中缺少的问题

Answer 1

拟议方法中存在三个问题：

1. 正如@Mark在他的评论中提到的，你需要一个加权随机选择。否则，建议的方法可能总是选择其中一条路径，并且绘图将产生一条直线，如上面所示。然而，我认为这是解决方案的一部分，因为即使这样，你仍然可能得到一条直线，因为早期的收敛导致了两个问题二

2. 蚁群优化是一种元启发式算法，需要配置多个（超）参数来指导对特定解决方案的搜索（例如，上面的tau或蚂蚁数量）。微调此参数非常重要，因为您可以提前收敛到特定的结果（这在某种程度上是很好的，如果您想将其用作启发式）。但元启发式的目的是在精确算法和启发式算法之间提供一些中间地带，这使得持续的探索/开发成为其工作的一个重要部分。这意味着需要针对您的问题大小/类型仔细优化参数

3. 鉴于ACO使用概率方法指导搜索（参考文献中的图表显示），您将需要多次运行实验，并计算这些数字的一些统计数据。在下面的例子中，我计算了100多个样本的平均值

   import random
   import matplotlib.pyplot as plt
   
   N = 10
   l1 = 1.1
   l2 = 1.5
   ru = 0.05
   Q = 1
   tau1 = 0.5
   tau2 = 0.5
   
   samples = 10
   epochs = 150
   
   success = [0 for x in range(epochs)]
   
   def compute_probability(tau1, tau2):
       return tau1/(tau1 + tau2), tau2/(tau1 + tau2)
   
   def weighted_random_choice(choices):
       max = sum(choices.values())
       pick = random.uniform(0, max)
       current = 0
       for key, value in choices.items():
           current += value
           if current > pick:
               return key
   
   
   def select_path(prob1, prob2):
       choices = {1: prob1, 2: prob2}
       return weighted_random_choice(choices)
   
   def update_accumulation(link_id):
       global tau1
       global tau2
       if link_id == 1:
           tau1 += Q / l1
       else:
           tau2 += Q / l2
   
   def update_evaporation():
       global tau1
       global tau2
       tau1 *= (1-ru)
       tau2 *= (1-ru)
   
   def report_results(success):
       plt.ylim(0.0, 1.0)
       plt.xlim(0, 150)
       plt.plot(success)
       plt.show()
   
   for sample in range(samples):
       for epoch in range(epochs):
           temp = 0
           for ant in range(N):
               prob1, prob2 = compute_probability(tau1, tau2)
               selected_path = select_path(prob1, prob2)
               if selected_path == 1:
                   temp += 1
               update_accumulation(selected_path)
               update_evaporation()
           ratio = ((temp + 0.0) / N)
           success[epoch] += ratio
       # reset pheromone values here to evaluate new sample
       tau1 = 0.5
       tau2 = 0.5
   
   success = [x / samples for x in success]
   
   for x in success:
       print(x)
   
   report_results(success)
   

上面的代码应该返回接近所需绘图的内容