人工智能-许建华- 南京师范大学计算机科学系-4.5遗传算法

人工智能ArtificialIntelligence(AI)许建华xujianhua@南京师范大学计算机科学系2006年9-12月2023/2/54.5遗传算法生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。2023/2/5遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一类方法。2023/2/5串码：表示染色体或者个体适应度函数：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解2023/2/54.5.1遗传算法的基本机理4.5.2遗传算法的求解步骤4.5.3遗传算法的收敛性（略）2023/2/54.5.1遗传算法的基本机理1编码与解码2适应度函数3遗传操作2023/2/51编码与解码在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行编码，运行遗传算法后，再通过解码得到问题的解。编码解码遗传算法问题2023/2/5编码：将问题解的结构转换成位串形式编码的过程解码：将位串形式编码转化成问题的解的过程染色体（个体）：位串形式编码2023/2/5编码与解码方法：二进制码方法浮点数方法符号方法格雷码方法2023/2/5二进制码方法编码方法：将参数的取值范围分成等长的2l–1

部分，再用l

个二进制来编码每一个等分，共有2l

种不同的编码。2023/2/5假设x[A,B],每一个部分的长度为l＝200A01A+δ10A+2δ11A+3δ=BAB2023/2/5解码方法：如果某一个体的编码为：X=xl

xl-1…x2

x1解码公式为2023/2/5特点：编码与解码简单码串比较长搜索空间是有限的，提高解的精度，必须加大码长求解多个参数时，将所有的码拼接起来2023/2/5符号方法：个体编码中的基因值只取代码含义的符号集例：TSP问题，按照一个回路中城市的序号进行编码相互之间不能相同2023/2/52适应度函数适应度函数：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。2023/2/5例：对于TSP问题，要求总路径长度为最小，适应度函数可以定义为最小化最大化其中，wn+1=w1

d(wj,wj+1)：两个城市之间的距离2023/2/53遗传操作三种简单的遗传操作：选择（Selection）交叉（Crossover）变异（Mutation）2023/2/5选择操作（复制操作）：根据适应度函数值所度量的个体的优劣程度决定此个体在下一代是被淘汰或是被遗。一般情况下，如果是求最大值，适应度函数值大的个体具有较大的生存机会。2023/2/5交叉操作：选出两个个体作为父母个体，将两种的部分码值进行交换。例：100011101101101110001011110111102023/2/5变异操作：改变数码串上的某一个位置的数码。例10100110101101102023/2/54.5.2遗传算法的求解步骤1遗传算法的特点通过编码使得解空间是有限的，所有遗传算法是一种基于空间搜索的求解技术，通过自然选择、交叉、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找问题的解。2023/2/5现在将遗传算法看成为一种现代的优化技术，但是不一定能找到问题的全局最优解。通过一定的手段，可以将误差控制在容许的范围内（以很大的概率找到全局最优解）。最优解2023/2/5特点：对参数集合的编码进行进化，不是参数本身进行进化从问题解的编码组（群体）开始，不是从单个解开始搜索只利用适应度函数（目标函数），不需要导数等信息只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作2023/2/52遗传算法的框图遗传算法的基本思想：通过随机方式产生若干个个体，形成一个初始种群；利用适应度函数计算它们的适应度函数值，淘汰适应度小的个体，选择适应度高的个体参加遗传操作；经过遗传操作后的个体形成下一代种群，再对新的种群进行新的一轮进化。2023/2/5基本思想简单的遗传算法基本的遗传算法复杂的遗传算法2023/2/5简单遗传算法的步骤：初始化种群计算种群中每一个个体的适应度函数值根据与适应度相关联的规则确定进入下一轮的个体2023/2/5按照某一个概率进行交叉操作按照某一个概率进行变异操作如果不满足终止条件，则转到(2)，否则继续将种群中适应度最优的个体作为问题的解2023/2/5开始初始化种群计算适应度值选择操作交叉操作变异操作终止条件？选取适应度最优个体作为解结束是2023/2/53遗传算法例子求最大值2023/2/5主要步骤：编码：22位二进制数码串种群初始化适应度函数：函数本身遗传操作：选择、交叉、变异操作算法的若干关键参数：种群大小、种群代数、选择交叉变异概率等2023/2/5结果：最佳个体：1111001101000100000101对于自变量值：1.850773函数值：2.8502272023/2/54Matlab中的遗传算法函数使用方式：函数形式ga图形界面形式gatool包含在Matlab7.0版本的GeneticAlgorithmandDirectSearch工具箱中，只能求最小值2023/2/5GA算法的函数形式：[x,fval,reason]=ga(@fitnessfcn,num,options)其中：fitnessfcn:求目标函数值的Matlab函数，用户自己编写num:变量的个数options：算法参数的设置(可缺省）2023/2/5函数fitnessfcn的编写：例：Matlab函数functiony=simple_fitness(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2用simple_fitness代替ga中的fitnessfcn2023/2/5Options的内容：PopulationType:'doubleVector'PopInitRange:[2x1double]PopulationSize:20EliteCount:2CrossoverFraction:0.8000MigrationDirection:'forward'MigrationInterval:20MigrationFraction:0.2000Generations:100TimeLimit:InfFitnessLimit:-InfStallLimitG:50StallLimitS:20InitialPopulation:[]InitialScores:[]PlotInterval:1CreationFcn:@gacreationuniformFitnessScalingFcn:@fitscalingrankSelectionFcn:@selectionstochunifCrossoverFcn:@crossoverscatteredMutationFcn:@mutationgaussianHybridFcn:[]Display:'final'PlotFcns:[]OutputFcns:[]Vectorized:'off’2023/2/5参数设置函数：gaoptimset生成参数结构与设置参数值：options=gaoptimset(‘param1’,val1,’param2’,val2,…)改变参数设置options=gaoptimset(options,’param1’,val2,….)2023/2/5参数获取函数val=gaoptimget(options,‘param’)2023/2/5返回结果的含义：[x,fval,reason]最优解算法终止的原因最优解对应的函数值2023/2/5终止算法的五个条件：Generations（代数，缺省值100）TimeLimit（运行时间，无穷）FitnessLimit（适应度函数值，负无