现代优化算法三部曲 ｜ 入门介绍

我我我想要立一个flag，今后七天每天写一个问题的文章。第一天从现代优化算法开始吧！

借鉴了很多资料，仅供学习，侵删。

战略性放弃编程学习，故三部曲不涉及代码（By the way，现成代码很多）。

为什么：这部分主要是介绍现代优化算法是解决什么问题的，最主要的概念是NP问题。

要计算或解决一个问题，该问题通常有一个大小规模，用n表示。

例如，将n个数按从大至小排序，n是其规模大小，若是我们按这样的方法：第一次从n个数里找最大，第二次从n-1个数里找最大，以此类推，需要的比较次数就是n(n-1)/2，称我们所用的方法为算法，称n(n-1)/2为该算法的时间复杂度。对于时间复杂度，当n足够大时，我们只注重最高次方的那一项，其他各项可以忽略，所以，n(n-1)/2我们只重视n的平方这一项了，记为O(n^2)，这就是该算法对该问题的时间复杂度的专业表示。

所有形如a?n^k+b?n^(k-1)+c?n^(k-2)+?都可记为O(n^k)，这样的复杂度为多项式(polynomial)时间复杂度。若是时间复杂度为 k^n，k为大于1的常数，或者n!的时间复杂度，或者比n!更大的时间复杂度 ，就称为指数型时间复杂度。显然，当n足够大时，指数型时间比多项式要大得多的多。

示例：
如果无论数据有多大，时间总是那么多，则称常数级复杂度，O(1)
若数据规模变多大，程序花费的时间变多长，即 O(n)；若数据变大2倍，时间变长4倍，即 O(n^2)；这些属于多项式时间复杂度，如找最大值，冒泡排序…
形如 O(a^n), O(n!) 等时间复杂度属于指数型时间复杂度，需要的时间太多计算机往往不能承受。

所有能用多项式时间算法计算得到结果的问题，称为多项式问题，也就是P；所有绝对不可能用多项式时间求解的可解问题，称为指数型问题。当然，还有一类问题属于不可解问题，也就是说你无论花多少时间也不能得到解答。

有这样一类问题，假使你得到了问题的解，我要验证你的解是否正确，我验证所花的时间是多项式，至于求解本身所花的时间是否是多项式我不管，可能有多项式算法，可能没有，也可能是不知道，这类问题称为NP问题。NP问题就是可以在多项式时间复杂度的算法去验证结果正确性的问题；比如随便拿一个结果，可在多项式时间内验证该结果是否正确，但是想要求解该结果的时间复杂度就不知道了。

NP概念的奥妙在于，它躲开了求解到底需要多少时间这样的问题，而仅仅只是强调验证需要多少时间。

问题A可以约化为问题B：可以采用解决问题B的方法解决问题A；或者说，问题A可以转化为问题B。（如：一元二次方程的解法可以用来解一元一次方程，只要令二次项系数a=0即可）

问题A可以约化为问题B 的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。

一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。

如果从某一个NP问题开始不断向上约化，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？

NPC问题：存在这样一个NP问题，所有的NP问题都可以约化成它。这种问题不只一个，它有很多个，它是一类问题。这一类问题就是NPC 问题。

NPC问题的定义：同时满足下面两个条件的问题就是NPC问题：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。

NP-hard问题满足NPC问题定义的第二条而不满足第一条。NP-hard问题的范围比NP问题要广。

NP-hard问题同样难以找到多项式时间复杂度的算法，但它也不一定是NP问题（只是所有的NP问题都可以约化到它）。

最优化问题一般分为两大类：一类是具有连续型的变量，另一类是具有离散型的变量；后一类被称为组合最优化，组合优化问题有时又称为离散优化(Discrete Optimization)问题。像简单的背包问题，TSP旅行商问题都是组合优化问题。

组合最优化问题（combinatorial optimizationproblem）是一类在离散状态下求极值的问题。把某种离散对象按某个确定的约束条件进行安排，当已知合乎这种约束条件的特定安排存在时，寻求这种特定安排在某个优化准则下的极大解或极小解的间题。

