元启发式算法

May 07, 2018算法点击

i.什么是元启发式算法

启发式算法

启发式算法(Heuristic Algorigthm)是一种基于 直观或经验 构造的算法, 并没有严格的数学证明过程，在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解，该可行解与与最优解的偏离程度一般不可以事先预计。
意味着启发式算法可以在可接受的计算费用内找到最好的解,但不一定能保证所得到解的可行性及最优性，甚至大多数情况下无法阐述所得解与最优解之间的近似程度。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。
启发式算法会在其过程成采用某种机制逐步的选择使得局部最优情况的当前解，通过这种机制不断的剪枝，即 降低分叉率 以相比与暴力解法而改进搜索效率。

元启发式算法

元启发式算法(Metaheuristic Algorithm)是启发式算法的改进，通过随机算法结合启发式算法使得其在每次迭代中能够有一定的概率跳出局部最优解逐步靠近全局最优解。在某个节点上的局部最优解不一定包含在全局最优解中，在很多元启发式算法中都是通过 轮盘转法 来做出随机选择。

ii.常见算法种类

这里只是列举种类，具体的每种算法的原理和实现将由单个文章说明。

启发式算法

贪婪算法
爬山法
蒙特卡洛树搜索算法
萤火虫算法

元启发式算法

模拟退火算法
蚁群算法
遗传算法
禁忌搜索
蝙蝠算法

iii.对元启发式算法的认识

特点

随机的初始可行解
在邻域产生新的可行解
用使得局部最优的评价函数来剪枝
随机算法选择和接受
收敛因子
有限的迭代次数

不完善的地方

启发式算法目前缺乏统一、完整的理论体系。
由于NP理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断。
各种启发式算法都有个自优点如何，完美结合。有很多的混合算法效果不错。
启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。
启发算法缺乏有效的迭代停止条件。通常式认为的设定迭代次数或者迭代影响因子的下限。
启发式算法收敛速度的研究等。

iiii.参考

https://zh.wikipedia.org/wiki/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2

元启发式算法