人工智能第3章遗传算法38课件.ppt

1、人人 工工 智智 能能Artificial Intelligence(AI)2022-11-163.4 遗传算法遗传算法生物群体的生存过程普遍遵循达尔文的物竞天生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境选择、交叉、变异来适应大自然环境。2022-11-16遗传算法遗传算法是模仿生物遗传学和自然选择机理，通是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一进化过程的一个数学仿真，

2、属于进化计算中的一类方法。类方法。2022-11-16串码串码：表示染色体或者个体：表示染色体或者个体适应度函数适应度函数：表示一个染色体的适应能力，其：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解最大值或者最小值就是最优化问题的解2022-11-16一、一、遗传算法的基本机理遗传算法的基本机理二、遗传算法的求解步骤二、遗传算法的求解步骤三、遗传算法的收敛性（略）三、遗传算法的收敛性（略）2022-11-16一、遗传算法的基本机理一、遗传算法的基本机理1 编码与解码编码与解码2 适应度函数适应度函数3 遗传操作遗传操作2022-11-161 编码与解码编码与解码在遗传算法中，

3、为了模仿遗传学的遗传规律，在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行必须对问题的解的结构进行编码编码，运行，运行遗传算遗传算法法后，再通过后，再通过解码解码得到问题的解。得到问题的解。编码编码解码解码遗传算法遗传算法问题问题2022-11-16编码编码：将问题解的结构转换成位串形式编码的过程：将问题解的结构转换成位串形式编码的过程解码解码：将位串形式编码转化成问题的解的过程：将位串形式编码转化成问题的解的过程染色体染色体（个体）：位串形式编码（个体）：位串形式编码2022-11-16编码与解码方法编码与解码方法：二进制码方法二进制码方法浮点数方法浮点数方法符号方法符号方法

4、格雷码方法格雷码方法2022-11-16二进制码方法二进制码方法编码方法编码方法：将参数的取值范围分成等长的：将参数的取值范围分成等长的 2l 1 部分，再用部分，再用 l 个二进制来编码每一个等分，共有个二进制来编码每一个等分，共有2l 种不同的编码。种不同的编码。2022-11-16假设假设 x A,B,每一个部分的长度为每一个部分的长度为21lBAl200A01A+10A+2 11A+3=BAB2022-11-16解码方法解码方法：如果某一个体的编码为：如果某一个体的编码为：X=xl xl-1 x2 x1解码公式为解码公式为11221liiliBAxAx2022-11-16特点特点：编码

5、与解码简单编码与解码简单 码串比较长码串比较长 搜索空间是有限的，提高解的精度，必须加搜索空间是有限的，提高解的精度，必须加大码长大码长 求解多个参数时，将所有的码拼接起来求解多个参数时，将所有的码拼接起来2022-11-16符号方法符号方法：个体编码中的基因值只取代码含义：个体编码中的基因值只取代码含义的符号集的符号集例例：TSP问题，按照一个回路中城市的序号进问题，按照一个回路中城市的序号进行编码行编码123.nw w ww相互之间不能相同相互之间不能相同2022-11-162 适应度函数适应度函数适应度函数适应度函数：度量染色体优劣程度的函数，体现：度量染色体优劣程度的函数，体现自然进化

6、中的优胜劣汰原则。对于优化问题，适自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。应度函数就是目标函数。2022-11-16例例：对于：对于TSP问题，要求总路径长度为最小，问题，要求总路径长度为最小，适应度函数可以定义为适应度函数可以定义为1211(.)(,)nnjjjf w wwd w w12111(.)(,)nnjjjf w wwd w w最小化最小化最大化最大化其中，其中，wn+1=w1 d(wj,wj+1)：两个城市之间的距离：两个城市之间的距离2022-11-163 遗传操作遗传操作三种简单的遗传操作三种简单的遗传操作：选择（选择（Selection）交叉（交叉（C

