遗传算法与优化问题
实验十遗传算法与优化问题
一、问题背景与实验目的
遗传算法(Genetic Algorithm—GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型,它就是由美国Michigan大学的J、Holland教授于1975年首先提出的.遗传算法作为一种新的全局优化搜索算法,以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点,奠定了它作为21世纪关键智能计算之一的地位.
本实验将首先介绍一下遗传算法的基本理论,然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算.
1.遗传算法的基本原理
遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程.它把问题的参数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生存竞争,适者有最好的机会生存与产生后代.后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解.值得注意的一点就是,现在的遗传算法就是受生物进化论学说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议).
(1)遗传算法中的生物遗传学概念
由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法;故而在这个算法中要用到各种进化与遗传学的概念.
首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系.
遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程,主要有三个基本操作(或称为算子):选择(Selection)、交叉(Crossover)、变异(Mutation).
遗传算法基本步骤主要就是:先把问题的解表示成“染色体”,在算法中也就就是以二进制编码的串,在执行遗传算法之前,给出一群“染色体”,也就就是假设的可行解.然后,把这些假设的可行解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉、变异过程产生更适应环境的新一代“染色体”群.经过这样的一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就就是问题的最优解.
下面给出遗传算法的具体步骤,流程图参见图1:
第一步:选择编码策略,把参数集合(可行解集合)转换染色体结构空间;
第二步:定义适应函数,便于计算适应值;
第三步:确定遗传策略,包括选择群体大小,选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数;
第四步:随机产生初始化群体;
第五步:计算群体中的个体或染色体解码后的适应值;
第六步:按照遗传策略,运用选择、交叉与变异算子作用于群体,形成下一代群体;
第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步.
图1
一个遗传算法的具体步骤
遗传算法有很多种具体的不同实现过程,以上介绍的就是标准遗传算法的主
要步骤,此算法会一直运行直到找到满足条件的最优解为止.
2.遗传算法的实际应用
例1:设2()20.5f x x x =-++,求 max (), [1,2]f x x ∈-.
注:这就是一个非常简单的二次函数求极值的问题,相信大家都会做.在此我们要研究的不就是问题本身,而就是借此来说明如何通过遗传算法分析与解决问题.
在此将细化地给出遗传算法的整个过程.
(1)编码与产生初始群体
首先第一步要确定编码的策略,也就就是说如何把1-到2这个区间内的数用计算机语言表示出来.
编码就就是表现型到基因型的映射,编码时要注意以下三个原则:
完备性:问题空间中所有点(潜在解)都能成为GA 编码空间中的点(染色体位串)的表现型;
健全性:GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解; 非冗余性:染色体与潜在解必须一一对应.
这里我们通过采用二进制的形式来解决编码问题,将某个变量值代表的个体表示为一个{0,1}二进制串.当然,串长取决于求解的精度.如果要设定求解精度到六位小数,由于区间长度为2(1)3--=,则必须将闭区间 [1,2]-分为6310?等分.因为216222097152231024194304=
将一个二进制串(b 21b 20b 19…b 1b 0)转化为区间[1,2]-内对应的实数值很简单,只需采取以下两步(Matlab 程序参见附录4):
1)将一个二进制串(b 21b 20b 19…b 1b 0)代表的二进制数化为10进制数:
21
212019102100()(2)'i i i b b b b b b x =?=?=∑
2)'x 对应的区间[1,2]-内的实数:
12)
1(2'122---?
+-=x x 例如,一个二进制串a=<10101000111>表示实数0、637197.
'x =(10101000111)2=2288967
637197.01232288967122=-?+-=x 二进制串<>,<1111111111111111111111>,则分别表示区间的两个端点值-1与2.
利用这种方法我们就完成了遗传算法的第一步——编码,这种二进制编码的方法完全符合上述的编码的三个原则.
首先我们来随机的产生一个个体数为4个的初始群体如下:
pop(1)={
<11100011110>, %% a1
<10001000010>, %% a2
<10110000000>, %% a3
<>} %% a4(Matlab 程序参见附录2)
化成十进制的数分别为:
pop(1)={ 1、523032,0、574022 ,-0、697235 ,0、247238 }
接下来我们就要解决每个染色体个体的适应值问题了.
(2)定义适应函数与适应值