from random import random , randint from operator import add import random import string #We would like to solve the problem of path : Genetic_Programming.txt #5 5 #0 0 0 0 0 #0 0 0 0 0 #0 0 0 0 0 #0 0 0 0 0 #0 0 0 0 0 #4 2 1 4 Right #0 0 #The solution is: 3 A2 L A3 actions = ['R' , 'L' , 'U' , 'D' , 'A1' , 'A2' , 'A3' ] target = ['A2' ,'L' , 'A3'] #print actions def individual(length,listofactions): 'Create a member of the population.' return [ random.choice(listofactions) for x in xrange(length) ] #print individual(3,actions) def population(count, length, listofactions): pop = [] for x in xrange(count) : indi=individual(length,listofactions) indi[len(indi):]=[0] pop.append(indi) return pop #print population(7,3,actions) def fitness(individual,target): #The elements to consider: #Distance to manhattan to the goal -> add distance #Number of different element between individual and target #Obstacles Not now #out of matrix ->100 #No mouvement ->50 StartPointX = 4 StartPointY = 2 EndPointX = 1 EndPointY = 4 Direction ='R' ActualPointX = 4 ActualPointY = 2 if len(individual) < 4: individual[len(individual):]=[0] if individual[len(individual)-1] == 0: for x in individual: if x is 'L' or x is 'U' or x is 'D' or x is 'R': if Direction is 'R': if x is 'R': Direction = 'D' if x is 'L': Direction = 'U' if x is 'U': Direction = 'U' if x is 'D': Direction = 'D' elif Direction is 'D': if x is 'R': Direction = 'L' if x is 'L': Direction = 'R' if x is 'D': Direction = 'D' if x is 'U': Direction = 'U' elif Direction is 'U': if x is 'R': Direction = 'R' if x is 'L': Direction = 'L' if x is 'U': Direction = 'U' if x is 'D': Direction = 'D' else : if x is 'R': Direction = 'U' if x is 'L': Direction = 'D' if x is 'U': Direction = 'U' if x is 'D': Direction = 'D' if x is 'A1': if Direction is 'R': ActualPointY = ActualPointY + 1 if Direction is 'U': ActualPointX = ActualPointX + 1 if Direction is 'D': ActualPointX = ActualPointX -1 if Direction is 'L': ActualPointY = ActualPointY -1 if x is 'A2': if Direction is 'R': ActualPointY = ActualPointY+2 if Direction is 'U': ActualPointX = ActualPointX+2 if Direction is 'D': ActualPointX = ActualPointX-2 if Direction is 'L': ActualPointY = ActualPointY-2 if x is 'A3': if Direction is 'R': ActualPointY = ActualPointY+3 if Direction is 'U': ActualPointX = ActualPointX-3 if Direction is 'D': ActualPointX = ActualPointX+3 if Direction is 'L': ActualPointY = ActualPointY-3 #Now we have the actual coordonate after the path we will give fitness #Out of index if ActualPointX < 0 or ActualPointX > 4 or ActualPointY < 0 or ActualPointY > 4 : individual[len(individual)-1] = individual[len(individual)-1]+100 #Distance to Manhattan DifferenceX = abs(EndPointX - ActualPointX) DifferenceY = abs(EndPointY - ActualPointY) fitnes = DifferenceX + DifferenceY individual[len(individual)-1] = individual[len(individual)-1]+fitnes action = 0 for i in [0 , 1 , 2] : if individual[i] is not target[i] : individual[len(individual)-1] = individual[len(individual)-1]+10 for x in individual : if x is 'A1' or x is 'A2' or x is 'A3': action = 1 if action == 0 : individual[len(individual)-1] = individual[len(individual)-1] + 50 return individual ##x = ['A2' ,'L' , 'A3'] ##indi = fitness(x,target) ##print indi def grade(population, target): summed = 0 #'Find average fitness for a population.' #summed = reduce(add, fitness(population) for x in population), 0) #return summed / (len(population) * 1.0) for x in population : y=fitness(x,target) summed = summed + y[len(y)-1] return summed / (len(population) * 1.0) def evolve(population, target, liste , retain=0.2, random_select=0.05, mutate=0.01): graded = [ fitness(x , target) for x in population] graded = sorted(graded, key=lambda x: x[3]) retain_length = int(len(graded)*retain) parents = graded[:retain_length] # randomly add other individuals to promote genetic diversity for individual in graded[retain_length:]: if random_select > random.random(): parents.append(individual) # mutate some individuals for individual in parents: if mutate > random.random(): pos_to_mutate = randint(0,2) # this mutation is not ideal, because it # restricts the range of possible values, # but the function is unaware of the min/max # values used to create the individuals, x = random.choice(liste) individual[pos_to_mutate] = x individual[3] = 0 individual= fitness ( individual, target) # crossover parents to create children parents_length = len(parents) desired_length = len(population) - parents_length children = [] while len(children) < desired_length: male = randint(0, parents_length-2) female = randint(0, parents_length-2) if male != female: male = parents[male] female = parents[female] child = male[:1] + female[1:3] children.append(child) parents.extend(children) return parents def Output(nom,type,population): f=open(nom,type) for x in population: f.write(str(x)+'\n') f.close() #test p_count = 100 length = 3 p = population(p_count ,length , actions) Output("FirstPopulation","w",p) fitness_history = [grade(p, target),] parents = evolve(p, target, actions) Output("Evolve 0","w",parents) for i in xrange(10): p = evolve(p, target, actions) fitness_history.append(grade(p, target)) Output("Evolve with fitness "+str(grade(p, target))+"and i "+ str(i),"w",p) for datum in fitness_history: print datum