人工智能---遗传算法.ppt

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={s?1=11100(28),s?2=11100(28)， s?3=11000(24)， s?4=10011(19)} 染色体 适应度 选择概率 累积概率 估计选中次数 s1=11100 784 0.44 0.44 2 s2=01001 81 0.04 0.48 0 s3=11000 576 0.32 0.80 1 s4=10011 361 0.20 1.00 1 人工智能---遗传算法全文共37页，当前为第30页。 4.7 算法举例 交叉 将s?1与s?4配对，s?2与s?3配对，交换后两位基因 新种群S2={s?1=11111(31),s?2=11100(28)， s?3=11000(24)，s?4=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)} 人工智能---遗传算法全文共37页，当前为第31页。 4.7 算法举例 在这一代种群中已经出现了适应度最高的染色体s1=11111。 遗传操作终止，将染色体“11111”作为最终结果输出。 将染色体“11111”解码为表现型，得所求最优解：31 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961 人工智能---遗传算法全文共37页，当前为第32页。 4.7 算法举例 Y Y y=x2 8 13 19 24 X 第一代种群及其适应度 y=x2 12 16 25 27 X Y 第二代种群及其适应度 y=x2 9 19 24 28 X Y 第三代种群及其适应度 y=x2 16 24 28 31 X 第四代种群及其适应度 人工智能---遗传算法全文共37页，当前为第33页。 小结 遗传算法 模拟自然选择和有性繁殖、遗传变异的自然原理 实现优化搜索和问题求解 遗传操作 选择算子 交叉算子 变异算子 人工智能---遗传算法全文共37页，当前为第34页。 小结 特点 直接对结构对象操作，不存在求导和函数连续性的限定； 遗传算法不是从单个点，而是从一个点地群体开始搜索； 具有内在的隐并行性和较好的全局寻优能力； 采用概率化寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定地规则； 鲁棒性 人工智能---遗传算法全文共37页，当前为第35页。 小结 遗传算法 图搜索 解空间搜索 问题空间搜索-解 随机搜索、随机选取初始点集/种群 固定初始/目标节点 寻找最优解/次优解 寻找解 点集-点集、并行计算 点-点 需适应度函数 需先验知识 全局搜索 约束较多 算法比较 人工智能---遗传算法全文共37页，当前为第36页。 参考书目 遗传算法:理论、应用与软件实现，王小平，曹立明著，西安交通大学出版社，2002.1 遗传算法与工程优化，玄光男，程润伟著 ，清华大学出版社，2004.1 人工智能---遗传算法全文共37页，当前为第37页。 * 07/16/96 * ## Introduction to Artificial Intelligence 第4章 遗传算法 4.1 基本概念 4.2 选择算子 4.3 交叉算子 4.4 变异算子 4.5 基本遗传算法 4.6 基本实现技术 4.7 遗传算法应用 人工智能---遗传算法全文共37页，当前为第1页。 第4章 遗传算法 生物进化 自然法则 优胜劣汰 适者生存 有性繁殖 基因通过有性繁殖不断进行混合和重组 遗传算法 从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法 人工智能---遗传算法全文共37页，当前为第2页。 第4章 遗传算法 应用 函数优化 组合优化：旅行商、图形化分… 生产调度：车间调度、生产规划… 自动控制：控制器、参数辨识… 机器人智能控制：机器人路径规划、运动轨迹规划… 图像处理与模式识别：特征提取、图像分割… 人工生命：进化模型、学习模型、行为模型… 遗传程序设计 机器学习 人工智能---遗传算法全文共37页，当前为第3页。