智能仿生算法概述模板课件

智能仿生算法概述xxxx中国民航大学计算机学院

1谢谢观赏2019-5-18智能仿生算法概述2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=03谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=04谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=55谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=56谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=87谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=78谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=89谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=2110谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=1411谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2112谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B213谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C114谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1

（C1，D1）D115谢谢观赏2019-5-182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1

（C1，D1）D1

（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E16谢谢观赏2019-5-182511214106104131112396581052C1旅行商问题

(TSP—TravelingSalesmanProblem)旅行商问题即TSP问题，又称Hamiltion回路问题。一个商人打算从所驻城市到其他城市推销商品，每个城市恰好去一次，最后返回出发地，问如何安排其旅行路线，使其所走的路线的总长度最短？17谢谢观赏2019-5-18旅行商问题

(TSP—TravelingSales组合爆炸完全枚举的方法求得最优解，若固定一个城市为起点，则需要（n-1）！个枚举，以计算机1秒可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为24秒，随着城市数增加，计算时间增加非常之快，当城市数增加到30时，计算时间约为10.8年，实际计算中已无法接受。同样，聚类问题的可划分方式有个，Job-Shop可能排列方式有个。18谢谢观赏2019-5-18组合爆炸完全枚举的方法求得最优解，若固定一个城市为起点，则需算法复杂度表1-1n增加过程中几种时间复杂度函数计算时间的比较

函数nnlognn22nn!N=1010ns10ns100ns1.0μs3.6msN=2020ns26ns400ns1.0ms77.1年N=3030ns44.3ns900ns1.1s8.4×1013.世纪N=4040ns64.1ns1.6μs18.3年2.6×1029.世纪N=100100ns200ns10μs4.0世纪3.0×10139.世纪19谢谢观赏2019-5-18算法复杂度表1-1n增加过程中几种时间复杂度函数计算时典型组合优化问题旅行商问题

(TSP—TravelingSalesmanProblem)加工调度问题（SchedulingProblem）0-1背包问题（KnapsackProblem）装箱问题（BinPackingProblem）图着色问题（GraphColoringProblem）聚类问题（ClusteringProblem）20谢谢观赏2019-5-18典型组合优化问题旅行商问题20谢谢观赏2019-5-18

组合优化问题组合优化：组合优化就是离散优化，它是通过数学方法寻找离散事件的最优编排、分组、次序或筛选等。这类问题可用数学模型描述为：目标函数：约束条件：决策变量：，其中D为有限个点组成的集合。特点：可行解集合为有限点集，只要将D中有限个点逐一判别是否满足的约束并比较目标值的大小，就可以得到该问题的最优解。对于组合优化问题，最关心的是如何找到有效的算法求得一个最优解。

21谢谢观赏2019-5-18组合优化问题组合优化：组合优化就是离散优化，它是通过数学算法的时间和空间复杂性算法的时间复杂性和空间复杂性对计算机的求解能力有重大影响。沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性；算法执行期间占用的存储单元则定义为算法的空间复杂性。问题的复杂性一般表示为问题规模的函数，按照计算复杂性理论研究问题求解的难易程度，可把问题分为P类、NP类和NP完全类。22谢谢观赏2019-5-18算法的时间和空间复杂性算法的时间复杂性和空间复杂性对计算机的

ＮＰ问题定义：对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项式函数和非负常数，使得，（1-1）（其中是计算总次数，是二进制输入长度）

对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，记作P(Polynomial)。通常称这种比P类问题更广泛的问题为非多项式确定问题NP（Non-deterministicPolynomial）。但迄今为止，许多优化问题仍没有找到求得最优解的多项式时间算法。

23谢谢观赏2019-5-18ＮＰ问题定义：对于给定的一个优化问题，若存在一个求解该问题

PNPNP-CNP-hard

图１－１四类问题的关系图图1-1表示，PNP，NP-CNP-hard,NP与NP-hard的公共部分为NP-C。在NP中，除P和NP-C，还有一部分问题的复杂性是未知的。到目前为止，组合优化问题研究中大家一般都接受的一个假设是PNP。

24谢谢观赏2019-5-1824谢谢观赏2019-5-18智能仿生算法

智能优化算法（IntelligentOptimizationAlgorithms）或称现代启发式算法（Meta-HeuristicAlgorithms）它是通过模拟或揭示某些自然现象或过程而发展起来，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段。它具有全局的、并行高效的优化性能，鲁棒性、通用性强，无需问题特殊信息等优点。25谢谢观赏2019-5-18智能仿生算法智能优化算法（IntelligentOpti模拟退火算法（SA）该算法建立在蒙特卡罗(MenteCarlo)原理的基础上，模拟固体退火过程，是一种启发式随机优化方法，1953年被Metropolis等首次提出，1983年Kirkpatrick等将其用于组合优化，适合求解大规模优化问题。特点：算法实现简单，使用灵活，可跳出局部极值区，但收敛速度慢，有关控制难以确定等。26谢谢观赏2019-5-18模拟退火算法（SA）该算法建立在蒙特卡罗(MenteCar禁忌搜索算法（TS）它是F.Glover在20世纪60年代末提出的一种模拟智力过程而扩展邻域的启发式搜索算法。特点：在搜索过程中获得知识，能够以较大的概率跳出局部极值，以其较高的求解质量和效率已在许多组合优化问题中显示出强大的寻优能力，但存在对初始解依赖性较强及搜索仅能单对单操作的缺点。27谢谢观赏2019-5-18禁忌搜索算法（TS）它是F.Glover在20世纪60年代Hopfield神经网络它是美国物理学家J.J.Hopfield于1982年首先提出的。其演变过程是一个非线性动力系统，系统的稳定性可用所谓的“能量函数”（即李雅普诺夫或哈密尔顿函数）进行分析。如果把能量函数视为一个优化问题的目标函数，那么从这个初态朝稳定点的演变过程就是一个求解该优化问题的过程。它主要用于模拟神经网络的记忆机理，是一种全连接反馈型神经网络，它有离散型（DHNN）和连续型（CHNN）两种。特点：具有单调下降、并行计算和联想记忆等优点，但同时也存在着收敛速度慢，易陷入局部极值点等缺点，且网络合适的隐含层数目和节点数目确定较困难。28谢谢观赏2019-5-18Hopfield神经网络它是美国物理学家J.J.Hopfi遗传算法（GA）它是美国密执安大学的JohnHolland教授于1975年首先提出的一类仿生型优化算法。它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上，子代是父代遗传基因在染色体上的有序排列”为基础，模拟生物界进化过程。特点：具有大范围全局搜索的能力，潜在的并行性、随机性，鲁棒性强，过程简单。缺点是不能很好的利用系统反馈信息，冗余迭代多，影响求优化解效率。29谢谢观赏2019-5-18遗传算法（GA）它是美国密执安大学的JohnHolland蚂蚁算法（ＡA）它是意大利学者M.Dorigo1991年提出的一种源于大自然新的仿生类随机优化算法。它主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初称蚁群优化方法（antcolonyoptimization简称ACO）。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统（antsystem简称AS）。其原理是一种正反馈机制或称增强型学习系统，它通过信息素的不断更新达到最终收敛于最优路径上。特点：具有并行、随机、全局优化的优点，其缺点是初期信息素匮乏，求解速度慢。30谢谢观赏2019-5-18蚂蚁算法（ＡA）它是意大利学者M.Dorigo1991年提出粒子群算法（PSO）粒子群优化(ParticleSwarmOptimization)是一个典型的集群集智能的代表方法之一，它是Kennedy和Eberhart在1995年IEEE国际的会议提出的，它起源于对一个简化社会系统的仿真，它和人工生命理论以及鸟类或鱼类的群集现象有十分明显的联系。PSO是通过一群随机粒子反复迭代找到最优解，每一次迭代中，粒子通过追踪个体极值和群体极值来更新自己，个体极值是粒子本身找到的最优解，群体极值是整个种群目前找到最优解。标准PSO算法收敛速度快，但容易陷入局部极小。31谢谢观赏2019-5-18粒子群算法（PSO）粒子群优化(ParticleSwar免疫算法（IA）免疫算法（ImmuneAlgorithm)是由T.Fukuda等人1998年提出并发展起来的一类求解多态优化问题的算法，它模拟生物免疫系统的识别多样性与多样性免疫细胞的产生与维持机制。其原理主要是通过抗原、抗体、抗原与抗体之间的亲和性分别对应优化目标的目标函数、优化解、以及它们之间的匹配程度。特点：多样性和自我调节能够获得许多优化问题的最优解，记忆训练和不同抗体的产生能够很快得到优化解。32谢谢观赏2019-5-18免疫算法（IA）免疫算法（ImmuneAlgorithm)DNA计算它是美国加利福尼亚大学的Adleman博士1994年第一次提出的一种借助生物分子DNA的结构利用现代分子生物技术进行计算的新方法，它开创了以化学反应作为计算工具的先例，并成功地在DNA溶液试管中对哈密尔顿有向路径问题进行求解实验。特点：DNA计算完全是一种新的概念，具有高度的并行性、海量存储、低能耗、资源丰富等显著特点。但最优解如何分离、“输出技术”瓶颈、“伪解”与“误差”如何避免等面临巨大的技术挑战。33谢谢观赏2019-5-18DNA计算它是美国加利福尼亚大学的Adleman博士1994

Adelman

算法创始人优化机制关键参数初始温度、退温函数、状态产生方式、抽样稳定准则基于MonteCarlo全局概率型串行搜索优化算法具有记忆功能的全局逐步优化算法列表大小、邻域函数结构与数量基于生物进化与遗传全局性并行优化算法种群数目及复制、交叉、变异操作概率基于神经网络原理及系统演变联想记忆算法神经元数目、输入输出变量、隐含层数具有强化学习功能的全局并行优化算法初始信息素、信息素增量、信息素积累量、消失因子、启发因子以化学反应为计算工具的分子生物计算方法生物酶、超声波、亲和层析、克隆、诱变、纯化、电泳、磁珠分离HopfieldGloveHollandDorigo模拟生物免疫系统的识别细胞产生的优化算法SATSGANNACOIAPSODNAKirkpatrickKennedy&EberhartFukuda抗原、抗体、抗原与抗体之间的亲和性模拟鸟类或鱼类的群集现象优化算法粒子反复迭代，粒子个体极值，粒子群体极值表1-2几种智能优化算法的优化机制与关键参数34谢谢观赏2019-5-18

智能优化算法与普通搜索算法区别（1）普通搜索算法是以一个解为迭代的初始值，而智能优化算法是以一组解(种群)为迭代的初始值；（2）智能优化算法需要将问题的优化参数进行编码，映射为可进行启发式操作的数据结构，而普通搜索算法不需要此过程；（3）普通搜索算法的搜索策略为确定性的，而智能优化算法的搜索策略是结构化和随机化的(概率型)；（4）智能优化算法仅用到优化的目标函数值的信息，