蚁群算法或遗传算法用于基于百分比的问题。

Question

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

例如：

用户输入：

1）限制量 -即可用于花费的能量数量。

2）染色体类型 -即蓝色（亚型-靛蓝等），红色（亚型-栗色等），黄色（亚型-浅黄色等） -每个主属性如蓝色都有一个“池”，其中包含不同的子类型，如靛蓝色，浅蓝色，海蓝色等。 -每个颜色的子类型都有不同的成本。

3）理想解法所需类型的百分比（可以引入+/-％以允许更多变化）。 -即 10％ 红色, 30％ 蓝色, 60％ 黄色。

输出：

1）可能的最终解决方案，满足两个要求，即成本低于，并接近要求的成本，同时满足超类型的百分比要求。

例如。

这是一个超级简单的例子，现实中它肯定会更加复杂。

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

用户选择 25% 蓝色，25% 黄色，50% 红色。 带有+/-5％偏差

每种颜色的可用池：

蓝色： 靛蓝：成本=25; 海蓝色：成本=30; 藏青色：成本=75;

黄色： 浅黄色：成本=20; 深黄色：成本=30; 超级深黄色(lol)：成本=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）。

- Odnxe

---

对于您的颜色问题，任何线性优化算法都可以解决（例如单纯形法、内点法等）。 - Alexandre C.

我可以为您提供另一个有趣的问题，让您用ACO来解决：资源平衡（有时称为CRSP）。与TSP类似。例如，给定一个软件开发团队和一个工作计划，其中任务相互依赖以完成，并且每个任务都分配给特定的人员，找到能够最早完成项目的时间表。 - Assaf Lavie

我刚意识到我提出的问题有误，我本意是要说明候选解是一组满足初始要求的组合。 - Odnxe

Answer 1

你的颜色问题对我来说似乎非常微不足道，即使是暴力算法也会很快，所以你的蚂蚁群可能也能解决它 :)

- duedl0r

---

是的，这个例子很简单，但我认为当不是只有3种颜色，而是5个及以上的超类型要求，并且每个超类型有数百甚至数千个可供选择的子类型时，运行时间问题可能会出现。 - Odnxe

Answer 2

我看到你对ACO的表示方式唯一的问题是+/- X%。

如果每种颜色都有固定的百分比，那么你可以按照你所说的方法进行：

蓝色、黄色和红色是位置， 不同的子类型代表道路，它们的权重取决于成本和所需的百分比。

然后，您只需像处理TSP一样应用AOC方法，但稍微改变蚂蚁的移动方式：

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对改善成本。

- Ricky Bobby

---

好的，首先使用固定百分比实现ACO，如果成本不够优化，则开始在百分比中创建差异，直到达到最佳成本为止？ - Odnxe

@Odnxe 是的，这种方式应该能够与ACO很好地配合使用。您只需要为蚂蚁移动的方式添加一些限制，因为您不是在寻找最短路径。我猜想，在不希望经过的路径上不放置信息素应该足够了，但我不确定。您可以在路径选择上添加一个限制，选择最接近中等成本N％的路径。 - Ricky Bobby

嗯，也许蚁群算法不是最好的选择，因为我想要实现多个良好但独特的解决方案 - 强调独特。我在想，如果不是追踪最佳解决方案，而是追踪一些任意数量的可能解决方案，比如5个。这样我就可以使用5种不同类型的蚂蚁，它们会释放不同种类的信息素，而蚂蚁的行为是尽可能避免其他类型蚂蚁释放的信息素，除非没有其他选择。这样我就可以保证有5个独特的良好解决方案。你觉得呢？ - Odnxe

@Odnxe 这是一种有趣的处理方式。我猜它应该可以工作，并且您对唯一性的约束将得到尊重。但由于算法并不完全是基本的ACO，我不确定它是否始终会收敛。添加新的约束（如信息素约束）可能会使算法不再收敛...但我认为您应该试试，这是一个相当不错的解决问题的方法。 - Ricky Bobby

那么，与其采用5种蚂蚁类型的方法，不如直接运行5次怎么样？这似乎是一个初始条件会起到重要作用的问题。 - Assaf Lavie

我编辑了我的问题，因为我意识到我没有呈现整个问题。它在第二次编辑部分下面。我不知道是否改变了什么。现在我想知道这是否是一个两部分的问题。一部分是我创建潜在候选人，然后第二部分是将它们组合以找到合适的解决方案。 - Odnxe

Answer 3

如果您的图符合三角不等式，我建议您尝试使用最小生成树和完美权重非二分图匹配算法。Christofides等人保证您可以在最优解的3/2内得到一个解决方案。 AOC可以为您提供良好快速的结果，但您必须针对许多问题进行优化。我用php编写了一个Christofides算法（phpclasses.org）。欢迎您来试用。我不确定它是否有效。有时会给出奇怪的结果。这可能是我对Fleury算法的实现方式导致的吗？

- Micromega

---

很多东西都超出了我的理解范围，所以我需要研究这些术语。但是仅仅浏览一下，完美权重非二分图匹配算法似乎是我想要实现的一个很好的匹配。 - Odnxe

这是一项困难的工作，我正在使用的匹配算法是我在互联网上找到的。你可以看一下这个JavaScript TSP求解器，它使用k2-opt算法来搜索可交换边的解决方案：http://code.google.com/p/google-maps-tsp-solver/ - Micromega