人工智能导论课件第4章 基于遗传算法的随机优化搜索.pptx
《人工智能导论课件第4章 基于遗传算法的随机优化搜索.pptx》由会员分享,可在线阅读,更多相关《人工智能导论课件第4章 基于遗传算法的随机优化搜索.pptx(22页珍藏版)》请在文库网上搜索。
1、 第4章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势 4.1 基本概念 1染色体及其编码染色体及其编码 遗传算法以生物细胞中的染色体(chromosome)代表问题中个体对象(即可能解)。一般用字符串表示,而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象,则我们就可以用它的二进制数串1001作为它的染色体编码。2.适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的适应程度,而对所求解问题中的对象(即染色体)设计的一种表征优劣的测度。适应度函数(fitness
2、 function)就是问题中的全体对象与其适应度之间的一个对应关系,即对象集合到适应度集合的一个映射。3.种群种群 种群(population)就是模拟生物种群而由若干个染色体组成的群体,它一般是整个论域空间的一个很小的子集。遗传算法就是通过在种群上实施所称的遗传操作,使其不断更新换代而实现对整个论域空间的搜索。4.遗传操作遗传操作 遗传算法中有三种关于染色体的运算:选择-复制*、交叉和变异,称为遗传操作或遗传算子(genetic operator)。选择-复制 选择概率P(xi)的计算公式为其中,f为适应度函数,f(xi)为xi的适应度。按概率选择的方法可用一种称为赌轮的原理来实现。算法中
3、赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的伪随机数r;若rq1,则染色体x1被选中;若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率,其计算公式为交叉 交叉(crossover)亦称交换、交配或杂交,就是互换两个染色体某些位上的基因。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即则得新串s1=01000101,s2=10011011。s1和s2可以看作是原染色体s1和s2的子代染色体。变异 变异(Mutation)亦称突变,就是改变染色体某个(些)位上的基因。例如,把染色体s=110
4、01101的第三位上的0变为1,则得到新染色体s=11101101。4.2 基本 遗传 算法4.3 遗传算法应用举例 例 4-1 利用遗传算法求区间0,31上的二次函数y=x2的最大值。解 (1)定义适应度函数,编码染色体。将函数f(x)=x2就可作为空间U上的适应度函数。(2)设定种群规模,产生初始种群。将种群规模设定为4,取染色体 s1=01101(13),s2=11000(24)s3=01000(8),s4=10011(19)组成初始种群S1。(3)计算各代种群中的各染色体的适应度,并进行遗传操作,直到适应度最高的染色体(该问题中显然为“11111”=31)出现为止。计算S1中各染色体的
5、适应度、选择概率、积累概率等并列表于表4-1中。选择-复制 设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503 按赌轮选择法,染色体s1,s2,s3,s4的被选中次数依次为:1,2,0,1。经复制得群体:s1=11000(24),s2=01101(13)s3=11000(24),s4=10011(19)交叉 设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。将s1与s2配对,s2与s4配对,分别交换后两位基因,得新染色体:s1=11001(25),s2=01100(12)s3=11011(27),s4=10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能导论课件第4章 基于遗传算法的随机优化搜索 人工智能 导论 课件 基于 遗传 算法 随机 优化 搜索