Anonymous user
Talk:Evolutionary algorithm: Difference between revisions
→How to make the algorithm scalable for larger target phrases?
Line 144:
::::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>.
::::: because i want to measure how the algorithm scales as <math>L</math> increases. <math>nL\ln(L)</math> only gives me the total number of mutations needed to find the solution. of course this number will get larger and larger as <math>L</math> gets larger. but if i calculate <math>nL\ln(L)/L</math> i get the average number of mutations needed to improve the result by one character. now if <math>nL\ln(L)/L</math> were constant then, that would mean that <math>nL\ln(L)</math> increases with <math>O(n)</math> (or rather <math>O(L)</math>) but that is not the case, and <math>nL\ln(L)/L</math> just makes this easy to see. it's a visual aid to avoid having to plot <math>nL\ln(L)</math> in order to see that it is a curve going up. --[[User:EMBee|eMBee]] 02:50, 12 October 2011 (UTC)
:::: 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>.
Line 149 ⟶ 150:
:::: 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)
::::: wow, thank you. i tried to figure it out, but my math is not good enough to even tell if i just missed something or if it is really complicated.
:::: You guys are amazing. You're right - I changed the MUTATE rate and the COPIES to 100 and even with 1000 characters I always get to the target in less than 10,000 iterations (sometimes as low as 5000).
:::: I need a bit of time to get my head around the maths. :)
| |||