• About
  • Gallery of Images
  • Archives
  • Categories
  •   Evolutionary Algorithms and Unity3d – part 2

    31/07/12 - 20:01

    The planet Kryack is populated by a race of super powerful bright green hermaphrodite ant people. Every Kryackian has four attributes – strength, speed, intelligence and health. The Kryackian people have an uneasy truce with giant gerbil people on a nearby planet – war is on the cards and the Kryackian people want to make sure they have the most powerful warriors to fight, so they recruit you, the humble coder, to find the best way of doing this.

    Let’s create a model of a Kryackian, four attributes, suggests a simple data structure :

    Strength : 5
    Speed : 5
    Intelligence : 5
    Health : 5

    Which I will represent like this :

    |5|5|5|5|

    For simplicities sake, all attributes range from 1 – 10. To find which warrior is the most powerful – you simply add up all their attributes ( like I said, a silly problem but should be nice and easy to follow ). As mentioned very briefly earlier, with an evolutionary algorithm, you create a random selection of solutions ( in this case, you create four bright green giant ant people ) and breed the best solutions together. So the first step is to create a random population :

    |1|5|3|9|
    |1|1|1|4|
    |7|4|9|7|
    |4|4|3|1|

    Now we have our population, lets rank them to see who are the most powerful warriors :

    |1|5|3|9| = 18
    |1|1|1|4| = 7
    |7|4|9|7| = 27
    |4|4|3|1| = 12

    As you can see, the first and third warriors are the most mighty, therefore, let us give them some privacy so they can work on making a new population. The two weaker warriors will die of old age during this process. Hmmm, but without seeing what happens next, this long winded example will be confusing, so let us have a look at how baby Kryachians are made.
    We have two strings of attributes :

    A: |1|5|3|9|
    B: |7|4|9|7|

    The baby Kryachians will be made by combining these attributes, by randomly selecting one from each parent. We are not assessing which choice should be made; we are simply flipping a biological coin and picking either A or B to make the new generation.

    This ( for example ) will give us the following new generation :

    |1|4|3|9| = 17 ( Coin : ABAB )
    |7|5|3|7| = 22 ( Coin : BAAB )
    |7|5|9|9| = 30 ( Coin : BABA )
    |1|4|9|7| = 21 ( Coin : ABBA )

    Wow! With only one generation, we have improved the average Kryachian from an average set of attributes of 16 to an average of 22.5. Once again, let us select the strongest, and give them some privacy :

    A: |7|5|9|9|
    B: |7|5|3|7|

    Children in generation 3 :

    |7|5|9|9| = 30
    |7|5|3|9| = 24
    |7|5|9|9| = 30
    |7|5|9|7 | = 28

    Wow! Once again, we have improved the average attribute of the generation to a total of 28. But, I’m sure you can see the next problem – no matter how we breed the two strongest warriors together, all the children will have the same attributes – |7|5|9|9| – a better solution than the random population, but how will they compete against the giant gerbil peoples |9|9|9|9| ? Are the Kryachian people doomed to have a stagnant gene pool?

    Lucky for us, the primary star of the planet Kryack is a giant unstable red thing that throws out intense amounts of cosmic energy randomly – causing strange mutations within the Kryachian people.
    How does this work with our model? Simply put, that there is a 1% chance then when flipping the coin to pick A or B, it lands on its side and you make up a completely new number :

    A: |7|5|9|9|
    B: |7|5|9|9|

    Children ( mutation occurs on the second attribute on the first child ) :

    |7|2|9|9| = 27
    |7|5|9|9| = 30
    |7|5|9|9| = 30
    |7|5|9|9| = 30

    Oh noes! Instead of helping, the mutation has actually made things worse! But not to fear O intergalactic ant breeder – when you breed the highest ones together, this weakness is bred out. Alas, the universe is a cruel mistress indeed.

    But look, with the new generation, a new mutation has occurred ( in the second child first attribute ) :

    |7|5|9|9| = 30
    |10|5|9|9| = 33
    |7|5|9|9| = 30
    |7|5|9|9| = 30

    We have a new genetic super ant! That 10 is now present, and when bred together, we will end up with something like this :

    |10|5|9|9| = 33
    |10|5|9|9| = 33
    |7|5|9|9| = 30
    |7|5|9|9| = 30

    Once again, we will have a reached a genetic dead end. But that is ok, we just have to keep them breeding and at some point the giant red star will cause additional mutations, slowly but surely turning the Kryachian people into the strongest giant green ants in the universe.

    Example over – as you can no doubt tell, generally when dealing with evolutionary algorithms, you have hundreds or thousands of children to deal with, with a lot more attributes than these. Also, ranking tends to be more complicated than just adding them all together. Evolutionary algorithms are not by any stretch of the imagination ‘fast’ – it can take thousands maybe even millions of evolutions in order to find the optimal solution. But it is a very interesting way of finding a solution :)


     

    lamentconfig  
    Share

    Your Reply