人工智能及其应用 教学课件 作者 孔月萍 周继chapter6_071103.ppt

《人工智能及其应用 教学课件 作者 孔月萍 周继chapter6_071103.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章遗传算法内容提要：遗传算法及其数学基础遗传算法的设计改进的遗传算法协进化算法1人工智能及其应用6.1遗传算法及其数学基础标准遗传算法及基本术语模式定理2人工智能及其应用标准遗传算法及基本术语标准遗传算法基本流程：参数编码初始群体设定适应度函数的设计遗传操作:选择、交叉、变异控制参数设定进化停止准则3人工智能及其应用模式定理模式基于三值字符集{0,1,*}所产生的可描述某种结构相似性的字符串称为模式。模式是描述个体字符串集的模板。模式的阶模式H中确定位置（位）的个数称为该模式的阶，记为O(H)。模式的定义距模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记为。4人工

2、智能及其应用模式定理选择操作对模式的影响交叉操作对模式的影响变异操作对模式的影响5人工智能及其应用模式定理经选择、交叉、变异操作后,子代中模式H的数目为：模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将以指数级增长。6人工智能及其应用模式定理积木块假设：低阶、短距、高平均适应度的模式（积木块）在遗传算子的作用下相互结合，能生成高阶、长距、高平均适应度的模式，并最终生成全局最优解。模式定理保证了较优模式的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找全局最优解的可能性。而积木块假设则指出，遗传算法具备寻

3、找到全局最优解的能力，即积木块在遗传算子的作用下，能生成高阶、长距、高平均适应度的模式，并最终生成全局最优解。7人工智能及其应用6.2遗传算法的设计编码初始群体设定适应度函数选择算子交叉算子变异算子8人工智能及其应用编码二进制编码十进制编码Gray编码多参数映射编码可变长度染色体编码多维染色体编码9人工智能及其应用初始群体设定群体规模的确定:群体规模大→个体多样性高→陷入局部解的危险小。但是规模太大→计算量加大。如果群体规模小→遗传算法在搜索空间中的分布范围受限→搜索过程可能提前停止于未成熟阶段(引起未成熟收敛)→必须保持群体的多样性。10人工智能及其应用初始群体设定初始群体的生成：遗传算法

4、中，初始群体中的个体可以根据具体的编码方法、在尽可能满足群体多样性的前提下随机产生。先随机生成一定数目的个体，然后从中挑选出性能优良的个体加入到群体中。重复该过程，直至满足群体规模。11人工智能及其应用适应度函数将目标函数映射为适应度函数：如果待求解问题是使目标函数最小，则GA中可采用如下变换：当原目标函数是求最大化的利润或效用函数时，可以按照下式变换：12人工智能及其应用适应度函数适应度调整：线性调整线性调整出现非负现象13人工智能及其应用选择算子适应度比例法:也称为轮盘赌法。群体中适应度值大的个体被选择的概率大，而适应度值低的个体被选择概率低。14人工智能及其应用选择算子最佳个体保存法(

5、精英选择法):群体中适应度最高的个体不经过遗传操作，直接复制到下一代群体中群体中。排序选择方法:根据适应度的大小对个体进行排序，然后把事先设计好的概率表分配给个体，作为各自的选择概率。个体的选择概率与其适应度无直接关系，仅与其在群体中的排序相关。15人工智能及其应用选择算子联赛选择方法:从群体中任意选择一定数量的个体（称为联赛规模），将其中适应度最高的个体保存到下一代。反复执行该过程，直到保存到下一代的个体数目达到预先设定的数目为止。联赛规模一般取2。16人工智能及其应用交叉算子单点交叉多点交叉17人工智能及其应用交叉算子一致交叉通过屏蔽字来决定新个体对父辈个体基因位的继承。屏蔽字可以随机生

6、成，由于概率的因素，会使模式被破坏的机率增加。18人工智能及其应用变异算子基本变异算子对二值编码，随机选择c个基因位作为待变异位置，然后根据设定的变异概率pm对这些基因位的值进行取反操作，即1变为0，0变为1。逆转变异算子随机挑选两个逆转点，然后将两个逆转点之间的基因值按变异概率逆向排列。19人工智能及其应用变异算子自适应变异算子变异概率不固定，它随群体中个体的多样性自适应调整。群体多样性越大，变异概率越小；多样性越差，变异概率越大。如：可根据交叉所得的两个新个体的Hamming距进行变异概率的调整，Hamming距越小，变异概率越大；Hamming距越大，变异概率越小。20人工智能及其应用

7、6.3改进的遗传算法微种群算法双种群算法自适应遗传算法21人工智能及其应用微种群算法算法步骤:(1)在群体中随机选择n个个体组成微群体。(2)计算适应度并确定最好的个体，直接遗传到下一代，保证优良的模式信息不致丢失。(3)按照联赛选择策略确定其余个体。(4)以概率1进行交叉运算，以加速产生确定位高的模式。这样处理之后可以保证有足够多的种类。(5)检验收敛条件，如果收敛则转(1)；否则转至(2)。22人工智能及