遗传算法

遗传算法

遗传算法（Genetic Algorithm）

一个讲得很清楚的博客：非常好理解的遗传算法的例子

简单理解：

用计算机模拟人类进化，适应环境（符合条件）的继续繁衍后代，不适应环境（不符合条件）的淘汰，从而逐步找到最优解。

整体思路：

随机挑选初始种群，根据适应度函数给初始种群中的个体“打分”，通过定义的规则进行选择，将选择出来的个体两两配对进行交叉，并在生成的对象中挑选变异点，将0变1，1变0，生成后代种群，如此循环找到最优个体即为最优解。

初始种群是啥：

利用二进制（一般）表示最终解

例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}

用六位二进制数表示由x，y组成的解，例如：001100 表示x=1，y=4

001100 称为一条基因序列，表示的是该问题的一种解决方案

种群是包含多个基因序列（解决方案/个体）的集合

适应度函数是啥，有什么作用：

适应度函数可以理解成“游戏规则”，如果问题较为复杂，需要自定义适应度函数，说明如何区分优秀与不优秀的个体; 如果问题比较简单，例如上述求最大值的问题，则直接用此函数式作为适应度函数即可。作用：评定个体的优劣程度，从而决定其遗传机会的大小。

怎么选择：

定义“适者生存不适者淘汰”的规则，例如：定义适应度高的被选择的概率更大

怎么交叉：

利用循环，遍历种群中的每个个体，挑选另一个体进行交叉。例如，通过遍历为基因序列A挑选出B配对，则取A的前半部分，B的后半部分，组合成新的个体（基因序列）C

如何变异：

随机挑选基因序列上的某一位置，进行0-1互换

Python实现

在此附上莫烦的python实现代码（解决在多峰曲线函数中寻找最大值的问题，如图所示）：

莫烦关于此部分的详细讲解视频/代码：遗传算法 莫烦源码

import numpy as np import matplotlib.pyplot as plt DNA_SIZE = 10 #序列长度 POP_SIZE = 100 #种群的个体数目 CROSS_RATE = 0.8 #选择多少个体进行交叉配对 MUTATION_RATE = 0.003 #变异的概率/强度 N_GENERATI 100 #有多少代（主循环的迭代次数） X_BOUND = [0,5] #输入数据的范围 #需要要找到哪个函数的最大值 def F(x): return np.sin(10*x)*x + np.cos(2*x)*x #返回y值（此例中为高度） #用0-1按照定义的规模表示一代种群 pop = np.random.randint(1, size=(POP_SIZE, DNA_SIZE)) #默认从0开始，随机（提供选择的数值个数，重复次数（纵向，横向）） #print(pop) #适应度函数(在本例中直接使用F函数就好，但是要处理返回值为负数的情况) def get_fitness(pred): return pred + 1e-3 - np.min(pred) #DNA的翻译规则 def translateDNA(pop): #把二进制翻译成十进制,并将其归一化至一个范围（0,5） return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE-1) * X_BOUND[1] #适者生存不适者淘汰 #idx:种群中个体的编号 #p参数定义：按什么规格来选择（此例中按照比例来选择，适应度得分高的p越大） def select(pop,fitness_score): idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=fitness_score/fitness_score.sum()) return pop[idx] #繁衍 #父母的DNA交叉配对(定义到底怎么个交叉法) def crosscover(parent,pop): if np.random.rand() < CROSS_RATE: i_ = np.random.randint(0,POP_SIZE,size = 1) cross_points = np.random.randint(0,2,size = DNA_SIZE).astype(np.bool) parent[cross_points] = pop[i_,cross_points] return parent #变异（定义如何随机挑选0-1互换的位置） def mutate(child): for point in range(DNA_SIZE): if np.random.rand() < MUTATION_RATE: child[point] = 1 if child[point] == 0 else 0 return child #画图 #plt.ion() # something about plotting #x = np.linspace(*X_BOUND, 200) #plt.plot(x, F(x)) for _ in range(N_GENERATIONS): F_values = F(translateDNA(pop)) print(translateDNA(pop)) #print(F_values) #计算适应度得分，适应度越高的越好（本例中，适应度就用y轴-高度，也就是F_value体现） fitness_score = get_fitness(F_values) #print("Most fitted DNA: ", pop[np.argmax(fitness_score), :]) #进行适者生存的选择（把种群和得分传入) pop = select(pop,fitness_score) #print(pop) pop_copy = pop.copy() #对于种群中所有个体，在种群中挑选另一个体进行配对: for parent in pop: child = crosscover(parent,pop_copy) child = mutate(child) parent[:] = child #plt.ioff();plt.show()

