基于遗传算法的随机优化搜索

第4章 基于遗传算法的随机优化搜索4.1 基本概念4.2 基本遗传算法4.3 遗传算法应用举例4.4 遗传算法的特点与优势4.1 基本概念 1. 个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。 3. 染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符 也就称为基因（gene）。例如：个体 染色体9 - 1001（2，5，6）- 010 101 1104. 遗传操作亦称遗传算子(genetic operator)，就是关 于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(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位基因, 即变异 就是改变染色体某个(些)位上的基因。例如, 设染色体 s=11001101将其第三位上的0变为1, 即s=11001101 11101101= s。s也可以看做是原染色体s的子代染色体。4.2 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止 ?结束算法中的一些控制参数： 种群规模 最大换代数 交叉率(crossover 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)所决定的选中机会， 每次从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； 4.3 遗传算法应用举例 例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。 y=x231 XY分析 原问题可转化为在区间0, 31中搜索能 使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）)出现为止。 首先计算种群S1中各个体s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的适应度f (si) 。容易求得f (s1) = f(13) = 132 = 169f (s2) = f(24) = 242 = 576f (s3) = f(8) = 82 = 64f (s4) = f(19) = 192 = 361再计算种群S1中各个体的选择概率。选择概率的计算公式为由此可求得P(s1) = P(13) = 0.14P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06P(s4) = P(19) = 0.31赌轮选择示意s4 0.31s2 0.49s1 0.14s30.06 赌轮选择法在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1<rqk(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 =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中共有5×4×0.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假设这一轮选择-复制操作中，种群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中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 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=11111（31）, s2=11100（28）s3=11000（24）, s4=10000（16） 显然，在这一代种群中已经出现了适应度 最高的染色体s1=11111。于是，遗传操作终止 ，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型， 即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即 函数y=x2的最大值为961。 YYy=x28 13 19 24 X第一代种群及其适应度y=x212 16 25 27 XY第二代种群及其适应度y=x29 19 24 28 XY第三代种群及其适应度y=x216 24 28 31 X第四代种群及其适应度例 4.2 用遗传算法求解TSP。分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。（1）定义适应度函数我们将一个合法的城市序列s=（c1, 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）实施常规的交叉或变异操作，如交换后三位，得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提出了许多编码方法和相应的特殊化了的交叉、变异操作， 如顺序编码或整数编码、随机键编码、部分 映射交叉、顺序交叉、循环交叉、位置