课件：几种智能算法概述及其应用.ppt

几种智能算法概述及其应用 汇报内容 几种智能算法概述 遗传算法 粒子群算法 模拟退火算法 蚁群算法 智能算法概述 1、遗传算法 遗传算法（Genetic Algorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体， 再利用迭代的方式进行选择、交叉以及 变异等运算来交换种群中染色体的信息， 最终生成符合优化目标的染色体。 智能算法概述 染色体：生物遗传物质主要载体。 基因：扩展生物性状的遗传物质的功能单元和结构单位。 基因座：染色体中基因的位置。 等位基因：基因所取的值。 生物遗传概念 遗产算法中的应用 适者生存 目标值比较大的解被选择的可能性大 个体 可能解 染色体 解的编码（字符串、向量等） 基因 解中每一分量的特征 适应性 适应函数值 群体 根据适应函数值选定的一组解（解的个数为群体的规模） 婚配 交叉选择两个染色体进行交叉产生一组新的染色体的过程 变异 编码的某一分量发生变化的过程 1、遗传算法 智能算法概述 遗传算法流程 遗传算法改进方向 1、遗传算法与非线性规划结合 2、与BP神经网络结合 3、基于量子遗传算法寻优 4、多种群遗传算法 5、多层编码遗传算法 1、遗传算法 智能算法概述 TSP（旅行商问题）问题描述与结果： 已知n个城市互相之间距离，某人从某城市出发访问每个城市且仅一次，如何安排才能使其所走路线最短 1、遗传算法 智能算法概述 制孔路径优化 在飞机装配线上用机器人带动末端执行器进行制孔，执行器由初始位置依次移动到每一孔位，最后返回初始位置，目标为所走路径最短，时间最少 产品生产安排 一个周期内生产n种产品，开销包括制造成本以及产品转换开支，因此生产成本与生产顺序有关，目标为使转换成本最低 1、遗传算法 智能算法概述 2、粒子群算法产生背景 粒子群算法（Particle Swarm Optimization， PSO）源于对鸟类捕食行为的研究，一群鸟随机分布在一个区域中，在这片区域只有一块食物，鸟类捕食时，所有鸟都不知道食物在哪里，但是他们知道当前位置距离食物 还有多远，那么找到食物最简单有效 的策略就是搜寻当前距离食物最近的 鸟的周围区域。 智能算法概述 2、粒子群算法基本思想 每个潜在解都是有哪些信誉好的足球投注网站空间的一只鸟，称之为“粒子”，所有粒子都有一个由被优化函数决定的适应值，还有一个速度决定其飞行方向及距离。粒子们追随当前最优粒子在解空间有哪些信誉好的足球投注网站，然后通过迭代找到最优解。在每一次的迭代中，粒子根据两个极值来更新自己： 粒子本身变化过程中的最优解，称为个体极值 整个种群目前找到的最优解，称为全局极值 有时为了避免陷入局部最优，可使用整体中一部分作为粒子邻居，则所有邻居中的极值就是局部极值。 智能算法概述 2、粒子群算法基本模型 设群体规模为N，目标有哪些信誉好的足球投注网站空间为D维。 表示第 个粒子的位置。 表示i的飞翔速度 表示i自身有哪些信誉好的足球投注网站到的最优点 智能算法概述 2、粒子群算法基本模型 学习因子c1： c1= 0，则只有社会，没有自我 学习因子c2： c2= 0，则只有自我，没有社会 智能算法概述 2、粒子群算法改进——加入惯性权重 由基本粒子群算法模型中粒子位置进化方程可看出，不同时刻位置由飞行速度决定，因此飞行速度大小直接影响算法的全局收敛性。 惯性权重分类： 固定权重，种群规模越大，所需权重越小 时变权重 随机权重 智能算法概述 3、模拟退火算法背景 退火是指将固体加热到足够高的温度，使分子呈现随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。该过 程属于热力学范畴，主要由三部分 组成：加温过程、等温过程以及冷 却过程。 智能算法概述 3、模拟退火算法 由统计力学研究表明，在温度T，分子滞留在状态r的概率满足波兹曼概率分布 其中， 为状态r的能量， 为概率分布的标准化因子 当 时 即分子停留在能量小的状态概率大 智能算法概述 3、模拟退火算法流程 ⑴ 初始化：初始温度 T（充分大），初始解状态 S（算法迭代的起点）， 每个T值的迭代次数L ⑵ 对 做第三至第六步： ⑶ 对当前解随机扰动，产生新解S′ ⑷ 计算增量 ，其中 为评价函数 ⑸ 若 0 则接受S′为新的当前解，否则以 概率接受S′作为新的当前解 ⑹ 如果满足终止条件则输出当前解作为最优解，结束程序 智能算法概述 4