Ant Colony Optimization or Genetic Algorithm for Percentage Problem

Question

So, I recently became really fascinated by the algorithms in general. And I recently implemented an ant colony optimization algorithm for solving TSP (a lot of fun). Now I look at other "problems" that need to be resolved. Now I wanted to implement an algorithm to solve the problem of fulfilling the percentage requirement and be below an arbitrary limit.

For instance:

User input:

1) -ie limit is the amount of energy that can be spent.

2) types of "chromosomes" —ie blue (subtypes - indigo, etc.), red (subtypes - maroon, etc.), yellow (subtypes - light yellow, etc.), - Each primary attribute , such as blue, has a "pool", the choice of which includes various subtypes, such as indigo, blue, blue. - Each color subtype has a variable value associated with it.

3) the percentage of types needed for an “ideal” solution (can enter + / -% to provide more variety). -ie 10% red, 30% blue, 60% yellow.

Conclusion:

1) possible final solutions that meet two requirements are lower - but close to the required cost and correspond to the percentage requirements of supertypes.

For example.

This is a super simple example, obviously that would be more complex than it really is.

The user indicates that the cost should be as follows: 95 <= cost <= 105.

The user selects 25% blue, 25% yellow, 50% red. with a deviation of +/- 5%

Available pools for each color

Blue: Indigo: value = 25; Blue blue: cost = 30; Blue blue: cost = 75;

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

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

Thus, the algorithm will work and return different combinations.

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

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

Combination 3: et cetera, etc.

EDIT: Second Editing

The output would consist of sets of various combinations.

For example, one solution may consist of combinations such as:

One solution will be presented as follows:

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 consists of x% blue, y% yellow, z% red,

Compare the solution with the requirements, if you close it, if you do not drop it.

End edit

So my question. I know that a genetic algorithm will work. But will there also be an ACO implementation? For example, blue, yellow and red will be equal to "places", then their subtypes will represent different "roads".

It’s just interesting what could be a more efficient solution, or perhaps some other algorithm. I am new to this material and just started reading about it a little over a week ago.

EDIT: First Edit

I want to point out that I want to have 5 good unique solutions (5 is an arbitrary number, maybe 3, maybe 20).

Answer 1

Your color problem seems pretty trivial to me, even brute force will be fast, I think .. so your ant colony will probably be able to solve it too :)

Answer 2

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

With a fixed percentage of each color, you can simply continue as you said:

Blue yellow and red are places. Different subtypes are roads, and their weight depends on the cost and quantity required.

Then you just apply your AOC method as a TSP, but change a little how the ants move:

• adding pheromones to one path only if it fills the cost constraints
• The choice of the path length closest to the "optimal length" = N% of the optimal cost (in the above example for the yellow path, one is closest to 25% * 95)

If you want to add a floating percentage limit, then:

let's say you stand better:

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

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

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

For example, for one small epsilon for each pair of Xi, Xj such that costi<costj (the cost of the color associated with me and j), you can try adding epsilon to Xi and remove it from Xj until you can improve the cost for everyone pairs Xi, Xj.

Answer 3

If your graph satisfies the triangle inequality, I suggest you try a minimal spanning tree and an ideal weight algorithm, rather than a bipartite one. Christofides et al. guarantee you a solution within 3/2 of the optimal. AOC can give you a good and quick result, but you must optimize it for many problems. I wrote the Christofides algorithm in php (phpclasses.org). You may try. I am not sure if it works. This sometimes gives strange results. Perhaps this is my implementation of the Fleury algorithm?