写在前面

本文旨在为对优化算法有兴趣的学弟学妹们提供一个了解相关问题和求解方法的参考，由于本人水平有限，有些描述可能不太准确，欢迎通过邮箱联系我更正

1. P and NP
关于P与NP问题的定义, 具体可以参考课程《可计算性与计算复杂性》关于确定性图灵机与多项式时间的描述

决策问题(Decision Problem): 一个输出为”是 / 否”(True or False)的可计算问题
P(Polynomial time) problem: 在多项式时间内可以求解的问题
NP(Nondeterministic Polynomial time) problem: 在多项式时间内，可以验证该问题的一个解是否为可行解
NP-completeness: 对所有的NP问题, 均可以通过多项式时间算法规约为NP问题B, 则称NP问题B是NP-完全的(NP-complete)[亦可翻译为NP-完备的]
NP-completeness: 对任意NP-完全问题A, 若A可以通过一个多项式时间算法规约为NP问题B, 则称NP问题B是NP-完全的(NP-complete)
NP-hard problem: 对任意NP-完全问题A, 若A可以通过一个多项式时间算法规约为问题B, 则称问题B是NP-困难的(NP-hard)[通常简称为NP难问题]

一些NPC问题：
Boolean satisfiability problem (SAT), Knapsack problem, Travelling salesman problem, Clique problem, Vertex cover problem, Independent set problem, Dominating set problem, Graph coloring problem…

[Stephen Cook. The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. 1971: 151–158.]
[Richard M. Karp. Reducibility Among Combinatorial Problems. R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. 1972: 85–103.]
[M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, CA, USA, 1979.]

一些NP-hard问题:
Minimum Vertex Cover (MVC)
maximum independent set (MIS)
Maximum Clique (MC)

这类问题往往是离散且复杂的, 无论是上述的理论问题还是其在实际工程中的运用(比如软件测试中的一些配置问题)

