1、几种智能算法概述及其应用汇报内容几种智能算法概述1.遗传算法2.粒子群算法3.模拟退火算法4.蚁群算法22020/4/12智能算法概述1、遗传算法遗传算法（GeneticAlgorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。32020/4/12智能算法概述染色体：生物遗传物质主要载体。基因：扩展生物性状的遗传物质的功能单元和结构单位。基因座：染色体中基因的位置。等位基因：基因所取的值。生物遗传概念遗产算法中的
2、应用适者生存目标值比较大的解被选择的可能性大个体可能解染色体解的编码（字符串、向量等）基因解中每一分量的特征适应性适应函数值群体根据适应函数值选定的一组解（解的个数为群体的规模）婚配交叉选择两个染色体进行交叉产生一组新的染色体的过程变异编码的某一分量发生变化的过程1、遗传算法42020/4/12智能算法概述遗传算法流程遗传算法改进方向1、遗传算法与非线性规划结合2、与BP神经网络结合 3、基于量子遗传算法寻优 4、多种群遗传算法 5、多层编码遗传算法1、遗传算法52020/4/12智能算法概述TSP（旅行商问题）问题描述与结果：已知n个城市互相之间距离，某人从某城市出发访问每个城市且仅一次，如
3、何安排才能使其所走路线最短1、遗传算法62020/4/12智能算法概述制孔路径优化在飞机装配线上用机器人带动末端执行器进行制孔，执行器由初始位置依次移动到每一孔位，最后返回初始位置，目标为所走路径最短，时间最少产品生产安排一个周期内生产n种产品，开销包括制造成本以及产品转换开支，因此生产成本与生产顺序有关，目标为使转换成本最低1、遗传算法72020/4/12智能算法概述2、粒子群算法产生背景粒子群算法（Particle Swarm Optimization，PSO）源于对鸟类捕食行为的研究，一群鸟随机分布在一个区域中，在这片区域只有一块食物，鸟类捕食时，所有鸟都不知道食物在哪里，但是他们知道当
4、前位置距离食物还有多远，那么找到食物最简单有效的策略就是搜寻当前距离食物最近的鸟的周围区域。82020/4/12智能算法概述2、粒子群算法基本思想每个潜在解都是搜索空间的一只鸟，称之为“粒子”，所有粒子都有一个由被优化函数决定的适应值，还有一个速度决定其飞行方向及距离。粒子们追随当前最优粒子在解空间搜索，然后通过迭代找到最优解。在每一次的迭代中，粒子根据两个极值来更新自己：粒子本身变化过程中的最优解，称为个体极值 整个种群目前找到的最优解，称为全局极值有时为了避免陷入局部最优，可使用整体中一部分作为粒子邻居，则所有邻居中的极值就是局部极值。92020/4/12智能算法概述2、粒子群算法基本模型
5、设群体规模为N，目标搜索空间为D维。?11,TiiiiDXv vv?1,2,i iN?11,TiiiiDVv vv?1,2,iN?11,TiiiiDPppp?表示第个粒子的位置。表示i的飞翔速度表示i自身搜索到的最优点?11 12 211kkkkkkididdididdgdidkkkidididvvcrpxc rpxxxv?102020/4/12智能算法概述2、粒子群算法基本模型学习因子c1：c1=0，则只有社会，没有自我学习因子c2：c2=0，则只有自我，没有社会112020/4/12智能算法概述2、粒子群算法改进加入惯性权重由基本粒子群算法模型中粒子位置进化方程可看出，不同时刻位置由飞行速
6、度决定，因此飞行速度大小直接影响算法的全局收敛性。惯性权重分类：1.固定权重，种群规模越大，所需权重越小2.时变权重3.随机权重122020/4/12智能算法概述3、模拟退火算法背景退火是指将固体加热到足够高的温度，使分子呈现随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。该过程属于热力学范畴，主要由三部分组成：加温过程、等温过程以及冷却过程。132020/4/12智能算法概述3、模拟退火算法由统计力学研究表明，在温度T，分子滞留在状态r的概率满足波兹曼概率分布P?=?=1?其中，为状态r的能量，为概率分布的标准化因子?SDexp?s?=当时即分子停留在能量小
7、的状态概率大12EE?12112BBE-E-=1-exp-k TE1P E=EP E=Eexp-Z Tk T?142020/4/12智能算法概述3、模拟退火算法流程初始化：初始温度T（充分大），初始解状态S（算法迭代的起点），每个T值的迭代次数L对做第三至第六步：对当前解随机扰动，产生新解S计算增量，其中为评价函数若 0 则接受S为新的当前解，否则以概率接受S作为新的当前解如果满足终止条件则输出当前解作为最优解，结束程序?Sf?21SSdfff?exp/df T?1,kL?152020/4/12智能算法概述4、蚁群算法背景单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物信息
8、素，信息素浓度越高，表示对应路径越短。当一条路上的信息素越来越多，后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度。162020/4/12智能算法概述4、蚁群算法模型蚁群转移概率公式信息更新公式Ant cycle systemAnt quantity systemAnt density system?,0,kkks Jii ji jif jJii si spi jotherwise?111,0ijijijijnkijktt?/,0,ijkkQ L?其他/,0,ijijkQ d?其他,0,ijkQ?其他172020/4/12智能算法概述4、蚁群算法二维路径规划问题描述与流程二维空间中存在4个障碍物，寻求一条从起点S到终点T的最优路径空间模型建立初始路径规划初始化参数开始搜索到达终点信息素更新是否结束得到最优路径是否182020/4/12智能算法概述4、蚁群算法路径规划结果192020/4/12谢谢观看谢谢观看202020/4/12
