人工智能第3章遗传算法38

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