遗传算法简述优秀PPT.ppt

《遗传算法简述优秀PPT.ppt》由会员分享，可在线阅读，更多相关《遗传算法简述优秀PPT.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 遗传算法（Genetic Algorithm）遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜寻最优解的方法。最初由美国Michigan高校J.Holland教授于1975年首先提出来，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才渐渐为人所知，J.Holland教授所提出的GA通常为简洁遗传算法（SGA）。1.1 1.1 基本概念基本概念 1.1.个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象个体就是模拟

2、生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个（一般就是问题的解）的一种称呼，一个个 体也就是搜寻空间中的一个点。体也就是搜寻空间中的一个点。种群种群(population)(population)就是模拟生物种群而由若就是模拟生物种群而由若 干个体组成的群体干个体组成的群体,它一般是整个搜寻空间它一般是整个搜寻空间 的一个很小的子集。的一个很小的子集。2.2.适应度与适应度函数适应度与适应度函数 适应度适应度(fitness)(fitness)就是借鉴生物个体对环境的就是借鉴生物个体对环境的 适应程度适应程度,而对问题中的个体对象所设计的而对问题中的个体对象所设计的 表征其

3、优劣的一种测度。表征其优劣的一种测度。适应度函数适应度函数(fitness function)(fitness function)就是问题中的就是问题中的 全体个体与其适应度之间的一个对应关系。全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算它一般是一个实值函数。该函数就是遗传算 法中指导搜寻的评价函数。法中指导搜寻的评价函数。3.3.染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体 染色体 9 -1001 （2，5，6）-010 101 1104.4.遗传操作遗传操作

4、亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:选择-复制(selection-reproduction)交叉(crossover，亦称交换、交配或杂交)变异(mutation，亦称突变)选选择择-复复制制通通常常做做法法是是：对对于于一一个个规规模模为为N的的种种群群S,按按每每个个染染色色体体xiS的的选选择择概概率率P(xi)所所确确定定的的选选中中机机会会,分分N次从次从S中随机选定中随机选定N个染色体个染色体,并进行复制。并进行复制。这里的选择概率P(xi)的计算公式为交叉 就是互换两个染色体某些位上的基因。s1=01000101,s

5、2=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即 变异变异 就是变更染色体某个就是变更染色体某个(些些)位上的位上的基因。基因。例如例如,设染色体设染色体 s=11001101将其第三位上的将其第三位上的0变为变为1,即即 s=11001101 11101101=s。s也可以看做是原染色体也可以看做是原染色体s的子代染色的子代染色体。体。1.2 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束 算法中的一些限制参数：种群规模 最大换代数 交叉率(c

6、rossover 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,sN，置代数计数器t=1；步3 计算S中每个个体的适应度f()；步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。步5 按选择概率P(xi)所

7、确定的选中机会，每次从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；1.3 遗传算法应用举例 例例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY 分析 原问题可转化为在区间0,31中搜

8、寻能使y取最大值的点a的问题。那么，0,31 中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间0,31就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2 (3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。首先

9、计算种群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)=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 赌轮选择法在算法中赌轮选择法可用下

10、面的子过程来模拟:在0,1区间内产生一个匀整分布的随机数r。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率,其计算公式为 选择-复制 设从区间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

11、=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）交叉 设交叉率pc=100%，即S1中的全体染色体都参与交叉运算。设s1与s2配对，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）其

12、次代种群其次代种群S2中各染色体的状况中各染色体的状况 染色体 适应度选择概率积累概率 估计的选中次数s1=11001 625 0.36 0.36 1s2=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=

13、11000（24）,s4=10011（19）这一轮仍旧不会发生变异。于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第三代种群第三代种群S3S3中各染色体的状况中各染色体的状况 染色体 适应度选择概率积累概率 估计的选中次数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=

14、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”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。YYy

15、=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 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

16、的适应度，从而适应度函数就是（2）对个体s=（c1,c2,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）可以看出，上面得到

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

18、法：枚举出可行解集合内的全部可行解，以求出精确最优解。*对于连续函数，要求先进行离散化处理。枚举空间比较大时，方法求解效率较低，甚至无法求解。-启发式算法：寻求一种能产生可行解的启发式规则，已找到一个最优解或近似最优解。*该方法的求解效率比较高，但对每一个需求解的问题必需找出其特有的启发式规则，这个启发式规则一般无通用性，不适合于其他问题。-搜寻算法：寻求一种搜寻算法，该算法在可行解集合的一个子集内进行搜寻操作，已找到问题的最优解或近似最优解。*该方法虽然保证不了能够获得问题的最优解，但若适当地利用一些启发式规则，就可以在近似解的质量和效率上达到一种较好的平衡。遗传算法的主要特点 遗传算法一般

19、是干脆在解空间搜寻,而不像图搜寻那样一般是在问题空间搜寻,最终才找到解，因而可以更加干脆地应用。遗传算法是一种随机搜寻算法，搜寻随机地始于搜寻空间的一个点集，避开使得算法总是陷入到相同的局部微小点（局部最优值）。遗传算法接受适应度函数和遗传操作，从而设法尽快找到解,所以遗传算法又是一种优化搜寻算法。遗传算法的搜寻过程是从空间的一个点集(种群)到另一个点集(种群)的搜寻,而不像图搜寻那样一般是从空间的一个点到另一个点地搜寻。因而它实际是一种并行搜寻,适合大规模并行计算,而且这种种群到种群的搜寻有实力跳出局部最优解。遗传算法的适应性强,除需知适应度函数外,几乎不须要其他的先验学问。遗传算法长于全局

20、搜寻,它不受搜寻空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。遗传算法对应给定问题，可产生很多潜在解，并可由运用者来确定最终解。2.2 遗传算法的数学基础u模式定理 u积木块假设 u模式是指种群个体基因串中的相像样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表随意字符，即 0 或者 1。u对于二进制编码串，当串长为l时，共有3l个不同的模式，遗传算法中串的运算事实上是模式的运算。u 模式示例：*1*u 表示四元子集010，011，110，111v与模式0*相比，模式

21、011*1 在相像性方面有更明确的表示；v模式0*0*与模式0*0相比要跨越整个串长更大的部分。v定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3。v定义2：模式 H 中第一个确定位置和最终一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1*)=4。v模式的阶和定义距的含义模式的阶和定义距的含义：v模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。v模式定理模式定理v模式定理：具有低阶、短定义距以及

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

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

