人工智能---遗传算法3735477.pptx
第4章 遗传算法4.1 4.1 基本概念基本概念 4.2 4.2 选择算子选择算子 4.3 4.3 交叉算子交叉算子 4.4 4.4 变异算子变异算子4.5 4.5 基本遗传算法基本遗传算法 4.6 4.6 基本实现技术基本实现技术4.7 4.7 遗传算法应用遗传算法应用 第4章 遗传算法n生物进化n自然法则n优胜劣汰n适者生存n有性繁殖n基因通过有性繁殖不断进行混合和重组n遗传算法n从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法第4章 遗传算法n应用n函数优化n组合优化：旅行商、图形化分n生产调度：车间调度、生产规划n自动控制：控制器、参数辨识n机器人智能控制：机器人路径规划、运动轨迹规划n图像处理与模式识别：特征提取、图像分割n人工生命：进化模型、学习模型、行为模型n遗传程序设计n机器学习4.1 基本概念 n个体个体n个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼n一个个体也就是搜索空间中的一个点n种群种群n 种群(population)就是模拟生物种群而由若 干个体组成的群体n它一般是整个搜索空间的一个很小的子集n通过对种群实施遗传操作，使其不断更新换代而实现对整个论域空间的搜索4.1 基本概念 n适应度适应度(fitness)n借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度n适应度函数适应度函数(fitness function)n问题中的全体个体与其适应度之间的一个对应关系n一般是一个实值函数n该函数就是遗传算法中指导搜索的评价函数 4.1 基本概念 n染色体染色体(chromosome)n染色体是由若干基因组成的位串（生物学）n个体对象由若干字符串组成来表示（遗传算法）n遗传算法遗传算法(genetic algorithm)n染色体就是问题中个体的某种字符串形式的编码表示n染色体以字符串来表示n基因是字符串中的一个个字符 个体 染色体 9 -1001 （2，5，6）-010 101 1104.1 基本概念 n遗传算子遗传算子(genetic operator)n选择(selection)n交叉(crossover)n变异(mutation)4.2 选择算子选择算子选择算子n模拟生物界优胜劣汰的自然选择法则的一种染色体运算n从种群中选择适应度较高的染色体进行复制，以生成下一代种群算法算法：n个体适应度计算n在被选集中每个个体具有一个选择概率n选择概率取决于种群中个体的适应度及其分布n个体适应度计算，即个体选择概率计算n个体选择方法n按照适应度进行父代个体的选择4.2 选择算子n个体适应度计算n按比例的适应度计算(proportional fitness assignment)n基于排序的适应度计算(rank-based fitness assignment)n个体选择方法n轮盘赌选择(roulette wheel selection)n随机遍历抽样(stochastic universal sampling)n局部选择(local selection)n截断选择(truncation selection)n锦标赛选择(tournament selection)4.2.1 按比例的适应度计算算法：算法：对一个规模为N的种群S，按每个染色体xiS的选择概率P(xi)所决定的选中机会，分N次从S中随机选择N个染色体，并进行复制 其中：nf为适应度函数nf(xi)为xi的适应度优胜劣汰1.概率越高，随机选中概率越大2.概率越高，选中次数越多3.适应度高的染色体后代越多4.2.3 轮盘赌选择原理：原理：n做一个单位圆，然后按各个染色体的选择概率将圆面划分为相应的扇形区域n转动轮盘，轮盘静止时指针指向某一扇区，即为选中扇区，相应的个体/染色体即被选中 4.2.3 轮盘赌选择算法：算法：n在0,1区间，产生一个均匀分布的伪随机数rn若rq1，则染色体1被选中n若qk-10)n指数比例法：g(x)=exp(a f(x)(a0)n幂指数比例法：g(x)=(f(x)a (a为偶数)4.7 算法举例例例7.17.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值分析分析n原问题转化为0,31中寻找能使y取最大值的点xn区间0,31为论域空间/解空间nx为个体对象n函数f(x)=x2 可作为适应度函数4.7 算法举例解解：n定义适应度函数，编码染色体n适应度函数取f(x)=x2 n用5位二进制数作为个体x的基因型编码/染色体n设定种群规模，产生初始种群n种群规模N=4n初始种群S=s1=01101(13),s2=11000(24)，s3=01000(8)，s4=10011(19)4.7 算法举例n计算各代种群中各染色体的适应度，并进行遗传操作 选择选择n设从区间0,1产生4个随机数r1=0.45,r2=0.11,r3=0.57,r4=0.98n按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，2，0，1n选择产生种群S1=s1=11000(24),s2=01101(13)，s3=11000(24)，s4=10011(19)染色体染色体适应度适应度选择概率选择概率累积概率累积概率估计选中次数估计选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0014.7 算法举例 交叉交叉n设交叉率Pc=100%,即S1全部染色体参与交叉n将s1与s2配对，s3与s4配对，交换后两位基因n新种群S2=s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)变异变异n设变异率Pm=0.001n种群变异基因位数：Pm*L*N=0.001*5*4=0.02n0.02不足1，本轮不做变异-第一代遗传操作完成-第二代种群S=s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)4.7 算法举例 选择选择n设从区间0,1产生4个随机数r1=0.25,r2=0.41,r3=0.77,r4=0.98n按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，1，1，1n选择产生种群S1=s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)染色体染色体适应度适应度选择概率选择概率累积概率累积概率估计选中次数估计选中次数s1=110016250.360.361s2=011001440.080.441s3=110117290.410.851s4=100002560.151.0014.7 算法举例 交叉交叉n将s1与s2配对，s3与s4配对，交换后三位基因n新种群S2=s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)变异变异n种群变异基因位数：Pm*L*N=0.001*5*4=0.02n0.02不足1，本轮不做变异-第二代遗传操作完成-第三代种群S=s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)4.7 算法举例 选择选择n设从区间0,1产生4个随机数r1=0.25,r2=0.41,r3=0.77,r4=0.98n按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为2，0，1，1n选择产生种群S1=s1=11100(28),s2=11100(28)，s3=11000(24)，s4=10011(19)染色体染色体适应度适应度选择概率选择概率累积概率累积概率估计选中次数估计选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0014.7 算法举例 交叉交叉n将s1与s4配对，s2与s3配对，交换后两位基因n新种群S2=s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)变异变异n种群变异基因位数：Pm*L*N=0.001*5*4=0.02n0.02不足1，本轮不做变异-第三代遗传操作完成-第四代种群S=s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)4.7 算法举例n在这一代种群中已经出现了适应度最高的染色体s1=11111。n遗传操作终止，将染色体“11111”作为最终结果输出。n将染色体“11111”解码为表现型，得所求最优解：31n将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961 4.7 算法举例YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度小结n遗传算法遗传算法n模拟自然选择和有性繁殖、遗传变异的自然原理n实现优化搜索和问题求解n遗传操作遗传操作n选择算子n交叉算子n变异算子小结特点特点n直接对结构对象操作，不存在求导和函数连续性的限定；n遗传算法不是从单个点，而是从一个点地群体开始搜索；n具有内在的隐并行性和较好的全局寻优能力；n采用概率化寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定地规则；n鲁棒性小结遗传算法遗传算法图搜索图搜索解空间搜索问题空间搜索-解随机搜索、随机选取初始点集/种群固定初始/目标节点寻找最优解/次优解寻找解点集-点集、并行计算点-点需适应度函数需先验知识全局搜索约束较多算法比较算法比较参考书目1.遗传算法:理论、应用与软件实现，王小平，曹立明著，西安交通大学出版社，2002.1 2.遗传算法与工程优化，玄光男，程润伟著，清华大学出版社，2004.1 演讲完毕，谢谢观看！
