问题标签 [ant-colony]

我一直在这里和那里阅读有关使用“蚁群”模型作为优化各种类型算法的启发式方法的内容。但是，我还没有找到一篇文章或书籍以介绍性的方式讨论蚁群优化，甚至是非常详细的讨论。谁能指出我可以了解更多关于这个想法的一些资源？

我正在寻找实现蚁群优化的 .NET-Class 库或 .NET-Framework。你能给我关于这个主题的任何链接、资源等吗？

所以我正在实现一个启发式算法，我遇到了这个函数。

我有一个 1 到 n 的数组（C 上的 0 到 n-1，w/e）。我想选择一些我将复制到另一个数组的元素。给定一个参数 y，(0 < y <= 1)，我想要一个平均数为 (y * n) 的数字分布。这意味着每当我调用这个函数时，它都会给我一个介于 0 和 n 之间的数字，这些数字的平均值是 y*n。

根据作者的说法，“l”是一个随机数：0 < l < n。在我的测试代码中，它当前生成 0 <= l <= n。而且我有正确的代码，但我现在已经搞砸了几个小时，而且我懒得把它编码回来。

所以我编写了函数的第一部分，对于 y <= 0.5，我将 y 设置为 0.2，将 n 设置为 100。这意味着它必须返回一个介于 0 和 99 之间的数字，平均为 20。结果不在0 和 n，但有些浮动。n 越大，这个浮点数就越小。

这是 C 测试代码。“x”是“l”参数。

以下是一些结果（截断 5 位小数）：

文章是：

http://www.scribd.com/doc/3097936/cAS-The-Cunning-Ant-System

第 6 页和第 7 页。

或在谷歌上搜索“cAS：狡猾的蚂蚁系统”。

那我做错了什么？我不相信作者是错的，因为有超过 5 篇论文描述了相同的功能。

我所有的互联网给任何帮助我的人。这对我的工作很重要。

谢谢 ：）

所以我最近对一般的算法非常着迷。我最近实现了一个蚁群优化算法来解决 TSP（显然很有趣）。现在我一直在寻找其他要解决的“问题”。现在我想实现一个算法来解决一个涉及满足百分比要求的问题，并且低于任意限制。

例如：

用户输入：

1) 限制 - 即可以花费的能量。

2）“染色体”类型 - 即蓝色（子类型 - 靛蓝等），红色（子类型 - 栗色等），黄色（子类型 - 浅黄色等） - 每个主要属性（如蓝色）都有一个“池”可供选择由不同的亚型组成，如靛蓝、浅蓝色、海蓝色等等。-每种颜色的子类型都有与之相关的不同成本。

3）“理想”解决方案所需的类型百分比（可以引入 +/- % 以允许更多种类）。-即 10% 红色、30% 蓝色、60% 黄色。

输出：

1) 满足这两个要求的可能最终解决方案，低于 - 但接近 - 所需成本并满足超类型的百分比要求。

举个例子。

这是一个超级简单的例子，显然它实际上会比这更复杂。

用户指定成本应如下 95 <= cost <= 105。

用户选择 25% 蓝色、25% 黄色、50% 红色。有 +/- 5% 的偏差

每种颜色的可用池

蓝色： 靛蓝：成本 = 25；海蓝：成本=30；海军蓝：成本 = 75；

黄色： 浅黄色：成本=20；深黄色：成本=30；超深黄色（笑）：成本= 75；

红色： 栗色：成本 = 20；血红色：成本= 45；亮红色：成本 = 55；

所以算法会运行并返回不同的组合。

组合1：靛蓝、深黄、血红：成本=100：蓝色=25%，黄色=30%，红色=55%。

组合2：海蓝、浅黄、血红：成本=105：蓝色=~30%，黄色=~20%，红色=~50%

组合3：依此类推。

编辑：第二次编辑

输出将由一组不同的组合组成。

例如，一种解决方案可能包含以下组合：

一种解决方案可以这样表示：

组合1：成本=20；50% 蓝色，25% 黄色，25% 红色；

组合2：成本=30；10% 蓝色，50% 黄色，40% 红色；

组合3：成本=50；25% 蓝色、25% 黄色、50% 红色；

解：=（组合1，组合2，组合3）总成本=100，由x%蓝色，y%黄色，z%红色组成；

将解决方案与需求进行比较，如果关闭则保留它，如果不丢弃它。

结束编辑

所以我的问题是。我知道遗传算法会起作用。但是 ACO 的实施是否也能奏效？例如，蓝色、黄色和红色将等于“位置”，那么它们的子类型将代表不同的“道路”。

只是想知道什么可能是更有效的解决方案，或者可能是完全不同的算法。我对这些东西很陌生，一个多星期前才开始阅读它。

编辑：第一次编辑

我想指定我想要 5 个好的唯一解决方案（5 是任意数字，可能是 3，可能是 20）。

我正在研究能够使用基因编程进行食物觅食行为的进化蚂蚁，正如 Koza在这里所描述的那样。每个时间步，我遍历每只蚂蚁，执行它的计算机程序（同一个程序被蚁群中的所有蚂蚁使用）。目前，我已经定义了简单的指令，如MOVE-ONE-STEP、TURN-LEFT、TURN-RIGHT等。但我也有一个PROGN按顺序执行参数的函数。我遇到的问题是，因为PROGN可以按顺序执行指令，这意味着蚂蚁可以在一个时间步内执行多个操作。与自然不同，我不能并行运行蚂蚁，这意味着一只蚂蚁可能会去执行几个动作，操纵环境，而所有其他蚂蚁都在等待轮到他们。

