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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2/23/2017,#,几种智能算法概述及其应用,汇报内容,几种,智能算法概述,遗传算法,粒子群算法,模拟退火算法,蚁群算法,智能,算法,概述,1,、遗传,算法,遗传算法（,GeneticAlgorithm,，,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,、,蚁,群,算法背景,单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物,信息素，信息素浓度越高，表示对应路径越短。,当一条路上的信息素越来越,多，,后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素,浓度。,智能,算法,概述,4,、,蚁,群,算法模型,蚁群转移概率公式,信息更新公式,Ant cycle system,Ant quantity system,Ant density system,智能,算法,概述,4,、蚁,群,算法二维路径规划,问题描述与流程,二维空间中存在,4,个障碍物，寻求一条从起点,S,到终点,T,的最优路径,智能,算法,概述,4,、,蚁,群,算法路径规划结果,谢谢观看,