遗传算法PPT课件.ppt

1、第4章 基于遗传算法的随机优化搜索4.1 4.1 基本概念基本概念4.2 4.2 基本遗传算法基本遗传算法4.3 4.3 遗传算法应用举例遗传算法应用举例4.4 4.4 遗传算法的特点与优势遗传算法的特点与优势 第 4 章 基于遗传算法的随机优化搜索 v遗传算法（Genetic AlgorithmGA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位 第 4 章 基于遗

2、传算法的随机优化搜索 遗传算法的基本原理v遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程第 4 章 基于遗传算法的随机优化搜索 v群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它

3、本身是否完全正确并不重要（目前生物界对此学说尚有争议）第 4 章 基于遗传算法的随机优化搜索 序号序号遗传学概念遗传学概念遗传算法概念遗传算法概念数学概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解9交叉一组染色体上对

4、应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间0,1上的一个值，一般为0.650.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值, 一般为0.0010.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解 4.1 基本概念 1. 1. 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组

5、成的群体, 它一般是整个搜索空间 的一个很小的子集。 2. 2. 适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。 3. 3. 染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010

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

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

8、色体总数的比例，记为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)所决定的选中机会，每次从S中随机

9、选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； 步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3； 4.3 遗传算法应用举例 例例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY 分析 原问题可转化为在区间0, 31中搜索能使y取最大值的

10、点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) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即

11、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) = 192 = 361再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49

