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

啟發(fā)式算法一般用于解決NP-hard問(wèn)題，其中NP是指非確定性多項(xiàng)式。

例如，著名的推銷員旅行問(wèn)題（Travel Saleman Problem or TSP）：假設(shè)一個(gè)推銷員需要從南京出發(fā)，經(jīng)過(guò)廣州，北京，上海，…，等 n 個(gè)城市， 最后返回香港。 任意兩個(gè)城市之間都有飛機(jī)直達(dá)，但票價(jià)不等。假設(shè)公司只給報(bào)銷 C 元錢，問(wèn)是否存在一個(gè)行程安排，使得他能遍歷所有城市，而且總的路費(fèi)小于 C？

推銷員旅行問(wèn)題顯然是 NP 的。因?yàn)槿绻闳我饨o出一個(gè)行程安排，可以很容易算出旅行總開(kāi)銷。但是，要想知道一條總路費(fèi)小于 C 的行程是否存在，在最壞情況下，必須檢查所有可能的旅行安排。

啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的，是基于直觀或者經(jīng)驗(yàn)構(gòu)造的算法，在可接受的開(kāi)銷（時(shí)間和空間）內(nèi)給出待解決組合優(yōu)化問(wèn)題的一個(gè)可行解。

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

目前比較通用的啟發(fā)式算法一般有模擬退火算法（SA）、遺傳算法（GA）、蟻群算法（ACO）、人工神經(jīng)網(wǎng)絡(luò)（ANN）等。

模擬退火算法(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

2. 隨機(jī)生成臨域解x_new;

3. 設(shè)f(x)函數(shù)來(lái)計(jì)算用來(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(xnew)-f(x))/k*T)接受x_new作為解。

5. 如果當(dāng)前溫度<Tmin時(shí)，則退出循環(huán)，輸出當(dāng)前結(jié)果，否則減少當(dāng)前溫度，回到第2步繼續(xù)循環(huán)，常用的降溫方法為T= a*T (0<a<1)，一般a取接近1的值

模擬退火算法實(shí)例

求解函數(shù)最小值問(wèn)題：? 其中，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ò)程以求得最佳解。

相關(guān)術(shù)語(yǔ)

編碼(coding)：將物體的表現(xiàn)型用編碼的方式轉(zhuǎn)為程序可控的基因型。

比如現(xiàn)在要計(jì)算北京、天津、廣東、新疆這四個(gè)城市的一條最優(yōu)路徑，但算法程序不能夠直接處理北京、天津、廣東、新疆這些數(shù)據(jù)，所以我們得給 它們編上號(hào)，北京（0）、天津（1）、廣東（2）、新疆（3），路徑（天津->新疆->北京->廣東）可以表示成基因型串結(jié)構(gòu)數(shù)據(jù) （1302），這樣算法程序只要直接處理它們的編號(hào)就行了。
（1）二進(jìn)制編碼，基因用0或1表示（常用于解決01背包問(wèn)題）
?
如：基因A：00100011010 (代表一個(gè)個(gè)體的染色體)
?
（2）互換編碼（用于解決排序問(wèn)題，如旅行商問(wèn)題和調(diào)度問(wèn)題）
?
如旅行商問(wèn)題中，一串基因編碼用來(lái)表示遍歷的城市順序，如：234517986，表示九個(gè)城市中，先經(jīng)過(guò)城市2，再經(jīng)過(guò)城市3，依此類推。

解碼(decoding)：基因型到表現(xiàn)型的映射。

基因型(genotype)：參數(shù)的因子；

表現(xiàn)型(phenotype)：根據(jù)不同因子最終展現(xiàn)的形態(tài)；

適應(yīng)度(fitness)：度量某個(gè)結(jié)果的好壞。

進(jìn)化(evolution)：不斷剔除差的結(jié)果，最終逐步留下好的結(jié)果。

選擇(selection)：以一定的概率從種群中選擇若干個(gè)個(gè)體留下，并繁殖。選擇過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。

復(fù)制(reproduction)：將父本、母本的基因復(fù)制，以便產(chǎn)生下一代。

交叉(crossover)：兩個(gè)染色體的某一相同位置處DNA被切斷，前后兩串分別交叉組合形成兩個(gè)新的染色體。也稱基因重組或雜交；

