9.6: Genetic Algorithm: Improved Fitness Function – The Nature of Code

9.6: Genetic Algorithm: Improved Fitness Function – The Nature of Code


Hello welcome to another genetic
algorithms video, in this video I want to talk about an improved fitness function,
now there are so many different ways you can improve a fitness function in ways
that you could design and think about a fitness function and I less mean this
video to be like here’s one thing but I just want to use this video as a way to
start thinking about how this fitness function is your creative thing that
you’re creating and anything you could imagine you could possibly do with that
function. So if you recall this particular example which is a search
problem it’s a simulation running a genetic
algorithm to evolve the phrase “To be or not to be” and every time I run this it takes it’s typically taken between
somewhere between like 300 and 600 generations to get to the correct phrase
and you can see it took five hundred fifty four generations
so let’s talk about the fitness function [Coding Power!!] let’s talk about the fitness function and the way to fitness.. if i were to
graph that fitness function right? This is number of, the x axis is the
number of characters correct ok? so the more characters
you get correct the higher the fitness right? Yay more characters correct higher the
fitness and this works because I might have you know in the case I might have a
phrase that’s like 20 characters long and I have you know 16 characters
correct versus 17 correctors.. characters correct, this as a higher fitness it’s going to be more likely to be
picked as a, in the selection process to have its genetic information passed to
the next generation but there’s a problem here what if this
phrase were not 20 characters long but what if it were two thousand or two
hundred thousand or two million characters long? Let’s think about the fitness values of
certain random phrases so one random phrase might
have 391 263 characters correct and another one might have
390 264 characters correct now this one is better than this one and in fact just one more character correct it’s
really a lot better than the other one and we really want to make it more
likely to have its genetic information passed down to the next generation but if you take this value and divide it by 2
million and you take this value and and divide it by 2 million, the number you get from this
value is only a tiny bit bigger than this one so in other words this value is only a
tiny bit bigger than this value but I really want that one that’s a little bit
a tiny bit higher to be much more likely to be picked because I want my evolution
to happen efficiently and faster and all of that so a simple way around this is to make
the uhh.. to make the fitness function exponential what if I could have the number of
charac.. the more characters you have correct the more.. the higher your fitness is
exponentially and there are a variety of ways you can do this I could say the
fitness is 2 to the n (2^n), being n is the number of characters correct I could take n squared or n to the
4th power you know I could probably come up with
some other fancy or math to do but I just want to get you thinking that these
are the types of issues that you want to think about and in fact let’s go back to
this program and I’m gonna go to the fitness function which is here right I’m
just gonna say is a very simple thing I’m gonna say this.fitness equals power this.fitness squared so this is me
taking fitness to the second power and I could’ve just said this.fitness times
this.fitness but whatever I’m doing this.fitness squared and now let’s run
it again and I.. you’ll have to sort of trust in me at this point but I run
this about four or five times and it’s solving it between about three hundred
and six hundred generations let’s run it again. We can play some music
while we wait.. there’s no music… ♪♫ Oh I didn’t have to wait very long – 240.
Let’s run it again ♪♫♩ ♪ ♫ ♬♪♫ ♭ ♩ ♪ ♫ ♬ ♭ ♪♫ boy it’s taking a long time… boy this is not good That was an anomaly, let’s run it again ♪♫♪♫ 217 – that’s pretty good. ♪ ♫ ♬♪♫ ♭ ♩
(music playing) 236, you can
see I’ve improved and I could even go..
I could go to the 4th power right? ♪ ♫ ♬♪♫ ♭ ♩ Aah 120 the wrong button.. refresh ♪ ♫ ♬♪♫ ♭ ♩ 89, so you can see that that exponential fitness function really
has improved things and so this is something you could consider. So you
could also go back to the Smart Rockets example as an exercise, find the Smart
Rockets example that I made in the previous coding challenge and see if you could
use that distance, the distance to the target which is part of the fitness, and
use an exponential function to see if you can make that particular evolution
happen you know more quickly or kind of work more efficiently
okay thanks for watching and I’ll see you in another video soon. Subtitles by the Amara.org community

