启发式算法

墨蓝 2022-06-06 14:38 168阅读 0赞

**1.定义**  
大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为“**启发式算法**（Heuristic Algorithm）”。  
现在的启发式算法也不是全部来自自然的规律，也有来自人类积累的工作经验。  
**2.发展**  
启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。  
40年代：由于实际需要，提出了启发式算法（快速有效）；  
50年代：逐步繁荣，其中他懒算法和局部搜索等得到人们的关注；  
60年代：反思，发现以前提出的启发式算法速度很快，但是解的质量得不到保证，而且对大规模的问题仍然无能为力（收敛速度慢）；  
70年代：计算复杂性理论提出，NP问题。许多实际问题不可能在合理的时间范围内得到最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解没有全局最优性。  
由此必须引入新的搜索机制和策略………..  
Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的  
兴趣。  
80年代以后：  
模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。  
最近比较热或刚热过去的：  
演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等。  
优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。

遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中，较好的个体有较大的生存几率。

模拟退火：是模拟统计物理中固体物质的结晶过程。在退火的过程中，如果搜索到好的解接受；否则，以一定的概率接受不好的解（即实现多样化或变异的思想），达到跳出局部最优解得目的。

神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程。

禁忌搜索：模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌某些解，以避免走回头路，达到跳出局部最优解的目的。

蚂蚁算法：模拟蚂蚁的行为，拟人拟物，向蚂蚁的协作方式学习。

这几种超启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解。

他们的基本要素：（1）随机初始可行解；

（２）给定一个评价函数（常常与目标函数值有关）；

（３）邻域，产生新的可行解；

（４）选择和接受解得准则；

（５）终止准则。

其中（４）集中反映了超启发式算法的克服局部最优的能力。