我只是想知道，这是通常的做法，还是有更好的方法？Koza 似乎没有提及任何关于它的事情。问题是，我想扩展场景以拥有其他代理（例如敌人），这可能依赖于在单个时间步中仅发生一次的事情。

我想在无向图中找到所有 k-clique。因此，我需要基于蚁群的精确算法来查找图中的所有 k-clique。例如，考虑这个相邻矩阵：

在这个相邻的矩阵中，我们有三个 3-clique：(1,2,3),(2,3,4),(3,4,5)

我想在每个图中找到这个 k-clique。note=K 是 K-clique 算法的输入。

我正在尝试为 01MKP 实施 ACO。我的输入值来自 OR-Library mknap1.txt。根据我的算法，首先我随机选择一个项目。然后我计算构造图上所有其他项目的概率。概率方程取决于信息素水平和启发式信息。

我的信息素矩阵的单元格在初始值 (0.2) 时具有恒定值。出于这个原因，当我试图找到下一个项目时，由于 0.2，pheremon 矩阵变得无效。所以，我的概率函数确定下一个要走的项目，检查启发式信息。如你所知，启发式信息方程是

（Ravg 是资源约束的平均值）。出于这个原因，我的概率。功能选择具有最大利润价值的项目。（假设在第一次迭代中，我的算法随机选择了一个具有 600 利润的项目。然后在第二次迭代中，选择 2400 利润值。但是，在 OR-Library 中，具有 2400 利润值的项目会导致资源违规。无论我做，第二个选择的是有2400利润的项目。

我的算法有什么问题吗？我希望对ACO有所了解的人应该帮助我。提前致谢。

输入值：

我的算法：

问题背景

我目前正在开发一个蚁群系统算法框架。我想我会先尝试他们应用到的第一个问题：旅行推销员问题（TSP）。我将使用 C# 来完成这项任务。

所有 TSP 实例将由一个完整的无向图组成，每个边有 2 个不同的权重。

问题

到目前为止，我只使用了邻接列表表示，但我读过它们只推荐用于稀疏图。由于我不是最了解数据结构的人，所以我想知道实现无向完整图的最有效方法是什么？

如果需要，我可以提供更多详细信息。

感谢您的时间。

更新

重量澄清。每条边都会有两个与之关联的值：

1. 两个城市之间的距离（ d(i,j) = d(j,i) 两个方向的距离相同）
2. 蚂蚁在特定边缘沉积的信息素量

操作。我将在图表上执行的操作的小总结：

• 对于每个节点，该特定节点上的蚂蚁将必须遍历与所有入射边关联的值

问题说明

蚁群优化算法可以“解决” TSP，因为这是它们首次应用于 . 我说“解决”是因为它们是称为元启发式优化的算法家族的一部分，因此它们从不保证返回最优解。

关于手头的问题：

• 蚂蚁会知道如何完成一次旅行，因为每只蚂蚁都会有记忆。
• 每次蚂蚁访问一个城市时，它都会将该城市存储在它的记忆中。
• 每次蚂蚁考虑访问一个新城市时，它都会在其记忆中搜索并选择一条出边，前提是该边不会将其引导至已访问过的城市。
• 当没有更多的边时，蚂蚁可以选择它已经完成了一次旅行；在这一点上，我们可以通过回溯它的记忆来回溯蚂蚁创建的旅程。

研究文章详情：蚁群系统文章

效率考虑

我更担心运行时间（速度）而不是内存。

我正在尝试构建一个简单的蚁群模拟。世界是方格；它们中的每一个都可以由某种程度的信息素和任意数量的蚂蚁组成。有两种类型的信息素：食物信息素和巢信息素。蚂蚁对环境一无所知，但返回巢穴的蚂蚁会跟随巢穴信息素（从某种意义上说，它们几乎总是选择移动到所有附近细胞中信息素水平最高的细胞）并留下食物信息素，反之亦然。

蚂蚁有时会随机移动，而不是朝着信息素最大的方向移动。模拟的每一刻蚂蚁都会检查附近 8 个单元格中的信息素水平，如果当前单元格中的信息素水平低于附近所有单元格中的最大信息素水平，它会添加一些信息素。

当前的模拟效果很好，但找到的路径不是最佳路径。我有两个问题我不知道如何解决：

1. 我如何模拟对角线移动比非对角线移动更长的事实（上，左下或右）？

1. 我应该如何模拟信息素的扩散？现在，信息素会随着时间的推移而蒸发，但没有扩散。我试图将一些信息素从每个细胞、模拟的每个滴答声转移到附近的 8 个细胞，但结果是一团糟——整个环境都充满了信息素——我认为这是因为机制蚂蚁用来调节信息素水平。

我开发了蚁群优化的软件实现来解决旅行商问题，但由于 ACO 的随机性，每次执行 ACO 算法都会产生不同的接近最优解。有没有办法让 ACO 更具确定性？我知道它永远不会是 100% 确定性的，但我需要它能够在同一个问题空间上运行多次，并且至少在大多数情况下都能提出类似的解决方案。我已经尝试调整 α、β、ρ 和迭代次数，但此时我只是在黑暗中拍摄。