遗传算法简述.ppt
《遗传算法简述.ppt》由会员分享,可在线阅读,更多相关《遗传算法简述.ppt(80页珍藏版)》请在三一文库上搜索。
1、遗传算法,1.1 基本概念 1.2 基本遗传算法 1.3 遗传算法应用举例,遗传算法(Genetic Algorithm) 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 最初由美国Michigan大学J.Holland教授于1975年首先提出来,并出版了颇有影响的专著Adaptation in Natural and Artificial Systems,GA这个名称才逐渐为人所知,J.Holland教授所提出的GA通常为简单遗传算法(SGA)。,1.1 基本概念 1. 个体与种
2、群 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼,一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。,2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,3. 染色体与基因 染色体(chromosome)就是问题中个体的某
3、种字符串形式的编码表示。字符串中的字符也就称为基因(gene)。 例如: 个体 染色体 9 - 1001 (2,5,6)- 010 101 110,4. 遗传操作 亦称遗传算子(genetic operator),就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover,亦称交换、交配或杂交) 变异(mutation,亦称突变),选择-复制 通常做法是:对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。,交叉 就是互换两个染色体某些位上的
4、基因。,s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。,例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即,变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101 将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。,1.2 基本遗传算法,算法中的一些控制参数: 种群规模 最大换代数 交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例,记为Pc,取值范围一般为0.40.99。 变
5、异率(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个染
6、色体组成群体S1; 步6 按交叉率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的最大值。,分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么,0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的
7、适应度,区间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(01
8、101), 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(8) = 0.06 P(s4) = P(19) = 0.31,赌轮选择示意, 赌轮选
9、择法,在算法中赌轮选择法可用下面的子过程来模拟: 在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 =11000(24), s2 =01101(13) s3 =11000(24), s4 =10011(19),交叉 设交叉率pc=100%,即S1
10、中的全体染色体都参加交叉运算。 设s1与s2配对,s3与s4配对。分别交换后两位基因,得新染色体: s1=11001(25), s2=01100(12) s3=11011(27), 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中各染色体的情况,假设这一轮选择-复制操作中,种群S2中的 4个染色体都被选中,则得到群体
11、:,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(28), s2=11100(28) s3=11000(24), s
12、4=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
13、=x2的最大值为961。,Y,例 1.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序列,即n个城市的一个排列,都可以事先构造出来。于是,我们就可以直接在解空间(所有合法的城市序列)中搜索最佳解。这正适合用遗传算法求解。,(1)定义适应度函数 我们将一个合法的城市序列s=(c1, c2, , cn, cn+1)(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度,从而适应度函数就是,(2)对个体s=(c1, c2, , cn, cn+1)进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当,就会在实施交叉
14、或变异操作时出现非法城市序列即无效解。 例如,对于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提出了
15、许多编码方法和相应的特殊化了的交叉、变异操作,如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。,遗传算法,2.1 遗传算法特点 2.2 遗传算法的数学基础 2.3 遗传算法的收敛性分析 2.4 遗传算法改进 2.5 遗传算法的融合,2.1 遗传算法的特点与优势,传统优化算法 - 枚举法:枚举出可行解集合内的所有可行解,以求出精确最优解。 * 对于连续函数,要求先进行离散化处理。枚举空间比较大时,方法求解效率较低,甚至无法求解。,- 启发式算法:寻求一种能产生可行解的启发式规则,已找到一个最优解或近
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 简述
链接地址:https://www.31doc.com/p-2973107.html