遗传算法算例课件

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

1、第4章 基于遗传算法的随机优化搜索4.1 4.1 基本概念基本概念4.2 4.2 基本遗传算法基本遗传算法4.3 4.3 遗传算法应用举例遗传算法应用举例4.4 4.4 遗传算法的特点与优势遗传算法的特点与优势 遗传算法算例 4.1 基本概念 1. 1. 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。遗传算法算例 2. 2. 适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个

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

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

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

5、e)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为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个染色体组成群

6、体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取最大值的点a的问题。那么，0, 31 中的点

7、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（111

8、11）)出现为止。 遗传算法算例 首先计算种群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(

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

10、色体 适应度选择概率积累概率选中次数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）

11、, 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=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s

12、4=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）, s2=01001（9） s3=11000（24）, s4=1001

13、1（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）, s2=11100（28） s3=110

14、00（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 27

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

16、对个体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,

17、A） 可以看出，上面得到的s1， s2和s1都是非法的城市序列。遗传算法算例 为此，对TSP必须设计合适的染色体和相应的遗传运算。 事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。 遗传算法算例4.4 遗传算法的特点与优势 遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才

18、找到解。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 遗传算法算例 遗传算法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。遗传算法算例遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法

19、长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 遗传算法算例遗传算法的应用v遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。遗传算法算例v另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。 遗传算法算例 对遗传算法的进一步研究将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。遗传算法算例