人工智能_遗传算法.ppt

人工智能_遗传算法,第4章 遗传算法,4.1 基本概念 4.2 选择算子 4.3 交叉算子 4.4 变异算子 4.5 基本遗传算法 4.6 基本实现技术 4.7 遗传算法应用,人工智能_遗传算法,第4章 遗传算法,生物进化 自然法则 优胜劣汰 适者生存 有性繁殖 基因通过有性繁殖不断进行混合和重组 遗传算法 从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法,人工智能_遗传算法,第4章 遗传算法,应用 函数优化 组合优化：旅行商、图形化分 生产调度：车间调度、生产规划 自动控制：控制器、参数辨识 机器人智能控制：机器人路径规划、运动轨迹规划 图像处理与模式识别：特征提取、图像分割 人工生命：进化模型、学习模型、行为模型 遗传程序设计 机器学习,人工智能_遗传算法,4.1 基本概念,个体 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼 一个个体也就是搜索空间中的一个点 种群 种群(population)就是模拟生物种群而由若 干个体组成的群体 它一般是整个搜索空间的一个很小的子集 通过对种群实施遗传操作，使其不断更新换代而实现对整个论域空间的搜索,人工智能_遗传算法,4.1 基本概念,适应度(fitness) 借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度 适应度函数(fitness function) 问题中的全体个体与其适应度之间的一个对应关系 一般是一个实值函数 该函数就是遗传算法中指导搜索的评价函数,人工智能_遗传算法,4.1 基本概念,染色体(chromosome) 染色体是由若干基因组成的位串（生物学） 个体对象由若干字符串组成来表示（遗传算法） 遗传算法(genetic algorithm) 染色体就是问题中个体的某种字符串形式的编码表示 染色体以字符串来表示 基因是字符串中的一个个字符,个体 染色体 9 - 1001 （2，5，6）- 010 101 110,人工智能_遗传算法,4.1 基本概念,遗传算子(genetic operator) 选择(selection) 交叉(crossover) 变异(mutation),人工智能_遗传算法,4.2 选择算子,选择算子 模拟生物界优胜劣汰的自然选择法则的一种染色体运算 从种群中选择适应度较高的染色体进行复制，以生成下一代种群 算法： 个体适应度计算 在被选集中每个个体具有一个选择概率 选择概率取决于种群中个体的适应度及其分布 个体适应度计算，即个体选择概率计算 个体选择方法 按照适应度进行父代个体的选择,人工智能_遗传算法,4.2 选择算子,个体适应度计算 按比例的适应度计算(proportional fitness assignment) 基于排序的适应度计算(rank-based fitness assignment) 个体选择方法 轮盘赌选择(roulette wheel selection) 随机遍历抽样(stochastic universal sampling) 局部选择(local selection) 截断选择(truncation selection) 锦标赛选择(tournament selection),人工智能_遗传算法,4.2.1 按比例的适应度计算,算法： 对一个规模为n的种群s，按每个染色体xis的选择概率p(xi)所决定的选中机会，分n次从s中随机选择n个染色体，并进行复制 其中： f为适应度函数 f(xi)为xi的适应度,优胜劣汰 概率越高，随机选中概率越大 概率越高，选中次数越多 适应度高的染色体后代越多,人工智能_遗传算法,4.2.3 轮盘赌选择,原理： 做一个单位圆，然后按各个染色体的选择概率将圆面划分为相应的扇形区域 转动轮盘，轮盘静止时指针指向某一扇区，即为选中扇区，相应的个体/染色体即被选中,人工智能_遗传算法,4.2.3 轮盘赌选择,算法： 在0, 1区间，产生一个均匀分布的伪随机数r 若rq1，则染色体1被选中 若qk-1 rqk(2 kn)，则染色体k被选中 其中 qi为染色体xi(i=1, 2, , n)的累积概率 一个染色体xi被选中的次数，可由期望值e(xi)来确定 为种群s中全体染色体的平均适应度,人工智能_遗传算法,4.3 交叉算子,交叉算子 交换、交配、杂交 互换两个染色体某些位上的基因 随机化算子，生成新个体,人工智能_遗传算法,4.3 交叉算子,一点杂交 产生一个在1到l1之间的随机数i 配对的两个串相互对应的交换从i1到l的位段,人工智能_遗传算法,4.3 交叉算子,例3.1 设染色体s1 = 1011 0111 00 染色体s2 = 0001 1100 11 交换其后2位基因,人工智能_遗传算法,4.4 变异算子,变异算子 突变 改变染色体某个/些位上的基因 随机化算子，生成新个体 次要算子，但在恢复群体中失去的多样性方面具有潜在的作用,人工智能_遗传算法,4.4 变异算子,例4.1 设染色体s = 1011 0111 00,人工智能_遗传算法,4.5 基本遗传算法,遗传算法 对种群中的染色体反复做三种遗传操作 使其朝着适应度增高的方向不断更新换代，直至出现了适应度满足目标条件的染色体为止 算法拓展 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用 基本遗传算法是holland提出的一种统一的最基本的遗传算法，简称sga（simple genetic algorithm )、cga（canonical genetic algorithm） 其它的“ga类”算法称为gas(genetic algorithms）,可以把ga看作是gas的一种特例,人工智能_遗传算法,4.5 基本遗传算法,参数 种群规模 种群的大小，用染色体个数表示 最大换代数 种群更新换代的上限，也是算法终止一个条件 交叉率pc 参加交叉运算的染色体个数占全体染色体总数的比例 取值范围：0.4-0.99 变异率pm 发生变异的基因位数占全体染色体的基因总位数的比例 取值范围：0.0001-0.1 染色体编码 长度l,人工智能_遗传算法,4.5 基本遗传算法,算法,步1 ：在论域空间u上定义一个适应度函数f(x)，给定种群规模n，交叉率pc， 变异率pm，代数gen 步2： 随机产生u中的n个染色体s1,s2sn, 组成初始种群s=s1,s2sn，置代 数t=1 步3：若终止条件满足，则取s中适应度最大的染色体作为所求结果，算法结束 步4：计算s中每个染色体的适应度f() 步5： 按选择概率p(si)所决定的选中机会，每次从s中随机选中1个染色体并将 其复制，共做n次，然后将复制得到的n染色体组成群体s1 步6 ：按pc所决定的参加交叉的染色体数c，从s1中随机确定c个染色体，配对 进行交叉操作，并用产生的染色体代替原染色体，组成群体s2 步7 ：按pm所决定的变异次数m，从s2中随机确定m个染色体，分别进行变异 操作，并用产生的新染色体代替原染色体，组成群体s3 步8 ：将群体s3作为新种群，即用s3代替s， gen = gen +1，转步3,人工智能_遗传算法,4.5 流程图,人工智能_遗传算法,4.6 基本实现技术,编码方法 二进制编码 格雷编码 编码规则 应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案 应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案,人工智能_遗传算法,4.6 基本实现技术,适应值函数 适应值函数必须是正数 出现负数时应进行变换，常用变换方式有三种： 线性比例法：g(x) = a*f(x)+b (b0) 指数比例法：g(x) = exp(a f(x) (a0) 幂指数比例法：g(x) = (f(x)a (a为偶数),人工智能_遗传算法,4.7 算法举例,例7.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值 分析 原问题转化为0,31中寻找能使y取最大值的点x 区间0,31为论域空间/解空间 x为个体对象 函数f(x)= x2 可作为适应度函数,人工智能_遗传算法,4.7 算法举例,解： 定义适应度函数，编码染色体 适应度函数取f(x)= x2 用5位二进制数作为个体x的基因型编码/染色体 设定种群规模，产生初始种群 种群规模n=4 初始种群s=s1=01101(13),s2=11000(24)， s3=01000(8)， s4=10011(19),人工智能_遗传算法,4.7 算法举例,计算各代种群中各染色体的适应度，并进行遗传操作 选择 设从区间0,1产生4个随机数r1=0.45, r2=0.11, r3=0.57, r4=0.98 按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，2，0，1 选择产生种群s1=s1=11000(24),s2=01101(13)， s3=11000(24)， s4=10011(19),人工智能_遗传算法,4.7 算法举例,交叉 设交叉率pc=100%,即s1全部染色体参与交叉 将s1与s2配对，s3与s4配对，交换后两位基因 新种群s2=s1=11001(25),s2=01100(12)， s3=11011(27)，s4=10000(16) 变异 设变异率pm=0.001 种群变异基因位数： pm*l*n=0.001*5*4=0.02 0.02不足1，本轮不做变异 -第一代遗传操作完成- 第二代种群s=s1=11001(25),s2=01100(12)， s3=11011(27)，s4=10000(16),人工智能_遗传算法,4.7 算法举例,选择 设从区间0,1产生4个随机数r1=0.25, r2=0.41, r3=0.77, r4=0.98 按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，1，1，1 选择产生种群s1=s1=11001(25),s2=01100(12)， s3=11011(27)， s4=10000(16),人工智能_遗传算法,4.7 算法举例,交叉 将s1与s2配对，s3与s4配对，交换后三位基因 新种群s2=s1=11100(28),s2=01001(9)， s3=11000(24)，s4=10011(19) 变异 种群变异基因位数： pm*l*n=0.001*5*4=0.02 0.02不足1，本轮不做变异 -第二代遗传操作完成- 第三代种群s=s1=11100(28),s2=01001(9)， s3=11000(24)，s4=10011(19),人工智能_遗传算法,4.7 算法举例,选择 设从区间0,1产生4个随机数r1=0.25, r2=0.41, r3=0.77, r4=0.98 按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为2，0，1，1 选择产生种群s1=s1=11100(28),s2=11100(28)， s3=11000(24)， s4=10011(19),人工智能_遗传算法,4.7 算法举例,交叉 将s1与s4配对，s2与s3配对，交换后两位基因 新种群s2=s1=11111(31),s2=11100(28)， s3=11000(24)，s4=10000(16) 变异 种群变异基因位数： pm*l*n=0.001*5*4=0.02 0.02不足1，本轮不做变异 -第三代遗传操作完成- 第四代种群s=s1=11111(31),s2=11100(28)， s3=11000(24)，s4=10000(16),人工智能_遗传算法,4.7 算法举例,在这一代种群中已经出现了适应度最高的染色体s1=11111。 遗传操作终止，将染色体“11111”作为最终结果输出。 将染色体“11111”解码为表现型，得所求最优解：31 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961,人工智能_遗传算法,4.7 算法举例,y,人工智能_遗传算法,小结,遗传算法 模拟自然选择和有性繁殖、遗传变异的自然原理 实现优化搜索和问题求解 遗传操作 选择算子 交叉算子