《人工智能导论-》-03搜索-03

《《人工智能导论-》-03搜索-03》由会员分享，可在线阅读，更多相关《《人工智能导论-》-03搜索-03（42页珍藏版）》请在金锄头文库上搜索。

1、人工智能导论方若宇 2009年秋季汕头大学计算机系本科课程遗传算法群体种群子群选择婚配变异遭淘汰 的群体达尔文进化论：“物竞天择、适者生存” 70年代由美国的密执根大学的Holland教授首先 提出遗传算法。近年来，遗传算法作为一种有效的工具，已广 泛地应用于最优化问题求解之中。 生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程生物进化与遗传算法之间的对应关系 遗传算法的三个主要操作

2、选择 交配 变异 “轮盘赌”法 ：设群体的规模为N，F(xi)(i=1, ., N)是其中N个染色体的适应值。则第i个染 色体被选中的概率由下式给出： 选择 x1x2x3x4x5x6“确定性”法 对于规模为N的群体，一个选择概率为p(xi)的染色体xi被选择次数的期望 值e(xi)： 1. 对于群体中的每一个xi，首先选择 次。这样共得到 个染色体。2.按照 从大到小对染色体排序，依次取出 个染色体. 3.两次得到的染色体合起来就得到了N个染色体。 交配交配发生在两个染色体之间，由两个被称之为双亲的父代染色体 ，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色 体采用二进制形式编码时

3、，交配过程是以这样一种形式进行的： a1 a2 . ai ai+1 . an b1 b2 . bi bi+1 . bna1 a2 . ai bi+1 . bn b1 b2 . bi ai+1 . an交配前交配后交配位置变异变异发生在染色体的某一个基因上，当以二进制编码时，变异的基 因由0变成1，或者由1变成0。如对于染色体x=11001，如果变异位发生在第三位，则变异后的染色体变成了y=11101。 遗传算法:1.给定群体规模N，交配概率pc和变异概率pm，t0；2.随机生成N个染色体作为初始群体；3.对于群体中的每一个染色体xi分别计算其适应值F(xi)；4.如果算法满足停止准则，则转（1

4、0）；5.对群体中的每一个染色体xi计算概率；6.依据计算得到的概率值，从群体中随机的选取N个染色体，得到种群；7.依据交配概率pc从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；8.依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；9.用新群体代替旧群体，t=t+1，转3；10.进化过程中适应值最大的染色体，经解码后作为最优解输出；11.结束。 例. 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。 y=x231 XY分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 3

5、1 中的点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）)出现为止

6、。第0代情况表 1. 对于群体中的每一个xi，首先选择 次。这样共得到 个染色体。2.按照 从大到小对染色体排序，依次取出 个染色体. 3.两次得到的染色体合起来就得到了N个染色体。 a序 号群体适应值选择概率（）期望次数选中次数101101(13)16914.440.581211000(24)57649.231.972301000(8)64 5.470.220410011(19)36130.851.2310代最大适应值=576，平均适应值=292.5序号种群交配对像交配位子代适应值101101 (13)2401100(12)144211000 (24)1411001(25)625311000

7、 (24)4211011(27)729410011 (19)3210000(16)256第0代种群的交配情况 序 号群体适应值选择概率（ ）期望次数选中次数101100 (12)144 8.210.330211001 (25)62535.621.421311011 (27)72941.561.662410000 (16)25614.600.581第1代情况表 交配后1代最大适应值=729，平均适应值=438.5序号种群交配对像交配位子代适应值111001 (25)2311011 (27)729211011 (27)1311001 (25)625311011 (16)4110000 (16)25

8、6410000 (27)3111011 (27)729第1代种群的交配情况 最大适应值=729，平均适应值=584.75 过早地陷入局部最优解的现象称为早熟。 防止出现早熟现象的方式有：1.扩大群体规模2.变异已经不可能通过交配达到最优解 ，出现早熟现象。序号种群是否变异变异位新群体适应值111001 (25)N11011 (27)729211011 (27)Y311101 (29)841311011 (16)N10000 (16)256410000 (27)N11011 (27)729第1代变异情况 如果在第1代群体交配之后的子代中发生了变异。序 号群体适应值选择概率（ ）期望次数选中次数1

