6

所以我最近对一般的算法非常着迷。我最近实现了一个蚁群优化算法来解决 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)。

4

3 回答 3

1

如果您的图满足三角不等式,我建议您尝试最小生成树和完美权重非二分匹配算法。克里斯托菲德斯等人。保证您在最佳解决方案的 3/2 范围内得到解决方案。AOC 可以为您提供良好且快速的结果,但您必须针对许多问题对其进行优化。我在 php (phpclasses.org) 中编写了一个 Christofides 算法。欢迎您试用。我不确定它是否有效。它有时会产生奇怪的结果。这可能是我对 Fleury 算法的实现?

于 2011-08-09T15:36:45.793 回答
1

我看到您代表 ACO 的唯一问题是 +/- X% 。

对于每种颜色的固定百分比,您可以按照您所说的进行:

蓝色黄色和红色是位置不同的子类型代表道路,它们的权重取决于成本和所需的流量。

然后,您只需将 AOC 方法应用于 TSP,但稍微改变蚂蚁的移动方式:

  1. 仅在满足成本约束时才将信息素添加到一条路径
  2. 选择最接近“最优长度”的路径长度=最优成本的N%(在上面的例子中,对于黄色路径,最接近25%*95的路径)

如果要添加浮动百分比约束,则:

假设您的最佳成本是:

Cost = X1*light yellow +X2*sea blue+X3*blood red for example.

如果这个成本不是最优的,你可以在 X1 X2 和 X3 上使用一些小的变化来优化你的成本:

例如 X1-e 和 X2+e 会改变你的成本e*(costseablue-costLightYellow)

例如,给定一个小的 epsilon,对于每一对 Xi,Xj 使得costi<costj(与 i 和 j 相关联的颜色成本),您可以尝试将 epsilon 添加到 Xi 并将其从 Xj 中删除,直到您无法提高所有 Xi 对的成本,Xj。

于 2011-08-09T15:17:18.937 回答
1

你的颜色问题对我来说似乎很微不足道,我猜即使蛮力也会很快..所以你的蚁群很可能也可以解决它:)

于 2011-08-09T15:11:49.087 回答