组合最优化问题的数学模型：
minf(x)
s.t. g(x)≥0
x∈D
其中，f(x)为目标函数，g(x)为约束函数，x为决策变量，D表示有限个点组成的集合。
一个组合最优化问题可以用三个参数(D,F,f)来表示，其中D表示决策变量的定义域，F表示可行解区域，F中的任意一个元素为该问题的可行解，f表示目标函数，满足使 f(x)值取到最小值的可行解区域中的 称为该问题的最优解。

从模型可看出组合优化问题是一个规划问题（在一定条件下，求解目标函数的最大值最小值，这类问题叫做数学规划，它是运筹学里的重要内容）。解决这类优化问题的方法有各种规划(线性、非线性、目标、整数、随机、模糊)、遗传算法、退火算法、神经网络、搜索算法、拉格朗日松弛算法等。

组合最优化问题多数属于所谓的NP完全问题，即对该问题基本上不存在一种算法，使得当所有的具体问题的变量和约束条件的数目两者之和甚大时，可以在容许时间（即所谓的多项式时间）之内给出所要的解。

售货员旅行问题 (traveling salesman problem)，是最具有代表性的NP问题之一。假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排! 这将是个天文数字。

这个天文数字到底有多大？目前的方法接近一个一个的排着试，还没有找到更好可以寻得最短路径的方法。对七个城而言，共有 6!=720 个排法，还比较简单；，但若有 20 个城，则排法就有 19! 种。因故在排列组合里 n! 写起来轻松。但 1.21?10171.21?1017 是一个大得不得了的数字。若每秒钟排一次，要排 3.84?1093.84?109 年（一年约为 3.15?1073.15?107 秒），即使使用计算器，每秒排一百万次（不容易做到）也得重做三千年才能找到答案。

是什么：这部分主要是简要介绍现代优化算法。

现代优化算法是 80 年代初兴起的启发式算法。

启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发法（heuristics，源自古希腊语的ε?ρ?σκω，是指依据有限的知识（或“不完整的信息”）在短时间内找到问题解决方案的一种技术。启发式算法是一种依据关于系统的有限认知和假说，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

现代启发式算法在优化机制方面存在一定的差异,但在优化流程上却具有较大的相似性,均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发,在算法的关键参数的控制下通过邻域函数产生若干邻域解,按接受准则(确定性、概率性或混沌方式)更新当前状态,而后按关键参数修改准则调整关键参数。如此重复上述搜索步骤直到满足算法的收敛准则,最终得到问题的优化结果。

模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

1. 初始化温度T（充分大），温度下限Tmin(充分小)，初始解X，每个T迭代次数为L；

2. 随机生成临时解域X_new;

3. 设f(x)函数来计算解的好坏，计算出f(X_new)-f(X);

4. 如果f(X_new)-f(X)>0，说明新解比原来的解好，则无条件接受，如果f(X_new)-f(X)<0，则说明旧解比新解好，则以概率exp((f(X_new)-f(x))/k*T)接受X_new作为解。

5. 如果当前温度小于Tmin的时候，退出循环，输出结果；否则，降低当前温度，T=a*T,(0<a<1)，跳转到第二步继续循环。

遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

· 编码：将物体的表现型转化为计算机可处理的编码的基因型；

· 解码(decoding)：基因型到表现型的映射；

· 基因型(genotype)：参数的因子；

· 表现型(phenotype)：根据不同因子最终展现的形态；

· 适应度(fitness)：度量某个结果的好坏；

· 进化(evolution)：不断剔除差的结果，最终逐步留下好的结果；

· 选择(selection)：以一定的概率从种群中选择若干个个体留下，并繁殖。选择过程是一种基于适应度的优胜劣汰的过程；

· 复制(reproduction)：将父本、母本的基因复制，以便产生下一代；

· 交叉：两个染色体的某一相同位置的DNA被切断，前后两串染色体分别交叉形成两个新的染色体；

· 变异：交叉后可能（极小概率）对染色体进行修改，来防止算法过早收敛而陷入局部最优解；

· 个体（individual）：指染色体带有特征的实体；

· 种群（population）：个体的集合，该集合内个体数称为种群的大小。

1. 对潜在问题进行编码，初始化基因组，并根据基因组随机初始化种群，并指定繁衍代数；

2. 计算种群中每个个体的适应度，选择一定数量的留下，其它淘汰；

3. 在留下的个体中，随机繁衍，对母基因进行交叉（极小概率变异），产生下一代；

4. 跳转到第2步，继续循环，直到达到繁衍代数为止。