几种智能算法概述及其应用

1、几种智能算法概述及其应用 汇报内容 几种智能算法概述 1.遗传算法 2.粒子群算法 3.模拟退火算法 4.蚁群算法 智能算法概述 1、遗传算法 遗传算法（GeneticAlgorithm，GA）是一种进化算法，其基本 原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传 算法的做法是把问题参数编码为染色体， 再利用迭代的方式进行选择、交叉以及 变异等运算来交换种群中染色体的信息， 最终生成符合优化目标的染色体。 智能算法概述 染色体：生物遗传物质主要载体。 基因：扩展生物性状的遗传物质 的功能单元和结构单位。 基因座：染色体中基因的位置。 等位基因：基因所取的值。 生物遗传概念遗产算法中

2、的应用 适者生存目标值比较大的解被选择的可能性大 个体可能解 染色体解的编码（字符串、向量等） 基因解中每一分量的特征 适应性适应函数值 群体根据适应函数值选定的一组解（解的个数为群 体的规模） 婚配交叉选择两个染色体进行交叉产生一组新的染 色体的过程 变异编码的某一分量发生变化的过程 1、遗传算法 智能算法概述 遗传算法流程 遗传算法改进方向 1、遗传算法与非线性规划结合2、与BP神经网络结合3、基于量子遗传算 法寻优4、多种群遗传算法5、多层编码遗传算法 1、遗传算法 智能算法概述 TSP（旅行商问题）问 题描述与结果： 已知n个城市互相之 间距离，某人从某城市 出发访问每个城市且仅 一次

3、，如何安排才能使 其所走路线最短 1、遗传算法 智能算法概述 制孔路径优化 在飞机装配线上用机器 人带动末端执行器进行制 孔，执行器由初始位置依 次移动到每一孔位，最后 返回初始位置，目标为所 走路径最短，时间最少 产品生产安排 一个周期内生产n种 产品，开销包括制造成 本以及产品转换开支， 因此生产成本与生产顺 序有关，目标为使转换 成本最低 1、遗传算法 智能算法概述 2、粒子群算法产生背景 粒子群算法（Particle Swarm Optimization， PSO）源于 对鸟类捕食行为的研究，一群鸟随机分布在一个区域中，在这 片区域只有一块食物，鸟类捕食时，所有鸟都不知道食物在哪 里，

4、但是他们知道当前位置距离食物 还有多远，那么找到食物最简单有效 的策略就是搜寻当前距离食物最近的 鸟的周围区域。 智能算法概述 2、粒子群算法基本思想 每个潜在解都是搜索空间的一只鸟，称之为“粒子”，所有粒子 都有一个由被优化函数决定的适应值，还有一个速度决定其飞行方 向及距离。粒子们追随当前最优粒子在解空间搜索，然后通过迭代 找到最优解。在每一次的迭代中，粒子根据两个极值来更新自己： 粒子本身变化过程中的最优解，称为个体极值 整个种群目前找到的最优解，称为全局极值 有时为了避免陷入局部最优，可使用整体中一部分作为粒子邻居， 则所有邻居中的极值就是局部极值。 智能算法概述 2、粒子群算法基本模

5、型 设群体规模为N，目标搜索空间为D维。 11 , T iiiiD Xvvv 1,2,i iN 11 , T iiiiD Vvvv 1,2,iN 11 , T iiiiD Pppp 表示第个粒子的位置。 表示i的飞翔速度 表示i自身搜索到的最优点 1 1 12 2 11 kkkkkk ididdididdgdid kkk ididid vvc rpxc rpx xxv 智能算法概述 2、粒子群算法基本模型 学习因子c1： c1=0，则只有社会， 没有自我 学习因子c2： c2=0，则只有自我， 没有社会 智能算法概述 2、粒子群算法改进加入惯性权重 由基本粒子群算法模型 中粒子位置进化方程可看

6、 出，不同时刻位置由飞行 速度决定，因此飞行速度 大小直接影响算法的全局 收敛性。 惯性权重分类： 1. 固定权重，种群规模 越大，所需权重越小 2. 时变权重 3. 随机权重 智能算法概述 3、模拟退火算法背景 退火是指将固体加热到足够高的温度，使分子呈现随机 排列状态，然后逐步降温使之冷却，最后分子以低能状态排 列，固体达到某种稳定状态。该过 程属于热力学范畴，主要由三部分 组成：加温过程、等温过程以及冷 却过程。 智能算法概述 3、模拟退火算法 由统计力学研究表明，在温度T，分子滞留在状态r的概率 满足波兹曼概率分布 其中，为状态r的能量，为概率分布的标准化因子 当时 即分子停留在能量小

7、的状态概率大 12 EE 121 12 BB E -E -=1-exp - k T E1 P E = EP E = Eexp - Z Tk T 智能算法概述 3、模拟退火算法流程 初始化：初始温度T（充分大），初始解状态S（算法迭代的 起点），每个T值的迭代次数L 对做第三至第六步： 对当前解随机扰动，产生新解S 计算增量，其中为评价函数 若0则接受S为新的当前解，否则以概率接 受S作为新的当前解 如果满足终止条件则输出当前解作为最优解，结束程序 Sf 21 SSdfff exp/dfT 1,kL 智能算法概述 4、蚁群算法背景 单个的蚂蚁为了避免自己迷路，它 在爬行时，同时也会释放一种特殊的分 泌物信息素，信息素浓度越高，表 示对应路径越短。当一条路上的信息素 越来越多，后来的蚂蚁选择这条路径的 概率也就越来越大，从而进一步增加了 该路径的信息素浓度。 智能算法概述 4、蚁群算法模型 蚁群转移概率公式信息更新公式 Ant cycle systemAnt quantity systemAnt density system , , , 0, k k k s Ji i ji j if jJi i si spi j otherwise 1 11 ,0 ij ijijij n k ij k tt /, 0, ij k k