启发式优化算法综述.docx

启发式优化算法综述
一、启发式算法简介
1、定义
由于传统的优化算法如最速下降法,线性规划,动态规划,分支定界法,单纯形法,共轭梯度法,拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解,使得学者们期望探索一种算法:它不依赖问题的数学性能,如连续可微,非凸等特性; 对初始值要求不严格、不敏感,并能够高效处理髙维数多模态的复杂优化问题,在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求,智能优化算法应运而生。智能优化算法借助自然现象的一些特点,抽象出数学规则来求解优化问题,受大自然的启发,人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法,人们常常称之为启发式算法(Heuristic Algorithm)。
为什么要引出启发式算法,因为NP问题,一般的经典算法是无法求解,或求解时间过长,我们无法接受。因此,采用一种相对好的求解算法,去尽可能逼近最优解,得到一个相对优解,在很多实际情况中也是可以接受的。启发式算法是一种技术,这种技术使得在可接受的计算成本内去搜寻最好的解,但不一定能保证所得的可行解和最优解,甚至在多数情况下,无法阐述所得解同最优解的近似程度。
启发式算法是和问题求解及搜索相关的,也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案,以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试,最终能找到问题的答案,但它是在很大的问题空间内,花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内,大大减少尝试的数量,能迅速地达到问题的解决。
2、发展历史
启发式算法的计算量都比较大,所以启发式算法伴随着计算机技术的发展,才能取得了巨大的成就。纵观启发式算法的历史发展史:
40年代:由于实际需要,提出了启发式算法(快速有效)。
50年代:逐步繁荣,其中贪婪算法和局部搜索等到人们的关注。
60年代: 反思,发现以前提出的启发式算法速度很快,但是解得质量不能保证,而且对大规模的问题仍然无能为力(收敛速度慢)。
70年代:计算复杂性理论的提出,NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快,但解不好的原因主要是他们只是在局部的区域内找解,等到的解没有全局最优性。由此必须引入新的搜索机制和策略。
Holland的遗传算法出现了(ic Algorithm)再次引发了人们研究启发式算法的兴趣。
80年代以后:模拟退火算法(Simulated Annealing Algorithm),人工神经网络(Artificial work),禁忌搜索(Tabu Search)相继出现。
最近比较火热的:演化算法(Evolutionary Algorithm), 蚁群算法(Ant Algorithms), 拟人拟物算法,量子算法等。
二、启发式算法类型
1、类型简介
大部分的算法都是仿生演变而来,如下:仿动物类的算法:粒子群优化,蚁群算法