常用的启发式算法

什么是启发式算法

启发式算法一般用于解决NP-hard问题，其中NP是指非确定性多项式。

例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从南京出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

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

启发式算法是相对于最优化算法提出的，是基于直观或者经验构造的算法，在可接受的开销（时间和空间）内给出待解决组合优化问题的一个可行解。

目前通用的启发式算法

目前比较通用的启发式算法一般有模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）、人工神经网络（ANN）等。

模拟退火算法(SA)

模拟退火算法(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(xnew)-f(x))/k*T)接受x_new作为解。

5. 如果当前温度<Tmin时，则退出循环，输出当前结果，否则减少当前温度，回到第2步继续循环，常用的降温方法为T= a*T (0<a<1)，一般a取接近1的值

模拟退火算法实例

求解函数最小值问题：​ 其中，0<=x<=100,给定任意y值，求x为多少时，F(x)最小。

public class SATest {
 public static final int T = 1000;// 初始化温度
 public static final double Tmin = 1;// 温度的下界
 public static final int k = 100;// 迭代的次数
 public static final double delta = 0.98;// 温度的下降率
​
 public static double getX() {
 return Math.random() * 100;
 }
​
 /**
 * 评价函数的值,即对应上文中的f(x)
 * 
 * @param x目标函数中的一个参数
 * @param y目标函数中的另一个参数
 * @return函数值
 */
 public static double getFuncResult(double x, double y) {
 double result = 6 * Math.pow(x, 7) + 8 * Math.pow(x, 6) + 7
 * Math.pow(x, 3) + 5 * Math.pow(x, 2) - x * y;
​
 return result;
 }
​
 /**
 * 模拟退火算法的过程
 * @param y目标函数中的指定的参数
 * @return最优解
 */
 public static double getSA(double y) {
 double result = Double.MAX_VALUE;// 初始化最终的结果
 double x[] = new double[k];
 // 初始化初始解
 for (int i = 0; i < k; i++) {
 x[i] = getX();
 }
 // 迭代的过程
 while (t > Tmin) {
 for (int i = 0; i < k; i++) {
 // 计算此时的函数结果
 double funTmp = getFuncResult(x[i], y);
 // 在邻域内产生新的解
 double x_new = x[i] + (Math.random() * 2 - 1);
 // 判断新的x不能超出界
 if (x_new >= 0 && x_new <= 100) {
 double funTmp_new = getFuncResult(x_new, y);
 if (funTmp_new - funTmp < 0) {
 // 替换
 x[i] = x_new;
 } else {
 // 以概率替换
 double p = 1 / (1 + Math
 .exp(-(funTmp_new - funTmp) / T));
 if (Math.random() < p) {
 x[i] = x_new;
 }
 }
 }
 }
 T = T * delta;
 }
 for (int i = 0; i < k; i++) {
 result = Math.min(result, getFuncResult(x[i], y));
 }
 return result;
 }
​
 public static void main(String args[]) {
 // 设置y的值
 int y = 0;
 System.out.println("最优解为：" + getSA(y));
 }
​
}

遗传算法(GA)

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

相关术语

编码(coding)：将物体的表现型用编码的方式转为程序可控的基因型。

比如现在要计算北京、天津、广东、新疆这四个城市的一条最优路径，但算法程序不能够直接处理北京、天津、广东、新疆这些数据，所以我们得给 它们编上号，北京（0）、天津（1）、广东（2）、新疆（3），路径（天津->新疆->北京->广东）可以表示成基因型串结构数据 （1302），这样算法程序只要直接处理它们的编号就行了。
（1）二进制编码，基因用0或1表示（常用于解决01背包问题）
​
如：基因A：00100011010 (代表一个个体的染色体)
​
（2）互换编码（用于解决排序问题，如旅行商问题和调度问题）
​
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。

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

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

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

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

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

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

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

交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

