人工智能第3章遗传算法

2020/2/15人工智能ArtificialIntelligence(AI)2020/2/153.4遗传算法生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。2020/2/15遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一类方法。2020/2/15串码：表示染色体或者个体适应度函数：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解2020/2/15一、遗传算法的基本机理二、遗传算法的求解步骤三、遗传算法的收敛性（略）2020/2/15一、遗传算法的基本机理1编码与解码2适应度函数3遗传操作2020/2/151编码与解码在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行编码，运行遗传算法后，再通过解码得到问题的解。编码解码遗传算法问题2020/2/15编码：将问题解的结构转换成位串形式编码的过程解码：将位串形式编码转化成问题的解的过程染色体（个体）：位串形式编码2020/2/15编码与解码方法：•二进制码方法•浮点数方法•符号方法•格雷码方法2020/2/15二进制码方法编码方法：将参数的取值范围分成等长的2l–1部分，再用l个二进制来编码每一个等分，共有2l种不同的编码。2020/2/15假设x[A,B],每一个部分的长度为21lBAl＝200A01A+δ10A+2δ11A+3δ=BAB2020/2/15解码方法：如果某一个体的编码为：X=xlxl-1…x2x1解码公式为11221liiliBAxAx2020/2/15特点：编码与解码简单码串比较长搜索空间是有限的，提高解的精度，必须加大码长求解多个参数时，将所有的码拼接起来2020/2/15符号方法：个体编码中的基因值只取代码含义的符号集例：TSP问题，按照一个回路中城市的序号进行编码123...n适应度函数适应度函数：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。2020/2/15例：对于TSP问题，要求总路径长度为最小，适应度函数可以定义为1211(...)(,)nnjjjf12111(...)(,)nnjjjf最小化最大化其中，wn+1=w1d(wj,wj+1)：两个城市之间的距离2020/2/153遗传操作三种简单的遗传操作：选择（Selection）交叉（Crossover）变异（Mutation）2020/2/15选择操作（复制操作）：根据适应度函数值所度量的个体的优劣程度决定此个体在下一代是被淘汰或是被遗。一般情况下，如果是求最大值，适应度函数值大的个体具有较大的生存机会。2020/2/15交叉操作：选出两个个体作为父母个体，将两种的部分码值进行交换。例：100011101101101110001011110111102020/2/15变异操作：改变数码串上的某一个位置的数码。例10100110101101102020/2/15二、遗传算法的求解步骤1遗传算法的特点通过编码使得解空间是有限的，所有遗传算法是一种基于空间搜索的求解技术，通过自然选择、交叉、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找问题的解。2020/2/15现在将遗传算法看成为一种现代的优化技术，但是不一定能找到问题的全局最优解。通过一定的手段，可以将误差控制在容许的范围内（以很大的概率找到全局最优解）。最优解2020/2/15特点：(1)对参数集合的编码进行进化，不是参数本身进行进化(2)从问题解的编码组（群体）开始，不是从单个解开始搜索(3)只利用适应度函数（目标函数），不需要导数等信息(4)只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作2020/2/152遗传算法的框图遗传算法的基本思想：通过随机方式产生若干个个体，形成一个初始种群；利用适应度函数计算它们的适应度函数值，淘汰适应度小的个体，选择适应度高的个体参加遗传操作；经过遗传操作后的个体形成下一代种群，再对新的种群进行新的一轮进化。2020/2/15基本思想简单的遗传算法基本的遗传算法复杂的遗传算法2020/2/15简单遗传算法的步骤：(1)初始化种群(2)计算种群中每一个个体的适应度函数值(3)根据与适应度相关联的规则确定进入下一轮的个体2020/2/15(4)按照某一个概率进行交叉操作(5)按照某一个概率进行变异操作(6)如果不满足终止条件，则转到(2)，否则继续(7)将种群中适应度最优的个体作为问题的解2020/2/15开始初始化种群计算适应度值选择操作交叉操作变异操作终止条件？选取适应度最优个体作为解结束是2020/2/15算法可定义为一个8元组：),,,,,,,(0TMPECSGAC---个体的编码方法；E---个体适应度评价函数；P0---初始群体；M---群体大小；Φ---选择算子；Γ---交叉算子；---变异算子T---遗传运算终止条件。2020/2/15例用遗传算法求解优化问题310,)(max2xxxf其中为整数。x(1)确定初始种群通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位——又称之为基因(genes)，使用计算机在0～1之间产生随机数K，并按照数K的变化区域来规定基因代码如下：0，（0≤K＜0.5）1，（0.5≤K≤1）G=2020/2/15①参数编码将整数x{0,1,…,31}作为参数，采用二进制进行编码：X=0—00000，……x=31—11111②随机生成例如:①01001；②11001；③01000；④10011。2020/2/15(2)选择根据“适者生存”的自然选择原理,从初始种群中选择生命力强的个体(适者)产生新的种群①确定适应度函数适应度函数取为非负函数,且适应度增大的方向对应于目标函数的优化方向本例取适应度函数fitness(X)=x²②计算适应度和选择率将初始种群的个体解码为X,并计算适应度f(X)及选择率f/∑,其中∑为适应度之和.2020/2/15选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙。要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：低于0.125以下的染色体被淘汰；在0.125～0.375之间的染色体被复制一个；在0.375～0.625之间的染色体被复制两个；在0.625～0.875之间的染色体被复制三个；在0.875以上的染色体可复制四个。2020/2/152020/2/15③随机选择适者个体采用轮盘法，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。49.2﹪30.9%14.4%5.5%011011100011000100112020/2/15(3)交叉将选择出的个体存入交配池中，用随机方法配对交叉，以产生新一代的个体①随机选择配对；②随机选择交叉点；③采用单点交叉，产生新的种群2020/2/15(4)变异在交叉过程中，可能丢失一些重要的遗传信息(特定位置的1与0)，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。设变异概率取为0.001,则对于种群总共有20个基因位.期望的变异串位数计算:20×0.001=0.02(位),故一般来说,该例中可无基因位数值的改变.2020/2/15