24、采样点，以致算法性能很差；种群太大，尽点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻挡早熟收敛的管可以增加优化信息，阻挡早熟收敛的发生，但无疑会增加计算量，造成收敛发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。时间太长，表现为收敛速度缓慢。v选择操作对收敛性的影响选择操作对收敛性的影响v选择操作使高适应度个体能够以更大的概率选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。生存，从而提高了遗传算法的全局收敛性。假如在算法中接受最优保存策略，即将父代假如在算法中接受最优保存策略，即将父代群体中最佳个体保留下来，不参与交叉和变群体中最佳个体保留

25、下来，不参与交叉和变异操作，使之干脆进入下一代，最终可使遗异操作，使之干脆进入下一代，最终可使遗传算法以概率传算法以概率1收敛于全局最优解。收敛于全局最优解。v交叉概率对收敛性的影响交叉概率对收敛性的影响v交叉操作用于个体对，产生新的个体，实交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜寻。交叉概质上是在解空间中进行有效搜寻。交叉概率太大时，种群中个体更新很快，会造成率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜寻小时，交叉操作很少进行，从而会使搜寻停滞不前，造成算法的不收敛。停滞不

26、前，造成算法的不收敛。v变异概率对收敛性的影响变异概率对收敛性的影响v变异操作是对种群模式的扰动，有利于增变异操作是对种群模式的扰动，有利于增加种群的多样性加种群的多样性。但是，变异概率太小则。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗很难产生新模式，变异概率太大则会使遗传算法成为随机搜寻算法。传算法成为随机搜寻算法。v遗传算法的本质遗传算法的本质v遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。2.4 遗传

27、算法的改进 u自从1975年J.H.Holland系统提出遗传算法的完整结构和理论以来，众多学者始终致力于推动遗传算法的发展，对编码方式、限制参数的确定、选择方式和交叉机理等进行了深化探讨，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种变形的遗传算法。u 基本改进途径概括起来包括u变更遗传算法的组成成分或运用技术，如选用优化限制参数、适合问题特性的编码技术等u接受混合遗传算法u接受动态自适应技术，在进化过程中调整算法限制参数和编码粒度u接受非标准的遗传操作算子u接受并行遗传算法v对编码方式的改进对编码方式的改进v二二进进制制编编码码优优点点在在于于编编码码、解解码码操操作作简简洁洁

28、，交交叉叉、变变异异等等操操作作便便于于实实现现，缺缺点点在在于于精精度度要要求求较较高高时时，个个体体编编码码串串较较长长，使使算算法法的的搜搜寻寻空空间间急急剧剧扩扩大大，遗遗传传算算法法的的性性能能降降低低。格格雷雷编编码码克克服服了了二二进进制制编编码码的的不不连连续续问问题题，浮浮点数编码改善了遗传算法的计算困难性点数编码改善了遗传算法的计算困难性。对遗传算子对遗传算子 的改进的改进v排序选择 v匀整交叉 v逆序变异（1）对群体中的全部个体按其适应度大小进行降序排序；（2）依据具体求解问题，设计一个概率安排表，将各个概率值按上述排列次序安排给各个个体；（3）以各个个体所安排到的概率值