7、rossover）变异（变异（Mutation）2022-11-16选择操作（复制操作）选择操作（复制操作）：根据：根据适应度函数值适应度函数值所所度量的度量的个体个体的优劣程度决定此的优劣程度决定此个体个体在下一代是在下一代是被被淘汰淘汰或是或是被遗被遗。一般情况下，如果是求最大。一般情况下，如果是求最大值，适应度函数值大的值，适应度函数值大的个体个体具有较大的具有较大的生存机生存机会会。2022-11-16交叉操作交叉操作：选出两个个体作为父母个体，将两种：选出两个个体作为父母个体，将两种的的部分码值部分码值进行交换。进行交换。例例：1000111011011011100010111101

8、11102022-11-16变异操作变异操作：改变数码串上的某一个位置的数码。：改变数码串上的某一个位置的数码。例例10100110101101102022-11-16二、遗传算法的求解步骤二、遗传算法的求解步骤1 遗传算法的特点遗传算法的特点通过编码使得通过编码使得解空间解空间是是有限有限的，所有遗传算法是的，所有遗传算法是一种基于一种基于空间搜索空间搜索的求解技术，通过自然的求解技术，通过自然选择选择、交叉交叉、变异变异等操作以及达尔文的等操作以及达尔文的适者生存适者生存的理论，的理论，模拟自然进化过程来寻找问题的解。模拟自然进化过程来寻找问题的解。2022-11-16现在将现在将遗传算法

9、遗传算法看成为一种现代的优化技术，但看成为一种现代的优化技术，但是不一定能找到问题的是不一定能找到问题的全局最优解全局最优解。通过一定的。通过一定的手段，可以将误差控制在手段，可以将误差控制在容许的范围容许的范围内（以很大内（以很大的概率找到全局最优解）。的概率找到全局最优解）。最优解最优解2022-11-16特点特点：(1)对参数集合的编码进行进化，不是参数本身进行对参数集合的编码进行进化，不是参数本身进行进化进化(2)从问题解的编码组（群体）开始，不是从单个解从问题解的编码组（群体）开始，不是从单个解开始搜索开始搜索(3)只利用适应度函数（目标函数），不需要导数等只利用适应度函数（目标函数

10、），不需要导数等信息信息(4)只利用选择、交叉、变异等操作，不需要利用确只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作定性规则进行随机操作2022-11-162 遗传算法的框图遗传算法的框图遗传算法的基本思想遗传算法的基本思想：通过：通过随机方式随机方式产生若干个产生若干个个体，形成一个个体，形成一个初始种群初始种群；利用适应度函数计算；利用适应度函数计算它们的它们的适应度函数值适应度函数值，淘汰淘汰适应度小的个体，选适应度小的个体，选择适应度高的择适应度高的个体个体参加遗传操作；经过遗传操作参加遗传操作；经过遗传操作后的个体形成下一代后的个体形成下一代种群种群，再对新的种群进

11、行新，再对新的种群进行新的一轮的一轮进化进化。2022-11-16基本思想基本思想简单的遗传算法简单的遗传算法基本的遗传算法基本的遗传算法复杂的遗传算法复杂的遗传算法2022-11-16简单遗传算法的步骤简单遗传算法的步骤：(1)初始化种群初始化种群(2)计算种群中每一个个体的适应度函数值计算种群中每一个个体的适应度函数值(3)根据与适应度相关联的规则确定进入下一轮的根据与适应度相关联的规则确定进入下一轮的个体个体2022-11-16(4)按照某一个概率进行交叉操作按照某一个概率进行交叉操作(5)按照某一个概率进行变异操作按照某一个概率进行变异操作(6)如果不满足终止条件，则转到如果不满足终止

