搜索
现代设计方法之遗传优化算法目录1、智能优化算法2、基本遗传算法3、遗传算法特点4、遗传算法的数学基础5、遗传算法的收敛性分析6、遗传算法应用举例7、遗传算法小结1、智能优化算法智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。常用的智能优化算法（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简称TS）……智能优化算法的特点它们的共同特点：都是从任一组解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。遗传算法起源遗传算法是由美国Michigan大学的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从候选解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。2、基本遗传算法基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串,所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命科学中所称的生物体的表现型(phenotype),而其编码即“染色体”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示,而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象,则我们就可以用它的二进制数串1001作为它的染色体编码。基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因适应度与适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度(fitness)就是借鉴生物个体对环境的适应程度,而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitnessfunction)就是问题中的全体对象与其适应度之间的一个对应关系,即对象集合到适应度集合的一个映射。它一般是定义在论域空间上的一个实数值函数。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。说明：“论域”是数理逻辑中的概念。“在一个逻辑系统中，所有的个体组成的集合，称为个体域，亦称论域。”种群(population)SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。或种群就是模拟生物种群而由若干个染色体组成的群体,它一般是整个论域空间的一个很小的子集。遗传操作遗传算法中有三种关于染色体的运算（遗传算子）:选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(geneticoperator)。选择-复制算子和选择概率选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算,就是从种群中选择适应度较高的染色体进行复制,以生成下一代种群。选择-复制的通常做法是,对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为1()()()iiNjjfxPxfxNote:复制即为个体被选中并遗传到下一代；其中,f为适应度函数,f(xi)为xi的适应度。可以看出,染色体xi被选中的概率就是其适应度f(xi)所占种群中全体染色体适应度之和的比例。显然,按照这种选择概率定义,适应度越高的染色体被随机选定的概率就越大,被选中的次数也就越多,从而被复制的次数也就越多。相反,适应度越低的染色体被选中的次数也就越少,从而被复制的次数也就越少。如果把复制看做染色体的一次换代的话,则这就意味着适应度越高的染色体其后代也就越多,适应度越低的染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰的自然选择法则。SGA选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。1()()()iiNjjfxPxfx上述按概率选择的方法可用一种称为赌轮的原理来实现。即做一个单位圆,然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图1所示)。这样,每次选择时先转动轮盘,当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。例如,假设种群S中有4个染色体:s1,s2,s3,s4,其选择概率依次为:0.11,0.45,0.29,0.15,则它们在轮盘上所占的份额如图1中的各扇形区域所示。图1赌轮选择示例在算法中赌轮选择法可用下面的过程来模拟:①在［0,1］区间内产生一个均匀分布的伪随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为：1()iijjqPx一个染色体xi被选中的次数,可以用下面的期望值e(xi)来确定：11()()()()()()()/iiiiiNNjjjjexPxNfxfxfxNffxfxN其中f为种群S中全体染色体的平均适应度值。交叉(crossover)算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换两个染色体某些位上的基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即：则得新串s1′=01000101,s2′=10011011。s1′和s2′可以看做是原染色体s1和s2的子代染色体。交叉(crossover)算子单点交叉运算：交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点变异(mutation)算子变异(mutation)亦称突变,就是改变染色体某个(些)位上(基因座)的基因。是依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。基本位变异算子基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点运行参数（1）M：种群规模(20-100)（2）T：遗传运算的终止进化代数(100-500)（3）Pc：交叉概率(0.4-0.9)（4）Pm：变异概率(0.001-0.01)参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc。由于生物繁殖时染色体的交叉是按一定的概率发生的,因此参加交叉操作的染色体也有一定的比例,而交叉率也就是交叉概率。变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm。由于在生物的繁衍进化过程中,变异也是按一定的概率发生的,而且发生概率一般很小,因此变异率也就是变异概率。SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次基本遗传算法流程说明：步1在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中的N个染色体s1,s2,…,sN，组成初始种群S={s1,s2,…,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代替S，t=t+1，转步3；需要说明的是,在应用遗传算法解决实际问题时,还需给出结构模式的表示方案、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串,字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。3、遗传算法的特点（1）GA搜索群体中的点是并行,而不是单点；（2）GA使用概率变换规则,而不是确定的变换规则;（3）适应度函数不受连续、可微等条件的约束，适用范围很广。只需要影响搜索方向的目标函数和相对应的适应度函数;(4)GA使用编码参数集,而不是自身的参数集;4、遗传算法的数学基础（1）模式定理(PatternTheorem)（2）积木块假设(BuildingBlockHypothesis)模式模式是指种群个体基因串中的相似样板，它是一种用来描述基因串中某些位置上具有结构相似性的0、1字符串集合的方法。在二进制编码中，基于三值字符集(0,1,*)的字符串所产生的能描述具有某些结构相似性的0,1字符串集的字符串称为模式.符号*代表任意字符，即0或者1。模式示例：*0001描述了具有”0001”特征的所有字符串,即(00001,10001);两个定义定义1：模式H中确定位置的个数称为模式H的阶，记作O(H)。例如O(10**1)=3。O(011*1*)=4;O(0*****)=1note:一个模式阶数越高，其样本数就越少,因而确定性就越高定义2：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4;δ(0*****)=0模式的阶和定义距的含义模式的阶用来反映不同模式间确定性的差异，一个模式阶数越高，其样本数就越少,因而确定性就越高。