29、作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。对遗传算子对遗传算子 的改进的改进v排序选择 v匀整交叉 v逆序变异（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；（2）按下列规则从A、B两个父代个体中产生两个新个体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

30、建议的最优参数范围是：v M=20-100，v T=100-500，v Pc=0.4-0.9，v Pm=0.001-0.01。v 对限制参数的改进对限制参数的改进vSrinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动变更，当种群的各个个体适应度趋于一样或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，接受较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，接受较高的PC和Pm，使性能较差的个体被淘汰。对执行策略的改进对执行策略的改进v混合遗传算法v免疫遗传算法v小生境遗传算法v单亲遗传算法v并行遗传算法

31、分层遗传算法分层遗传算法 分层遗传算法基本流程框图初始化N个子种群N个子种群独立运行遗传算法一定代数N个结果种群及平均适应度值记录到R1.N,1.n及Ai对R1.N,1.n进行选择和交叉对R1.N,1.n进行变异操作对新的N个子种群重新开始遗传算法操作性能满足?结束并行遗传算法（并行遗传算法（parallel GA，PGA）v遗传算法中适应度的计算最费时间，再加上须要不断产生新一代，而每一代又有若干个个体，随意如何提高遗传算法的运行速率显得尤为突出。由于遗传算法的内在并行机制，其并行处理是很自然的解决途径。v并行遗传算法的实现方案v全局型主从式模式（master-slave model）v独立

32、型粗粒度模型（coarse-grained model）；孤岛模型；分布式遗传算法v分散型细粒度模型（fine-grained model）v全局型v处理方式：并行系统分为一个主处理器和若干个从处理器主处理器监控整个染色体种群，并基于全局统计执行选择操作；各个从处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算适应度，再把计算结果传给主处理器。v缺点：适应度评价很费时且远远超过通信时间有效的状况下才有效，否则通信时间超过计算时间，反而会降低速度。这种方法要求同步机制，会导致主进程忙二子进程闲置或反之，引起负载不平衡，效率不高。v独立型独立型v处理方式：将种群分成若干个子种群

33、并安排给处理方式：将种群分成若干个子种群并安排给各自对应的处理器，每个处理器不仅独立计算各自对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择、重组交叉和变异适应度，而且独立进行选择、重组交叉和变异操作，还要定期地相互传送适应度最好的个体，操作，还要定期地相互传送适应度最好的个体，从而加快满足终止条件的要求。从而加快满足终止条件的要求。v特点：基于粗粒度模型的遗传算法也称之为分特点：基于粗粒度模型的遗传算法也称之为分布式遗传算法，是目前应用最广泛的一种并行布式遗传算法，是目前应用最广泛的一种并行遗传算法。遗传算法。v分散型分散型v处理方式：为种群中的每一个个体安排一个处处理方式：为种

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

35、。v以基于粗粒度模型的并行遗传算法为例，迁移策略可分为以以基于粗粒度模型的并行遗传算法为例，迁移策略可分为以下两种：下两种：v一传多：每个处理器对易于若干相邻处理器，将其最好传给一传多：每个处理器对易于若干相邻处理器，将其最好传给全部相邻处理器，并接受来自相邻处理器的最好的个体，将全部相邻处理器，并接受来自相邻处理器的最好的个体，将这些个体与自己个体同时考虑，淘汰适应度差的个体。这些个体与自己个体同时考虑，淘汰适应度差的个体。v一传一：每个处理器将其最好传给与之相邻的一个处理器，一传一：每个处理器将其最好传给与之相邻的一个处理器，同时增加同时增加“处理器之间通讯的频率处理器之间通讯的频率”和和

36、“每次传送给最好个体的每次传送给最好个体的数目数目”两个参数。两个参数。v处理器之间通讯的频率 send_rate如send_rate=3时，表示当遗传代数是3的倍数时，各处理器之间相互传递个体。v每次传送给最好个体的数目send_bestsend_best=5时表示每个处理器把最好的前5个个体传给各自相邻的处理器2.5 遗传算法的融合 v遗传算法在人工智能的众多领域便得到了广泛应用。例如机器学习、聚类、限制、规划、设计、调度、组合优化、函数的最大值以及图像处理和信号处理等等。v另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解实力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。v混合遗传算法v引入局部搜寻过程v增加编码变换操作过程vDe Jong提出下面三个基本原则v尽量接受原有算法的编码v利用原有算法全局搜寻的优点v改进遗传算子v遗传算法与最速下降法相结合v遗传算法与模拟退火算法相结合v遗传算法与神经网络的结合：v遗传算法用于神经网络主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构；用遗传算法来取代一些传统的学习算法，利用GA的寻优实力获得最佳权重。v目前广泛探讨的是BP神经网络+遗传算法确定BP网络的连接权，发挥网络的泛化实力，而且使网络具有快速收敛及增加式学习性能