12、条件，则转到(2)，否则继续，否则继续(7)将种群中适应度最优的个体作为问题的解将种群中适应度最优的个体作为问题的解2022-11-16开始开始初始化种群初始化种群计算适应度值计算适应度值选择操作选择操作交叉操作交叉操作变异操作变异操作终止条件？终止条件？选取适应度最选取适应度最优个体作为解优个体作为解结束结束是是2022-11-16 算法可定义为一个算法可定义为一个8元组：元组：),(0TMPECSGAC-个体的编码方法；个体的编码方法；E-个体适应度评价函数；个体适应度评价函数；P0-初始群体；初始群体；M-群体大小；群体大小；-选择算子；选择算子；-交叉算子；交叉算子；-变异算子变异算子

13、T-遗传运算终止条件。遗传运算终止条件。2022-11-16例例 用遗传算法求解优化问题用遗传算法求解优化问题310,)(max2xxxf其中其中 为整数。为整数。x(1)确定初始种群确定初始种群通过随机的方法来产生染色体的数字串，并组成通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位初始种群。例如，为得到数字串的某位又称之又称之为基因为基因(genes)(genes)，使用计算机在使用计算机在0 01 1之间产生随机数之间产生随机数K K，并按照数并按照数K K的变化区域来规定基因代码如下：的变化区域来规定基因代码如下：0 0，（0 0K K0.50.5）1 1，

14、（0.50.5K K1 1）2022-11-16 参数编码参数编码 将整数将整数 x 0,1,31作为参数，采用二进制进行作为参数，采用二进制进行编码：编码：X=000000，x=31 11111 随机生成随机生成例如例如:01001；11001；01000；10011。2022-11-16(2)选择选择 根据根据“适者生存适者生存”的自然选择原理的自然选择原理,从初始种群中选从初始种群中选择生命力强的个体择生命力强的个体(适者适者)产生新的种群产生新的种群 确定适应度函数确定适应度函数 适应度函数取为非负函数适应度函数取为非负函数,且适应度增大的方向对且适应度增大的方向对应于目标函数的优化方

15、向应于目标函数的优化方向 本例取适应度函数本例取适应度函数 fitness(X)=x 计算适应度和选择率计算适应度和选择率 将初始种群的个体解码为将初始种群的个体解码为X,并计算适应度并计算适应度f(X)及及选择率选择率f/,其中其中为适应度之和为适应度之和.2022-11-16选择适应值大的串作为母本选择适应值大的串作为母本，使在下一代中有更多的，使在下一代中有更多的机会繁殖其子孙。机会繁殖其子孙。要在四个种子个体中做选择，要求仍然得到四个染色要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：体，可依据适应度概率比例制定如下规则：低于低于0.1250.125

16、以下的染色体被淘汰；以下的染色体被淘汰；在在0.1250.1250.3750.375之间的染色体被复制一个；之间的染色体被复制一个；在在0.3750.3750.6250.625之间的染色体被复制两个；之间的染色体被复制两个；在在0.6250.6250.8750.875之间的染色体被复制三个；之间的染色体被复制三个；在在0.8750.875以上的染色体可复制四个。以上的染色体可复制四个。2022-11-162022-11-16 随机选择适者个体随机选择适者个体 采用采用轮盘法轮盘法，对初始种群进行选择，使得最优，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。秀的个体获得最多的生存繁

17、殖机会。49.230.9%14.4%5.5%2022-11-16(3)(3)交叉交叉 将选择出的个体存入交配池中，用将选择出的个体存入交配池中，用随机方法随机方法配对配对交叉，以产生新一代的个体交叉，以产生新一代的个体 随机选择配对；随机选择配对；随机选择交叉点；随机选择交叉点；采用单点交叉，产生新的种群采用单点交叉，产生新的种群2022-11-16(4)(4)变异变异 在交叉过程中，可能丢失一些重要的遗传信在交叉过程中，可能丢失一些重要的遗传信息息(特定位置的特定位置的1 1与与0)0)，因而产生变异。为了获，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。得新的遗传信息，则需引入适度的变异。设变异概率取为设变异概率取为0.001,则对于种群总共有则对于种群总共有20个个基因位基因位.期望的变异串位数计算期望的变异串位数计算:200.001=0.02(位位),故一般来说故一般来说,该例中可无基因位数值的改变该例中可无基因位数值的改变.2022-11-162022-11-16