《人工智能第3章遗传算法课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第3章遗传算法课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、2023/4/1,人 工 智 能Artificial Intelligence(AI),2023/4/1,3.4 遗传算法,生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。,2023/4/1,遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一类方法。,2023/4/1,串码：表示染色体或者个体适应度函数：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解,2023/4/1,一、遗传算法的基本机理二、遗传算法的求解步骤三、遗传算法的收敛性（略）
2、,2023/4/1,一、遗传算法的基本机理1 编码与解码2 适应度函数3 遗传操作,2023/4/1,1 编码与解码,在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行编码，运行遗传算法后，再通过解码得到问题的解。,编码,解码,遗传算法,问题,2023/4/1,编码：将问题解的结构转换成位串形式编码的过程解码：将位串形式编码转化成问题的解的过程染色体（个体）：位串形式编码,2023/4/1,编码与解码方法：二进制码方法浮点数方法符号方法格雷码方法,2023/4/1,二进制码方法,编码方法：将参数的取值范围分成等长的 2l 1 部分，再用 l 个二进制来编码每一个等分，共有2l 种
3、不同的编码。,2023/4/1,假设 x A,B,每一个部分的长度为,l2,00A01A+10A+2 11A+3=B,A,B,2023/4/1,解码方法：,如果某一个体的编码为：X=xl xl-1 x2 x1解码公式为,2023/4/1,特点：编码与解码简单码串比较长搜索空间是有限的，提高解的精度，必须加大码长求解多个参数时，将所有的码拼接起来,2023/4/1,符号方法：个体编码中的基因值只取代码含义的符号集,例：TSP问题，按照一个回路中城市的序号进行编码,相互之间不能相同,2023/4/1,2 适应度函数,适应度函数：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，
4、适应度函数就是目标函数。,2023/4/1,例：对于TSP问题，要求总路径长度为最小，适应度函数可以定义为,最小化,最大化,其中，wn+1=w1 d(wj,wj+1)：两个城市之间的距离,2023/4/1,3 遗传操作,三种简单的遗传操作：选择（Selection）交叉（Crossover）变异（Mutation）,2023/4/1,选择操作（复制操作）：根据适应度函数值所度量的个体的优劣程度决定此个体在下一代是被淘汰或是被遗。一般情况下，如果是求最大值，适应度函数值大的个体具有较大的生存机会。,2023/4/1,交叉操作：选出两个个体作为父母个体，将两种的部分码值进行交换。,例：,2023/
5、4/1,变异操作：改变数码串上的某一个位置的数码。,例,2023/4/1,二、遗传算法的求解步骤,1 遗传算法的特点通过编码使得解空间是有限的，所有遗传算法是一种基于空间搜索的求解技术，通过自然选择、交叉、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找问题的解。,2023/4/1,现在将遗传算法看成为一种现代的优化技术，但是不一定能找到问题的全局最优解。通过一定的手段，可以将误差控制在容许的范围内（以很大的概率找到全局最优解）。,最优解,2023/4/1,特点：对参数集合的编码进行进化，不是参数本身进行进化从问题解的编码组（群体）开始，不是从单个解开始搜索只利用适应度函数（目标函
6、数），不需要导数等信息只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作,2023/4/1,2 遗传算法的框图,遗传算法的基本思想：通过随机方式产生若干个个体，形成一个初始种群；利用适应度函数计算它们的适应度函数值，淘汰适应度小的个体，选择适应度高的个体参加遗传操作；经过遗传操作后的个体形成下一代种群，再对新的种群进行新的一轮进化。,2023/4/1,基本思想,简单的遗传算法,基本的遗传算法,复杂的遗传算法,2023/4/1,简单遗传算法的步骤：初始化种群计算种群中每一个个体的适应度函数值根据与适应度相关联的规则确定进入下一轮的个体,2023/4/1,按照某一个概率进行交叉操作按照
7、某一个概率进行变异操作如果不满足终止条件，则转到(2)，否则继续将种群中适应度最优的个体作为问题的解,2023/4/1,开始,初始化种群,计算适应度值,选择操作,交叉操作,变异操作,终止条件？,选取适应度最优个体作为解,结束,是,2023/4/1,算法可定义为一个8元组：,C-个体的编码方法；E-个体适应度评价函数；P0-初始群体；M-群体大小；-选择算子；-交叉算子；-变异算子T-遗传运算终止条件。,2023/4/1,例 用遗传算法求解优化问题,其中 为整数。,(1)确定初始种群,通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位又称之为基因(genes)，使用计算
8、机在01之间产生随机数K，并按照数K的变化区域来规定基因代码如下：0，（0K0.5）1，（0.5K1）,2023/4/1,参数编码 将整数 x 0,1,31作为参数，采用二进制进行编码：X=000000，x=31 11111 随机生成例如:01001；11001；01000；10011。,2023/4/1,(2)选择 根据“适者生存”的自然选择原理,从初始种群中选择生命力强的个体(适者)产生新的种群 确定适应度函数 适应度函数取为非负函数,且适应度增大的方向对应于目标函数的优化方向 本例取适应度函数 fitness(X)=x 计算适应度和选择率 将初始种群的个体解码为X,并计算适应度f(X)及
9、选择率f/,其中为适应度之和.,2023/4/1,选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙。要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：低于0.125以下的染色体被淘汰；在0.1250.375之间的染色体被复制一个；在0.3750.625之间的染色体被复制两个；在0.6250.875之间的染色体被复制三个；在0.875以上的染色体可复制四个。,2023/4/1,2023/4/1,随机选择适者个体 采用轮盘法，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。,01101 11000 11000 10011,2023/4/1,(3)交叉 将选择出的个体存入交配池中，用随机方法配对交叉，以产生新一代的个体 随机选择配对；随机选择交叉点；采用单点交叉，产生新的种群,2023/4/1,(4)变异 在交叉过程中，可能丢失一些重要的遗传信息(特定位置的1与0)，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。,设变异概率取为0.001,则对于种群总共有20个基因位.期望的变异串位数计算:200.001=0.02(位),故一般来说,该例中可无基因位数值的改变.,2023/4/1,
