3

I want to implement a genetic algorithm (I'm not sure about the language/framework yet, maybe Watchmaker) to optimize the mixing ratio of some fluids.

Each mix consists of up to 5 ingredients a, b, c, d, e, which I would model as genes with changing values. As the chromosome represents a mixing ratio, there are (at least) two additional conditions:

(1) a + b + c + d + e = 1
(2)    a, b, c, d, e >= 0

I'm still in the stage of planning my project, therefore I can give no sample code, however I want to know if and how these conditions can be implemented in a genetic algorithm with a framework like Watchmaker.

[edit]
As this doesn't seem to be straight forward some clarification:

The problem is condition (1) - if each gene a, b, c, d, e is randomly and independently chosen, the probability of this to happen is approximately 0. I would therefore need to implement the mutation in a way where a, b, c, d, e are chosen depending on each other (see Random numbers that add to 100: Matlab as an example).

However, I don't know if this is possible and if it this would be in accordance with evolutionary algorithms in general.

Community
  • 1
  • 1
speendo
  • 13,045
  • 22
  • 71
  • 107
  • What is your objective function? How are you planning to do crossover and mutation? – idfah Sep 12 '13 at 07:40
  • @idfah I don't have precise plans about that yet, however I think I will go with some standard funktions here. The objective function could possibly be the taste of the recipe. Crossover and mutation have to be tested. – speendo Sep 12 '13 at 07:44
  • I don’t see how your constraints are special in a sense of genetic algorithms. It seems you should study the general way of implementing such algorithms first, e.g. reading the framework’s documentation and come back if you have a real question. – Holger Sep 12 '13 at 08:28
  • @Holger You are certainly right, that I need to study genetic algorithms more. Can you recommend a source where I can read about genes that depend on each other (because this is the problem I address in my question - condition (1)). – speendo Sep 12 '13 at 09:01
  • 1
    There are two ways to implement this. First you can enforce the constraints in the mutation part forbidding mutations which yield to a violation. Alternatively you can allow violating the constraints and integrate the check into the fitness function assigning results the more fitness the better they meet the constraints. Both are not that hard once you are into the evolution concept in general. – Holger Sep 12 '13 at 10:45
  • @Holger thanks for your suggestions. As every chromosome should represent a mix and the ingredients of a mix must add up to one per definition, suggestion 2 (fitness function) would not fit here. When I stick with suggestion 1 I would refuse all mutations where `a + b + c + d + e != 1`, with `a, b, c, d, e` being independently and randomly chosen. It is however *really* extremely unlikely that `a + b + c + d + e == 1`. Therefore I doubt this would work (at least in reasonable time). Hope this clarifies my problem? – speendo Sep 12 '13 at 12:29
  • It depends on how you mutate. There is no mandatory way to do it. You might mutate by choosing a pair of genes randomly, mutate one of that pair in an arbitrary way (it’s up to you) and subtract the difference between the old value and the new value from that second gene. So the sum always stays the same. – Holger Sep 12 '13 at 12:35
  • @Holger ok, thanks. A general approach on problems like this is discussed in http://stackoverflow.com/questions/8064629/random-numbers-that-add-to-100-matlab (also see my edit). I am however unsure if doing this is ok in evolutionary algorithms and if implementing a mutation function like this is possible in Watchmaker – speendo Sep 12 '13 at 12:45
  • That sounds too dogmatic to me. If it does mutation and selection, (repeatedly), it’s evolutionary. Regarding Watchmaker… try to find out. – Holger Sep 12 '13 at 12:54
  • @Holger concerning dogmas: ok, sounds consequent, concerning Watchmaker: yeah, partially that's why I posted this question ;-) – speendo Sep 12 '13 at 13:04
  • Using the Watchmaker Framework you can implement your own evolutionary (mutation) operators (see http://watchmaker.uncommons.org/api/org/uncommons/watchmaker/framework/EvolutionaryOperator.html), so you should be able to do what is being described. – Dan Dyer Oct 17 '13 at 11:09

1 Answers1

2

The first condition (a+b+c+d+e=1) can be satisfied by having shorter chromosomes, with only a,b,c,d. The e value can then be represented (in the fitness function or for later use) by e:=1-a-b-c-d.

EDIT:
Another way to satisfy the first condition would be to normalize the values:

sum:= a+b+c+d+e
a:= a/sum;
b:= b/sum;
c:= c/sum;
d:= d/sum;
e:= e/sum;

The new sum will then be 1.

For the second condition (a,b,c,d,e>=0), you can add an approval phase for the new offspring chromosomes (generated by mutation and/or crossover) before throwing them into the gene pool (and allowing them to breed), and reject those who dont satisfy the condition.

Peter Walser
  • 15,208
  • 4
  • 51
  • 78
  • thank you! But how can you prevent that `a + b + c + d > 1` in this solution? Like `a = 0.7` and `b = 0.4`. – speendo Sep 12 '13 at 13:45
  • 1
    In that case, e would become negative and therefore violate the second condition, resulting in this chromosome being rejected. – Peter Walser Sep 12 '13 at 14:22
  • ok, I see... However, I doubt e has the same probability distribution as a-d... But I'm not sure. – speendo Sep 12 '13 at 14:27
  • e actually has a different distribution than a-d, but for the chromosomes it shouldn't matter as only a-d are free parameters. If you do need the same distribution, you can use a-e freely and *normalize* them afterwards by dividing each parameter by the sum of all parameters, giving you a new sum of exactly 1. – Peter Walser Sep 13 '13 at 07:26
  • normalization is probably the best way to go I have read so far. However, there is also a problem with normalization: we change the distribution of the chromosome (see here: http://stackoverflow.com/questions/8064629/random-numbers-that-add-to-100-matlab). – speendo Sep 13 '13 at 09:06
  • 2
    In genetic algorithms, the distribution does not really matter, it affects only the initial population. I'd recommend having the chromosomes redundancy-free, which in your case means only 4 free parameters. Sure, when randomly chosing values for a,b,c,d in the initial population (geneation zero), e tends to be smaller, but as your solution evolves, that effect will vanish and all parameters will likely reach optimal values. – Peter Walser Sep 13 '13 at 10:15