人工智能课件蔡自兴不全第3章幻灯片.pptVIP

3.3.1 遗传算法的几个概念 3.遗传操作 变异操作——一种简单方式是改变数码串的某个位置上的数码。 … 3.3.1 遗传算法的几个概念 4.控制参数 （1）实施交叉、变异操作的概率 并非所有被选择了的染色体都要进行交叉操作和变异操作，而是按一定的概率进行。一般在程序设计中选择： 交叉操作概率变异操作概率 （2）种群规模 3.3.2 遗传算法的基本原理 初始化种群 变异操作 计算适应度值 选择操作 交叉操作 适应度最优个体 终止条件 开始 3.3.3 遗传算法的收敛性 一般的遗传算法不一定收敛。 促使遗传算法收敛的措施之一——优秀个体保护法： 将每代中的最优个体，直接进入子代，相应淘汰其子代中适应度最差的个体，使种群规模不变。 3.3.3 遗传算法的收敛性 当遗传算法收敛时，求到的解通常只是所要解决问题的最优解的一个近似解，或者叫满意解。 近似解与问题真正的最优解的差是一个统计意义下的量，也就是说每次程序运行得到的解的质量可能存在较大的差别。 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （1）种群的规模 种群规模太小，种群中就没有充分的多样性，不利于适应度值高的染色体的进化，致使算法得不到满意的解。可以认为种群规模大有利于种群的进化；但种群规模太大，即染色体太多，则每进行一轮进化花费的机器时间就多，致使算法的效率低。 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （2）适应度函数 适应度是衡量染色体优劣的准则，有时优劣染色体的适应度值没有拉开距离。有必要提升优良染色体的适应度值，降低劣弱染色体的适应度值，给优良染色体很多的生存机会，达到提高进化速度的目标。 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （2）适应度函数 可以结合所求解问题的实际情况对适应度函数作适当的变换，提高选择过程的效率。如下有一个线性变换： f r=c1fi+c2 fi：个体i的适应度；f r：经标度变换后的适应度； c1、c2 ：常数 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （3）交叉和变异操作的方式 交叉和变异操作的重要的一点是，不同的问题要构造一些性能更优的交叉和变异操作，才能保证算法的高效率，构造时往往需要对所要求解的问题进行分析和运用一些经验。… 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （4）交叉和变异操作的概率 交叉和变异操作的概率应根据具体问题选定。对某些问题遗传算法求解时其性能主要由交叉操作决定，甚至没有变异操作时，算法的性能更好；而对另外的某些问题遗传算法求解时其性能主要由变异操作决定，甚至不要交叉操作更合适。 3.3.4 遗传算法的性能 影响遗传算法性能的因素： （5）父个体能否与新个体进行竞争 按简单遗传算法，交叉或变异产生的新个体不论优劣都取代父个体，并不科学。对新个体要有与父个体进行竞争的机会，当父个体比新个体优时，按一定的概率保留父个体而舍去新个体。 遗传算法实际应用举例 针对实际的中国144个城市，应用遗传算法，解决TSP问题。 （1）编码方案 采用实数编码，对城市采用序号表达式方法。 例如：[4,7,6,5,9,1,2,8,0,3]代表从城市4出发，经由城市7-6-5-9-1-2-8-1-3，最后又回到城市4的一条路径。 遗传算法实际应用举例 （2）适应度函数 个体的评估是对每个个体计算其路径的长度，并把该长度作为个体的适应度函数。则规定适应度函数为： 遗传算法实际应用举例 （3）遗传操作 a. 选择 产生初始群体后，根据计算的个体适应度对整 个群体进行适应度从小到大排序。 设定选择百分比p，为保持群体的多样性，在作选择时，规定选择p/2的好个体，再选择p/2的其它个体放入到交配池中进行交叉和变异等遗传操作。 遗传算法实际应用举例 （3）遗传操作 b. 交叉 设有2个个体： P1=1245673098 P2=5671430892 随机产生两个数r1和r2，如果r1≠r2，则判断P1中的r1位置上的城市与P2中r2位置上的城市是不是相等。如果不等，则P1中的r1到r2位置之间的城市进行倒位操作；再对P2作同样处理。 遗传算法实际应用举例 （3）遗传操作 c. 变异 采用相当于单点变异方法。随机产生两个数m1和m2。如果m1≠m2，则将个体中 m1位置和m2位置的城市进行交换，实现变异。 遗传算法实际应用举例 （4）控制参数 a. 交叉概率的设计采用动态概率：