《智能算法综述.docx》由会员分享，可在线阅读，更多相关《智能算法综述.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、智能算法综述 1什么是智能算法智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，依据其原理，仿照求解问题的算法。从自然界得到启迪，仿照其结构进行独创创建，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。这方面的内容许多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。2人工神经网络算法“人工神经网络”(ARTIFICIALNEURALNETWORK，简称ANN)是在对人脑组织结构和运行机制的相识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年头初期，心理学家Mc
2、Culloch、数学家Pitts就提出了人工神经网络的第一个数学模型，从今开创了神经科学理论的探讨时代。其后，FRosenblatt、Widrow和J.J.Hopfield等学者又先后提出了感知模型，使得人工神经网络技术得以蓬勃发展。神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本单元。据神经生物学家探讨的结果表明，人的一个大脑一般有10101011个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支树突组成。轴突的功能是将本神经元的输出信号(兴奋)传递给别的神经元。其末端的很多神经末梢使得兴奋可以同时传送给多个神经元。树突
3、的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到的全部信号进行简洁处理(如：加权求和，即对全部的输入信号都加以考虑且对每个信号的重视程度体现在权值上有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。2.1人工神经网络的特点人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点确定着人工神经网络具有高速信息处理的实力。人脑的每个神经元大约有103104个树突及相应的突触，一个人的大脑总计约形成10141015个突触。用神经网络的术语来说，即是人脑具有10141015个相互连接的存储潜力。虽然每个神经元的运算功能非常简洁，且信号传输速率也较低(大约10
4、0次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个一般人的大脑在约1秒内就能完成现行计算机至少须要数10亿次处理步骤才能完成的任务。人工神经网络的学问存储容量很大。在神经网络中，学问与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息，而不是一个完整详细概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和学问。由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理实力。即使输入信息不完全、不精确或模糊不清，神经网络仍旧能够联想思维存在于记忆中的事物的完整
5、图象。只要输入的模式接近于训练样本，系统就能给出正确的推理结论。正是因为人工神经网络的结构特点和其信息存储的分布式特点，使得它相对于其它的推断识别系统，如：专家系统等，具有另一个显著的优点：健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受稍微损伤之后，并不会失去原有事物的全部记忆。人工神经网络也有类似的状况。因某些缘由，无论是网络的硬件实现还是软件实现中的某个或某些神经元失效，整个网络仍旧能接着工作。人工神经网络是一种非线性的处理单元。只有当神经元对全部的输入信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高
6、度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标记着人们智能信息处理实力和模拟人脑智能行为实力的一大飞跃。2.2几种典型神经网络简介2.2.1多层感知网络(误差逆传播神经网络)在1986年以Rumelhart和McCelland为首的科学家出版的ParallelDistributedProcessing一书中，完整地提出了误差逆传播学习算法，并被广泛接受。多层感知网络是一种具有三层或三层以上的阶层型神经网络。典型的多层感知网络是三层、前馈的阶层网络，即：输入层I、隐含层(也称中间层)J和输出层K。相邻层之间的各神经元实现全连接，即下一层的每一个神经
7、元与上一层的每个神经元都实现全连接，而且每层各神经元之间无连接。但BP网并不是非常的完善，它存在以下一些主要缺陷：学习收敛速度太慢、网络的学习记忆具有不稳定性，即：当给一个训练好的网供应新的学习记忆模式时，将使已有的连接权值被打乱，导致已记忆的学习模式的信息的消逝。2.2.2竞争型(KOHONEN)神经网络它是基于人的视网膜及大脑皮层对剌激的反应而引出的。神经生物学的探讨结果表明：生物视网膜中，有很多特定的细胞，对特定的图形(输入模式)比较敏感，并使得大脑皮层中的特定细胞产生大的兴奋，而其相邻的神经细胞的兴奋程度被抑制。对于某一个输入模式，通过竞争在输出层中只激活一个相应的输出神经元。很多输入
8、模式，在输出层中将激活很多个神经元，从而形成一个反映输入数据的“特征图形”。竞争型神经网络是一种以无老师方式进行网络训练的网络。它通过自身训练，自动对输入模式进行分类。竞争型神经网络及其学习规则与其它类型的神经网络和学习规则相比，有其自己的显明特点。在网络结构上，它既不象阶层型神经网络那样各层神经元之间只有单向连接，也不象全连接型网络那样在网络结构上没有明显的层次界限。它一般是由输入层(模拟视网膜神经元)和竞争层(模拟大脑皮层神经元，也叫输出层)构成的两层网络。两层之间的各神经元实现双向全连接，而且网络中没有隐含层。有时竞争层各神经元之间还存在横向连接。竞争型神经网络的基本思想是网络竞争层各神
9、经元竞争对输入模式的响应机会，最终仅有一个神经元成为竞争的胜者，并且只将与获胜神经元有关的各连接权值进行修正，使之朝着更有利于它竞争的方向调整。神经网络工作时，对于某一输入模式，网络中与该模式最相近的学习输入模式相对应的竞争层神经元将有最大的输出值，即以竞争层获胜神经元来表示分类结果。这是通过竞争得以实现的，事实上也就是网络回忆联想的过程。除了竞争的方法外，还有通过抑制手段获得成功的方法，即网络竞争层各神经元抑制全部其它神经元对输入模式的响应机会，从而使自己“脱颖而出”，成为获胜神经元。除此之外还有一种称为侧抑制的方法，即每个神经元只抑制与自己邻近的神经元，而对远离自己的神经元不抑制。这种方法
10、经常用于图象边缘处理，解决图象边缘的缺陷问题。竞争型神经网络的缺点和不足：因为它仅以输出层中的单个神经元代表某一类模式。所以一旦输出层中的某个输出神经元损坏，则导致该神经元所代表的该模式信息全部丢失。2.2.3Hopfield神经网络1986年美国物理学家J.J.Hopfield接连发表几篇，提出了Hopfield神经网络。他利用非线性动力学系统理论中的能量函数方法探讨反馈人工神经网络的稳定性，并利用此方法建立求解优化计算问题的系统方程式。基本的Hopfield神经网络是一个由非线性元件构成的全连接型单层反馈系统。网络中的每一个神经元都将自己的输出通过连接权传送给全部其它神经元，同时又都接收全
11、部其它神经元传递过来的信息。即：网络中的神经元t时刻的输出状态事实上间接地与自己的t-1时刻的输出状态有关。所以Hopfield神经网络是一个反馈型的网络。其状态改变可以用差分方程来表征。反馈型网络的一个重要特点就是它具有稳定状态。当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。这里的能量函数不是物理意义上的能量函数，而是在表达形式上与物理意义上的能量概念一样，表征网络状态的改变趋势，并可以依据Hopfield工作运行规则不断进行状态改变，最终能够达到的某个微小值的目标函数。网络收敛就是指能量函数达到微小值。假如把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络
12、的状态，那么Hopfield神经网络就能够用于解决优化组合问题。对于同样结构的网络，当网络参数(指连接权值和阀值)有所改变时，网络能量函数的微小点(称为网络的稳定平衡点)的个数和微小值的大小也将改变。因此，可以把所需记忆的模式设计成某个确定网络状态的一个稳定平衡点。若网络有M个平衡点，则可以记忆M个记忆模式。当网络从与记忆模式较靠近的某个初始状态(相当于发生了某些变形或含有某些噪声的记忆模式，也即：只供应了某个模式的部分信息)动身后，网络按Hopfield工作运行规则进行状态更新，最终网络的状态将稳定在能量函数的微小点。这样就完成了由部分信息的联想过程。Hopfield神经网络的能量函数是朝着
13、梯度减小的方向改变，但它仍旧存在一个问题，那就是一旦能量函数陷入到局部微小值，它将不能自动跳出局部微小点，到达全局最小点，因而无法求得网络最优解。3遗传算法遗传算法（GeneticAlgorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜寻与优化的方法。其主要特点是群体搜寻策略和群体中个体之间的信息交换，搜寻不依靠于梯度信息。它是在70年头初期由美国密执根（Michigan）高校的霍兰（Holland）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著自然系统与人工系统中的适应性（AdaptationinNaturalandArtificialS
14、ystems）。遗传算法最初被探讨的动身点不是为特地解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。近几年来，遗传算法主要在困难优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，所以引起了许多人的关注。在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法胜利的应用包括：作业调度与排序、牢靠性设计、车辆路径选择与调度、成组技术、设备布置与安排、交通问题等等。3.1特点遗传算法是解决搜寻问题的一种通用算法，对于各种通用问题都可以运用。搜寻算法的共同特征为：首先组成
15、一组候选解；依据某些适应性条件测算这些候选解的适应度；依据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特别的方式组合在一起：基于染色体群的并行搜寻，带有揣测性质的选择操作、交换操作和突变操作。这种特别的组合方式将遗传算法与其它搜寻算法区分开来。遗传算法还具有以下几方面的特点：(1)遗传算法从问题解的串集起先嫂索，而不是从单个解起先。这是遗传算法与传统优化算法的极大区分。传统优化算法是从单个初始值迭代求最优解的；简单误入局部最优解。遗传算法从串集起先搜寻，覆盖面大，利于全局择优。(2)很多传统搜寻算法都是单点搜寻算法，简单陷入
16、局部的最优解。遗传算法同时处理群体中的多个个体，即对搜寻空间中的多个解进行评估，削减了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜寻空间的学问或其它协助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以随意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采纳确定性规则，而是采纳概率的变迁规则来指导他的搜寻方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜寻时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。3.2运用领域前面描述是简洁的遗传算法
17、模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域：优化：遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。程序设计：遗传算法可以用于某些特别任务的计算机程序设计。机器学习：遗传算法可用于很多机器学习的应用，包括分类问题和预料问题等。经济学：应用遗传算法对经济创新的过程建立模型，可以探讨投标的策略，还可以建立市场竞争的模型。免疫系统：应用遗传算法可以对自然界中免疫系统的多个方面建立模型，探讨个体的生命过程中的突变现象以及发掘进化过程中的基因资源。进化现象和学习现象：遗传算法可以用来探讨个体是如何学习生存技巧的，一个物种的进化对
18、其他物种会产生何种影响等等。社会经济问题：遗传算法可以用来探讨社会系统中的各种演化现象，例如在一个多主体系统中，协作与沟通是如何演化出来的。4模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓缓冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而缓缓冷却时粒子渐趋有序，在每个温度都达到平衡态，最终在常温时达到基态，内能减为最小。依据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其变更量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成限制参数t，即得到解组合优化问题
19、的模拟退火算法：由初始解i和限制参数初值t起先，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜寻过程。退火过程由冷却进度表(CoolingSchedule)限制，包括限制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。5群体（群集）智能（SwarmIntelligence）受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些探讨就是群集智能的探讨。群集智能(SwarmIntelligence)中的群体(Swarm)指的是“
20、一组相互之间可以进行干脆通信或者间接通信(通过变更局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中限制并且不供应全局模型的前提下，为找寻困难的分布式问题的解决方案供应了基础。群集智能的特点和优点：群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前网络环境下的工作状态;没有中心的限制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间干脆通信而是通过非干脆通信(Stimergy)进行合作，这样的系统具有更好的可扩
21、充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里非常小。系统中每个个体的实力非常简洁，这样每个个体的执行时间比较短，并且实现也比较简洁，具有简洁性(Simplicity)。因为具有这些优点，虽说群集智能的探讨还处于初级阶段，并且存在很多困难，但是可以预言群集智能的探讨代表了以后计算机探讨发展的一个重要方向。在计算智能(ComputationalIntelligence)领域有两种基于群智能的算法，蚁群算法(AntColonyOptimization)和粒子群算法(ParticleSwarmOptimization)，前者是对蚂蚁群落食物采集过程的模拟，已经胜利运
22、用在许多离散优化问题上。5.1蚁群优化算法受蚂蚁觅食时的通信机制的启发，90年头Dorigo提出了蚁群优化算法(AntColonyOptimization，ACO)来解决计算机算法学中经典的“货郎担问题”。假如有n个城市，须要对全部n个城市进行访问且只访问一次的最短距离。在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路途，并留下会随时间渐渐消逝的虚拟“信息素”。虚拟的“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。依据“信息素较浓的路途更近的原则，即可选择出最佳路途。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得
23、到选择，并且由于采纳了概率算法，所以它能够不局限于局部最优解。蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法，它已经被胜利用于解决其他组合优化问题，例如图的着色(GraphColoring)以及最短超串(ShortestCommonSupersequence)等问题。5.2粒子群优化算法粒子群优化算法(PSO)是一种进化计算技术(EvolutionaryComputation)，有Eberhart博士和Kennedy博士独创。源于对鸟群捕食的行为探讨。PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组
24、随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜寻。同遗传算法比较，PSO的优势在于简洁简单实现并且没有很多参数须要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统限制以及其他遗传算法的应用领域。粒子群优化算法(PSO)也是起源对简洁社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发觉PSO是一种很好的优化工具。5.2.1算法介绍PSO模拟鸟群的捕食行为。一群鸟在随机搜寻食物，在这个区域里只有一块食物。全部的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是
25、什么呢。最简洁有效的就是搜寻目前离食物最近的鸟的四周区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜寻空间中的一只鸟。我们称之为“粒子”。全部的粒子都有一个由被优化的函数确定的适应值(fitnessvalue)，每个粒子还有一个速度确定他们翱翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜寻。PSO初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用
26、整个种群而只是用其中一部分最优粒子的邻居，那么在全部邻居中的极值就是局部极值。5.2.2PSO算法过程种群随机初始化。对种群内的每一个个体计算适应值(fitnessvalue)。适应值与最优解的距离干脆有关。种群依据适应值进行复制。假如终止条件满意的话，就停止，否则转步骤。从以上步骤，我们可以看到PSO和遗传算法有许多共同之处。两者都随机初始化种群，而且都运用适应值来评价系统，而且都依据适应值来进行肯定的随机搜寻。两个系统都不是保证肯定找到最优解。但是，PSO没有遗传操作如交叉(crossover)和变异(mutation)，而是依据自己的速度来确定搜寻。粒子还有一个重要的特点，就是有记忆。与
27、遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes)相互共享信息，所以整个种群的移动是比较匀称的向最优区域移动。在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流淌。整个搜寻更新过程是跟随当前最优解的过程。与遗传算法比较,在大多数的状况下，全部的粒子可能更快的收敛于最优解。现在已经有一些利用PSO代替反向传播算法来训练神经网络的论文。探讨表明PSO是一种很有潜力的神经网络算法，同时PSO速度比较快而且可以得到比较好的结果。6展望目前的智能计算探讨水平短暂还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发展。不仅仅只是功能仿照要持有信息机理一样的观点。即人工脑与生物脑将不只是功能仿照，而是具有相同的特性。这两者的结合将开拓一个全新的领域，开拓许多新的探讨方向。智能计算将探究智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大成就。.