Ant Colony Optimization or Genetic Algorithm for percentage based problem

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).

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 :)

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?

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.