问题标签 [ant-colony]

我想使用 matlab 比较这些方法。那么计算最佳方法的标准是什么，尽管根据应用程序有不同的方法是有用的。我可以使用下面链接中描述的目标函数吗？此外，哪个函数对计算更有用。

http://www.geatbx.com/download/GEATbx_ObjFunExpl_v37.pdf

我正在研究 ACO，对选择下一个城市的可能性有点困惑。我已经阅读了一些论文和书籍，但仍然不清楚选择的想法。我正在寻找这个路径构建如何工作的简单解释。此外，启发式和信息素是如何进入这个决策的？因为一开始我们在每条边都有相同的信息素值，并且启发式（接近）值保持不变，那么不同的蚂蚁将如何根据这些值做出不同的决定呢？

如果我们有 5 个城市和 5 只蚂蚁。所有蚂蚁都必须从同一个城市开始吗？如果他们从不同的城市出发，有什么区别。我将蚂蚁随机放置在不同的城市作为起点。我尝试使用这两种情况，但我的结果是一样的。我想知道它是否正确或我的代码有问题。

我可以将这个问题命名为“具​​有互节点的多个旅行推销员问题”。我有一群来自城市不同地点的人。他们想计划参观特定的商店。我怎么解决这个问题？如何对问题建模以使用元启发式算法，例如 GA 或 ACO？

我的目标是使用蚁群算法获得图中两个节点之间的最短路径及其长度。

比方说，我们有一个这样的图表：

我想找到从节点0到的最短路径5

目标输出：

我做了什么：

我创建了 Ant Class，但我无法完成它。

我还创建了另一个文件来测试它的类：

我不知道下一步该做什么。

互联网上有许多使用 TSP 的示例。

我正在测试一个蚁群优化 (ACO) 软件，该软件使用多个线程（每个创建的蚂蚁 1 个线程）运行。

在允许下一次迭代开始之前，每次 ACO 迭代都应该等待所有线程完成。我正在使用线程模块中的“条件（）”来执行此操作。

由于蚂蚁共享一个信息素矩阵，因此对该矩阵的读写受制于锁，也来自线程模块。

现在描述问题：

我运行该函数并在每次迭代时打印一些东西。有时，并非总是如此，函数的执行似乎会停止，也就是说，它会停止打印，这意味着迭代从未完成。

老实说，我现在不知道为什么会发生这种情况，我将不胜感激任何可以让我走上正轨的答案。如果我不得不猜测，我会说条件变量没有被正确调用，或者类似的东西。但是我不确定，而且我也觉得奇怪的是这种情况有时会发生。

下面是相关功能。ACO 通过调用 start() 函数开始。这会创建 N 个线程，完成后调用 update()。此更新函数在被调用 N 次后调用 notify，这允许 start() 继续该过程，并最终开始下一次迭代。我还发布了每个线程的运行方法。

值得一提的是，如果没有守护程序操作，错误几乎不会发生。对于守护进程操作，它几乎总是发生（我也觉得很奇怪）。最后，错误并不总是发生在同一次迭代中。

问题的解决方案： 首先，我根据这里的评论纠正了条件变量等待中的错误。其次，它有时仍然挂起，这是由于线程计数器更新中的一些错误错误。解决方案是将计数器从 int 更改为长度为 num_threads、全为 0 的数组，其中每个线程更新其在列表中的位置。当所有线程完成时，计数器数组应该全为 1。这目前工作得很好。

我对算法非常陌生，现在正在研究一些路线优化问题，并遇到了一些关于以下方法的论文：

• 元启发式方法 基于种群（遗传算法、蚁群优化等） 基于单一解决方案（迭代局部搜索）

• 基于图的方法 ，例如 A* 算法

• 混合整数线性规划方法

我对这些方法之间的关系有点困惑，我们是使用例如使用 GA 来解决 MILP 还是它们都只是单独的方法？

提前致谢！！

我已经使用来自以下链接的 Dorigo 的论文在 Java 中为对称 TSP 实现了蚁群系统：http: //people.idsia.ch/~luca/acs-bio97.pdf

我还调整了以下策略：

1.虽然不是所有的蚂蚁都构建了解决方案，但每只蚂蚁移动 1 步到一个新城市，并使用 Dorigo 的本地信息素更新更新边缘上的信息素。

2. 产生最短路径的蚂蚁使用 Dorigo 的全局更新公式全局更新所使用边缘上的信息素

3. 多次迭代后，返回所有迭代中找到的最短路径

有没有办法改进算法以获得更好的结果？例如，在 TSPLIB 中找到的 TSP 实例 ch130 的最佳解决方案是 6110，而我的算法返回答案 6223。

到目前为止，我的 ACS 已将参数设置为 Dorigo 论文中定义的参数

目标是找到起点和终点之间的最短路径，总路径长度被选择为与每个可能的解决方案相关的成本或奖励。在模拟中，考虑了三种不同尺寸的网格网络，即20X20、30X30 和40X40。假设一只蚂蚁只能占据一个节点，并且一次只能沿四个不同方向移动到其相邻节点之一，即上、下、左、右。所有节点均匀分布在网络中；将任意两个相邻节点之间的距离归一化为 1（或 1 个单位块）。因此，路径长度以（单位）块的数量表示。模拟从“干净”的环境开始；即原网络中没有障碍物。选择左上角作为起点，选择右下角作为目的地。所有的信息素都初始化为 0.1。然后应用蚁群算法找到最短路径并沉积信息素。计算流程图如图1所示。图2说明了ACO算法在20X20网格网络中找到的路径收敛到其最佳值，其中y轴表示路径长度（以块/网格数为单位），x -axis 表示模拟运行时间（以秒为单位）。为了模拟动态环境，在算法收敛后添加障碍（障碍物）（为了公平比较，障碍物的大小与网络的大小成正比）。其中 40X40 网格内的两个较暗区域代表添加的两个任意障碍物随机选择的位置。为了在这个有障碍物的新网络中找到最短路径，必须再次调用ACO算法。信息素初始化在ACO算法中起着重要的作用。在这个项目中，添加障碍物后，网络中的信息素被重新初始化。测试了两种不同的重新初始化方案，即全局初始化和局部初始化，并比较了它们的性能。全局初始化时，将全网所有信息素统一重置回原来的信息素水平，即0.1。通过局部初始化，信息素的“梯度”在对象周围初始化。网络中最高信息素水平一半的值直接应用于对象旁边的点。然后信息素水平降低一小部分（例如，

看了很多关于蚁群优化的文档，但是对信息素更新的过程不是很了解。我知道一开始，所有路径都有相同的信息素轨迹。我想知道，在迭代之后，信息素是否将仅在使用的路径上更新，或者该值将在所有路径上更新（我的意思是未使用路径上的信息素轨迹是否等于 (1-r) tau0 ，其中 r 是蒸发速率，tau0 是初始信息素轨迹）？先感谢您