资源描述
人人 工工 智智 能能Artificial Intelligence(AI)许建华许建华南京师范大学计算机科学与技术学院南京师范大学计算机科学与技术学院2016年秋季年秋季2024/7/12背背 景景求非线性函数的极小点及其对应的函数值求非线性函数的极小点及其对应的函数值凸函数凸函数2024/7/122024/7/12经典的最优化技术经典的最优化技术：假设变量与函数是连续的，：假设变量与函数是连续的，然后利用导数构造迭代形式的优化算法，最后获然后利用导数构造迭代形式的优化算法，最后获得最优解。得最优解。梯度法的示意图梯度法的示意图初始解初始解初始解初始解局部最优解局部最优解2024/7/12TSP：变量是离散变量是离散(北京北京,南京南京,上海上海,.)总路程是离散总路程是离散(北京北京-南南京京1000km,北京北京-南京南京-上海上海1350km,)现代优化技术：不用导数现代优化技术：不用导数代表性算法有：遗传算法，粒子群算法、蚁代表性算法有：遗传算法，粒子群算法、蚁群算法等群算法等2024/7/125.4 遗传算法遗传算法5.4.1 遗传算法的基本机理遗传算法的基本机理5.4.2 遗传算法的求解步骤遗传算法的求解步骤2024/7/125.4 遗传算法遗传算法生物群体的生存过程普遍遵循达尔文的生物群体的生存过程普遍遵循达尔文的物竞物竞天择、适者生存天择、适者生存的进化准则；生物通过个的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境体间的选择、交叉、变异来适应大自然环境。2024/7/12遗传算法遗传算法是模仿生物遗传学和自然选择机理，通是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一进化过程的一个数学仿真，属于进化计算中的一类方法。类方法。2024/7/12串码串码：表示染色体或者个体：表示染色体或者个体适应度函数适应度函数：表示一个染色体的适应能力，其：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解最大值或者最小值就是最优化问题的解100110101010101010AGCTTCGAGGAA2024/7/125.4.1 遗传算法的基本机理遗传算法的基本机理5.4.2 遗传算法的求解步骤遗传算法的求解步骤2024/7/125.4.1 遗传算法的基本机理遗传算法的基本机理1 编码与解码编码与解码2 适应度函数适应度函数3 遗传操作遗传操作2024/7/121 编码与解码编码与解码在遗传算法中，为了模仿遗传学的遗传规律，在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行必须对问题的解的结构进行编码编码，运行，运行遗传算遗传算法法后，再通过后，再通过解码解码得到问题的解。得到问题的解。编码编码解码解码遗传算法遗传算法问题问题2024/7/12编码编码：将问题解的结构转换成位串形式编码的过程：将问题解的结构转换成位串形式编码的过程解码解码：将位串形式编码转化成问题的解的过程：将位串形式编码转化成问题的解的过程染色体染色体（个体）：位串形式编码（个体）：位串形式编码00001001201030114100510161107111说明：初始解有多个个体构造说明：初始解有多个个体构造2024/7/12编码与解码方法编码与解码方法：二进制码方法二进制码方法浮点数方法浮点数方法符号方法符号方法格雷码方法格雷码方法2024/7/12二进制码方法二进制码方法编码方法编码方法：将参数的取值范围分成等长的：将参数的取值范围分成等长的 2l 1 部分，再用部分，再用 l 个二进制来编码每一个等分，共有个二进制来编码每一个等分，共有2l 种不同的编码。种不同的编码。2024/7/12假设假设 x A,B,每一个部分的长度为每一个部分的长度为l210A+2AB01A+11A+3=B00A2024/7/12解码方法解码方法：如果某一个体的编码为：如果某一个体的编码为：X=xl xl-1 x2 x1解码公式为解码公式为00A11A+111A+211A+3=B2024/7/12特点特点：编码与解码简单编码与解码简单码串比较长码串比较长搜索空间是有限的，提高解的精度，必须加搜索空间是有限的，提高解的精度，必须加大码长大码长求解多个参数时，将所有的码拼接起来求解多个参数时，将所有的码拼接起来x1x2xi2024/7/12符号方法符号方法：个体编码中的基因值只取代码含义：个体编码中的基因值只取代码含义的符号集的符号集例例：TSP问题，按照一个回路中城市的序号进问题，按照一个回路中城市的序号进行编码行编码相互之间不能相同相互之间不能相同2024/7/122 适应度函数适应度函数适应度函数适应度函数：度量染色体优劣程度的函数，体现：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，适自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。应度函数就是目标函数。2024/7/12例例：对于：对于TSP问题，要求总路径长度为最小，问题，要求总路径长度为最小，适应度函数可以定义为适应度函数可以定义为最小化最小化最大化最大化其中，其中，wn+1=w1 d(wj,wj+1)：两个城市之间的距离：两个城市之间的距离2024/7/123 遗传操作遗传操作三种简单的遗传操作三种简单的遗传操作：选择（选择（Selection）交叉（交叉（Crossover）变异（变异（Mutation）2024/7/12选择操作（复制操作）选择操作（复制操作）：根据：根据适应度函数值适应度函数值所度所度量的量的个体个体的优劣程度决定此的优劣程度决定此个体个体在下一代是被在下一代是被淘淘汰汰或是或是被遗被遗。一般情况下，如果是求最大值，适。一般情况下，如果是求最大值，适应度函数值大的应度函数值大的个体个体具有较大的具有较大的生存机会生存机会。2024/7/12淘汰哪一个个体？淘汰哪一个个体？2024/7/12交叉操作交叉操作：选出两个个体作为父母个体，将两种：选出两个个体作为父母个体，将两种的的部分码值部分码值进行交换。进行交换。例例：10001110110110111000101111011110关键：关键：选多少位？选多少位？选在哪里？选在哪里？2024/7/12变异操作变异操作：改变数码串上的某一个位置的数码。：改变数码串上的某一个位置的数码。例例1010011010110110关键：关键：选多少位？选多少位？选在哪里？选在哪里？2024/7/125.4.2 遗传算法的求解步骤遗传算法的求解步骤1 遗传算法的特点遗传算法的特点通过编码使得通过编码使得解空间解空间是是有限有限的，所有遗传算法是的，所有遗传算法是一种基于一种基于空间搜索空间搜索的求解技术，通过自然的求解技术，通过自然选择选择、交叉交叉、变异变异等操作以及达尔文的等操作以及达尔文的适者生存适者生存的理论，的理论，模拟自然进化过程来寻找问题的解。模拟自然进化过程来寻找问题的解。2024/7/12现在将现在将遗传算法遗传算法看成为一种现代的优化技术，但看成为一种现代的优化技术，但是不一定能找到问题的是不一定能找到问题的全局最优解全局最优解。通过一定的。通过一定的手段，可以将误差控制在手段，可以将误差控制在容许的范围容许的范围内（以很大内（以很大的概率找到全局最优解）。的概率找到全局最优解）。最优解最优解2024/7/12特点特点：(1)对参数集合的编码进行进化，不是参数本身进行对参数集合的编码进行进化，不是参数本身进行进化进化(2)从问题解的编码组（群体）开始，不是从单个解从问题解的编码组（群体）开始，不是从单个解开始搜索开始搜索(3)只利用适应度函数（目标函数），不需要导数等只利用适应度函数（目标函数），不需要导数等信息信息(4)只利用选择、交叉、变异等随机操作只利用选择、交叉、变异等随机操作2024/7/122 遗传算法的框图遗传算法的框图遗传算法的基本思想遗传算法的基本思想：通过：通过随机方式随机方式产生若干个产生若干个个体，形成一个个体，形成一个初始种群初始种群；利用适应度函数计算；利用适应度函数计算它们的它们的适应度函数值适应度函数值，淘汰淘汰适应度小的个体，选适应度小的个体，选择适应度高的择适应度高的个体个体参加遗传操作；经过遗传操作参加遗传操作；经过遗传操作后的个体形成下一代后的个体形成下一代种群种群，再对新的种群进行新，再对新的种群进行新的一轮的一轮进化进化。2024/7/12基本思想基本思想简单的遗传算法简单的遗传算法基本的遗传算法基本的遗传算法复杂的遗传算法复杂的遗传算法2024/7/12简单遗传算法的步骤简单遗传算法的步骤：(1)初始化种群初始化种群(2)计算种群中每一个个体的适应度函数值计算种群中每一个个体的适应度函数值(3)根据与适应度相关联的规则确定进入下一轮的根据与适应度相关联的规则确定进入下一轮的个体个体2024/7/12(4)按照某一个概率进行交叉操作按照某一个概率进行交叉操作(5)按照某一个概率进行变异操作按照某一个概率进行变异操作(6)如果不满足终止条件，则转到如果不满足终止条件，则转到(2)，否则继续，否则继续(7)将种群中适应度最优的个体作为问题的解将种群中适应度最优的个体作为问题的解2024/7/12遗传算法的终止条件：需满足其中之一遗传算法的终止条件：需满足其中之一1、完成预先给定的进化代数。、完成预先给定的进化代数。2、种群中最优个体或者平均适应度在连续若干代没、种群中最优个体或者平均适应度在连续若干代没有改进。有改进。2024/7/12开始开始初始化种群初始化种群计算适应度值计算适应度值选择操作选择操作交叉操作交叉操作变异操作变异操作终止条件？终止条件？选取适应度最选取适应度最优个体作为解优个体作为解结束结束是是2024/7/123 遗传算法例子遗传算法例子求最大值求最大值2024/7/12求一阶导数，并令其为零求一阶导数，并令其为零得得求二阶导数求二阶导数2024/7/12f(x)f(x)f(x)2024/7/12主要步骤主要步骤：(1)编码：编码：22位二进制数码串位二进制数码串(2)种群初始化种群初始化(3)适应度函数：函数本身适应度函数：函数本身(4)遗传操作：选择、交叉、变异操作遗传操作：选择、交叉、变异操作(5)算法的若干关键参数：种群大小、种群代算法的若干关键参数：种群大小、种群代数、选择交叉变异概率等数、选择交叉变异概率等2024/7/12结果结果：最佳个体：最佳个体：1111 0011 0100 0100 0001 01对于自变量值：对于自变量值：1.850773函数值：函数值：2.8502272024/7/124 Matlab中的遗传算法函数中的遗传算法函数使用方式使用方式：函数形式函数形式 ga图形界面形式图形界面形式 optimtool(选择选择ga)包含在包含在Matlab2010版本的版本的Global Optimization Toolbox 工具箱中，只能求工具箱中，只能求最小值最小值2024/7/12数学问题：数学问题：线性的等式与不等式约束线性的等式与不等式约束非线性的等式与不等式约束非线性的等式与不等式约束变量的上下界变量的上下界变量变量2024/7/12GA算法的函数形式算法的函数形式：x=ga(fitnessfcn,nvars)x=ga(fitnessfcn,nvars,A,b)x=ga(fitnessfcn,nvars,A,b,Aeq,beq)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)x=ga(problem)x,fval=ga(.)x,fval,exitflag=ga(.)2024/7/12x,fval,exitflag=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)输入输入：fitnessfcn:求目标函数值的求目标函数值的Matlab函数，用户自函数，用户自己编写，调用必须带己编写，调用必须带num:变量的个数变量的个数options：算法参数的设置：算法参数的设置(可缺省）可缺省）2024/7/12函数函数fitnessfcn的编写：的编写：例：例：Matlab函数函数function y=simple_fitness(x)y=100*(x(1)2-x(2)2+(1-x(1)2用用simple_fitness代替代替ga中的中的fitnessfcn2024/7/12PopulationType:doubleVectorPopInitRange:2x1 doublePopulationSize:20EliteCount:2CrossoverFraction:0.8000MigrationDirection:forwardMigrationInterval:20MigrationFraction:0.2000Generations:100TimeLimit:InfFitnessLimit:-InfStallLimitG:50StallLimitS:20Options 的内容：的内容：InitialPopulation:InitialScores:PlotInterval:1CreationFcn:gacreationuniformFitnessScalingFcn:fitscalingrankSelectionFcn:selectionstochunifCrossoverFcn:crossoverscatteredMutationFcn:mutationgaussianHybridFcn:Display:finalPlotFcns:OutputFcns:Vectorized:off2024/7/12参数设置函数参数设置函数：gaoptimset生成参数结构与设置参数值：生成参数结构与设置参数值：options=gaoptimset(param1,val1,param2,val2,)改变参数设置改变参数设置options=gaoptimset(options,param1,val2,.)2024/7/12参数获取函数参数获取函数val=gaoptimget(options,param)2024/7/12返回结果的含义：返回结果的含义：x,fval,exitflag最优解最优解算法终止的原因算法终止的原因最优解对应的函数值最优解对应的函数值2024/7/12终止算法的五个条件终止算法的五个条件：Generations（代数，缺省值（代数，缺省值100）Time Limit（运行时间，无穷）（运行时间，无穷）Fitness Limit（适应度函数值，负无穷）（适应度函数值，负无穷）Stall Generations（连续不能改善目标函数的代（连续不能改善目标函数的代数，数，50）Stall time limit（连续不能改善目标函数的时间，（连续不能改善目标函数的时间，20）说明说明：满足任一条件，算法将终止运行：满足任一条件，算法将终止运行2024/7/12界面形式界面形式：在自己编写在自己编写fitness函数的子目录下，敲入函数的子目录下，敲入optimtool2024/7/12用户的函数：用户的函数：sin_fitness12024/7/12例例1:函数：函数：sin_function，optimtool演示演示例例2 40个城市的个城市的TSP问题（问题（demo程序）程序）MatlabGraphicsOtherDemos2024/7/12
展开阅读全文