《遗传算法简述ppt课件》由会员分享，可在线阅读，更多相关《遗传算法简述ppt课件（80页珍藏版）》请在金锄头文库上搜索。
1、遗传算法1.1 1.1 根本概念根本概念1.2 1.2 根本根本遗传遗传算法算法1.3 1.3 遗传遗传算法运用算法运用举举例例 遗传算法Genetic Algorithm 遗传算法Genetic Algorithm是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种经过模拟自然进化过程搜索最优解的方法。 最初由美国Michigan大学J.Holland教授于1975年首先提出来，并出版了颇有影响的专著，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. 染色体与基因染色体与基因染染色色体体 chromosomechromosome 就就是是问问题题中中个个体体的的某某种种字字符符串串方方式式的的编编码码表表示示。字字符符串串中中的的字字符符也也就称就称为为基因基因 genegene 。 例如：例如： 个体个体 染色
4、体染色体 9 - 1001 9 - 1001 2 2，5 5，6 6 - 010 101 110- 010 101 1104. 4. 遗传遗传操作操作亦亦称称遗遗传传算算子子(genetic (genetic operator)operator)，就就是是关关于于染染色色体体的的运运算算。遗遗传传算算法法中中有有三三种种遗遗传传操操作作: : 选择选择- -复制复制(selection-reproduction)(selection-reproduction) 交交叉叉(crossover(crossover，亦亦称称交交换换、交交配配或或杂杂交交) ) 变变异异(mutation(mutat
5、ion，亦称突，亦称突变变) ) 选择-复复制制通通常常做做法法是是：对于于一一个个规模模为N的的种种群群S,按按每每个个染染色色体体xiS的的选择概概率率P(xi)所所决决议的的选中中时机机, 分分N次从次从S中随机中随机选定定N个染色体个染色体, 并并进展复制。展复制。 这里的选择概率P(xi)的计算公式为交叉交叉 就是互就是互换两个染色体某些位上的基因。两个染色体某些位上的基因。 s1=01000101, s2=10011011可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即 变变异异 就是改就是改动
6、动染色体某个染色体某个(些些)位上的位上的基因。基因。 例如例如, 设设染色体染色体 s=11001101将其第三位上的将其第三位上的0变为变为1, 即即 s=11001101 11101101= s。 s也可以看做是原染色体也可以看做是原染色体s的子代染色的子代染色体。体。1.2 根本遗传算法 遗传算法根本流程框图生成初始种群计算顺应度选择-复制交叉变异生成新一代种群终止 ?终了 算法中的一些控制参数： 种群规模 最大换代数 交叉率(crossover rate)就是参与交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围普通为0.40.99。 变异率(mutation rate)
7、是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为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)所决议的选中时机，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率
8、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中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的顺应度，区间0,
9、 31就是一个(解)空间 。这样, 只需能给出个体x的适当染色体编码, 该问题就可以用遗传算法来处理。解(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取以下个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义顺应度函数, 取顺应度函数：f (x)=x2 (3) 计算各代种群中的各个体的顺应度, 并对其染色体进展遗传操作,直到顺应度最高的个体(即3111111)出现为止。 首先计算种群S1中各个体 s1= 13(01101), s2= 24(
10、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
11、.06 赌轮选择法在算法中赌轮选择法可用下面的子过程来模拟: 在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 6
12、4 0.06 0.69 0s4=10011 361 0.31 1.00 1于是，经复制得群体：s1 =1100024, s2 =0110113 s3 =1100024, s4 =1001119 交叉 设交叉率pc=100%，即S1中的全体染色体都参与交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=1100125, s2=0110012 s3=1101127, s4=1000016变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02位基因可以变异。 0.02位显然缺乏1位，所以本轮遗传操作不做变异。 于是，得到第二代种群S2： s
13、1=1100125, s2=0110012 s3=1101127, s4=1000016 第二代种群第二代种群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=1100125, s2= 0110012 s3=1101127, s4= 1000016 做交叉运算，让s1与s2，s3与s4 分
14、别交换后三位基因，得 s1 =1110028, s2 = 010019 s3 =1100024, s4 = 1001119 这一轮依然不会发生变异。 于是，得第三代种群S3： s1=1110028, s2=010019 s3=1100024, s4=1001119 第三代种群第三代种群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
15、=1110028, s2=1110028 s3=1100024, s4=1001119 做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=1111131, s2=1110028 s3=1100024, s4=1000016 这一轮依然不会发生变异。 于是，得第四代种群S4： s1=1111131, s2=1110028 s3=1100024, s4=1000016 显然，在这一代种群中曾经出现了顺应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111作为最终结果输出。然后，将染色体“11111解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中
16、，即得原问题的解，即函数y=x2的最大值为961。 YYy=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)作为一个个
17、体。这个序列中相邻两城之间的间隔之和的倒数就可作为相应个体s的顺应度，从而顺应度函数就是 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
18、第二位的C变为E，得 s1=A, E, B, E, D, A 可以看出，上面得到的s1， s2和s1都是非法的城市序列。 为此，对TSP必需设计适宜的染色体和相应的遗传运算。 现实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法处理了TSP。 遗传算法2.1 2.1 遗传算法特点遗传算法特点2.2 2.2 遗传算法的数学根底遗传算法的数学根底2.3 2.3 遗传算法的收敛性分析遗传算法的收敛性分析2.4 2.4 遗传算法改良遗传算法改良2.5
19、 2.5 遗传算法的交融遗传算法的交融 2.1 遗传算法的特点与优势 传统优化算法 - 枚举法：枚举出可行解集合内的一切可行解，以求出准确最优解。* 对于延续函数，要求先进展离散化处置。枚举空间比较大时，方法求解效率较低，甚至无法求解。 - 启发式算法：寻求一种能产生可行解的启发式规那么，已找到一个最优解或近似最优解。* 该方法的求解效率比较高，但对每一个需求解的问题必需找出其特有的启发式规那么，这个启发式规那么普通无通用性，不适宜于其他问题。 - 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进展搜索操作，已找到问题的最优解或近似最优解。* 该方法虽然保证不了可以获得问题的最优解
20、，但假设适当地利用一些启发式规那么，就可以在近似解的质量和效率上到达一种较好的平衡。遗传算法的主要特点 遗传算法普通是直接在解空间搜索, 而不像图搜索那样普通是在问题空间搜索, 最后才找到解，因此可以更加直接地运用。 遗传算法是一种随机搜索算法，搜索随机地始于搜索空间的一个点集，防止使得算法总是堕入到一样的部分极小点部分最优值。 遗传算法采用顺应度函数和遗传操作，从而设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样普通是从空间的一个点到另一个点地搜索。 因此它实践是一种并行搜索, 适宜大规模并行计算,
21、而且这种种群到种群的搜索有才干跳出部分最优解。遗传算法的顺应性强, 除需知顺应度函数外, 几乎不需求其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求延续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。遗传算法对应给定问题，可产生许多潜在解，并可由运用者来确定最终解。 2.2 遗传算法的数学根底u方式定理 u积木块假设 u方式是指种群个体基因串中的类似样板，它用来描画基因串中某些特征位一样的构造。在二进制编码中，方式是基于三个字符集(0,1,*)的字符串，符号*代表恣意字符，即 0 或者 1。 u对于二进制编码串，当串长为l时，共有
22、3l个不同的方式，遗传算法中串的运算实践上是方式的运算。u 方式例如：* 1 * u 表示四元子集010，011，110，111v与方式0*相比，方式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方式阶用来反映不同方式间确定性的差别，方方式阶用来反映不同方式间确定性的差别，
23、方式阶数越高，方式确实定性就越高，所匹配的式阶数越高，方式确实定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数一样样本数就越少。在遗传操作中，即使阶数一样的方式，也会有不同的性质，而方式的定义距的方式，也会有不同的性质，而方式的定义距就反映了这种性质的差别。就反映了这种性质的差别。 v方式定理方式定理v方式定理：具有低阶、短定义距以及平均顺应度高方式定理：具有低阶、短定义距以及平均顺应度高于种群平均顺应度的方式在子代中呈指数增长。于种群平均顺应度的方式在子代中呈指数增长。v方式定理保证了较优的方式遗传算法的较优解方式定理保证了较优的方式遗传算法的较优解的数目呈指数增长，为解释遗传算法机
24、理提供了数的数目呈指数增长，为解释遗传算法机理提供了数学根底。学根底。 v从方式定理可看出，有高平均顺应度、短定义距、低阶的方式，在延续的后代里获得至少以指数增长的串数目，这主要是由于选择使最好的方式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的方式，而普通突变概率又相当小，因此它对这些重要的方式几乎没有影响。 v积木块假设：积木块假设：v积木块假设：遗传算法经过短定义距、低阶以及积木块假设：遗传算法经过短定义距、低阶以及高平均顺应度的方式积木块，在遗传操作下高平均顺应度的方式积木块，在遗传操作下相互结合，最终接近全局最优解。相互结合，最终接近全局最优解。v 方式定理保证了较优方式的
25、样本数呈指数增长，方式定理保证了较优方式的样本数呈指数增长，从而使遗传算法找到全局最优解的能够性存在；从而使遗传算法找到全局最优解的能够性存在；而积木块假设那么指出了在遗传算子的作用下，而积木块假设那么指出了在遗传算子的作用下，能生成全局最优解。能生成全局最优解。 2.3 遗传算法的收敛性分析v 遗传算法要实现全局收敛，首先要求恣意初始种群经有限步都能到达全局最优解，其次算法必需由保优操作来防止最优解的遗失。与算法收敛性有关的要素主要包括种群规模、选择操作、交叉概率和变异概率。 v种群规模对收敛性的影响种群规模对收敛性的影响v通常，种群太小那么不能提供足够的采通常，种群太小那么不能提供足够的采
26、样点，以致算法性能很差；种群太大，样点，以致算法性能很差；种群太大，虽然可以添加优化信息，阻止早熟收敛虽然可以添加优化信息，阻止早熟收敛的发生，但无疑会添加计算量，呵斥收的发生，但无疑会添加计算量，呵斥收敛时间太长，表现为收敛速度缓慢。敛时间太长，表现为收敛速度缓慢。v选择操作对收敛性的影响选择操作对收敛性的影响v选择操作使高顺应度个体可以以更大的概率选择操作使高顺应度个体可以以更大的概率生存，从而提高了遗传算法的全局收敛性。生存，从而提高了遗传算法的全局收敛性。假设在算法中采用最优保管战略，即将父代假设在算法中采用最优保管战略，即将父代群体中最正确个体保管下来，不参与交叉和群体中最正确个体保
27、管下来，不参与交叉和变异操作，使之直接进入下一代，最终可使变异操作，使之直接进入下一代，最终可使遗传算法以概率遗传算法以概率1收敛于全局最优解。收敛于全局最优解。v交叉概率对收敛性的影响交叉概率对收敛性的影响v交叉操作用于个体对，产生新的个体，本交叉操作用于个体对，产生新的个体，本质上是在解空间中进展有效搜索。交叉概质上是在解空间中进展有效搜索。交叉概率太大时，种群中个体更新很快，会呵斥率太大时，种群中个体更新很快，会呵斥高顺应度值的个体很快被破坏掉；概率太高顺应度值的个体很快被破坏掉；概率太小时，交叉操作很少进展，从而会使搜索小时，交叉操作很少进展，从而会使搜索停滞不前，呵斥算法的不收敛。停
28、滞不前，呵斥算法的不收敛。 v变异概率对收敛性的影响变异概率对收敛性的影响v变异操作是对种群方式的扰动，有利于添变异操作是对种群方式的扰动，有利于添加种群的多样性加种群的多样性 。但是，变异概率太小那。但是，变异概率太小那么很难产生新方式，变异概率太大那么会么很难产生新方式，变异概率太大那么会使遗传算法成为随机搜索算法。使遗传算法成为随机搜索算法。 v遗传算法的本质遗传算法的本质v遗传算法本质上是对染色体方式所进展的一遗传算法本质上是对染色体方式所进展的一系列运算，即经过选择算子将当前种群中的系列运算，即经过选择算子将当前种群中的优良方式遗传到下一代种群中，利用交叉算优良方式遗传到下一代种群中
29、，利用交叉算子进展方式重组，利用变异算子进展方式突子进展方式重组，利用变异算子进展方式突变。经过这些遗传操作，方式逐渐向较好的变。经过这些遗传操作，方式逐渐向较好的方向进化，最终得到问题的最优解。方向进化，最终得到问题的最优解。 2.4 遗传算法的改良 u自从1975年J.H. Holland系统提出遗传算法的完好构造和实际以来，众多学者不断努力于推进遗传算法的开展，对编码方式、控制参数确实定、选择方式和交叉机理等进展了深化研讨，引入了动态战略和自顺应战略以改善遗传算法的性能，提出了各种变形的遗传算法。u 根本改良途径概括起来包括u改动遗传算法的组成成分或运用技术，如选用优化控制参数、适宜问题
30、特性的编码技术等u采用混合遗传算法u采用动态自顺应技术，在进化过程中调整算法控制参数和编码粒度u采用非规范的遗传操作算子u采用并行遗传算法v对编码方式的改良对编码方式的改良v二二进进制制编编码码优优点点在在于于编编码码、解解码码操操作作简简单单，交交叉叉、变变异异等等操操作作便便于于实实现现，缺缺陷陷在在于于精精度度要要求求较较高高时时，个个体体编编码码串串较较长长，使使算算法法的的搜搜索索空空间间急急剧剧扩扩展展，遗遗传传算算法法的的性性能能降降低低。格格雷雷编编码码抑抑制制了了二二进进制制编编码码的的不不延延续续问问题题 ，浮浮点数编码改善了遗传算法的计算复杂性点数编码改善了遗传算法的计算
31、复杂性 。 对遗传算子对遗传算子 的改良的改良v排序选择 v均匀交叉 v逆序变异1 对群体中的一切个体按其顺应度大小进展降序排序；2 根据详细求解问题，设计一个概率分配表，将各个概率值按上述陈列次序分配给各个个体；3 以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。 对遗传算子对遗传算子 的改良的改良v排序选择 v均匀交叉 v逆序变异1 随机产生一个与个体编码长度一样的二进制屏蔽字P = W1W2Wn ；2 按以下规那么从A、B两个父代个体中产生两个新个体X、Y：假设Wi = 0，那么X的第i个基因承继A的对应基因，Y的第i个基因承继B的对应基因；
32、假设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等人提出自顺应遗传算法，即PC和Pm可以随顺应度自动改动，当种群的各个个体顺应度趋于一致或趋于部分最优时，使二者
33、添加，而当种群顺应度比较分散时，使二者减小，同时对顺应值高于群体平均顺应值的个体，采用较低的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进展变异操作对新的N个子种群重新开场遗传算法操作性能满足?终了并行遗传算法并行遗传算法p
34、arallel GA，PGAv遗传算法中顺应度的计算最费时间，再加上需求不断产生新一代，而每一代又有假设干个个体，随意如何提高遗传算法的运转速率显得尤为突出。由于遗传算法的内在并行机制，其并行处置是很自然的处理途径。v并行遗传算法的实现方案v全局型主从式方式master-slave modelv独立型粗粒度模型coarse-grained model；孤岛模型；分布式遗传算法v分散型细粒度模型fine-grained model v全局型v处置方式：并行系统分为一个主处置器和假设干个从处置器主处置器监控整个染色体种群，并基于全局统计执行选择操作；各个从处置器接受来自主处置器的个体进展重组交叉和
35、变异，产生新一代个体，并计算顺应度，再把计算结果传给主处置器。v缺陷：顺应度评价很费时且远远超越通讯时间有效的情况下才有效，否那么通讯时间超越计算时间，反而会降低速度。这种方法要求同步机制，会导致主进程忙二子进程闲置或反之，引起负载不平衡，效率不高。v独立型独立型v处置方式：将种群分成假设干个子种群并分配处置方式：将种群分成假设干个子种群并分配给各自对应的处置器，每个处置器不仅独立计给各自对应的处置器，每个处置器不仅独立计算顺应度，而且独立进展选择、重组交叉和变算顺应度，而且独立进展选择、重组交叉和变异操作，还要定期地相互传送顺应度最好的个异操作，还要定期地相互传送顺应度最好的个体，从而加快满
36、足终止条件的要求。体，从而加快满足终止条件的要求。v特点：基于粗粒度模型的遗传算法也称之为分特点：基于粗粒度模型的遗传算法也称之为分布式遗传算法，是目前运用最广泛的一种并行布式遗传算法，是目前运用最广泛的一种并行遗传算法。遗传算法。v分散型分散型v处置方式：为种群中的每一个个体分配一个处处置方式：为种群中的每一个个体分配一个处置器，每个处置器进展顺应度的计算，而选择、置器，每个处置器进展顺应度的计算，而选择、重组交叉和变异操作仅在与之相邻的一个处置重组交叉和变异操作仅在与之相邻的一个处置器之间相互床底个体中进展。器之间相互床底个体中进展。v特点：细粒度模型也称邻域模型，适宜于衔接特点：细粒度模
37、型也称邻域模型，适宜于衔接机、阵列机。机、阵列机。v并行遗传算法的迁移战略并行遗传算法的迁移战略v迁移是并行遗传算法中引入的一个新的算子，迁移是并行遗传算法中引入的一个新的算子，它是指在进化的过程中子群体间交换个体的过它是指在进化的过程中子群体间交换个体的过程，普通的迁移方法是将子群体中最好的个体程，普通的迁移方法是将子群体中最好的个体发给其它的子种群，经过迁移可以加快较好个发给其它的子种群，经过迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度。体在群体中的传播，提高收敛速度和解的精度。v以基于粗粒度模型的并行以基于粗粒度模型的并行遗传算法算法为例，迁移例，迁移战略可分略可分为以以下
38、两种：下两种：v一一传多：每个多：每个处置器置器对易于假易于假设干相干相邻处置器，将其最好置器，将其最好传给一切相一切相邻处置器，并接受来自相置器，并接受来自相邻处置器的最好的个体，置器的最好的个体，将将这些个体与本人个体同些个体与本人个体同时思索，淘汰思索，淘汰顺应度差的个体。度差的个体。v一一传一：每个一：每个处置器将其最好置器将其最好传给与之相与之相邻的一个的一个处置器，置器，同同时添加添加“处置器之置器之间通通讯的的频率和率和“每次每次传送送给最好个体最好个体的数目两个参数。的数目两个参数。v处置器之间通讯的频率 send_ratev如send_rate=3时，表示当遗传代数是3的倍数
39、时，各处置器之间相互传送个体。v每次传送给最好个体的数目send_bestvsend_best=5时表示每个处置器把最好的前5个个体传给各自相邻的处置器2.5 遗传算法的交融 v遗传算法在人工智能的众多领域便得到了广泛运用。例如机器学习、聚类、控制、规划、设计、调度、组合优化、函数的最大值以及图像处置和信号处置等等。v另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解才干得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已获得了不少成果。 v混合遗传算法v引入部分搜索过程v添加编码变换操作过程vDe Jong提出下面三个根本原那么v尽量采用原有算法的编码v利用原有算法全局搜索的优点v改良遗传算子v遗传算法与最速下降法相结合v遗传算法与模拟退火算法相结合v遗传算法与神经网络的结合：v遗传算法用于神经网络主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑构造；用遗传算法来取代一些传统的学习算法，利用GA的寻优才干获取最正确权重。v目前广泛研讨的是BP神经网络+遗传算法确定BP网络的衔接权，发扬网络的泛化才干，而且使网络具有快速收敛及加强式学习性能
