1、实验十遗传算法与优化问题数学实验问题背景和实验目的问题背景和实验目的遗传算法（遗传算法（Genetic Algorithm，简称，简称 GA），），是模是模拟达尔文的遗传选择和自然淘汰的生物进化过程的拟达尔文的遗传选择和自然淘汰的生物进化过程的计计算机算法，它由美国算机算法，它由美国 Holland 教授教授1975年提出。年提出。遗传算法作为一种新的全局优化搜索算法，以其遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为等显著特点，奠定了它作为21世纪关键智能计算之世纪关键智能计算之一的地
2、位。一的地位。本实验主要介绍遗传算法的基本理论，然后通过本实验主要介绍遗传算法的基本理论，然后通过求解几个简单的函数最值问题，来说明如何利用遗求解几个简单的函数最值问题，来说明如何利用遗传算法进行初步的优化计算传算法进行初步的优化计算。遗传算法基本原理遗传算法基本原理基本思想：基本思想：基于模仿生物界遗传学的遗传过程，把问题的参数基于模仿生物界遗传学的遗传过程，把问题的参数用用基因来表示，把问题的解用染色体来表示代表（基因来表示，把问题的解用染色体来表示代表（在计在计算算机里用二进制码表示），机里用二进制码表示），从而得到一个由具有不同染从而得到一个由具有不同染色色体的个体组成的群体。体的个体
3、组成的群体。这个群体在问题特定的环境里生存竞争，适者有最这个群体在问题特定的环境里生存竞争，适者有最好好的机会生存和产生后代，后代随机化地继承父代的最的机会生存和产生后代，后代随机化地继承父代的最好好特征，并也在生存环境的控制支配下继续这一过程。特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后群体的染色体都将逐渐适应环境，不断进化，最后收收敛到一族最适应环境的类似个体，即得到问题最优解。敛到一族最适应环境的类似个体，即得到问题最优解。遗传学相关概念遗传学相关概念遗传学遗传学遗传算法遗传算法数学数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合
4、被选定的一组可行解3染色体 个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位 某一基因在染色体中的位置 元素在编码中的位置6适应值 个体对于环境的适应程度，可行解所对应的适应或在环境压力下的生存能力 函数值7种群被选定的一组染色体或个体 根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解遗传学相关概念遗传学相关概念遗传学遗传学遗传算法遗传算法数学数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10 交叉概率染色体对应基因段交换的概率（可能性大小）闭区间0,1上的一个值，一般为0.650.901
5、1 变异染色体水平上基因变化编码的某些元素被改变12 变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.0010.0113 进化、适者生存个体进行优胜劣汰的进化一代又一代地优化，目标函数取到最大值，最优的可行解遗传算法的步骤遗传算法的步骤遗传算法计算优化的过程就如同生物学上生物遗传算法计算优化的过程就如同生物学上生物遗遗传进化的过程，主要有三个基本操作（或算子传进化的过程，主要有三个基本操作（或算子）：）：选择选择（Selection）交叉交叉（Crossover）变异变异（Mutation）遗传算法的步骤遗传算法的步骤遗传算法基本步骤：遗传算法基本步骤：把问题
6、的解表示成把问题的解表示成“染色体染色体”，在算法中就是以二进制，在算法中就是以二进制编码编码的串，给出一群的串，给出一群“染色体染色体”，也就是假设的可行解，也就是假设的可行解把这些可行解置于问题的把这些可行解置于问题的“环境环境”中，按适者生存的原则，中，按适者生存的原则，选取较适应环境的选取较适应环境的“染色体染色体”进行复制，并通过交叉、变异过进行复制，并通过交叉、变异过程产生更适应环境的新一代程产生更适应环境的新一代“染色体染色体”群群经过这样的一代一代地进化，最后就会收敛到最适应环经过这样的一代一代地进化，最后就会收敛到最适应环境境的一个的一个“染色体染色体”上，它就是问题的最优解
7、上，它就是问题的最优解遗传算法有很多种具体的不同实现过程，这里仅介绍标准遗传算法的主要步骤。遗传算法具体步骤遗传算法具体步骤 选择编码策略，把参数集合（可行解集合）选择编码策略，把参数集合（可行解集合）转换染色转换染色体结构空间；体结构空间；定义适应函数，便于计算适应值；定义适应函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；异方法以及确定交叉概率、变异概率等遗传参数；随机产生初始化群体；随机产生初始化群体；计算群体中的个体或染色体解码后的适应值；计算群体中的个体或染色体解码后的适应值
8、；按照遗传策略，运用选择、交叉和变异算子作用于群按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策迭代次数，不满足则返回第五步，或者修改遗传策略略再返回第六步再返回第六步产生初始群体是否满足终止条件得到结果是结束程序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体例例 1.设设 f(x)=-x2+2x+0.5，求，求 max f(x),
9、x-1,2。遗传算法的实际应用遗传算法的实际应用我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。1编码和产生初始群体编码和产生初始群体首先需要确定编码的策略，也就是说如何把-1,2 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应编码编码我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个0,1二进制串。串的长度取决于求解的精度，例如假设求解
10、精度为保留六位小数，由于区间-1,2的长度为 3，则必须将该区间分为 3106 等分。因为 2213106222，所以编码所用的二进制串至少需要22位。二进制串（b21b20b19b1b0）与 a,b 内实数的一一映射：二进制串十进制数a,b 内实数b21b20b19b1b0编码编码其对应的十进制数为：转化到-1,2 内的实数为：例例.二进制串 a=产生初始群体产生初始群体随机的产生一个初始群体。pop1=，%a1，%a2，%a3%a4这里假设初始群体的个体数为 4。转化成-1,2 之间的十进制数即为：下面就需要解决每个染色体个体的适应值pop1=1.523032,0.574022,-0.69
11、7235,0.247238适应函数适应函数（2）定义适应函数和适应值由于目标函数 f(x)在-1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。定义适应函数：为了便于计算，这里的Fmin采用了一个特定的输入值例：例：如果取如果取 Fmin=-1，则，则 f(x)=1 对应的适应值为对应的适应值为 g(x)=2适应函数和适应值适应函数和适应值上述随机产生的初始群体，取 Fmin=-1，则，则它们的目标函数值和适应值分别为：f(pop1)=1.226437,1.3185
12、43,-1.380607,0.933350g(pop1)=2.226437,2.318543,0,1.933350选择标准选择标准（3）确定选择标准用适应值比例来作为入选概率。设给定的规模为 n 的群体 pop=a1,a2,.,an，个体ai 的适应值为 g(ai)，则其入选概率为上述随机产生的初始群体，它们的入选概率分别为：p(pop1)=g(pop1)/sum(g(pop1)=0.343675,0.357892,0,0.298433产生种群产生种群，%a1，%a2，%a2%a4（4）产生种群将入选概率大的个体选入种群，淘汰概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群
13、。在上述随机产生的初始群体中，淘汰掉 a3，再加入 a2，得到新的种群：newpop1=Matlab 程序参见附录程序参见附录 11交叉交叉（5）交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。将前面得到的 newpop1 的四个个体两两配对，重复的不配对，进行交叉（可以在任一位进行交叉）：新的群体 jchpop1变异变异（6）变异变异就是通过一个小概率改变染色体位串上的某个基因。现把 jchpop1 中第 3 个个体中的第 9 位改变，就产生了变异，得到了新的群体 pop2：pop2=,然后重复上述的选择、交叉、变异，直到满足终止条件为止然后重
14、复上述的选择、交叉、变异，直到满足终止条件为止终止条件终止条件（7）终止条件遗传算法的终止条件有两类常见条件：采用设定最大（遗传）代数的方法，一般可设定为 50代，此时就可能得出最优解此种方法简单易行，但可能不是 很精确（Matlab程序参见附录1）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制遗传算法的收敛性遗传算法的收敛性遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索均衡搜索的具体实现图示遗传算法的收敛性遗传算法的收敛性遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优
15、化收敛性的理论分析尚待解决。目前普遍认为，标准遗传算法并不保证全局最优收敛。但是，在一定的约束条件下，遗传算法可以实现这一点。定理 1如果变异概率为 ，交叉概率为，同时采用比例选择法(按个体适应度占群体适应度的比例进行复制)，则标准遗传算法的变换矩阵 P 是基本的。遗传算法的收敛性遗传算法的收敛性定理 2标准遗传算法（参数如定理1）不能收敛至全局最优解。标准遗传算法是不能收敛至全局最最优解，对标准遗传算法作一些改进，就能够保证其收敛性。最佳个体保存方法（elitist model）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。设时刻 t(第 t 代)时，群体中 a*(t)
16、为最佳个体，并设 A(t+1)为新一代群体，若 A(t+1)中不存在 a*(t)，则把 a*(t)作为 A(t+1)中的第 n+1 个个体(其中，n 为群体大小)最佳个体保存方法最佳个体保存方法该方法的优点：确保进化过程中某一代的最优解不被交叉和变异操作所破坏。该方法的缺点：局部最优个体的遗传基因会急速增加而使进化有可能限于局部解，即该方法的全局搜索能力差，它更 适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。使用策略：与其他选择方法结合使用。最佳个体保存方法最佳个体保存方法定理 4具有定理 1 所示参数，且在选择前保留当前最优解的遗传算法可收敛于全局最优解。定理 3具有定理 1 所示参
17、数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解。实验举例实验举例例例 1.设设 f(x)=-x2+2x+0.5，求，求 max f(x),x-1,2。解：解：群体中包含六个染色体，每个染色体用 22 位码表示，变异概率为 0.01，变量区间为-1,2，取 Fmin=-2，遗传代数为 50 代，运用第一种终止条件（指定遗传代数）的Matlab 程序为Count,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)教材教材 P：练习：练习 1、2、4、6要求写入实验报告册要求写入实验报告册其它练习自己上机练习，不用写入报其它练习自己上机练习，不用写入报告告上机作业上机作业