Wikipedia 是一个非常好用的工具
[https://en.wikipedia.org/wiki/Decision_problem]
[https://en.wikipedia.org/wiki/P_versus_NP_problem]
[https://en.wikipedia.org/wiki/NP_(complexity)]
[https://en.wikipedia.org/wiki/NP-completeness]
[https://en.wikipedia.org/wiki/NP-hardness]
[https://en.wikipedia.org/wiki/Co-NP]

2. Algorithm
求解NP-hard问题的方法主要有2种途径: 基于穷举的精确求解 与 基于随机(经验)的启发式搜索

2.1.精确算法
比较常用的精确算法有分支限界(branch and bound)方法: 设计算法找到问题的一个下界(lower bound, LB), 找到问题的一个上界(upper bound, UB), 将问题分为较小的子问题求解.

比如，对于最小顶点覆盖(MVC)问题, 该问题可以被描述为: 对于一个无向图G=(V,E),找出一个基数最小的顶点集合A( minimum card(A) )，使得G中每条边都至少有一个顶点属于A.
易证: 对任意一个最小顶点覆盖问题实例,设其顶点数为n, 其最小顶点覆盖k的下界为1，上界为(n-1). (在实际求解中，往往可以找到更逼近最优解的下界与上界).

此外，还有割平面法,整数规划等.
目前而言，将问题转化为可满足性(SAT)问题,再通过命题逻辑推理进行精确求解是一个比较热门且有效的精确求解方向.
一个比较广泛使用的精确求解器：CPLEX.

2.2.启发式算法(Heuristic Algorithm)
相较于直接求出问题最优解的精确算法,启发式算法在一定的计算资源（时间与空间）的限制下，对所求问题给出一个接近最优解的可行解.

启发式算法没有一个比较严格的分类，有文献将其分为局部搜索(Local Search, LS)算法, 进化算法/演化算法(Evolutionary Algorithm, EA) 与 元启发式算法(meta-heuristic). 也有文献将演化算法归类为元启发式算法的一部分.

此外，还有超启发式算法(Hyper-Heuristic Algorithm) 其大致实现为通过机器学习等方式对一系列基本的启发式规则{a,b,c}生成一个序列(eg: (a,a,c,c,b,c))，然后使用该规则序列对问题进行搜索/求解 本篇不讨论该类算法.

2.2.1. 局部搜索
对当前生成的一个可行解(候选解)进行局部地扰动,生成一个新的可行解(移动到其相邻的候选解)
局部搜索的关键是定义候选解的领域结构和扰动规则。此处的描述也许比较抽象，我们举一个例子：

EG:
集合覆盖问题(Set Covering Problem，SCP). 给定一个集合系统(R,S), 其中, R是n个元素的集合, S是R的若干子集的集合. 集合覆盖的目标是找到一个S的子集S’, 使得S’中的子集的并集等于R, 即R中的元素全部被S’所覆盖. 集合覆盖的最优化问题为求出一个满足要求的S’, 并使S’中的子集数最小,即最小集合覆盖问题(Minimum Set Covering Problem，MSCP). 最小集合覆盖问题是NP难的组合优化问题.
给定上述集合系统 $(R,S)$ ,设 $R$ 中元素的个数为 $m$ , $S$ 中子集的个数为 $n$ . 记 $c_j$ 为 $S$ 中的第 $j$ 个子集 $(0 \lt j \le n)$ , $e_i$ 为 $R$ 中的第 $i$ 个元素 $(0 \lt i \le m)$ . 最小集合覆盖的数学整形规划形式如下式所示:

实例：
对元素 $ a,b,c,d,e,f,g,h,i $ 构成的集合

有 $Z$ 的子集

子集集合
为该问题的一个集合覆盖, 是一个可行解. 一个基于交换的局部搜索策略, 倾向于对当前候选解的邻域进行搜索.
比如，先移除一个子集F, 并将D加入当前解, 获得可行解 .
这里我们发现E中所有元素都被 $ S_{2} $ 中其它的集合覆盖, 因此移除E后所得

依然为一个可行解.
[在实现中，我们可以通过对每个元素被当前解中的子集的覆盖次数来计算每个子集对覆盖的收益来达成上述的效果，这其实是一个基于加权的思想]

也许上面的策略还是稍微复杂了一些,我们尝试一个更加简洁的方法: 对 $ S_{2} $ , 我们移除2个子集, 再加入1个子集. 假如构成了一个新的可行解, 那么显然我们获得了一个更优秀的解. 否则，我们可以回退，重新选择加入的子集或者移除的子集.
那么如何选择呢？也许, 我们可以移除覆盖元素最少的子集, 并加入覆盖元素最多的子集. 比如,我们移除了 $E,F$ ,并加入了 $D$ . 问题依然没有解决: 算法可能并不会选择 $E$ 移除, 它可能会移除 $A$ 或者 $B$ . 如何尽可能地避免这种情况？

  1. tabu: 禁忌列表 - 若当前操作并没有改善当前解, 则在一定步数内禁止该操作, 或者禁止对该结构的操作 比如 $A$ 的移除被禁止,接下来算法就有很大概率移除 $E$ . 类似的策略有格局检测, 在很多问题中, 格局检测与列表长度为1的tabu相结合, 往往比设计一个复杂的tabu策略或者简单使用一个基础的tabu策略要有效.
  2. 加权: 每一次移动操作被采用后, 未被选取的子集权重增加(也可以增加它们覆盖的元素的权值, 此处只是一个举例).
  3. …

P.S. 实际上, 基于交换的策略比较有效(而不是移除2个再加入1个)，并且也可以与tabu等方法结合.

2.2.2.
元启发式搜索, 演化计算, 群智能

比较好的例子有遗传算法, 粒子群算法, 蚁群算法. 此外华中科技大学的吕志鹏教授最近提出的师徒进化算法最近刷新了一些工程问题上的记录.
需要注意的是, 目前不再建议提出新的仿生算法, “一个改进的粒子群算法”, “基于XX策略的遗传算法”, “XX算法与XX的结合/改进/扩展” 要比 “蟑螂算法”, “羊驼算法”, “猫猫算法”更务实, 也更容易被审稿人和大多数正常人接受. (可能有太多人改了改传统方法的框架又套个名字就开始水论文, 导致风气不太好).
基础的遗传算法, 粒子群算法和蚁群算法并不难, 建议自行了解一下, 基本的实现也有很多对应的代码, 掌握基础的框架即可. — 改进比较容易, 真正的复杂程度往往和问题的结构有关

群智能的基本思想是构建一系列的初始解, 这些解也许是完全随机生成的, 也许是由一些启发式信息(经验策略)按概率引导生成的[如蚁群中的启发式因子].(以上述集合覆盖为例, 可以在生成初始解的时候 更倾向 于加入 $D$ , 因为 $D$ 覆盖了 $3$ 个元素, 是覆盖元素数量最多的子集).

然后对当前种群的所有个体进行变异, 或者重构, 生成新的子代.

当然, 上述只是一个抽象的思路, 具体而言, 遗传算法有选择, 交叉, 互换 操作, 粒子群会更新速度和位置, 蚁群会基于信息素因子和启发式因子按概率重新生成子代.

对于每个子代, 可以为其进行局部搜索以改进解的质量[可选, 当种群规模很大时, 也可以选择不使用局部搜索, 或者只进行少量的搜索操作]. 然后再根据这些子代生成新一轮的子代.

演化计算的好处: 可并行[然而事实上,在很多问题上还是需要单线程计算性能对比结果], 多目标[群智能在多目标问题上的应用], 可扩展[传统的智能算法实现起来很简单,很容易扩展其框架.但是新的框架需要有一定的鲁棒性(一般来说，至少需要设置一组对照试验来证明策略的有效性,即策略验证)]

3. 实践
这里推荐阅读蔡少伟老师的博士论文
以及对应的代码
也许可以为理解组合优化问题的求解提供一定的帮助和启发

4. SAT与SMT
这里涉及到精确求解的相关知识, 但是目前而言不用太深入了解。
花一天时间自行浏览一下Wikipedia和百度了解一下大概是什么问题，对应的求解器可以求解哪些问题即可。如果有不懂的地方可以邮件或者微信或者线下讨论。
有时候，我们可以将问题转换为SAT问题进行精确求解，可以将问题转换为SAT进行启发式求解。这样做的好处在于SAT问题的求解被研究的比较深入，技术比较成熟。

5. 精确算法与启发式的结合
对于规模较大的问题，精确方法往往会需要很大的时间和空间来求解，这是一件很折磨人的事情（机器会因为内存会崩溃，科研人员会因为时间而崩溃）。但是这并不妨碍我们在大规模的实例上使用精确算法。
我们可以通过启发式方法，在尽量不损耗问题结构的情况下将问题简化为一些子问题，削减问题规模。而后通过精确算法求解。
更多的情况下，我们使用后者：即先通过精确算法对问题进行一定的约简（约简之后问题规模依旧很大），然后再用启发式算法求解。

依然以上述的集合覆盖问题为例：我们注意到元素a,b,c,d等只被一个子集覆盖，那么通过精确算法可以得到一个准确的下界，即如果要满足一个集合覆盖，覆盖这些只被覆盖一次的元素的子集们必然被所有可行解包含。从而子集 $A,B,C$ 一定在最优解中。

6. 我想不到取什么名字了
总而言之，一个成体系的优化求解的工作涉及到以下几个关键的步骤：

  1. 问题的描述，约束，目标，数据结构的表示（建模）
  2. 初始解的生成（随机或贪心或基于概率 + 可能的约简）
  3. 算法框架的设计（群智能框架（&& / ||）启发式规则的结合方式）
  4. 启发式规则的设计（3和4往往在一起，顺序可逆，怎么合理怎么来，但是一般的，算法框架图需要最先给出）
  5. 实验（数据集的选取，与最新算法的对比，与传统算法的对比，与精确求解器的对比，策略验证等）

需要掌握的技能：

  1. 快速的理解能力，我们组可能并不倾向于在一个问题上不断突破/刷新记录
  2. 能够将问题建模成比较容易处理的数据结构（比如矩阵），有时候，边界条件可能不太需要关注

关于合作项目：

  1. 可能还是得考虑一些边界条件，毕竟不是理论问题
  2. 以后组里的优化问题很可能会是一些冷门的问题或者比较奇怪/罕见的问题，所以个人感觉假如有机会在前期参与一下类似的项目或者比赛锻炼一下是比较合适的。

关于局部最优：

  1. 前面我忘写了…想到哪写到哪不是一个好习惯…可见提纲的重要性…
  2. 简单且不严谨而言，局部最优就是搜索阶段停留在一个邻域/解结构中往复循环，尽管tabu，格局检测（CC），解重构等策略都是为了在一定程度上避免算法陷入局部最优，或者”跳出局部最优”，但这依然是一个很难被避免的问题
    对应的，如果算法陷入了局部最优，不妨尝试一下上面提到的方法

7. Thank you~