Talk:Evolutionary algorithm: Difference between revisions
→Are the Python and C++ solution cheating?: Observation on counter-intuitive effect of a variable mutation rate.
(→Are the Python and C++ solution cheating?: Observation on counter-intuitive effect of a variable mutation rate.) |
|||
| (4 intermediate revisions by 3 users not shown) | |||
Line 78:
== Problem in previous Python implementation ==
In the first Python example:
<
'Less mutation the closer the fit of the parent'
#This formula does not work as intended because it performs int division
return 1-((perfectfitness - fitness(parent)) / perfectfitness * (1 - minmutaterate))
</syntaxhighlight>
For ex- ((20 - 10)/20*(1-0.09)) will evaluate to 0
Thus it gets stuck in an infinite loop waiting for mutation to occur.
Line 108 ⟶ 109:
: Varying the mutation rate is not necessarily cheating but it is deviating from Richard Dawkins' purpose of demonstrating "random variation combined with non-random cumulative selection". The Weasel model uses a mutator and a selector. The mutator is intended to be random while the selector is non-random. If you add a non-random process to the mutator it breaks down the whole purpose of Dawkins' model. I don't understand why it's necessary to vary the mutation rate in the model. Is there biological evidence that nature reduces mutations when we near the ideal target? Dawkins states the notion of the ideal target is "absurd". It's important to stick with the purpose of the model and not change the essence of the model to simple converge more quickly. It's not a competition about who has the most rapidly converging model. --[[User:Davidj|Davidj]] 18:02, 1 October 2011 (UTC)
: Out of curiosity, could the author of the C++ solution explain the constants 0.02 and 0.9 used to calculate the mutation_rate. Thank you. (double const mutation_rate = 0.02 + (0.9*fitness)/initial_fitness;) --[[User:Davidj|Davidj]] 18:02, 1 October 2011 (UTC)
::|I noticed the Algol 68 solution (not written by me) also reduces the mutation rate as the fitness increases - this appears to have the counter-intuitive effect of increasing the time taken to reach the target phrase. Running it with the reducing rate appears to take around 300 iterations on TIO.RUN, whilst with a constant 5% rate, it takes around 110. Note the iteration counts vary widely but a constant rate appears faster. I'll change the Algol 68 code to use a constant rate.
::The Python sample also appears to run faster with a fixed rate (0.95 = 5%, I believe as it mutates if the random number is > the rate). --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 12:40, 16 August 2023 (UTC)
In answer to the first questioner of this section, the target is clearly given and is a static value. This is a major departure from what happens naturally. This is a task to show evolution, as in the gradual development of an answer towards a goal and shouldn't be taken as the answer to evolution theory sceptics. There is no intended cheating in the Python solution, it just "is what it is" and was written to follow the task goals.<br>
Line 144 ⟶ 148:
::::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 ⟶ 154:
:::: 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. :)
:::: I added the following because I was getting the same random sequence every time. Not sure if there's a more efficient way to do that... <code>srand ( time(NULL) );</code> and included <time.h>
:::: Thank you --[[User:Davidj|Davidj]] 18:45, 11 October 2011 (UTC)
== Genetic Algorithm Okay? ==
I've included a Genetic Algorithm implemented in MATLAB. I am unaware if this was okay or not. Genetic Algorithms are considered a subset of evolutionary programming and are very similar to Evolutionary Algorithms, but have a few differences in the way they go about evolving the population. I made sure to include some of the differences between Genetic Algorithms and straight Evolutionary Algorithms, but i believe the code i posted would be a great resource for anyone who wants to implement a vectorized GA in MATLAB (and i have tried to comment out the code well enough that people will understand it).
If you guys disagree that the Genetic Algorithm should be included then i may go ahead and make a new task for it. It just didn't seem quite different enough to warrant its own task. Let me know what you guys think!
--[[User:Gwilli|Gwilli]] ([[User talk:Gwilli|talk]]) 06:30, 3 March 2015 (UTC)
| |||