基于百分比问题的蚁群优化或遗传算法

发布于 2024-11-28 10:31:59 字数 1486 浏览 3 评论 0 原文

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

例如:

用户输入:

1) limit -即可用于消耗的能量量。

2)“染色体”类型 -即蓝色(亚型 - 靛蓝等)、红色(亚型 - 栗色等)、黄色(亚型 - 浅黄色等) - 每个主要属性(如蓝色)都有一个“池”可供选择,其中包含不同的子类型(如靛蓝、浅蓝色、海蓝色等)。 -每种颜色子类型都有不同的相关成本。

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

输出:

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

例如。

这是一个超级简单的例子,显然实际情况会比这更复杂。

用户指定成本应如下 95 <= 成本 <= 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)。

So I've recently become really fascinated with algorithms in general. And I recently implemented an ant colony optimization algorithm to solve the TSP (very fun obviously). Now I've been looking at other "problems" to solve. Now I wanted to implement an algorithm to solve a problem involving fulfilling a percentage requirement, and to be below an arbitrary limit.

For example:

User input:

1) limit
-i.e. amount of energy available to spend.

2) "chromosome" types
-i.e. blue(subtypes - indigo, etc), red(subtypes - maroon, etc), yellow(subtypes - light yellow, etc)
-each primary attribute like blue has a "pool" to choose from which consist of different subtypes like indigo, light blue, sea blue whatever.
-each sub type of color has a varying cost associated to it.

3) percentage of types required for the "ideal" solution (can introduce a +/- % to allow for more variety).
-i.e. 10% red, 30% blue, 60% yellow.

Output:

1) possible final solutions which fulfill the two requirements, being below - but close to the - required cost and meeting the percentage requirements of supertypes.

So for example.

This is a super simple example, obviously it'd be more complex than this in reality.

User specifies cost should be as follows
95 <= cost <= 105.

User chooses 25% blue, 25% yellow, 50% red.
with +/- 5% deviation

Available pools for each color

Blue:
Indigo: cost = 25;
Sea blue: cost = 30;
Navy Blue: cost = 75;

Yellow:
Light yellow: cost = 20;
Dark yellow: cost = 30;
Super dark yellow(lol): cost = 75;

Red:
Maroon: cost = 20;
Blood Red: cost = 45;
Bright Red: cost = 55;

So the algorithm would run and return different combinations.

Combination 1: indigo, dark yellow, blood red: cost = 100: blue = 25%, yellow = 30%, red = 55%.

Combination 2: sea blue, light yellow, blood red: cost = 105: blue = ~30%, yellow = ~20%, red = ~50%

Combination 3: so on and so forth.

EDIT: Second edit

Output would consist of sets of different combinations.

For example, one solutions might consist of combinations like:

One solution would be represented by this:

Combination 1: Cost = 20; 50% blue, 25% yellow, 25% red;

Combination 2: Cost = 30; 10% blue, 50% yellow, 40% red;

Combination 3: Cost = 50; 25% blue, 25% yellow, 50% red;

Solution: = (combination 1, combination 2, combination 3) total cost = 100, and it consists of x% blue, y% yellow, z% red;

compare solution to requirements, if its close keep it, if not discard it.

END EDIT

So my question is. I know a genetic algorithm would work. But would an implementation of ACO work as well? For example, blue, yellow and red would equal "locations", then their subtypes would represent different "roads".

Just wondering what might be a more efficient solution or maybe some different algorithm entirely. I'm pretty new to this stuff and just started reading about it a little over a week ago.

EDIT: First edit

I want to specify that I want to have 5 good unique solutions (5 being an arbitrary number, could be 3, could be 20).

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

蹲墙角沉默 2024-12-05 10:31:59

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

Your color problem seems pretty trivial to me, even brute force would be fast, I guess.. so your ant colony most probably can solve it too :)

茶色山野 2024-12-05 10:31:59

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

If your graph satisfy the triangle inequality I suggest you to try a minimal spanning tree and a perfect-weight-non-bipartite matching algorithm. Christofides et al. guarantee you a solution within 3/2 of the optimum. An AOC can give you good and fast result, but you have to optimized it for many problems. I've wrote a Christofides algorithm in php (phpclasses.org). You are welcome to try it out. I'm not sure if it's working. It give sometimes strange results. It's maybe my implementation of the Fleury algorithm?

芯好空 2024-12-05 10:31:59

我认为您对 ACO 的代表的唯一问题是 +/- X% 。

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

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

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

  1. 仅在以下情况下将信息素添加到一条路径 :它满足约束条件
    成本
  2. 选择最接近“最佳长度”的路径长度 = N% of
    最优成本(在上面的示例中,对于黄色路径,
    最接近 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 (链接到 i 和 j 的颜色成本),您可以尝试将 epsilon 添加到 Xi 并从 Xj 中删除它,直到您无法提高所有 Xi 对的成本, Xj。

The only problem I see with your representation for the ACO, is the +/- X% .

With a fixed percentage of each color, you could just proceed as you said:

Blue yellow and red are the locations
The different subtypes represent roads, and their weight depend on the cost and the pourcentage needed.

Then you just apply your AOC method as for the TSP, but changing a bit how the ants move:

  1. adding pheromones to one path only if it fullfills the constraints
    of cost
  2. Selecting the path length closest to the "optimal length" = N% of
    the optimal cost (in the example above, for the yellow path, the one
    closest to 25%*95)

If you want to add the floating percentage constraint then:

let's say you're best cost is:

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

if this cost is not optimal you can work with some small varations on X1 X2 and X3, to optimize your cost:

for example X1-e and X2+e would change your cost by e*(costseablue-costLightYellow)

For example, given one small epsilon, for each pair Xi,Xj such that costi<costj (the cost of color linked to i and j) you can try adding epsilon to Xi and deleting it from Xj until you cannot improve the cost for all couples of Xi,Xj.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文