元启发式算法手记一 入门

元启发式（Metaheuristics）算法是当前大数据领域最前沿的解决实际最困难问题的一系列算法框架，针对NP-Hard组合优化问题，用元启发式搜索往往可以得到相当不错的结果。本系列内容将持续更新所有具有代表性的元启发式算法，一方面是个人学习笔记，另一方面是为了填补中文圈准确资料稀少的问题。因为学习源头为英文，部分名词的翻译并不精准，仅以个人喜好进行名词翻译，如果有别的地方不同的翻译方法，请以英文为准。

本文为系列一，提供一些常见的名词解释以入门。

0. P,NP,NP-hard,NP-complete

这些都是算法复杂度理论中的基础概念： P是指多项式时间（polynomial time）,其含义是指一个算法能否在可接受的时间内得到一个问题的解法。 NP是指未决多项式时间（nondeterministic polynomial time），是指一些难题不好解，但易验证。 总结就是：P 简单问题。 NP：难题但容易验证。NP难：难题但容易转成另一类问题。NP完全问题：同时有NP和NP难的特质，最难解的一类。元启发算法的目标，几乎都是在解决NP完全问题。

1. 目标函数 （Objective function）

目标函数是指这个算法要通过这一函数得到一个值，而此算法的目标是让这一值最大或者最小。

2. 近邻函数（neighbourhood function）

生成一系列solution（解法）的集合，这些集合都有一个相关的因素，所以才叫邻居。比如某两个元素交换等等。

3. 移动函数 (moving function)

从一堆解法（neighbourhoods）移动到下一堆解法的办法，比如说交换两个元素后重新生成新的解空间。

4. 启发（Heuristics）与元启发（Metaheuristics）算法

启发算法与问题密切相关，解决A问题的办法不能解决B问题。元启发算法是算法框架，往往需要和启发算法进行合作，其自身往往没有问题相关性。

5. 构造性算法（Construction Algorithms）

构造性算法，主要是以渐进式的方法进行构建可能的解，但并不进行回溯，一次性从一个空解得到最终的结果。比如说最简单的办法开始构建解的办法就是随机顺序。如果每次渐进再增加一些启发性的好处预计在里面的话，就可以取到更好的结果。贪婪构建办法在每次渐进的时候都以最大收益来衡量。其缺点是产生的解空间非常有限，而且在算法运行的后期，进步非常慢。

构造性算法是典型的最快近似算法，但其得到的解并不是非常高的质量，而且其并不保证在一些小的改动上能有优化，因此，构造性启发算法常常可以被本地搜索算法所提升结果。

6. 本地搜索算法（Local Search Algorithms）

本地搜索算法开始于一个完整的初始解，然后尝试去在一个恰当定义的邻居（neighborhood: 就是具有相关性的一群解）中找一个更好的解。本地搜索最基础的版本，就是迭代提升（iterative improvement），每次迭代都去找一个比当前解更好的解，周而复始，直到结果没有提升。这往往可以得到一个局部的最优解。本地搜索算法的性能，取决于合适的邻居定义，而且这个定义往往是与要解决的问题高度相关的，比如你不能用一个物流调度的邻居生成办法，去生成sudoku的邻居。本地搜索算法的问题在于，其结果非常容易困在一个本地的局部最优上，最终的质量完全取决于第一个解决方案的构建。