12、 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)的积累概率积累概率, 其计算公式为 ijjixPq1)(选择-复制 设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.9850

13、3 染色体 适应度选择概率积累概率选中次数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配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=1000

14、0（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=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1 假设这

15、一轮选择-复制操作中，种群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）, s2=01001（9） s3=11000（24）, s4=10011（19） 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体

16、适应度选择概率积累概率 估计的选中次数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）, s2=11100（28） s3=11000（24）, s4=10000（16） 这一轮仍然不会发生变异。 于是，得第四代种群S4： s1=11

17、111（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 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度例

18、4.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。（1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 niiiccdsf11),(1)(（2）对个体s=（c1, c2, , cn, cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或

19、变异操作时出现非法城市序列即无效解。 例如，对于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和s1都是非法的城市序列。 为此，对TSP必须设计合适的染色体和相应的遗传运算。 事实上，人们针对TSP提出了许多编码

20、方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。 第 4 章 基于遗传算法的随机优化搜索 v例4.3设 ，求 v解：v（1）编码和产生初始群体v首先第一步要确定编码的策略，也就是说如何把 到-1，2这个区间内的数用计算机语言表示出来v编码就是表现型到基因型的映射，编码时要注意以下三个原则：v完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体

21、位串）的表现型；v健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；v非冗余性：染色体和潜在解必须一一对应 5 . 02)(2xxxf2 , 1),(maxxxf第 4 章 基于遗传算法的随机优化搜索 v这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个0，1二进制串当然，串长取决于求解的精度如果要设定求解精度到六位小数，由于区间长度为3 ，则必须将闭区间-1,2分为 等分因为 所以编码的二进制串至少需要22位v将一个二进制串（b21b20b19b1b0）转化为区间-1,2 内对应的实数值很简单，只需采取以下两步 6103第 4 章 基于遗传算法的随机

22、优化搜索 v1）将一个二进制串（b21b20b19b1b0）代表的二进制数化为10进制数：v2） 对应的区间-1,2内的实数：第 4 章 基于遗传算法的随机优化搜索 v例如，一个二进制串a=表示实数0.637197v x=(10101000111)2=2288967v二进制串，则分别表示区间的两个端点值-1和2v利用这种方法我们就完成了遗传算法的第一步编码，这种二进制编码的方法完全符合上述的编码的三个原则v首先我们来随机的产生一个个体数为4个的初始群体如下：第 4 章 基于遗传算法的随机优化搜索 vpop(1)=v， % a1v， % a2v， % a3v % a4v化成十进制的数分别为：vp

23、op(1)= 1.523032，0.574022 ，-0.697235 ，0.247238 第 4 章 基于遗传算法的随机优化搜索 v（2）定义适应函数和适应值v由于给定的目标函数 在-1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础v对于本题中的最大化问题，定义适应函数 ，采用下述方法：第 4 章 基于遗传算法的随机优化搜索 v式中 Fmin既可以是特定的输入值，也可以是当前所有代或最近K代中 f(x)的最小值，这里为了便于计算，将采用了一个特定的输入值v若取Fm

24、in=-1 ，则当f(x)=1 时适应函数g(x)=2 ；当f(x)=-1.1 时适应函数g(x)=0 v由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下vf pop(1)= 1.226437 , 1.318543 , -1.380607 , 0.933350 v然后通过适应函数计算出适应值分别如下v取Fmin=-1 ，vgpop(1)= 2.226437 , 2.318543 , 0 , 1.933350 第 4 章 基于遗传算法的随机优化搜索 v（3）确定选择标准v这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率其计算公式如下：v对于给定的规

25、模为n的群体pop=a1,a2,a3,an ，个体 的适应值为g(ai) ，则其入选概率为第 4 章 基于遗传算法的随机优化搜索 v由上述给出的群体，我们可以计算出各个个体的入选概率v首先可得 ，v然后分别用四个个体的适应值去除以 ，得：vP(a1)=2.226437 / 6.478330 = 0.343675 % a1vP(a2)=2.318543 / 6.478330 = 0.357892 % a2vP(a3)= 0 / 6.478330 = 0 % a3vP(a4)=1.933350 / 6.478330 = 0.298433 % a4第 4 章 基于遗传算法的随机优化搜索 v（4）产生

26、种群v计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群v由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的种群得到newpop(1)如下：vnewpop(1)=v， % a1v， % a2v， % a2v % a4第 4 章 基于遗传算法的随机优化搜索 v（5）交叉v交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体v我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉（可以在任一位进行交叉）v ， v 交叉得：v， v v ， v

27、 交叉得：v， 第 4 章 基于遗传算法的随机优化搜索 v通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：vjchpop(1)=v，v，v，v第 4 章 基于遗传算法的随机优化搜索 v（6）变异v变异也就是通过一个小概率改变染色体位串上的某个基因v现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：vpop(2)= v，v，v，v v然后重复上述的选择、交叉、变异直到满足终止条件为止第 4 章 基于遗传算法的随机优化搜索 v（7）终止条件v遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为50

28、代，此时就可能得出最优解此种方法简单易行，但可能不是很精确（Matlab程序参见附录1）；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制第 4 章 基于遗传算法的随机优化搜索 Matlab程序v求解过程为：v群体中包含六个染色体，每个染色体用22位01码，变异概率为0.01，变量区间为-1，2，取Fmin=-2 ，遗传代数为50代，则运用第一种终止条件（指定遗传代数）的Matlab程序为：vCount,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)v执行结果为：vCount =

29、v 50vResult =v 1.0316 1.0316 1.0316 1.0316 1.0316 1.0316v 1.4990 1.4990 1.4990 1.4990 1.4990 1.4990vBestMember =v 1.0316v 1.4990第 4 章 基于遗传算法的随机优化搜索 v我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当 x取1.0316时，maxf(x)=1.4990 v当然这个解和实际情况还有一点出入（应该是 取1时， ），但对于一个计算机算法来说已经很不错了第 4 章 基于遗传算法的随机优化搜索 4.4 遗传算法的特点与优势 遗传算

30、法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 遗传算法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。遗传算法的适

31、应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 遗传算法的应用v遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。v另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。 66写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢聆听 学习就是为了达到一定目的而努力去干, 是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard, Is A Process To Overcome Various Difficulties For A Goal