## Friday, 27 February 2015

### Review 1.4: Give your program the ability to evolve

Give your program the ability to evolve.

After studied program tree, mutation and crossover(summarized in study notes 1,2,3), all things needed to let a program to evolve by itself is ready. The raw logic is, generate a random set of population, then rank them with a given ranking function and select some elites to breed the next generation. Repeat these steps until one or a set of people(program) which satisfies a given condition.

Here is a sample code to evolve a program:

```
def evolve(paramCount:Int,popSize:Int=500,genSize:Int=500,probMut:Double=0.1,probCross:Double=0.6,probNew:Double=0.2,probExp:Double=0.7) = {
val ancestors = (for( i ← 0 until popSize ) yield makeRandomTree(2)).toList
val last = breed(ancestors,paramCount,popSize,genSize,probNew,probExp)
last.displayTree()
last
}

def breed(ancestors:List[N],paramCount:Int,popSize:Int,genSize:Int,probNew:Double,probExp:Double):N = {
var population = ancestors
for( i ← 0 until genSize ) {
val rankedPrograms = rankPrograms(population)

//Display the score of this generation, the first people is the best one
println(rankedPrograms(0)._2)

//We get the program we want when the score become 0
if( rankedPrograms(0)._2 == 0 )
return rankedPrograms(0)._1

population = breedOneGeneration(rankedPrograms,paramCount,popSize,probNew,probExp)
}
return population(0)
}

def breedOneGeneration(rankedPrograms:List[(N,Int)],paramCount:Int,popSize:Int,probNew:Double,probExp:Double) = {
//Always reserve the top 2 best programs
var newgen = List(rankedPrograms(0)._1,rankedPrograms(1)._1)
while (newgen.length < popSize ) {
if (seed.nextDouble > probNew) {
val eliteFather = rankedPrograms(eliteIndex(probExp))._1
val eliteMother = rankedPrograms(eliteIndex(probExp))._1
val child = mutate(crossover(eliteFather,eliteMother),paramCount)
newgen = newgen:::List(child)
}
else { //We need aliens to make the group of people to be diversity. This can avoid local maxima problem
newgen = newgen:::List(makeRandomTree(paramCount))
}
}
newgen
}
```

In function breedOneGeneration, there are two condition. The first condition means the probility that a member of the new generation will breeded from the old generation. The other condition means the problitiy that a member generated randomly. The reason why we need the second condition is that if all generated from the older generation, new memembers tend to be extremely homogeneous. It will lead a problem call local maxima, a state that is good but not quite good enough. So we need to maintain diversity in each generation.

The function eliteIndex will select a random but pretty good solution from ranked programs. We can use Math.log to achieve this. e.g. (Int)(Math.log(randomDouble) / Math.log(probExp)). If we set probExp to be 0.7 and the population size to be 500. Then the probility of getting a small number is relatively larger than the probility of getting a big number. It is easy to understand when you think about the logarithms curve below.