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.

No comments:

Post a Comment