智能仿生算法概述概要

智能仿生算法概述丁建立中国民航大学计算机学院[e-mail]2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f52242511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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→E旅行商问题(TSP—TravelingSalesmanProblem)旅行商问题即TSP问题，又称Hamiltion回路问题。一个商人打算从所驻城市到其他城市推销商品，每个城市恰好去一次，最后返回出发地，问如何安排其旅行路线，使其所走的路线的总长度最短？组合爆炸完全枚举的方法求得最优解，若固定一个城市为起点，则需要（n-1）！个枚举，以计算机1秒可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为24秒，随着城市数增加，计算时间增加非常之快，当城市数增加到30时，计算时间约为10.8年，实际计算中已无法接受。同样，聚类问题的可划分方式有个，Job-Shop可能排列方式有个。!kknmn)!(算法复杂度表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.世纪典型组合优化问题旅行商问题(TSP—TravelingSalesmanProblem)加工调度问题（SchedulingProblem）0-1背包问题（KnapsackProblem）装箱问题（BinPackingProblem）图着色问题（GraphColoringProblem）聚类问题（ClusteringProblem）组合优化问题组合优化：组合优化就是离散优化，它是通过数学方法寻找离散事件的最优编排、分组、次序或筛选等。这类问题可用数学模型描述为：目标函数：约束条件：决策变量：，其中D为有限个点组成的集合。特点：可行解集合为有限点集，只要将D中有限个点逐一判别是否满足的约束并比较目标值的大小，就可以得到该问题的最优解。对于组合优化问题，最关心的是如何找到有效的算法求得一个最优解。)(xfMin0)(..xgtsDx算法的时间和空间复杂性算法的时间复杂性和空间复杂性对计算机的求解能力有重大影响。沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性；算法执行期间占用的存储单元则定义为算法的空间复杂性。问题的复杂性一般表示为问题规模的函数，按照计算复杂性理论研究问题求解的难易程度，可把问题分为P类、NP类和NP完全类。ＮＰ问题定义：对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项式函数和非负常数，使得，（1-1）（其中是计算总次数，是二进制输入长度）对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，记作P(Polynomial)。通常称这种比P类问题更广泛的问题为非多项式确定问题NP（Non-deterministicPolynomial）。但迄今为止，许多优化问题仍没有找到求得最优解的多项式时间算法。))(()(IdgaIC)(IC)(Id)(xgaPNPNP-CNP-hard图１－１四类问题的关系图图1-1表示，PNP，NP-CNP-hard,NP与NP-hard的公共部分为NP-C。在NP中，除P和NP-C，还有一部分问题的复杂性是未知的。到目前为止，组合优化问题研究中大家一般都接受的一个假设是PNP。智能仿生算法智能优化算法（IntelligentOptimizationAlgorithms）或称现代启发式算法（Meta-HeuristicAlgorithms）它是通过模拟或揭示某些自然现象或过程而发展起来，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段。它具有全局的、并行高效的优化性能，鲁棒性、通用性强，无需问题特殊信息等优点。模拟退火算法（SA）该算法建立在蒙特卡罗(MenteCarlo)原理的基础上，模拟固体退火过程，是一种启发式随机优化方法，1953年被Metropolis等首次提出，1983年Kirkpatrick等将其用于组合优化，适合求解大规模优化问题。特点：算法实现简单，使用灵活，可跳出局部极值区，但收敛速度慢，有关控制难以确定等。禁忌搜索算法（TS）它是F.Glover在20世纪60年代末提出的一种模拟智力过程而扩展邻域的启发式搜索算法。特点：在搜索过程中获得知识，能够以较大的概率跳出局部极值，以其较高的求解质量和效率已在许多组合优化问题中显示出强大的寻优能力，但存在对初始解依赖性较强及搜索仅能单对单操作的缺点。Hopfield神经网络它是美国物理学家J.J.Hopfield于1982年首先提出的。其演变过程是一个非线性动力系统，系统的稳定性可用所谓的“能量函数”（即李雅普诺夫或哈密尔顿函数）进行分析。如果把能量函数视为一个优化问题的目标函数，那么从这个初态朝稳定点的演变过程就是一个求解该优化问题的过程。它主要用于模拟神经网络的记忆机理，是一种全连接反馈型神经网络，它有离散型（DHNN）和连续型（CHNN）两种。特点：具有单调下降、并行计算和联想记忆等优点，但同时也存在着收敛速度慢，易陷入局部极值点等缺点，且网络合适的隐含层数目和节点数目确定较困难。遗传算法（GA）它是美国密执安大学的JohnHolland教授于1975年首先提出的一类仿生型优化算法。它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上，子代是父代遗传基因在染色体上的有序排列”为基础，模拟生物界进化过程。特点：具有大范围全局搜索的能力，潜在的并行性、随机性，鲁棒性强，过程简单。缺点是不能很好的利用系统反馈信息，冗余迭