首页
学习
活动
专区
工具
TVP
发布

机器学习·遗传算法

随着学习的拓展,发现机器学习分支众多,除了当前热门的深度学习之外,还有强化学习(Q_learning)和前几天遇到的遗传算法。

通过这一年对机器学习的接触,不得不对计算机算法与数学工程师产生由衷的佩服。

这些天才的工程师竟然能用数学模型(一系列的公式)来模拟生物的工作机理,这真是太神奇了。

深度学习中的cnn(卷积神经网络)是受到大脑视觉神经的启发而发明的。

强化学习灵感来源于心理学中的行为主义理论。

遗传算法则借鉴了达尔文的进化论和孟德尔的遗传学说,借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。

遗传算法已广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

遗传算法包括突变(mutation)、选择(selection)以及杂交(crossover)等过程。基本运算过程如下:

a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。

b)个体评价:计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。

应用实例:

用遗传算法求解既定区间函数y=f(x)最大值:

思路:

可以随机产生众多个群体(population)X,——即100的0-5之间的数,把200个数(X)代入f(x)中,得到100个y;

y的值就是x的适应度。通过“适者生存, 不适者淘汰”的原则,留下y值的的x,淘汰y值小的x。

将留下的x个体的基因进行杂交,产生新的X,其中部分X产生变异,再计算对应的y值。

经过若干次的迭代,产生最优解:即y值最大的x是什么。

算法首先借用生物学中的DNA这一概念:DNA决定了生物的特点,本例中,DNA就是X。

DNA有多种表示方法,本例使用最简单的方法:二进制。即用十位二进制数表示0~5之间的数:

产生十位二进制数

把十位二进制数转化是0~5之间的实数:

def translate_dna(pop):

return pop.dot(2**np.arange(10)[::-1])/float(2**10-1)*5

y=f(x)函数:

def F(x):

return np.sin(10*x)*x+np.tanh(2*x)*x

该函数的图像如上图。

计算出每个个体的适应度,本例是适应就是与解的符合度,也就是y值,y值越大,符合度越高,适应度越大。

def get_fitness(y):

return y+1e-3-np.min(y)

注:y+1e-3-np.min(y) 中,减去np.min(y)是确保适应度为非负数,加1e-3是避免适应度为0.

选择操作是建立在群体中个体的适应度评估基础上的,目前常用的选择算子有:适应度比例方法、随机遍历抽样法、局部选择法。其中轮盘赌选择法 是最简单也是最常用的选择方法。在该方法中,各个个体的选择概率和其适应度值成比例。个体适应度越大。其被选择的概率就越高、反之亦然。

借用某网帖上的例子:

比如有5个个体,他们所对应的适应度评分分别为:5,7,10,13,15。累计总适应度为:

各个个体被选中的概率分别为:

从100个个体中选择适应度高的个体,淘汰低的个体:

def select(pop,fitness):

return pop[idx]

经过选择后,个体总数仍是100个,都是适应度高的个体,个体有重复出现。下面是选择后的100个个体号。

[57 72 55 15 97 57 38 72 69 45 68 95 21 93 95 37 13 72 58 40 80 67 97 62 25 78 87 93 9 94 42 63 94 74 9 28 98 64 6 9 99 42 99 67 62 1 80 84 24 39 54 54 1 1 20 13 47 97 12 68 82 4 37 62 46 87 62 81 21 33 84 38 87 14 26 11 46 52 71 80 11 40 87 54 40 43 50 30 84 32 29 12 15 90 74 38 27 56 91 54]

个体被选后,可随机地组成交配对,以供后面的交叉操作。

在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样,遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉,遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因,能够产生新的基因组合,期望将有益基因组合在一起。

def cross_over(parent,pop):

parent[cross_point]=pop[i_,cross_point]

return parent

本代码中,parent是群体中的某个个体,作为父本,i_是另一个个体,作为母本。父母交叉产生新的个体parent

#old_parent: [011110]

#pop[i_] : [1111]

#cross_points[TTTFF FTFFF]

#new_parent:[11110 10]

基因突变:基因突变是DNA的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因,并且通常会引起一定的表现型(X值的)变化。正如上面所说,二进制编码的遗传操作过程和生物学中的过程非常相类似,基因串上的“ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码:

pop1=[1,1,1,0,1,0,0,0,1,1] (转化为x后是4.55)

经过基因突变后,可能变成以下这串新的编码:

pop2=[1,0,1,0,1,0,0,0,1,1](转化为x后是3.299)

def mutate(child):

for point in range(10):

if child[point]==0:

child[point]=1

else:

child[point]=0

return child

下面是200代进化的过程:

for _ in range(200):

X=translate_dna(pop)

Y=F(X)

fitness=get_fitness(Y)#计算适应度

pop=select(pop,fitness)#根据适应度选择产生新的100个群体

pop_copy=pop.copy()

for parent in pop:#群体中两两交叉,按一个微小比例变异

child=cross_over(parent,pop_copy)

child=mutate(child)

parent=child

把最优DNA转化为x,计算出y值:

best=pop[np.argmax(fitness),:]

print("\n best x is",translate_dna(best))

print("\n it's y value is",F(translate_dna(best)))

完整代码:

import numpy as np

import matplotlib.pyplot as plt

def translate_dna(pop):

return pop.dot(2**np.arange(10)[::-1])/float(2**10-1)*5

def get_fitness(y):

return y+1e-3-np.min(y)

def cross_over(parent,pop):

parent[cross_point]=pop[i_,cross_point]

return parent

def select(pop,fitness):

print(idx)

return pop[idx]

def mutate(child):

for point in range(10):

if child[point]==0:

child[point]=1

else:

child[point]=0

return child

def F(x):

return np.sin(10*x)*x+np.tanh(2*x)*x

#画出函数图像

x=np.linspace(0,5,200)

y=F(x)

plt.ion()

plt.plot(x,y)

#200次进化

for _ in range(200):

X=translate_dna(pop)

Y=F(X)

#画图动态效果

if 'sca' in globals():sca.remove()

sca=plt.scatter(X,Y,s=100, c='red', alpha=0.5)

plt.pause(0.05)

fitness=get_fitness(Y)

best=pop[np.argmax(fitness),:]

print("\nmost good x is",translate_dna(best))

print("\nit's y value is",F(translate_dna(best)))

pop=select(pop,fitness)

pop_copy=pop.copy()

for parent in pop:

child=cross_over(parent,pop_copy)

child=mutate(child)

parent=child

plt.ioff()

plt.show()

计算结果:(图中红点为最化值)

感谢莫烦python遗传算法讲解

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190129G0TBK400?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券