1、现代设计方法之遗传优化算法现代设计方法之遗传优化算法产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次染色体及其编码染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串, 所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命科学中所称的生物体的表现型(phenotype), 而其编码即“染色体
2、”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示, 而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象, 则我们就可以用它的二进制数串1001作为它的染色体编码。 编码解码个体（染色体）基因适应度与适应度函数适应度与适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数值越大，解的质量越好。适应度(fitness)就是借鉴生物个体对环境的适应程度, 而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitness function)
3、就是问题中的全体对象与其适应度之间的一个对应关系, 即对象集合到适应度集合的一个映射。 它一般是定义在论域空间上的它一般是定义在论域空间上的一个实数值函数。一个实数值函数。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。说明：“论域”是数理逻辑数理逻辑中的概念。“在一个逻辑系统中，所有的个体组成的集合，称为个体域，亦称论域。” 种群种群(population) 或种群就是模拟生物种群而由若干个染色体组成的群体, 它一般是整个论域空间的一个很小的子集。遗传操作遗传操作遗传算法中有三种关于染色体的运算（遗传算子）遗传算子）: 选择-复制、交叉
4、和变异,这三种运算被称为遗传操作或遗传算子(genetic operator)。 选择选择- -复制算子和选择概率复制算子和选择概率选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算, 就是从种群中选择适应度较高的染色体进行复制,以生成下一代种群。选择-复制的通常做法是, 对于一个规模为N 的种群S,按每个染色体xiS 的选择概率P(xi)所决定的选中机会, 分N 次从S中随机选定N 个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为 1( )( )()iiNjjf xP xf xNote:复制即为个体被选中并遗传到下一代
5、；其中, 为适应度函数, f(xi)为xi 的适应度。可以看出, 染色体xi被选中的概率就是其适应度f(xi)所占种群中全体染色体适应度之和的比例。 显然显然, 按照这种选择概率定义按照这种选择概率定义, 适应度越高适应度越高的染色体被随机选定的概率就越大的染色体被随机选定的概率就越大, 被选中的次数也就越多被选中的次数也就越多, 从而被复制的次数也就越多。从而被复制的次数也就越多。相反,适应度越低的染色体被选中的次数也就越少,从而被复制的次数也就越少。如果把复制看做染色体的一次换代的话,则这就意味着适应度越高的染色体其后代也就越多,适应度越低的染色体其后代也就越少, 甚至被淘汰。 这正吻合了
6、优胜劣汰的自然选择法则。 轮盘赌选择又称轮盘赌选择又称比例选择算子比例选择算子，它的基本思想是：，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成各个个体被选中的概率与其适应度函数值大小成正比。正比。1( )( )()iiNjjf xP xf x上述按概率选择的方法可用一种称为赌轮的原理来实现。 即做一个单位圆, 然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图1所示)。这样, 每次选择时先转动轮盘, 当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。 例如, 假设种群S中有4个染色体: s1,s2, s3, s4,其选择概率依次为:
7、 0.11, 0.45, 0.29, 0.15, 则它们在轮盘上所占的份额如图1中的各扇形区域所示。 图1 赌轮选择示例 在算法中赌轮选择法可用下面的过程来模拟: 在0, 1区间内产生一个均匀分布的伪随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi(i=1, 2, , n)的积累概率, 其计算公式为：1()iijjqP x一个染色体xi被选中的次数, 可以用下面的期望值e(xi)来确定： 11( )( )( )( )( )()()/iiiiiNNjjjje xP xNf xf xf xNff xf xN其中f 为种群S中全
8、体染色体的平均适应度值。 例如,设染色体s1=01001011, s2=10010101, 交换其后4位基因, 即： 则得新串s1=01000101,s2=10011011。s1和s2可以看做是原染色体s1和s2的子代染色体。 交叉交叉(crossover)算子算子单点交叉运算：单点交叉运算：交叉点交叉点变异点变异点参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc。由于生物繁殖时染色体的交叉是按一定的概率发生的, 因此参加交叉操作的染色体也有一定的比例,而交叉率也就是交叉概率。变异率(mutation rate)是指发生变异的基因位数所占全体染色发生变异的基因位数所占全体染色体的基因总
9、位数体的基因总位数的比例，记为Pm。由于在生物的繁衍进化过程中, 变异也是按一定的概率发生的, 而且发生概率一般很小, 因此变异率也就是变异概率。产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次基本遗传算法流程说明：步1 在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2 随机产生U中的N个染色体s1, s2, , sN，组成初始种群S=s1, s2
10、, , sN，置代数计数器t=1；步3 计算S中每个染色体的适应度f(si) ；步4 若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。 步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； 步8 将群体S3作为新一代种群，即用S3代
11、替S，t=t+1，转步3； 需要说明的是, 在应用遗传算法解决实际问题时, 还需给出结构模式的表示方案、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串, 字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。 初始初始种群种群第二第二代种代种群群积木块：AA BB CC第三代种群第三代种群小小 结结1.轮盘赌2.随机竞争选择(按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的选中，如此反复，直到选满为止)3. 最优保留策略(当前种群中适应度最高的个体不参与交叉和变异操作，而是用它来替换掉本代种群中经交叉、变异等操作
12、后所产生的适应度最低的个体，保证算法终止时得到的最后结果是历代出现过得最高适应度个体) 4. . 交叉操作用于个体对个体对，产生新的个体，实质上是在解空间中进行有效搜索进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。 例例1.利用遗传算法求解区间0,31上的二次函数y=x2的最大值； 【分析分析】可以看出,只要能在区间0,31中找到函数值最大的点a,则函数y=x2的最大值也就可以求得。于是, 原问题转化为在区间0, 31中寻找能使y取最大值的点a的问题。显然, 对于这个问题, 任一点x0
13、, 31都是可能解, 而函数值f(x)= x2也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看, 区间0, 31就是一个(解)空间,x就是其中的个体对象, 函数值f(x)恰好就可以作为x的适应度。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。 解：解： (1)定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面, 5位二进制数也刚好能表示区间0, 31中的全部整数。所以, 我们就仅取0,31中的整数来作为参加进化的个体,并且用5位二进制数作为个体
14、x的基因型编码, 即染色体即染色体。 (2)设定种群规模, 产生初始种群。设定种群规模为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8), s4=10011(19)组成初始种群S1。 (3) 计算各代种群中的各染色体的适应度, 并进行遗传操作,直到适应度最高的染色体(该问题中显然为该问题中显然为“1111111111”=31=31)出现为止。 计算S1中各染色体的适应度、选择概率、积累概率等并列于表1中。 r1=0.450126, r2=0.110347, r3=0.572496, r4=0.98503 设从区间0, 1中产生4个随机数如下:选择-复制 设
15、从区间0, 1中产生4个随机数如下: r1=0.450126, r2=0.110347, r3=0.572496, r4=0.98503 按赌轮选择法，染色体s1, s2, s3, s4的被选中次数依次为：1, 2, 0, 1。于是，经复制得到新的群体如下： s1=11000（24）, s2=01101（13）, s3=11000（24）, s4=10011（19） 可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低的染色体s3一次也没有选中而遭淘汰。 交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交
16、换染色体后两位基因，得新染色体：s1=11001（25）, s2=01100（12）, s3=11011（27）, s4=10000（16）变 异 设 变 异 率 pm= 0 . 0 0 1 。 这 样 ， 群 体 S1中 共 有540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，我们得到了第二代种群S2：s1=11001（25）, s2=01100（12）, s3=11011（27）, s4=10000（16）Note:s1=11000（24）, s2=01101（13）, s3=11000（24）, s4=10011（19） 假设这一轮选择-复制
17、操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体： s1=11001（25）, s2=01100（12）, s3=11011（27）, s4=10000（16） 然后，做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得 s1=11100（28）, s2=01001（9）, s3=11000（24）, s4=10011（19） 这一轮仍然不会发生变异。于是，得第三代种群S3： s1=11100（28）, s2=01001（9）, s3=11000（24）, s4=10011（19） 设这一轮的选择-复制结果为
18、： s1=11100（28）, s2=11100（28）, s3=11000（24）, s4=10011（19） 然后，做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）, s2=11100（28）, s3=11000（24）, s4=10000（16） 这一轮仍然不会发生变异。于是，得第四代种群S4： s1=11111（31）, s2=11100（28）, s3=11000（24）, s4=10000（16） 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“111
19、11”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。 7.7.遗传算法小结遗传算法小结 由上所述, 我们看到,遗传算法模拟自然选择和有性繁殖、 遗传变异的自然原理, 实现了优化搜索和问题求解。遗传算法的主要特点是: 遗传算法一般是直接在解空间搜索; 遗传算法的搜索随机地始于搜索空间的一个点集, 而不是固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 二维优化问题的迭代过程二维优化问题的迭代过程梯度方向与等值线的关系梯度方向与等值线的关系 遗传算法总是在寻找优解(最优解或次优解), 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。 遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。