---

微生物遗传算法（Microbial GA）

为“升级版GA”，由Inman Harvey于2009年提出，原文:《The Microbial Genetic Algorithm》

解决了什么问题：

主要解决遗传算法中，无法有效保留“好父母”的问题(Elitism)：分析GA可是无论父母多么优秀，都不会被保留，只能将各自基因的一部分进行重组，但是重组后的子代并不会一定优于父母。

改进做法：

1.把种群中表现好的基因不做任何改变放入子代中

2.只对表现较差的基因序列进行交叉/变异处理

3.交叉方法：表现较差的在表现较好的基因序列中抽取一部分替换进来

4.变异方法：只在表现较差的基因序列中挑选变异点

注：表现好坏由fitness的得分决定

具体做法：

1.生成初始种群

2.在初始种群中随机抽取两个基因序列A/B，对比fitness（假定A的fitness值高）

3.从A中截取部分基因序列替换掉B中对应位置

4.随机在B中抽取位置，进行变异

5.将A与处理后的B‘放回种群中

6.自定义每一代进行多少次抽取/放回操作

Python实现

对于前文提到的在多峰曲线函数中寻找最大值的问题，此处使用MGA解决：

来源：莫烦源码

import numpy as np import matplotlib.pyplot as plt DNA_SIZE = 10 # DNA length POP_SIZE = 20 # population size CROSS_RATE = 0.6 # mating probability (DNA crossover) MUTATION_RATE = 0.01 # mutation probability N_GENERATI 200 X_BOUND = [0, 5] # x upper and lower bounds def F(x): return np.sin(10*x)*x + np.cos(2*x)*x # to find the maximum of this function class MGA(object): def __init__(self, DNA_size, DNA_bound, cross_rate, mutation_rate, pop_size): self.DNA_size = DNA_size DNA_bound[1] += 1 self.DNA_bound = DNA_bound self.cross_rate = cross_rate self.mutate_rate = mutation_rate self.pop_size = pop_size # initial DNAs for winner and loser self.pop = np.random.randint(*DNA_bound, size=(1, self.DNA_size)).repeat(pop_size, axis=0) def translateDNA(self, pop): # convert binary DNA to decimal and normalize it to a range(0, 5) return pop.dot(2 ** np.arange(self.DNA_size)[::-1]) / float(2 ** self.DNA_size - 1) * X_BOUND[1] def get_fitness(self, product): return product # it is OK to use product value as fitness in here def crossover(self, loser_winner): # crossover for loser cross_idx = np.empty((self.DNA_size,)).astype(np.bool) for i in range(self.DNA_size): cross_idx[i] = True if np.random.rand() < self.cross_rate else False # crossover index loser_winner[0, cross_idx] = loser_winner[1, cross_idx] # assign winners genes to loser return loser_winner def mutate(self, loser_winner): # mutation for loser mutation_idx = np.empty((self.DNA_size,)).astype(np.bool) for i in range(self.DNA_size): mutation_idx[i] = True if np.random.rand() < self.mutate_rate else False # mutation index # flip values in mutation points loser_winner[0, mutation_idx] = ~loser_winner[0, mutation_idx].astype(np.bool) return loser_winner def evolve(self, n): # nature selection wrt pop's fitness for _ in range(n): # random pick and compare n times sub_pop_idx = np.random.choice(np.arange(0, self.pop_size), size=2, replace=False) sub_pop = self.pop[sub_pop_idx] # pick 2 from pop product = F(self.translateDNA(sub_pop)) fitness = self.get_fitness(product) loser_winner_idx = np.argsort(fitness) loser_winner = sub_pop[loser_winner_idx] # the first is loser and second is winner loser_winner = self.crossover(loser_winner) loser_winner = self.mutate(loser_winner) self.pop[sub_pop_idx] = loser_winner DNA_prod = self.translateDNA(self.pop) pred = F(DNA_prod) return DNA_prod, pred plt.ion() # something about plotting x = np.linspace(*X_BOUND, 200) plt.plot(x, F(x)) ga = MGA(DNA_size=DNA_SIZE, DNA_bound=[0, 1], cross_rate=CROSS_RATE, mutation_rate=MUTATION_RATE, pop_size=POP_SIZE) for _ in range(N_GENERATIONS): # 100 generations DNA_prod, pred = ga.evolve(5) # natural selection, crossover and mutation # something about plotting if 'sca' in globals(): sca.remove() sca = plt.scatter(DNA_prod, pred, s=200, lw=0, c='red', alpha=0.5); plt.pause(0.05) plt.ioff();plt.show()