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

Crossover help for Genetic algorithm

  1. May 12, 2015 #1
    Hey all, we're making a robot that teaches itself to walk using a genetic algorithm(took a hiatus with this but have returned).
    So i coded a simulator that to see why the GA wasn't working well with realistic physics.
    The GA works like this "A++,B---,D+" would mean motor A's angle increase by 2*num, and B's angle decrease by 3*num value, angle D's, will be increased by 1*num. But now we can't use standard crossover otherwise they will be a HUGE change between the new and old chromosomes, So our current idea is to cross just the +'s and -'s ie
    A++,B---
    A--,B++
    Would cross to
    A+-,B-+
    But then motor changes have to be in a specific order, so unless they're in the optimum configuration which is cheating) it can never get to an optimum, Any advice? this is like the travelling salesman Genetic algorithm, which needed its own unique crossover and mutation. Any help appreciated.
     
  2. jcsd
  3. May 12, 2015 #2
    The paramétrization of your problem is bad, you can change it now ! By using the one you explain, the convergence of the genetic algorithm will be extremely long for multiple reason :
    - random mutation change sequence leight.
    - random mutation have a great probability to make a very bad individu.
    - cross over is hard to write
    - A small change on the entry give a very high change of the cost function.
    - Angle are discrete so optimisation is combinatorial AND localy discrete (Haaaard to optimise !)

    The simpler and perfect way :

    for each motor (joint) create a vector, each element at index i of the vector is the value of the motor at time i. Optimise this set of vector as the term of a matrice.
    T1 T2 T3 T4
    Motor 1 : 0.22 0.44 1.02 0.002
    Motor 2 : 0.04 0.00 2.0 8.59
    Motor 3 : 3.25 4.5 4.8 20.1

    with this solution mutating a solution is just adding random value to an élément. Crossing over is selecting a part of the matrix and remplace from another : Easy !
     
  4. May 12, 2015 #3
    Thanks kroni! Was hoping you'd reply. We had this other idea to help it get to the solution faster,
    assume we have population of 5 (i know its small its hypothetical). then we take top percentile, so 2
    now we look for "patterns" in them, to try find what makes them good.
    ie in strings
    abcdabcdabcd
    abbabdbabda
    the pattern would be:
    ab,ab,da,bd

    Second question, that matrix form means that the order which the motors are activated would be the same every time, can you think of a way that we could avoid that and still get to a solution?
     
  5. May 13, 2015 #4
    No no no ! Why there is an order to activate motors ?
    In my solution, motor are all activated at the SAME TIME for each collumn of the matrix.
    do you understand it ?
     
  6. May 14, 2015 #5
    Oh, I see now, initially i thought t represented the generation at time t, but why would that make a difference?
     
  7. May 14, 2015 #6
    Because in your solution motor order is important so this add a lot of combinaison for équivalent solution, this is more complex for the Genetic Algorithm to converge. In the matrix representation of the parameter to optimize, you don't have this order, you have only continuous value in each case, so a small variation of the parameter make a small variation of the score. In you parameterization, small variation of the parametre (A to D, or permutation) imply a great variation of the score. Genetic algorithm will have great difficulty to converge.
     
  8. May 14, 2015 #7
    I think you need to try the both.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook