2

我已经实现了一个 Ant System 算法来解决 TSP，它获得的游览结果仅比最佳游览长约 5%（可接受）。现在我正在尝试实现类似的Max Min Ant System algorithm。

我实现的算法如下：

func UpdateMaxMin {
    // decay pheromone
    graph.decayPheromone()

    // get best path from this iteration
    bestPath = paths[0]
    for path in paths {
        bestPath = path.length < bestPath.length ? path : bestPath
    }

    // update for only the best path (sometimes use the global best)
    if random(0, 10) > 8 {
        graph.updatePheromone(globalBestPath)
    } else {
        graph.updatePheromone(bestPath)
    }

    // clamp pheromone levels between min and max
    graph.clampPheromone()

    // check for stagnation
    if graph.checkStagnation() {
        // update max
        max = 1 / (rho * globalBestPath.Length)
        // reset all pheromones to max
        graph.SetPheromoneMatrix(max)
    }
}

但是，算法停滞得太快（仅经过几次迭代），一旦停滞，最大信息素就变成了一个很小的数字（小于最小值）。

根据我在网上找到的信息，我正在使用一个信息素衰减率rho = 0.5并初始化max为一个大数，min并

    a := antCount
    p := math.Pow(0.05, 1/a)
    min = max * (1 - p) / (((a / 2) - 1) * p)

除此之外，最好的蚂蚁在他们的旅行中每条边缘沉积的信息素的实际数量由以下公式计算：

    deposit = 1 / tour.Length

然而，这个值太小了，无法真正创建一个明显的最佳路径——例如，如果信息素从 5 开始，在第一次巡回之后它将衰减到 2.5，而最佳蚂蚁将在相关边缘放置大约 0.001 信息素. 即使我将存款乘以蚂蚁的数量，也需要大量的蚂蚁才能产生重大变化。

我的 MMAS 的结果比随机的要好，但比原版的 AS 差得多。MMAS 构建的行程大约是最佳行程的两倍。

谁能指出我对算法的错误（或建议改进）？

4

0 回答 0