Anonymous user
Talk:Evolutionary algorithm: Difference between revisions
→How to make the algorithm scalable for larger target phrases?: "Math is hard." --Barbie
(→How to make the algorithm scalable for larger target phrases?: "Math is hard." --Barbie) |
|||
Line 143:
}</lang> which produces a very slowly rising value for <math>nL\ln(L)/L</math>.--[[User:EMBee|eMBee]] 16:40, 11 October 2011 (UTC)
::::on a slight tangent, how would that formula look like if i don't pick 1 char but <math>y</math> chars? there is a chance that some chars are unmatched while others are matched, thus reducing the overall chance of getting an improvement.--[[User:EMBee|eMBee]] 16:52, 11 October 2011 (UTC)
:::: Firstly, I'm not sure why you are calculating <math>nL\ln(L)/L</math>.
:::: Secondly, formulating an expression for a general case of <math>y</math> is huuuugely complicated. The case <math>y=2</math> is doable, though. Suppose you always pick two letters to mutate; there are two cases where a mutation is an improvement:
::::# Both letters are unmatched (chance <math>{x\over L}{x-1\over L}</math>), and both are mutated into the matching char (chance <math>{1\over n}{1\over n}</math>). Overall chance: <math>x(x-1)\over L^2n^2</math>.
::::# First choice chooses an unmatched char and mutates into matched, chance <math>{x\over L}{1 \over n}</math>; second choice chooses an unmatched char and mutates into an unmatched char (chance <math>{x-1\over L}{n-1\over n}</math>), '''or''' choose a matched char and "mutates" into the same char (chance <math>{L-x\over L}{1\over n}</math>). Overall chance: <math>2{x\over n^2L^2}\Big((x-1)(n-1)+L-x\Big)</math> (the 2 in the front is from the permutation of 2 choices).
:::: Adding them up, we get the chance at step <math>x</math> as: <math>x(x-1)(2n-1)+2x(L-x)\over n^2L^2</math>. Summing the inverse of that should give you the answer of needed total mutations, unfortunately it's non-trivial to do. However, we can examine its tendency: when <math>x</math> is large (many unmatched chars), the expression is roughly <math>2 x^2\over nL^2</math>; recall that the single char mutation had <math>x\over nL</math>, which means double char mutation is initially faster than single char mutation, until <math>x\approx L/2</math>, i.e. half of the letters matched (this shouldn't be surprising).
:::: After that, when <math>x</math> becomes very small, the expression is <math>\approx {2x\over n^2L}</math>, about <math>2/n</math> of the single char mutation speed, meaning it requires about 13 (n=27)times as many mutations when close to perfect match. Since this is the slowest part of the evolution already, mutating two chars is overall probably about an order of magnitude slower. --[[User:Ledrug|Ledrug]] 18:34, 11 October 2011 (UTC)
| |||