（1）單交叉點(diǎn)法 （用于二進(jìn)制編碼）
?
選擇一個(gè)交叉點(diǎn),子代在交叉點(diǎn)前面的基因從一個(gè)父代基因那里得到,后面的部分從另外一個(gè)父代基因那里得到。
?
如：交叉前：
?
00000|01110000000010000
?
11100|00000111111000101
?
交叉后：
?
00000|00000111111000101
?
11100|01110000000010000
?
（2）雙交叉點(diǎn)法 （用于二進(jìn)制編碼）
?
選擇兩個(gè)交叉點(diǎn),子代基因在兩個(gè)交叉點(diǎn)間部分來(lái)自一個(gè)父代基因,其余部分來(lái)自于另外一個(gè)父代基因.
?
如：交叉前：
?
01 |0010| 11
?
11 |0111| 01
?
交叉后：
?
11 |0010| 01
?
01 |0111| 11
?
（3）基于“ 與/或 ”交叉法 （用于二進(jìn)制編碼）
?
對(duì)父代按位"與”邏輯運(yùn)算產(chǎn)生一子代A;按位”或”邏輯運(yùn)算產(chǎn)生另一子代B。該交叉策略在解背包問(wèn)題中效果較好 .
?
如：交叉前：
?
01001011
?
11011101
?
交叉后：
?
01001001
?
11011111
?
（4）單交叉點(diǎn)法 （用于互換編碼）
?
選擇一個(gè)交叉點(diǎn)，子代的從初始位置出發(fā)的部分從一個(gè)基因復(fù)制，然后在另一個(gè)基因中掃描，如果某個(gè)位點(diǎn)在子代中沒(méi)有，就把它添加進(jìn)去。
?
如：交叉前：
?
87213 | 09546
?
98356 | 71420
?
交叉后：
?
87213 | 95640
?
98356 | 72104
?
（5）部分匹配交叉（PMX）法（用于互換編碼）
?
先隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用交換兩個(gè)父代的匹配區(qū)域。
?
父代A：872 | 130 | 9546
?
父代B：983 | 567 | 1420    變?yōu)椋??
TEMP A: 872 | 567 | 9546
?
TEMP B: 983 | 130 | 1420
?
對(duì)于 TEMP A、TEMP Ｂ中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替換。匹配關(guān)系：1<——>５?。?lt;——>６?。?lt;——>０
?
子代Ａ：802 | 567 | 9143
?
子代Ｂ：986 | 130 | 5427
?
（6）順序交叉法(OX) （用于互換編碼）
?
從父代Ａ隨機(jī)選一個(gè)編碼子串，放到子代Ａ的對(duì)應(yīng)位置；子代Ａ空余的位置從父代Ｂ中按Ｂ的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代Ｂ。
?
父代A: 872 | 139 | 0546
?
父代B: 983 | 567 | 1420
?
交叉后：
?
子代A: 856 | 139 | 7420
?
子代B: 821 | 567 | 3904
?
（7）循環(huán)交叉（CX）（用于互換編碼）
?
CX同OX交叉都是從一個(gè)親代中取一些城市，而其它城市來(lái)自另外一個(gè)親代，但是二者不同之處在于：OX中來(lái)自第一個(gè)親代的編碼子串是隨機(jī)產(chǎn)生的，而CX卻不是，它是根據(jù)兩個(gè)雙親相應(yīng)位置的編碼而確定的。
?
父代A：1 2 3 4 5 6 7 8 9
?
父代B：5 4 6 9 2 3 7 8 1
?
可得循環(huán)基因：1->5->2->4->3->6->9->7->8
?
子代Ｂ的編碼同理。（循環(huán)基因 5->1->4->2->6->3->9->7->8）

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

變異概率Pm不能太小，這樣降低全局搜索能力；也不能太大，Pm > 0.5，這時(shí)GA退化為隨機(jī)搜索。

（1）基本位變異算子（用于二進(jìn)制編碼）

基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。

變異前：

000001110000000010000

變異后：

000001110001000010000

（2）逆轉(zhuǎn)變異算子（用于互換編碼）（源代碼中使用類似此方法）

在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因交換。

變異前：

1346798205

變異后：

1246798305

個(gè)體（individual）：指染色體帶有特征的實(shí)體；

種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大小

遺傳算法步驟

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. 回到第2步進(jìn)行循環(huán)。直到達(dá)到指定的繁衍代數(shù)

蟻群算法(ACO)

簡(jiǎn)單介紹一下蟻群算法的思路。我們嘗試復(fù)原一下螞蟻尋找食物的場(chǎng)景。想象有一只螞蟻找到了食物，這時(shí)它需要將食物帶回蟻穴。對(duì)于這一只螞蟻而言，它顯然并不知道應(yīng)該怎么走。那么，這只螞蟻有可能會(huì)隨機(jī)選擇一條路線。

這條路線很可能是一條遠(yuǎn)路。但是，螞蟻一路上留下了記號(hào)，也就是信息素。如果這只螞蟻繼續(xù)不停地搬運(yùn)食物，或者有許多其他螞蟻一塊搬運(yùn)的話。他們總會(huì)在運(yùn)氣好的時(shí)候走到更快往返的路線上。螞蟻選擇的路越好，相同時(shí)間內(nèi)往返的次數(shù)也就更多，也就在路上留下了更多的信息素。

于是，螞蟻們總會(huì)發(fā)現(xiàn)，有一些路徑的信息素更濃，這些路徑就是更好的路線。于是螞蟻也就更多地向信息素更濃的路徑上偏移。螞蟻們不停重復(fù)這個(gè)過(guò)程，最終總能找到一條確定的路線，而這條路線就是螞蟻們找到的最優(yōu)路徑。

蟻群算法步驟

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

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

3. 螞蟻從起點(diǎn)出發(fā)根據(jù)信息素濃度，有一定的概率性選擇路段，濃度越高，概率越大，逐步回到終點(diǎn)。

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

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

6. 回到第二步進(jìn)行循環(huán)，直到螞蟻數(shù)量迭代完。