什么是啟發(fā)式算法

節(jié)選自維基百科：

啟發(fā)法（heuristics，源自古希臘語(yǔ)的ε?ρ?σκω，又譯作：策略法嚎朽、助發(fā)現(xiàn)法、啟發(fā)力柬帕、捷思法）是指依據(jù)有限的知識(shí)（或“不完整的信息”）在短時(shí)間內(nèi)找到問(wèn)題解決方案的一種技術(shù)哟忍。

它是一種依據(jù)關(guān)于系統(tǒng)的有限認(rèn)知和假說(shuō)從而得到關(guān)于此系統(tǒng)的結(jié)論的分析行為。由此得到的解決方案有可能會(huì)偏離最佳方案陷寝。通過(guò)與最佳方案的對(duì)比锅很，可以確保啟發(fā)法的質(zhì)量。

計(jì)算機(jī)科學(xué)的兩大基礎(chǔ)目標(biāo)凤跑，就是發(fā)現(xiàn)可證明其運(yùn)行效率良好且可得最佳解或次佳解的算法爆安。

而啟發(fā)式算法則試圖一次提供一個(gè)或全部目標(biāo)。例如它常能發(fā)現(xiàn)很不錯(cuò)的解饶火，但也沒(méi)辦法證明它不會(huì)得到較壞的解鹏控； 它通持鲁叮可在合理時(shí)間解出答案肤寝，但也沒(méi)辦法知道它是否每次都可以這樣的速度求解。

有時(shí)候人們會(huì)發(fā)現(xiàn)在某些特殊情況下抖僵，啟發(fā)式算法會(huì)得到很壞的答案或效率極差鲤看，然而造成那些特殊情況的數(shù)據(jù)結(jié)構(gòu)，也許永遠(yuǎn)不會(huì)在現(xiàn)實(shí)世界出現(xiàn)耍群。

因此現(xiàn)實(shí)世界中啟發(fā)式算法很常用來(lái)解決問(wèn)題义桂。啟發(fā)式算法處理許多實(shí)際問(wèn)題時(shí)通常可以在合理時(shí)間內(nèi)得到不錯(cuò)的答案蹈垢。

有一類(lèi)的通用啟發(fā)式策略稱(chēng)為元啟發(fā)式算法（metaheuristic）慷吊，通常使用隨機(jī)數(shù)搜索技巧。他們可以應(yīng)用在非常廣泛的問(wèn)題上曹抬，但不能保證效率溉瓶。

節(jié)選自百度百科：

啟發(fā)式算法可以這樣定義：一個(gè)基于直觀(guān)或經(jīng)驗(yàn)構(gòu)造的算法， 在可接受的花費(fèi)（指計(jì)算時(shí)間和空間）下給出待解決組合優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解， 該可行解與最優(yōu)解的偏離程度一般不能被預(yù)計(jì)堰酿。 現(xiàn)階段疾宏，啟發(fā)式算法以仿自然體算法為主，主要有蟻群算法触创、模擬退火法坎藐、神經(jīng)網(wǎng)絡(luò)等。

通用的啟發(fā)式算法

目前比較通用的啟發(fā)式算法一般有模擬退火算法（SA）哼绑、遺傳算法（GA）岩馍、蟻群算法（ACO）。

模擬退火算法（SA）

模擬退火算法(Simulated Annealing, SA)的思想借鑒于固體的退火原理凌那，當(dāng)固體的溫度很高的時(shí)候兼雄，內(nèi)能比較大，固體的內(nèi)部粒子處于快速無(wú)序運(yùn)動(dòng)帽蝶，當(dāng)溫度慢慢降低的過(guò)程中赦肋，固體的內(nèi)能減小，粒子的慢慢趨于有序励稳，最終佃乘，當(dāng)固體處于常溫時(shí)，內(nèi)能達(dá)到最小驹尼，此時(shí)趣避，粒子最為穩(wěn)定。模擬退火算法便是基于這樣的原理設(shè)計(jì)而成新翎。

步驟

1. 初始化溫度T（充分大）程帕，溫度下限Tmin(充分小)，初始解X地啰，每個(gè)T迭代次數(shù)為L(zhǎng)愁拭；

2. 隨機(jī)生成臨時(shí)解域X_new;

3. 設(shè)f(x)函數(shù)來(lái)計(jì)算解的好壞，計(jì)算出f(X_new)-f(X);

4. 如果f(X_new)-f(X)>0亏吝，說(shuō)明新解比原來(lái)的解好岭埠，則無(wú)條件接受，如果f(X_new)-f(X)<0蔚鸥，則說(shuō)明舊解比新解好惜论，則以概率exp((f(X_new)-f(x))/k*T)接受X_new作為解。

5. 如果當(dāng)前溫度小于Tmin的時(shí)候止喷，退出循環(huán)馆类，輸出結(jié)果；否則弹谁，降低當(dāng)前溫度乾巧，T=a*T,(0<a<1)技羔，跳轉(zhuǎn)到第二步繼續(xù)循環(huán)。

實(shí)例&代碼實(shí)現(xiàn)

求解給定函數(shù)的最小值：其中卧抗，0<=x<=100,給定任意y的值藤滥，求解x為多少的時(shí)候，F(xiàn)(x)最猩珩伞拙绊？

public class SATest {
 public static final int T = 1000;// 初始化溫度
 public static final double Tmin = 1;// 溫度的下界
 public static final int k = 100;// 迭代的次數(shù)
 public static final double delta = 0.98;// 溫度的下降率
?
 public static double getX() {
 return Math.random() * 100;
 }
?
 /**
 * 評(píng)價(jià)函數(shù)的值,即對(duì)應(yīng)上文中的f(x)
 * 
 * @param x目標(biāo)函數(shù)中的一個(gè)參數(shù)
 * @param y目標(biāo)函數(shù)中的另一個(gè)參數(shù)
 * @return函數(shù)值
 */
 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;
 }
