关于一个简单蚁群算法的实现

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

提议方法中的三个问题：

正如@Mark 在他的评论中提到的，您需要一个加权随机选择。否则，建议的方法可能总是选择其中一条路径，并且绘图将导致如上所示的直线。但是，我认为这是解决方案的一部分，因为即使这样，由于早期收敛，您可能仍然会得到一条直线，这导致了两个问题二。
蚁群优化是一种元启发式算法，需要配置多个（超）参数来指导搜索特定解决方案（例如，上面的 tau 或蚂蚁数量）。微调此参数很重要，因为您可以尽早收敛于特定结果（这在某种程度上很好 - 如果您想将其用作启发式算法）。但是元启发式算法的目的是为您提供精确算法和启发式算法之间的一些中间地带，这使得连续 exploration/exploitation 成为其工作的重要组成部分。这意味着需要针对您的问题仔细优化参数 size/type。

鉴于 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)

上面的代码应该return接近所需的情节。

关于一个简单蚁群算法的实现

On the implementation of a simple ant colony algorithm

python

ant-colony