Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Genetic Algorithms, Why does random crossover work?

  1. Feb 7, 2015 #1
    Hi all, I understand Genetic algorithms aside form why crossover helps things, it has no guarantee of getting the best characteristics of each chromosome.
    Ie say you had a genetic algorithm to calculate square roots, fitness = 1(Abs(NumToFindRoot of-(Guess*Guess))
    and your guess was a binary string 00100111001 where the bottom half represents the decimals and the top half the integer part. say our initial population was

    110011= 51
    001010= 20
    111000 =7
    001011= 52

    now select using tournament or roulette method:

    111000 =7
    001010 =20
    and cross them:
    111010= 23
    then mutate
    110010 =19

    Now say we keep repeating this:

    111000=7
    cross->
    110011=51
    equals->
    111111=63
    mutate->
    111110 31
    ---------
    001010 20
    cross
    110011 51
    equals
    001011 52
    mutate
    000011 = 48

    Continue repeating with population of 3, assuming we trying to find square root of 16

    000011 = 48
    111110 = 31
    110010 = 19
    ----------
    010010 = 18
    111000 = 7
    001010 = 20
    ---------
    010000 = 2
    101010 = 21
    110010 =19
    -------
    010110 = 26
    100010 = 17
    010000 =2
    Seems to be getting circular. Am I going about this wrong? can someone explain why random crossover can actually work?
    My code just infinite loops, so i found a GA online and modified it to do this job and it still infinite loops, unless the fitness function needs to be a lot more in depth perhaps? I'm thinking my issue is that there isn't a "close to square root" because of the way im representing my number?
    Code (Text):

    for (int i = 0; i <30; i++)
                {
                    Individual indiv1 = tournamentSelection(pop);
                    Individual indiv2 = tournamentSelection(pop);
                    Individual newIndiv = crossover(indiv1, indiv2);
                    newPopulation.saveIndividual(i, newIndiv);
                }

                for (int i = elitismOffset; i < newPopulation.size(); i++)
                {
                    mutate(newPopulation.getIndividual(i));
                }
     
     
    Last edited: Feb 7, 2015
  2. jcsd
  3. Feb 7, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't understand your example, but in general most crossovers won't give good results - but there is a small chance to get an interesting result that would be hard to reach with smaller mutations.
     
  4. Feb 7, 2015 #3
    but even with those, the premise seems flawed. It seems to just randomly reach instead of converge since the best traits arnt carried over, how does it converge? Can someone explain?
     
  5. Feb 7, 2015 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    There isn't any guarantee of convergence.

    In nature, it is not only specific genetic make-up that evolves; the method of translating genetic make-up into behavior and the method of creating genetic variation evolves. For example, if your system represented "animals" that needed to adapt to producing the square root of a number that slowly varied (e.g. 16, 25, 19, 22...) then your species of animals might go extinct if there were competing species that used different methods of creating genetic variation or translated the bits in the genetic representation into an algorithm differently.

    Intuitively, if the parent animals did a fairly good job of estimate sqr(k) then a good system of reproduction would assure that many of their descendants also did a fairly good job - or at least had a better than completely random chance of doing as well or better than their parents. You could try introducing some genes that affect how two individuals are crossed.

    Genetic programming is trial-and-error with some heuristics thrown-in that hope to make it better than completely random trial-and-error. If your program is repeating the same populations over and over again, you have lost the trial-and-error aspect.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook