遗传算法简述ppt课件

《遗传算法简述ppt课件》由会员分享，可在线阅读，更多相关《遗传算法简述ppt课件（80页珍藏版）》请在金锄头文库上搜索。

1、遗传算法1.1 1.1 基本概念基本概念1.2 1.2 基本遗传算法基本遗传算法1.3 1.3 遗传算法应用举例遗传算法应用举例 遗传算法（Genetic Algorithm） 遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 最初由美国Michigan大学J.Holland教授于1975年首先提出来，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单

2、遗传算法（SGA）。 1.1 基本概念 1. 1. 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。 2. 2. 适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算

3、法中指导搜索的评价函数。 3. 3. 染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 1104. 4. 遗传操作遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变) 选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选

4、择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为交叉 就是互换两个染色体某些位上的基因。 s1=01000101, s2=10011011可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即 变异变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。1.2 基本遗传算法 遗传算法基本流程框图生成初始

5、种群计算适应度选择-复制交叉变异生成新一代种群终止 ?结束 算法中的一些控制参数： 种群规模种群规模 最大换代数最大换代数 交交叉叉率率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。 变变异异率率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1。 基本遗传算法步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； 步2 随机产生U中的N个个体s1, s2, , sN，组成初始种群S=s1, s2,

6、 , sN，置代数计数器t=1； 步3 计算S中每个个体的适应度f() ；步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

7、，t = t+1，转步3； 1.3 遗传算法应用举例 例例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY 分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。解(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3=

8、 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2 (3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。 首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) =

9、192 = 361再计算种群S1中各个体的选择概率。选择概率的计算公式为 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31 赌轮选择示意s40.31s20.49s10.14s30.06 赌轮选择法在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积积累累概概率率, 其计算公式为 选择-复制 设

10、从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色体 适应度选择概率积累概率选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 1于是，经复制得群体：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对

11、，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异。 于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16） 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数s1=11001 625 0.36 0.36 1s2

12、=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1 假设这一轮选择-复制操作中，种群S2中的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）

13、, s2=01001（9） s3=11000（24）, s4=10011（19） 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1 设这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19） 做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31

14、）, 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”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。 YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25

15、 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度例 1.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。（1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 （2）对个体s=（c1, c2, ,

16、 cn, cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。 例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。然后进行遗传操作。设 s1=（A, C, B, E, D, A），s2=（A, E, D, C, B, A）实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,C,B,A）， s2=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得 s1=（A, E, B, E, D, A） 可以看出，上面得到的s1， s2和s

17、1都是非法的城市序列。 为此，对TSP必须设计合适的染色体和相应的遗传运算。 事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。 遗传算法2.1 2.1 遗传算法特点遗传算法特点2.2 2.2 遗传算法的数学基础遗传算法的数学基础2.32.3 遗传算法的收敛性分析遗传算法的收敛性分析2.4 2.4 遗传算法改进遗传算法改进2

18、.5 2.5 遗传算法的融合遗传算法的融合 2.1 遗传算法的特点与优势 传统优化算法 - 枚枚举举法法：枚举出可行解集合内的所有可行解，以求出精确最优解。* 对于连续函数，要求先进行离散化处理。枚举空间比较大时，方法求解效率较低，甚至无法求解。 - 启启发发式式算算法法：寻求一种能产生可行解的启发式规则，已找到一个最优解或近似最优解。* 该方法的求解效率比较高，但对每一个需求解的问题必须找出其特有的启发式规则，这个启发式规则一般无通用性，不适合于其他问题。 - 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，已找到问题的最优解或近似最优解。* 该方法虽然保证不了能够获

19、得问题的最优解，但若适当地利用一些启发式规则，就可以在近似解的质量和效率上达到一种较好的平衡。遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解，因而可以更加直接地应用。 遗传算法是一种随机搜索算法，搜索随机地始于搜索空间的一个点集，避免使得算法总是陷入到相同的局部极小点（局部最优值）。 遗传算法采用适应度函数和遗传操作，从而设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大

20、规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。遗传算法对应给定问题，可产生许多潜在解，并可由使用者来确定最终解。 2.2 遗传算法的数学基础u模式定理 u积木块假设 u模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 u对于二进制编码串，当串

21、长为l时，共有3l个不同的模式，遗传算法中串的运算实际上是模式的运算。 模式示例：* 1 * 表示四元子集010，011，110，111v与模式0*相比，模式011*1 在相似性方面有更明确的表示；v模式0*0*与模式0*0相比要跨越整个串长更大的部分。定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3 。定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1*)=4 。 v模式的阶和定义距的含义模式的阶和定义距的含义：v模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹

22、配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 v模式定理模式定理v模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。v模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。 v从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。 v积木块假设：积木块假设：v积木

23、块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。v 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。 2.3 遗传算法的收敛性分析v 遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。 v种群规模对收敛性的影响种群规模对收敛性的影响v通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增

24、加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。v选择操作对收敛性的影响选择操作对收敛性的影响v选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。v交叉概率对收敛性的影响交叉概率对收敛性的影响v交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造

25、成算法的不收敛。 v变异概率对收敛性的影响变异概率对收敛性的影响v变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。 v遗传算法的本质遗传算法的本质v遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。 2.4 遗传算法的改进 u自从1975年J.H. Holland系统提出遗传算法的完整结构和理论以来，众多学者一直致力于推动遗传算法的发展，对

26、编编码码方方式式、控控制制参参数数的的确确定定、选选择择方方式式和和交交叉叉机机理理等进行了深入研究，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种变形的遗传算法。u 基本改进途径概括起来包括基本改进途径概括起来包括改变遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等采用混合遗传算法采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度采用非标准的遗传操作算子采用并行遗传算法v对编码方式的改进对编码方式的改进v二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能

27、降低。格雷编码克服了二进制编码的不连续问题 ，浮点数编码改善了遗传算法的计算复杂性 。 对遗传算子对遗传算子 的改进的改进v排序选择 v均匀交叉 v逆序变异（1） 对群体中的所有个体按其适应度大小进行降序排序；（2） 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3） 以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。 对遗传算子对遗传算子 的改进的改进v排序选择 v均匀交叉 v逆序变异（1） 随机产生一个与个体编码长度相同的二进制屏蔽字P = W1W2Wn ；（2） 按下列规则从A、B两个父代个体中产生两个新个体

28、X、Y：若Wi = 0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi = 1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。 对遗传算子对遗传算子 的改进的改进v排序选择 v均匀交叉 v逆序变异变异前：3 4 8 | 7 9 6 5 | 2 1变异前：3 4 8 | 5 6 9 7 | 2 1对控制参数的改进v Schaffer建议的最优参数范围是： v M = 20-100， v T = 100-500， v Pc = 0.4-0.9，v Pm = 0.001-0.01。v 对控制参数的改进对控制参数的改进vSrinvivas等人提出自适应遗传算法，即

29、PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰 。对执行策略的改进对执行策略的改进v混合遗传算法v免疫遗传算法v小生境遗传算法v单亲遗传算法v并行遗传算法分层遗传算法分层遗传算法 分层遗传算法基本流程框图初始化N个子种群N个子种群独立运行遗传算法一定代数N个结果种群及平均适应度值记录到R1.N,1.n及Ai对R1.N,1.n进行选择和交叉对R1.N,1.n进

30、行变异操作对新的N个子种群重新开始遗传算法操作性能满足?结束并行遗传算法（并行遗传算法（parallel GA，PGA）v遗传算法中适应度的计算最费时间，再加上需要不断产生新一代，而每一代又有若干个个体，随意如何提高遗传算法的运行速率显得尤为突出。由于遗传算法的内在并行机制，其并行处理是很自然的解决途径。v并行遗传算法的实现方案全局型主从式模式（master-slave model）独立型粗粒度模型（coarse-grained model）；孤岛模型；分布式遗传算法分散型细粒度模型（fine-grained model ）v全局型v处理方式：处理方式：并行系统分为一个主处理器和若干个从处理器

31、主处理器监控整个染色体种群，并基于全局统计执行选择操作；各个从处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算适应度，再把计算结果传给主处理器。v缺点：缺点：适应度评价很费时且远远超过通信时间有效的情况下才有效，否则通信时间超过计算时间，反而会降低速度。这种方法要求同步机制，会导致主进程忙二子进程闲置或反之，引起负载不平衡，效率不高。v独立型独立型v处理方式：处理方式：将种群分成若干个子种群并分配给各自对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择、重组交叉和变异操作，还要定期地相互传送适应度最好的个体，从而加快满足终止条件的要求。v特点：特点：基于粗粒度模

32、型的遗传算法也称之为分布式遗传算法，是目前应用最广泛的一种并行遗传算法。v分散型分散型v处理方式：处理方式：为种群中的每一个个体分配一个处理器，每个处理器进行适应度的计算，而选择、重组交叉和变异操作仅在与之相邻的一个处理器之间相互床底个体中进行。v特点：特点：细粒度模型也称邻域模型，适合于连接机、阵列机。v并行遗传算法的迁移策略并行遗传算法的迁移策略v迁移迁移是并行遗传算法中引入的一个新的算子，它是指在进化的过程中子群体间交换个体的过程，一般的迁移方法是将子群体中最好的个体发给其它的子种群，通过迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度。v以基于粗粒度模型的并行遗传算法为例，迁

33、移策略可分为以以基于粗粒度模型的并行遗传算法为例，迁移策略可分为以下两种：下两种：一传多：每个处理器对易于若干相邻处理器，将其最好传给所有相邻处理器，并接受来自相邻处理器的最好的个体，将这些个体与自己个体同时考虑，淘汰适应度差的个体。一传一：每个处理器将其最好传给与之相邻的一个处理器，同时增加“处理器之间通讯的频率”和“每次传送给最好个体的数目”两个参数。v处理器之间通讯的频率 send_rate如send_rate=3时，表示当遗传代数是3的倍数时，各处理器之间相互传递个体。v每次传送给最好个体的数目send_bestsend_best=5时表示每个处理器把最好的前5个个体传给各自相邻的处理

34、器2.5 遗传算法的融合 v遗传算法在人工智能的众多领域便得到了广泛应用。例如机器学习、聚类、控制、规划、设计、调度、组合优化、函数的最大值以及图像处理和信号处理等等。v另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。 v混合遗传算法v引入局部搜索过程v增加编码变换操作过程vDe Jong提出下面三个基本原则v尽量采用原有算法的编码v利用原有算法全局搜索的优点v改进遗传算子v遗传算法与最速下降法相结合v遗传算法与模拟退火算法相结合v遗传算法与神经网络的结合：v遗传算法用于神经网络主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构；用遗传算法来取代一些传统的学习算法，利用GA的寻优能力获取最佳权重。v目前广泛研究的是BP神经网络+遗传算法确定BP网络的连接权，发挥网络的泛化能力，而且使网络具有快速收敛及增强式学习性能