有关启发式算法（Heuristic Algorithm）的一些总

什么是启发式算法

节选自维基百科：

启发法（heuristics，源自古希腊语的εὑρίσκω，又译作：策略法、助发现法、启发力、捷思法）是指依据有限的知识（或“不完整的信息”）在短时间内找到问题解决方案的一种技术。

它是一种依据关于系统的有限认知和假说从而得到关于此系统的结论的分析行为。由此得到的解决方案有可能会偏离最佳方案。通过与最佳方案的对比，可以确保启发法的质量。

计算机科学的两大基础目标，就是发现可证明其运行效率良好且可得最佳解或次佳解的算法。

而启发式算法则试图一次提供一个或全部目标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解； 它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。

因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

有一类的通用启发式策略称为元启发式算法（metaheuristic），通常使用随机数搜索技巧。他们可以应用在非常广泛的问题上，但不能保证效率。

节选自百度百科：

启发式算法可以这样定义：一个基于直观或经验构造的算法， 在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解， 该可行解与最优解的偏离程度一般不能被预计。 现阶段，启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、神经网络等。

通用的启发式算法

目前比较通用的启发式算法一般有模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）。

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

5. 如果当前温度小于Tmin的时候，退出循环，输出结果；否则，降低当前温度，T=a*T,(0<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）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

术语

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

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

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

步骤

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

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

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

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

实例&实现

给定一组五个基因，每一个基因可以保存一个二进制值 0 或 1。这里的适应度是基因组中 1 的数量。如果基因组内共有五个 1，则该个体适应度达到最大值。如果基因组内没有 1，那么个体的适应度达到最小值。该遗传算法希望最大化适应度，并提供适应度达到最大的个体所组成的群体。

public class SimpleDemoGA {
​
 Population population = new Population();
 Individual fittest;
 Individual secondFittest;
 int generationCount = 0;
​
 public static void main(String[] args) {
​
 Random rn = new Random();

 SimpleDemoGA demo = new SimpleDemoGA();

 //Initialize population
 demo.population.initializePopulation(10);

 //Calculate fitness of each individual
 demo.population.calculateFitness();

 System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
​
 //While population gets an individual with maximum fitness
 while (demo.population.fittest < 5) {
 ++demo.generationCount;

 //Do selection
 demo.selection();

 //Do crossover
 demo.crossover();

 //Do mutation under a random probability
 if (rn.nextInt()%7 < 5) {
 demo.mutation();
 }

 //Add fittest offspring to population
 demo.addFittestOffspring();

 //Calculate new fitness value 
 demo.population.calculateFitness();

 System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
 }
​
 System.out.println("\nSolution found in generation " + demo.generationCount);
 System.out.println("Fitness: "+demo.population.getFittest().fitness);
 System.out.print("Genes: ");
 for (int i = 0; i < 5; i++) {
 System.out.print(demo.population.getFittest().genes[i]);
 }
​
 System.out.println("");
​
 }
​
 //Selection
 void selection() {

 //Select the most fittest individual
 fittest = population.getFittest();

 //Select the second most fittest individual
 secondFittest = population.getSecondFittest();
 }
​
 //Crossover
 void crossover() {
 Random rn = new Random();

 //Select a random crossover point
 int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);
​
 //Swap values among parents
 for (int i = 0; i < crossOverPoint; i++) {
 int temp = fittest.genes[i];
 fittest.genes[i] = secondFittest.genes[i];
 secondFittest.genes[i] = temp;
​
 }
​
 }
​
 //Mutation
 void mutation() {
 Random rn = new Random();

 //Select a random mutation point
 int mutationPoint = rn.nextInt(population.individuals[0].geneLength);
​
 //Flip values at the mutation point
 if (fittest.genes[mutationPoint] == 0) {
 fittest.genes[mutationPoint] = 1;
 } else {
 fittest.genes[mutationPoint] = 0;
 }
​
 mutationPoint = rn.nextInt(population.individuals[0].geneLength);
​
 if (secondFittest.genes[mutationPoint] == 0) {
 secondFittest.genes[mutationPoint] = 1;
 } else {
 secondFittest.genes[mutationPoint] = 0;
 }
 }
​
 //Get fittest offspring
 Individual getFittestOffspring() {
 if (fittest.fitness > secondFittest.fitness) {
 return fittest;
 }
 return secondFittest;
 }
​
​
 //Replace least fittest individual from most fittest offspring
 void addFittestOffspring() {

 //Update fitness values of offspring
 fittest.calcFitness();
 secondFittest.calcFitness();

 //Get index of least fit individual
 int leastFittestIndex = population.getLeastFittestIndex();

 //Replace least fittest individual from most fittest offspring
 population.individuals[leastFittestIndex] = getFittestOffspring();
 }
​
}
​
​
//Individual class
class Individual {
​
 int fitness = 0;
 int[] genes = new int[5];
 int geneLength = 5;
​
 public Individual() {
 Random rn = new Random();
​
 //Set genes randomly for each individual
 for (int i = 0; i < genes.length; i++) {
 genes[i] = rn.nextInt() % 2;
 }
​
 fitness = 0;
 }
​
 //Calculate fitness
 public void calcFitness() {
​
 fitness = 0;
 for (int i = 0; i < 5; i++) {
 if (genes[i] == 1) {
 ++fitness;
 }
 }
 }
​
}
​
//Population class
class Population {
​
 int popSize = 10;
 Individual[] individuals = new Individual[10];
 int fittest = 0;
​
 //Initialize population
 public void initializePopulation(int size) {
 for (int i = 0; i < individuals.length; i++) {
 individuals[i] = new Individual();
 }
 }
​
 //Get the fittest individual
 public Individual getFittest() {
 int maxFit = Integer.MIN_VALUE;
 for (int i = 0; i < individuals.length; i++) {
 if (maxFit <= individuals[i].fitness) {
 maxFit = i;
 }
 }
 fittest = individuals[maxFit].fitness;
 return individuals[maxFit];
 }
​
 //Get the second most fittest individual
 public Individual getSecondFittest() {
 int maxFit1 = 0;
 int maxFit2 = 0;
 for (int i = 0; i < individuals.length; i++) {
 if (individuals[i].fitness > individuals[maxFit1].fitness) {
 maxFit2 = maxFit1;
 maxFit1 = i;
 } else if (individuals[i].fitness > individuals[maxFit2].fitness) {
 maxFit2 = i;
 }
 }
 return individuals[maxFit2];
 }
​
 //Get index of least fittest individual
 public int getLeastFittestIndex() {
 int minFit = 0;
 for (int i = 0; i < individuals.length; i++) {
 if (minFit >= individuals[i].fitness) {
 minFit = i;
 }
 }
 return minFit;
 }
​
 //Calculate fitness of each individual
 public void calculateFitness() {
​
 for (int i = 0; i < individuals.length; i++) {
 individuals[i].calcFitness();
 }
 getFittest();
 }
​
}

蚁群算法（ACO）

想象有一只蚂蚁找到了食物，那么它就需要将这个食物待会蚂蚁穴。对于这只蚂蚁来说，它并不知道应该怎么回到蚂蚁穴。

这只蚂蚁有可能会随机选择一条路线，这条路可能路程比较远，但是这只蚂蚁在这条路上留下了记号（一种化学物质，信息素）。如果这只蚂蚁继续不停地搬运食物的时候，有其它许多蚂蚁一起搬运的话，它们总会有运气好的时候走到更快返回蚂蚁穴的路线。当蚂蚁选择的路线越优，相同时间内蚂蚁往返的次数就会越多，这样就在这条路上留下了更多的信息素。

这时候，蚂蚁们就会选择一些路径上信息素越浓的，这些路径就是较优的路径。当蚂蚁们不断重复这个过程，蚂蚁们就会更多地向更浓的信息素的路径上偏移，这样最终会确定一条路径，这条路径就是最优路径。

步骤

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

2. 设定蚂蚁的起点和终点；

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

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

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

6. 返回第二步，继续循环，直到蚂蚁数量迭代完成。

参考资料

• https://www.jianshu.com/p/e2aec624106a

• Introduction to Genetic Algorithms — Including Example Code