（1）单交叉点法 （用于二进制编码）
​
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
​
如：交叉前：
​
00000|01110000000010000
​
11100|00000111111000101
​
交叉后：
​
00000|00000111111000101
​
11100|01110000000010000
​
（2）双交叉点法 （用于二进制编码）
​
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.
​
如：交叉前：
​
01 |0010| 11
​
11 |0111| 01
​
交叉后：
​
11 |0010| 01
​
01 |0111| 11
​
（3）基于“ 与/或 ”交叉法 （用于二进制编码）
​
对父代按位"与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好 .
​
如：交叉前：
​
01001011
​
11011101
​
交叉后：
​
01001001
​
11011111
​
（4）单交叉点法 （用于互换编码）
​
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。
​
如：交叉前：
​
87213 | 09546
​
98356 | 71420
​
交叉后：
​
87213 | 95640
​
98356 | 72104
​
（5）部分匹配交叉（PMX）法（用于互换编码）
​
先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
​
父代A：872 | 130 | 9546
​
父代B：983 | 567 | 1420    变为：
​
TEMP A: 872 | 567 | 9546
​
TEMP B: 983 | 130 | 1420
​
对于 TEMP A、TEMP Ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５　３<——>６　７<——>０
​
子代Ａ：802 | 567 | 9143
​
子代Ｂ：986 | 130 | 5427
​
（6）顺序交叉法(OX) （用于互换编码）
​
从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复）。同理可得子代Ｂ。
​
父代A: 872 | 139 | 0546
​
父代B: 983 | 567 | 1420
​
交叉后：
​
子代A: 856 | 139 | 7420
​
子代B: 821 | 567 | 3904
​
（7）循环交叉（CX）（用于互换编码）
​
CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。
​
父代A：1 2 3 4 5 6 7 8 9
​
父代B：5 4 6 9 2 3 7 8 1
​
可得循环基因：1->5->2->4->3->6->9->7->8
​
子代Ｂ的编码同理。（循环基因 5->1->4->2->6->3->9->7->8）

变异(mutation)：交叉后可能（很小的概率）对染色体进行更改，来防止算法过早收敛而陷入局部最优解中。

变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm > 0.5，这时GA退化为随机搜索。

（1）基本位变异算子（用于二进制编码）

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。

变异前：

000001110000000010000

变异后：

000001110001000010000

（2）逆转变异算子（用于互换编码）（源代码中使用类似此方法）

在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。

变异前：

1346798205

变异后：

1246798305

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

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

遗传算法步骤

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

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

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

4. 回到第2步进行循环。直到达到指定的繁衍代数

蚁群算法(ACO)

简单介绍一下蚁群算法的思路。我们尝试复原一下蚂蚁寻找食物的场景。想象有一只蚂蚁找到了食物，这时它需要将食物带回蚁穴。对于这一只蚂蚁而言，它显然并不知道应该怎么走。那么，这只蚂蚁有可能会随机选择一条路线。

这条路线很可能是一条远路。但是，蚂蚁一路上留下了记号，也就是信息素。如果这只蚂蚁继续不停地搬运食物，或者有许多其他蚂蚁一块搬运的话。他们总会在运气好的时候走到更快往返的路线上。蚂蚁选择的路越好，相同时间内往返的次数也就更多，也就在路上留下了更多的信息素。

于是，蚂蚁们总会发现，有一些路径的信息素更浓，这些路径就是更好的路线。于是蚂蚁也就更多地向信息素更浓的路径上偏移。蚂蚁们不停重复这个过程，最终总能找到一条确定的路线，而这条路线就是蚂蚁们找到的最优路径。

蚁群算法步骤

1. 初始化蚂蚁数量、可行路段、每条路段距离、每条路段的初始信息素大小等信息

2. 设定蚂蚁的起点、终点。

3. 蚂蚁从起点出发根据信息素浓度，有一定的概率性选择路段，浓度越高，概率越大，逐步回到终点。

4. 在蚂蚁走过的路径上，根据每条路段的长度按比例释放信息素，短的路段释放的信息素多，长的路段释放的信息素少。

5. 对所有路段的信息素进行挥发。

6. 回到第二步进行循环，直到蚂蚁数量迭代完。