31 thoughts on “9.6: Genetic Algorithm: Improved Fitness Function – The Nature of Code

  1. how ur typing speed is so good??
    .
    plz give some tips.
    .
    I am saying this after watching snake video game
    ( may u not reply it so 1st comment)

  2. Thank you so much for these video's they're helping me understand so much more about coding and how things work. also love that you tell us to try and do something with the example given it's a really really good exercise

  3. could you provide the source code for this example .. I couldn't find it in your repo. I am interested in understanding how the code works

  4. While having a bit of a play around I found a fairly efficient fitness function where instead of just using the number of matches, keep track of the number of matching characters in a row and add that instead of 1, resetting to 0 if a mismatch is found. Managed to get my code down to ~85 generations rather than 300-600

  5. Sir,this is j.gowtham Doing project on" FRACTIONAL ORDER PID CONTROLLER FOR AN AVR SYSTEM" my Question is How we can apply Fitness function for an fractional order system?
    please sent my information that how we can select for a fractional order transfer function
    please sent to my mail [email protected]
    thank you sir,

    with regards,
    j.gowtham.
    [email protected]

  6. Sir,according to you is macbook air 2016 good for developing games mostly in unity,unreal engine4 & cryengine

  7. I know this might be nitpicky, but technically any fitness function that has a power in it could be called polynomial and it might make more sense. The 2^N function would be exponential, although exponentials can be represented as polynomial functions (a pretty example is of course http://www.wolframalpha.com/input/?i=e%5Ex+expansion) these are only approximations that take infinitely many polynomials to converge. I'm new to these kind of algorithms so take that lightly. Also a question: is it possible that a higher order (polynomial, exponential) functions negatively effect the genetic algorithm's speed? My guess is that there is a point that the function jumps too quickly and the variation of mutations becomes a limiting factor.

  8. I am having some trouble with this code. I made one that works in the same way of yours, but in python; and when I add an exponencial function in Fitness it becomes slow, cause of the size of the list that store all that data. How can I solve it? It seens that as I am storing toons of arrays it is filling my memory.
    By the way, that is an awesome serie, I am waching all your videos!

  9. i have problem in generating my fitness function using both PSNR and NCC parameter. The aim is to find the most optimize or best solution for my image watermarking scaling factor (using genetic algorithm)

    Hopefully, you guys can help me. Thank you

  10. I found that if the crossover is based on the weight of the fitness it can perform faster. If for example you want the crossover between .7 and .8 fitness you have a ~.46 chance from the the first and .53 from the second (.7/(.7+.8)). In the loop you can generate a random(1) and check if it is less then this.fitness/sum, then set child genes to this.genes at i.

  11. Great video Daniel. Love your work. I notice you're typing examples in JavaScript but the code on your github for this project is all in Java. Is that intentional or am I missing something?

    https://github.com/shiffman/The-Nature-of-Code-Examples/tree/master/chp09_ga/NOC_9_01_GA_Shakespeare

    Thanks and keep up the great work

  12. The matingPool Algorithm is good but when I am selecting the top 2 fittest and mating them population.length times that is giving me results better than the Shakespeare Example of yours

  13. Hello!
    I ran into a problem that I think you didn't mention in the video. When you take score of an individual and divide it by the length of the target phrase, you always get a numer between zero and one, right? And when you take that value squared, or taken to the fourth power, or whatever, you end up with a smaller number (for example: 0.2^2=0.04). Depending on small that number is across the population, you might end up with no individuals in the mating pool at all, because the fitnesses are so small. And that's what happened to me. Am I missing something? Am I doing something wrong? Thanks!

  14. I'm kind of proud of myself for thinking of that after watching a few of the previous videos and writing my own algorithm.
    I think your videos are amazing! Keep up the good work. 👍

  15. What is the draw back to using an exponential function as opposed to al linear function? Given the efficiency you demonstrated here, why would anyone use a linear function to reward fitness?

Leave a Reply

Your email address will not be published. Required fields are marked *