今晚简单研究下遗传算法，学习的是一个求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_length33     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) / 241             child = male[:half] + female[half:]42             children.append(child)43     parents.extend(children)44     return parents45 46 47 target = 37148 p_count = 10049 i_length = 650 i_min = 051 i_max = 10052 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         break61 62 for datum in fitness_history:63     print datum64     65 individual = p[len(p) - 1]66 print 'individual is'67 sum  = 068 for n in individual:69     sum += n70     print n71 print 'total=%d,target=%d,evolve=%d'%(len(fitness_history), target, sum)