?
 /**
 * 模擬退火算法的過(guò)程
 * @param y目標(biāo)函數(shù)中的指定的參數(shù)
 * @return最優(yōu)解
 */
 public static double getSA(double y) {
 double result = Double.MAX_VALUE;// 初始化最終的結(jié)果
 double x[] = new double[k];
 // 初始化初始解
 for (int i = 0; i < k; i++) {
 x[i] = getX();
 }
 // 迭代的過(guò)程
 while (t > Tmin) {
 for (int i = 0; i < k; i++) {
 // 計(jì)算此時(shí)的函數(shù)結(jié)果
 double funTmp = getFuncResult(x[i], y);
 // 在鄰域內(nèi)產(chǎn)生新的解
 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[]) {
 // 設(shè)置y的值
 int y = 0;
 System.out.println("最優(yōu)解為：" + getSA(y));
 }
?
}

遺傳算法（GA）

遺傳算法（Genetic Algorithm, GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。它是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方法泳秀，借鑒了達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)标沪。其本質(zhì)是一種高效、并行嗜傅、全局搜索的方法金句，能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最佳解吕嘀。

術(shù)語(yǔ)

• 編碼：將物體的表現(xiàn)型轉(zhuǎn)化為計(jì)算機(jī)可處理的編碼的基因型违寞；

• 交叉：兩個(gè)染色體的某一相同位置的DNA被切斷，前后兩串染色體分別交叉形成兩個(gè)新的染色體偶房；

• 變異：交叉后可能（極小概率）對(duì)染色體進(jìn)行修改趁曼，來(lái)防止算法過(guò)早收斂而陷入局部最優(yōu)解；

步驟

1. 對(duì)潛在問(wèn)題進(jìn)行編碼棕洋，初始化基因組挡闰，并根據(jù)基因組隨機(jī)初始化種群，并指定繁衍代數(shù)掰盘；

2. 計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度摄悯，選擇一定數(shù)量的留下，其它淘汰愧捕；

3. 在留下的個(gè)體中奢驯，隨機(jī)繁衍，對(duì)母基因進(jìn)行交叉（極小概率變異）晃财，產(chǎn)生下一代叨橱；

4. 跳轉(zhuǎn)到第2步，繼續(xù)循環(huán)，直到達(dá)到繁衍代數(shù)為止撒璧。

實(shí)例&實(shí)現(xiàn)

給定一組五個(gè)基因赐俗，每一個(gè)基因可以保存一個(gè)二進(jìn)制值 0 或 1。這里的適應(yīng)度是基因組中 1 的數(shù)量蒙畴。如果基因組內(nèi)共有五個(gè) 1，則該個(gè)體適應(yīng)度達(dá)到最大值。如果基因組內(nèi)沒(méi)有 1命迈，那么個(gè)體的適應(yīng)度達(dá)到最小值贩绕。該遺傳算法希望最大化適應(yīng)度，并提供適應(yīng)度達(dá)到最大的個(gè)體所組成的群體壶愤。

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）

想象有一只螞蟻找到了食物淑倾，那么它就需要將這個(gè)食物待會(huì)螞蟻穴。對(duì)于這只螞蟻來(lái)說(shuō)征椒，它并不知道應(yīng)該怎么回到螞蟻穴娇哆。

這只螞蟻有可能會(huì)隨機(jī)選擇一條路線(xiàn)，這條路可能路程比較遠(yuǎn)勃救，但是這只螞蟻在這條路上留下了記號(hào)（一種化學(xué)物質(zhì)碍讨，信息素）。如果這只螞蟻繼續(xù)不停地搬運(yùn)食物的時(shí)候蒙秒，有其它許多螞蟻一起搬運(yùn)的話(huà)勃黍，它們總會(huì)有運(yùn)氣好的時(shí)候走到更快返回螞蟻穴的路線(xiàn)。當(dāng)螞蟻選擇的路線(xiàn)越優(yōu)晕讲，相同時(shí)間內(nèi)螞蟻往返的次數(shù)就會(huì)越多覆获，這樣就在這條路上留下了更多的信息素。

這時(shí)候瓢省，螞蟻們就會(huì)選擇一些路徑上信息素越濃的锻梳，這些路徑就是較優(yōu)的路徑。當(dāng)螞蟻們不斷重復(fù)這個(gè)過(guò)程净捅，螞蟻們就會(huì)更多地向更濃的信息素的路徑上偏移疑枯，這樣最終會(huì)確定一條路徑，這條路徑就是最優(yōu)路徑蛔六。

步驟

1. 初始化螞蟻數(shù)量荆永、可行路段、每條路段距離国章、每條路段的初始信息素大小等信息具钥；

2. 設(shè)定螞蟻的起點(diǎn)和終點(diǎn)；

3. 螞蟻從起點(diǎn)出發(fā)根據(jù)信息素濃度液兽，有一定概率性地選擇路段骂删，濃度越高，概率越大四啰，逐步到達(dá)終點(diǎn)宁玫；

4. 在螞蟻?zhàn)哌^(guò)的路徑上，根據(jù)每條路段的長(zhǎng)度按照比例釋放信息素柑晒，短的路段釋放的信息素多欧瘪，長(zhǎng)的路段釋放的信息素少；

5. 對(duì)所有路段的信息素進(jìn)行揮發(fā)匙赞；

6. 返回第二步佛掖，繼續(xù)循環(huán)妖碉，直到螞蟻數(shù)量迭代完成。

參考資料

• http://www.reibang.com/p/e2aec624106a

• Introduction to Genetic Algorithms?—?Including Example Code