今晚简单研究下遗传算法,学习的是一个求N个数,使之加起来恰好为X的例子,比较简明易懂,python实现起来也很方便。
几个基础的概念:
个体individual,它有自己的生存力,也就是适应力,强弱就是与我们的目标的差距
种群population,个体的集合,生存力不同,有强有弱
适应力fitness,针对个体而言,越小越好,看它与目标的差距
评分grade,针对种群而言,同样越小越好,定义了所有个体与目标差距的平均值
进化evolve,核心部分,生物的物竞天择适者生存过程,不断淘汰种群中的弱者,留下强者,并从强者中选择2个作为父母繁衍后代,后代有父母的基因,同时产生的过程中有概率发生变异,也可以选择让父母产生变异,从结果上看效果是一样的。
下面的例子中,设定目标值371,种群中个体数100,每个个体由6个数组成,在0到100之间,每次进化留下的优良个体比例20%,不良个体被留下的概率为5%(这个可以不要,留下会表现有遗传的多样性),留下的个体中,变异概率1%。进化前会对种群中个体的适应力排序,选择一定比例的留下,然后让其中的每个按概率发生变异,结果作为父母,繁衍后代,直到个体总量达到规定值。这里,我们预先知道我们的目标值,因此发现有个体完全适应时就可以停止进化了,而有些问题并不能准确知道这个值,因此可以将结果不断的保留,最后取一个最值作为我们的结果,得到原问题的近似最优解。
1 # -*- coding:gbk -*- 2 import random, operator 3 4 def individual(length, min, max): 5 return [random.randint(min, max) for x in xrange(length)] 6 7 def population(count, length, min, max): 8 return [individual(length, min, max) for x in xrange(count)] 9 10 def fitness(individual, target): 11 sum = reduce(operator.add, individual, 0) 12 return abs(target - sum) 13 14 def grade(pop, target): 15 summed = reduce(operator.add, (fitness(x, target) for x in pop)) 16 return summed / (len(pop) * 1.0) 17 18 def evolve(pop, target, retain = 0.2, random_select = 0.05, mutate = 0.01): 19 graded = [(fitness(x, target), x) for x in pop] 20 graded = [x[1] for x in sorted(graded)] 21 retain_length = int(len(graded) * retain) 22 parents = graded[:retain_length] 23 for individual in graded[retain_length:]: 24 if random_select > random.random(): 25 parents.append(individual) 26 27 for individual in parents: 28 if mutate > random.random(): 29 pos_to_mutate = random.randint(0, len(individual) - 1) 30 individual[pos_to_mutate] = random.randint(min(individual), max(individual)) 31 parents_length = len(parents) 32 desired_length = len(pop) - parents_length 33 children = [] 34 while len(children) < desired_length: 35 male = random.randint(0, parents_length - 1) 36 female = random.randint(0, parents_length - 1) 37 if male != female: 38 male = parents[male] 39 female = parents[female] 40 half = len(male) / 2 41 child = male[:half] + female[half:] 42 children.append(child) 43 parents.extend(children) 44 return parents 45 46 47 target = 371 48 p_count = 100 49 i_length = 6 50 i_min = 0 51 i_max = 100 52 53 p = population(p_count, i_length, i_min, i_max) 54 fitness_history = [grade(p, target),] 55 for i in xrange(200): 56 p = evolve(p, target) 57 g = grade(p, target) 58 fitness_history.append(g) 59 if g == 0: 60 break 61 62 for datum in fitness_history: 63 print datum 64 65 individual = p[len(p) - 1] 66 print 'individual is' 67 sum = 0 68 for n in individual: 69 sum += n 70 print n 71 print 'total=%d,target=%d,evolve=%d'%(len(fitness_history), target, sum)