启发式优化算法综述.doc

《启发式优化算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、启发式优化算法综述一、启发式算法简介K定义由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共辘梯度法,拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性;对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大口然的运行规律中找到了许多解决实际问题的方法。对于那些受大

2、自然的运行规律或者面向具体问题的经验、规则启发岀來的方法，人们常常称之为启发式算法(HeuristicAlgorithm)。为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经

3、验规则进行发现的方法。其特点是在解决问题时，利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案,以随机或近似随机方法搜索非线性复朵空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。2、发展历史启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史：40年代：由于实际需要，提出了启发式算法(快速有效)

4、。50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。60年代：反思，发现以前捉出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力(收敛速度慢)。70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。Holland的遗传算法出现T(GeneticAlgorithm)再次引发了人们研究启发式算法的兴趣。80年代以后：模拟退火算法(SimulatedAnnealingAlgorith

5、m),人工神经网络(ArtificialNeuralNetwork),禁忌搜索(TabuSearch)相继出现。最近比较火热的：演化算法(EvolutionaryAlgorithm),蚁群算法(AntAlgorithms),拟人拟物算法，量子算法等。二、启发式算法类型1、类型简介大部分的算法都是仿生演变而来，如下：仿动物类的算法：粒子群优化，蚁群算法，鱼群算法，蜂群算法等；仿植物类的算法：向光性算法，朵草优化算法等；仿人类的算法有：遗传基因算法，和声搜索算法，神经网络；以及其他的理论成熟并被广泛使用的算法如：模拟退火算法、禁忌搜索等等%1、粒子群算法粒子群优化算法的基本思想是通过群体中

6、个体之间的协作和信息共享来寻找最优解.粒子群算法源于复杂适应系统（ComplexAdaptiveSystem,CAS）OCAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知

7、道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻日前离食物最近的鸟的周围区域。%1、蚁群算法蚁群算法（antcolonyoptimization,ACO）,又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在运动过程中，会留下一种称为信息素的东西，并一且会随着移动的距离，播散的信息素越来越少，