遗传算法示例

时间:2022-03-22 11:09:28

今晚简单研究下遗传算法,学习的是一个求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)