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.

## No comments:

## Post a Comment