9、11011 (27)72928.531.141211101 (29)84132.921.311310000 (16)25610.020.401411011 (27)72928.531.141第2代情况表 序号种群交配对像交配位子代适应值111011 （27）2311001（ 25）625211101 （29）1311111（ 31）961310000 （16）4410001（ 17）289411011 （27）3411010（ 26）676第2代种群的交配情况 最大适应值=961，平均适应值=637.75，刚好找到了该问题的最优解， 其对应的染色体是11111，x=31Yy=x28 13 19

10、 24 X第0代种群及其适应度y=x212 16 25 27 XY第1代种群及其适应度y=x216 19 27 29 XY第2代种群及其适应度Yy=x217 2526 31 X第3代种群及其适应度最大适应值、平均适应值进化曲线 赌轮选择示意s4 0.31s2 0.49s1 0.14s30.06赌轮选择法的例子在算法中赌轮选择法可用下面的子过程来模 拟: 在0, 1区间内产生一个均匀分 布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体 xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积累概率, 其计算公式为 赌轮选择法的例子：设从区间0,

11、 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色体 适应度选择概率积累概率选中次数01101 169 0.14 0.14 111000 576 0.49 0.63 201000 64 0.06 0.69 010011 361 0.31 1.00 1用遗传算法求解TSP。分析： 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。（1）定义适应度函数我们将一个合法的城市序列s=（c1,

12、 c2, , cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体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）实施常规的交叉或变异操作，如交换后三位，得s

13、1=（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提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、 随机键编码、部分映射交叉、顺序交叉、循环交叉、位 置交叉、反转变异、移位变异、互换变异等等。从而巧 妙地用遗传算法解决了TSP。 如果在进化过程中，遗传算法每次保留到目前为止 的最好解，并且算法以交配和变异为其随机化操作， 则对于一个全局最优化问

14、题，当进化代数趋于无穷时 ，遗传算法找到最优解的概率为1。 遗传算法的收敛性在线比较法:该方法用当前代中染色体的平均指标函数值来刻划算法的变化趋势 。计算方法如下：其中T为当前代中染色体的个数 。离线比较法:该方法与在线比较法有些相似，但是用进化过程中每代最好解的指 标函数值的平均值，来评价算法的进化过程。计算方法如下：其中T是到目前为止的进化代数，f*(t)是第t代中，染色体的最好指标函数值。 当进化代数趋于无穷时，遗传算法找到最优解的概率为1。即保证了遗传算 法的收敛性。但在实际计算时，希望随时了解遗传算法的进展情况，监视算法的变化趋势。 当前最好法:在每一代进化过程中，记录得到的最好解，

15、通过最好解的变化 ，了解算法的变化趋势。不同的算法之间，也可以通过该最好解的变化情况 进行横向比较。遗传算法的评价适应函数 一般情况下，我们可以直接选取问题的指标函数作为适应函数。 如求函数f(x)的最大值，就可以直接采用f(x)为适应函数。但在 有些情况下，函数f(x)在最大值附近的变化可能会非常小，以至 于他们的适应值非常接近，很难区分出那个染色体占优。在这种 情况下，希望定义新的适应函数，要求该适应函数与问题的指标 函数具有相同的变化趋势，但变化的速度更快。 非线性加速适应函数 其中f(x)是问题的指标函数，fmax是当前得到的最优指标函数值，M是一个充分大的数。 线性加速适应函数 上式中的第一个方程表示变换前后的平均值不变，第二个方程表示将当前的最优值放大为平均值的M倍。 遗传算法的特点 遗传算法是一个随机搜索算法，利用概率转移规则，而非确定性规则。适用于数值求解具有多参数、多变量、多目标等复杂的最优化问题。在经过编码以后，遗传算法几乎不需要任何与问题有关的知识，唯一需 要的信息是适应值