《智能仿生算法概述概要ppt课件.ppt》由会员分享，可在线阅读，更多相关《智能仿生算法概述概要ppt课件.ppt（39页珍藏版）》请在三一办公上搜索。
1、智能仿生算法概述,丁建立 中国民航大学计算机学院 24092486 13920250068 J,一、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D
2、1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,
3、13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C
4、3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,1
5、0,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最
6、优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6
7、,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f
8、4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E,旅行商问题(TSPTraveling Salesman Problem),旅行商问题即TSP问题，又称Hamiltion回路问题。一个商人打算从所驻城市到其他城市推销商品，每个城市恰好去一次，最后返回出发地，问如何安排其旅行路线，使其所走的路线的总长度最短？,组合爆炸,完全枚
9、举的方法求得最优解，若固定一个城市为起点，则需要（n-1）！个枚举，以计算机1秒可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为24秒，随着城市数增加，计算时间增加非常之快，当城市数增加到30时，计算时间约为10.8年，实际计算中已无法接受。同样，聚类问题的可划分方式有个，Job-Shop可能排列方式有个。,算法复杂度,表1-1 n增加过程中几种时间复杂度函数计算时间的比较,典型组合优化问题,旅行商问题(TSPTraveling Salesman Problem)加工调度问题（Scheduling Problem）0-1背包问题（Knapsack Problem）装箱问题（Bin
10、 Packing Problem）图着色问题（Graph Coloring Problem）聚类问题（Clustering Problem）,组合优化问题,组合优化：组合优化就是离散优化，它是通过数学方法寻找离散事件的最优编排、分组、次序或筛选等。这类问题可用数学模型描述为：目标函数：约束条件：决策变量：，其中D为有限个点组成的集合。特点：可行解集合为有限点集，只要将D中有限个点逐一判别是否满足的约束并比较目标值的大小，就可以得到该问题的最优解。对于组合优化问题，最关心的是如何找到有效的算法求得一个最优解。,算法的时间和空间复杂性,算法的时间复杂性和空间复杂性对计算机的求解能力有重大影响。沿用
11、实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性；算法执行期间占用的存储单元则定义为算法的空间复杂性。问题的复杂性一般表示为问题规模的函数，按照计算复杂性理论研究问题求解的难易程度，可把问题分为P类、NP类和NP完全类。,问题,定义：对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项式函数 和非负常数，使得，（1-1）（其中 是计算总次数，是二进制输入长度）对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，记作P(Polynomial)。通常称这种比P类问题更广泛的问题为非
12、多项式确定问题NP（Non-deterministic Polynomial）。但迄今为止，许多优化问题仍没有找到求得最优解的多项式时间算法。,P NP NP-C NP-hard 图 四类问题的关系图图1-1表示，P NP，NP-C NP-hard,NP与NP-hard的公共部分为NP-C。在NP中，除P和NP-C，还有一部分问题的复杂性是未知的。到目前为止，组合优化问题研究中大家一般都接受的一个假设是P NP。,智能仿生算法,智能优化算法（Intelligent Optimization Algorithms）或称现代启发式算法（Meta-Heuristic Algorithms）它是通过模
13、拟或揭示某些自然现象或过程而发展起来，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段。它具有全局的、并行高效的优化性能，鲁棒性、通用性强，无需问题特殊信息等优点。,模拟退火算法（SA）,该算法建立在蒙特卡罗(Mente Carlo)原理的基础上，模拟固体退火过程，是一种启发式随机优化方法，1953年被Metropolis等首次提出，1983年Kirkpatrick等将其用于组合优化，适合求解大规模优化问题。特点：算法实现简单，使用灵活，可跳出局部极值区，但收敛速度慢，有关控制难以确定等。,禁忌搜索算法（TS）,它是F.Glover
14、 在20世纪60年代末提出的一种模拟智力过程而扩展邻域的启发式搜索算法。特点：在搜索过程中获得知识，能够以较大的概率跳出局部极值，以其较高的求解质量和效率已在许多组合优化问题中显示出强大的寻优能力，但存在对初始解依赖性较强及搜索仅能单对单操作的缺点。,Hopfield神经网络,它是美国物理学家J.J.Hopfield于1982年首先提出的。其演变过程是一个非线性动力系统，系统的稳定性可用所谓的“能量函数”（即李雅普诺夫或哈密尔顿函数）进行分析。如果把能量函数视为一个优化问题的目标函数，那么从这个初态朝稳定点的演变过程就是一个求解该优化问题的过程。它主要用于模拟神经网络的记忆机理，是一种全连接反
15、馈型神经网络，它有离散型（DHNN）和连续型（CHNN）两种。特点：具有单调下降、并行计算和联想记忆等优点，但同时也存在着收敛速度慢，易陷入局部极值点等缺点，且网络合适的隐含层数目和节点数目确定较困难。,遗传算法（GA）,它是美国密执安大学的John Holland教授于1975年首先提出的一类仿生型优化算法。它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上，子代是父代遗传基因在染色体上的有序排列”为基础，模拟生物界进化过程。特点：具有大范围全局搜索的能力，潜在的并行性、随机性，鲁棒性强，过程简单。缺点是不能很好的利用系统反馈信息，冗余迭代多，影
16、响求优化解效率。,蚂蚁算法（A）,它是意大利学者M.Dorigo1991年提出的一种源于大自然新的仿生类随机优化算法。它主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初称蚁群优化方法（ant colony optimization简称ACO）。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统（ant system简称AS）。其原理是一种正反馈机制或称增强型学习系统，它通过信息素的不断更新达到最终收敛于最优路径上。特点：具有并行、随机、全局优化的优点，其缺点是初期信息素匮乏，求解速度慢。,粒子群算法（PSO）,粒子群优化(Particle Swarm Optimization)是一个典
17、型的集群集智能的代表方法之一，它是Kennedy 和 Eberhart在1995年IEEE 国际的会议提出的，它起源于对一个简化社会系统的仿真，它和人工生命理论以及鸟类或鱼类的群集现象有十分明显的联系。PSO是通过一群随机粒子反复迭代找到最优解，每一次迭代中，粒子通过追踪个体极值和群体极值来更新自己，个体极值是粒子本身找到的最优解，群体极值是整个种群目前找到最优解。标准 PSO算法收敛速度快，但容易陷入局部极小。,免疫算法（IA）,免疫算法（Immune Algorithm)是由T.Fukuda等人1998年提出并发展起来的一类求解多态优化问题的算法，它模拟生物免疫系统的识别多样性与多样性免疫
18、细胞的产生与维持机制。其原理主要是通过抗原、抗体、抗原与抗体之间的亲和性分别对应优化目标的目标函数、优化解、以及它们之间的匹配程度。特点：多样性和自我调节能够获得许多优化问题的最优解，记忆训练和不同抗体的产生能够很快得到优化解。,DNA计算,它是美国加利福尼亚大学的Adleman博士1994年第一次提出的一种借助生物分子DNA的结构利用现代分子生物技术进行计算的新方法，它开创了以化学反应作为计算工具的先例，并成功地在DNA溶液试管中对哈密尔顿有向路径问题进行求解实验。特点：DNA计算完全是一种新的概念，具有高度的并行性、海量存储、低能耗、资源丰富等显著特点。但最优解如何分离、“输出技术”瓶颈、
19、“伪解”与“误差”如何避免等面临巨大的技术挑战。,算法,创始人,优化机制,关键参数,初始温度、退温函数、状态产生方式、抽样稳定准则,基于Monte Carlo全局概率型串行搜索优化算法,具有记忆功能的全局逐步优化算法,列表大小、邻域函数结构与数量,基于生物进化与遗传全局性并行优化算法,种群数目及复制、交叉、变异操作概率,基于神经网络原理及系统演变联想记忆算法,神经元数目、输入输出变量、隐含层数,具有强化学习功能的全局并行优化算法,初始信息素、信息素增量、信息素积累量、消失因子、启发因子,以化学反应为计算工具的分子生物计算方法,生物酶、超声波、亲和层析、克隆、诱变、纯化、电泳、磁珠分离,Hopf
20、ield,Glove,Holland,Dorigo,模拟生物免疫系统的识别细胞产生的优化算法,SA,TS,GA,NN,ACO,IA,PSO,DNA,Kirkpatrick,Kennedy&Eberhart,Fukuda,抗原、抗体、抗原与抗体之间的亲和性,模拟鸟类或鱼类的群集现象优化算法,粒子反复迭代，粒子个体极值，粒子群体极值,表1-2 几种智能优化算法的优化机制与关键参数,智能优化算法与普通搜索算法区别,（1）普通搜索算法是以一个解为迭代的初始值，而智能优化算法是以一组解(种群)为迭代的初始值；（2）智能优化算法需要将问题的优化参数进行编码，映射为可进行启发式操作的数据结构，而普通搜索算法
21、不需要此过程；（3）普通搜索算法的搜索策略为确定性的，而智能优化算法的搜索策略是结构化和随机化的(概率型)；（4）智能优化算法仅用到优化的目标函数值的信息，不必用到目标函数的导数信息，而普通搜索算法的大多数算法需要导数信息；,智能优化算法与普通搜索算法区别,（5）智能优化算法对问题的数学描述不要求满足可微性、凸性等条件，而普通搜索算法对此有着较严格的要求；（6）智能优化算法具有全局优化性能、鲁棒性强、通用性强且适于并行处理的特点，而普通搜索算法不具备这些优点。因而，智能优化算法的适用范围非常广泛，且其算法易于修改，特别适用大规模的并行计算。,表1-3 几种智能优化算法的研究概况,注：“”表示有
22、相当部分成果，“？”表示仅有少量结果，“”表示未开发。,智能优化算法可研究问题,（1）缺乏普遍适用的算法收敛性理论；（2）缺乏完备计算搜索效率及时空复杂度理论评价体系；（3)没有建立起完备的算法结构框架；（4）算法的理论基础还不能清楚地解释算法在应用过程中出现的各种问题；（5）算法参数的选择主要还是凭经验选取；（6）对操作算子的作用机理及作用效果的分析仍不充分；(7)由于它们的研究机制和侧重点的不同，使得研究成果相当分散。,课程学习,重点蚂蚁算法，免疫算法，粒子群算法,DNA计算、其他仿生算法；分五组讨论，每组34人，每人选一种算法，每人阅读两篇论文，在课上讲解讨论，最后，每人根据自己的课程学习写一篇有关算法的课程论文；根据阅读论文讲解情况和最后提交课程论文判定成绩。,
