旅行商問題的近似最優(yōu)解（局部搜索躺盛、模擬退火项戴、遺傳算法）

關(guān)鍵字：旅行商問題，TSP槽惫，局部搜索周叮，模擬退火，遺傳算法

TSP問題（Traveling Salesman Problem）是一個組合優(yōu)化問題界斜。該問題可以被證明具有NPC計算復(fù)雜性仿耽。

迄今為止，這類問題中沒有一個找到有效算法各薇。

也就是說氓仲，沒有一個算法能夠在多項式時間內(nèi)解得TSP問題的最優(yōu)解，所以只能通過我們介紹的方法得糜，即遺傳算法、模擬退火算法晰洒、局部搜索朝抖，來尋求近似最優(yōu)解。

遺傳算法

遺傳算法（Genetic Algorithm, GA）起源于對生物系統(tǒng)所進行的計算機模擬研究谍珊。

它是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法治宣，借鑒了達(dá)爾文的進化論和孟德爾的遺傳學(xué)說。

其本質(zhì)是一種高效、并行侮邀、全局搜索的方法坏怪，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最佳解绊茧。

image-20210402133435682

private double fitness; // 適應(yīng)度
private double selectedRate; // 被選中的概率铝宵，歸一化處理
@Override
public int compareTo(Species o) {
    if (getRouteLength() < o.getRouteLength()) {
        return -1;
    } else if (getRouteLength() == o.getRouteLength()) {
        return 0;
    } else {
        return 1;
    }
}

對個體的操作有可能會影響到適應(yīng)度，所以在關(guān)鍵操作之前必須更新適應(yīng)度华畏。

由于距離越短鹏秋，表現(xiàn)越好，那么適應(yīng)度就越高亡笑，所以可以定義適應(yīng)度為距離的倒數(shù)侣夷。

/**
 * 獲得適應(yīng)度
 * @return 適應(yīng)度
*/
public double getFitness() {
    updateFiness(); // 返回之前必須先更新（如果需要）
    return fitness;
}
/**
 * 計算并設(shè)置適應(yīng)度
*/
private void calculateAndSetFitness() {
    updateLength(); // 計算適應(yīng)度之前必須更新長度
    this.fitness = 1.0 / getRouteLength();
}

后面用到輪盤賭，被選中的概率必須歸一化處理仑乌。

/**
 * 設(shè)置被選中的概率百拓，歸一化處理
 * @param selectedRate 被選擇的概率，歸一化處理
*/
public void setSelectedRate(double selectedRate) {
    this.selectedRate = selectedRate;
}

后面用到變異晰甚，設(shè)計到一個逆轉(zhuǎn)給定區(qū)間衙传，即1-2-3-4，逆轉(zhuǎn)2-3压汪，就變成1-3-2-4粪牲。為方便起見，封裝成了一個方法止剖。

/**
 * 逆轉(zhuǎn)給定區(qū)間
 * @param left 左端點（包含）
 * @param right 右端點（包含）
*/
public void reverse(int left, int right) {
    // 逆轉(zhuǎn)
    while (left < right) {
        City c = routeList.get(left);
        routeList.set(left, routeList.get(right));
        routeList.set(right, c);
        ++left;
        --right;
    } 

雜交和變異都是以一定概率進行的腺阳，下面省略隨機數(shù)生成和比較的部分，只給出核心代碼穿香，完整代碼參見第4部分亭引。

隨機選擇一對父母，隨機選擇一段基因皮获。

直接把這一段父親的基因復(fù)制到孩子對應(yīng)的部分焙蚓，孩子缺少的基因從母親那里拿，已經(jīng)重復(fù)的基因跳過洒宝。

image-20210402134106439

那么可以得到核心部分的代碼购公。

// 直接把這一段父親的基因復(fù)制到孩子對應(yīng)的部分
for (int i = beginIndex; i < endIndex; ++i)
    list.set(i, father.get(i));

// 孩子缺少的基因從母親那里拿
int i = 0;
// 從頭開始遍歷母親的基因
for (int j = 0; j < size; ++j) {
    if (i == beginIndex)
        i = endIndex; // 跳過父親那一段
    City c = mother.get(j); // 獲取母親的基因
    // 如果母親的基因已經(jīng)在孩子身上，就跳過雁歌，否則加入
    if (!list.contains(c)) { 
        list.set(i, c);
        i++;
    }
}

在實現(xiàn)的過程中宏浩，需要保證父母不是同一個個體，需要保證隨機一段的序列左端點小于右端點……

得到了孩子的序列以后靠瞎，構(gòu)造一個對象比庄，加入到種群中求妹。

變異對每一個個體都有概率，以一定的概率變異

這里的處理有很多種方法佳窑，例如制恍，隨機交換任意兩個城市的位置，又如神凑，隨機逆序一段路徑净神，再如，隨機選擇若干個奇數(shù)位的城市重新隨機打亂以后按順序放回……

這里采用了隨機逆序一段路徑的方法耙厚。

事實上强挫，也僅對收尾2個城市（4段路徑）影響較大。

image-20210402134139209

同樣薛躬，可以得到核心代碼俯渤。

// 隨機選擇一段基因，逆序
int left = (int) (Math.random() * sp.size());
int right = (int) (Math.random() * sp.size());
if (left > right) {
    int tmp = left;
    left = right;
    right = tmp;
}
sp.reverse(left, right);

物競天擇型宝，適者生存八匠。

所有表現(xiàn)不好的個體都應(yīng)該被淘汰。

考慮到表現(xiàn)越好趴酣，意味著路徑長度越短梨树，那么容易想到的是，把種群中所有的個體拿出來看看岖寞，按照路徑長度排個序抡四，取最短的若干名，其他淘汰仗谆。

由于個體Species已經(jīng)實現(xiàn)了Comparable接口指巡，所以直接放進優(yōu)先級隊列PriorityQueue，然后一個個取出來隶垮，要么取到取完藻雪，要么取到種群最大容量。

// 直接把個體丟掉優(yōu)先級隊列中狸吞，由于個體實現(xiàn)了Comparable接口勉耀，所以距離短的方案表現(xiàn)好，優(yōu)先級高
PriorityQueue<Species> pq = new PriorityQueue<Species>();
pq.addAll(group);
// 清空種群蹋偏，然后按照個體的表現(xiàn)從好到差放到種群中
group.clear();
while (!pq.isEmpty()) { // 要么放完
    group.add(pq.poll());
    if (group.size() == capacity) // 要么超過了最大容量就不放了
        break;

為方便起見晨雳，我采用的是這樣的方法秧廉，并且實踐證明效果能夠接受枫弟。

其主要思想是客燕，表現(xiàn)越好的個體越有可能活著（當(dāng)然也可能會被淘汰闺鲸，只是概率太低了以至于可以認(rèn)為小概率事件不發(fā)生）巡通，而表現(xiàn)差的個體存活的可能性就小鸠按，極有可能被淘汰（當(dāng)然也可能活著）醒陆。

具體的做法是，隨機選擇一個概率葫掉，然后看是不是滿足這個個體被選中的概率些举，如果是，那么就把這個個體放入到新的種群中俭厚，如果不是户魏，就用歸一化的概率減去隨機概率，用新的概率檢查下一個個體挪挤。

所有個體檢查完叼丑，如果仍沒有放滿種群容量，就再次循環(huán)扛门，再比較每一個個體鸠信，于是，表現(xiàn)較好的個體就可能會被放入新種群2次论寨、3次甚至更多次星立，直到種群容量滿了。

事實上葬凳，更常見的做法是輪盤賭绰垂。

下面給出核心部分代碼。

double rate = Math.random() / 100.0;
Species oldPoint = origin.get(i);
while (oldPoint != null && !oldPoint.equals(best))
{
    if (rate <= oldPoint.getSelectedRate()) {
        group.add(oldPoint);
            break;
    } else {
        rate = rate - oldPoint.getSelectedRate();
    }
}

這樣有可能會走到兩個極端火焰。

第一個極端劲装，很有可能表現(xiàn)最好的個體被淘汰了。

盡管表現(xiàn)最好的個體存活的概率非常非常大昌简，但是如果不幸發(fā)生小概率事件占业，把表現(xiàn)最好的個體淘汰了，那么就會丟失最優(yōu)解江场。

當(dāng)循環(huán)次數(shù)足夠多的時候纺酸，原來的表現(xiàn)第二的個體會在若干次的雜交和變異中變得越來越好，并進一步優(yōu)于原來表現(xiàn)最好的個體址否。

但是這樣明顯會使程序工作效率下降餐蔬，并且，很可能若干次以后表現(xiàn)最好的個體再次被淘汰佑附。

我們希望的是樊诺，表現(xiàn)最好的那一個，或者那兩個音同，以1的概率一定存活词爬。

第二個極端，表現(xiàn)最好的個體存活概率很大权均，后面的個體大多數(shù)都被淘汰了顿膨，那么整個新種群就可能會出現(xiàn)90%甚至更多的都是來自最好的那一個或者那兩個個體锅锨，后面10%是第三、第五恋沃、第十表現(xiàn)好的個體必搞。

這樣就會導(dǎo)致其實很多時候父親和母親都是一樣的，或者說囊咏，就是自交而不是雜交恕洲，會明顯地降低效率。

綜合上面這兩個極端梅割，可以給出一種妥協(xié)的方案——表現(xiàn)最好的個體以1的概率一定存活霜第，但是，最多不能超過新種群的四分之一户辞，剩下的部分按照標(biāo)準(zhǔn)輪盤賭的方案進行泌类，但是當(dāng)輪盤賭了若干次以后還沒有填滿種群，不再反復(fù)進行咆课，而是直接用表現(xiàn)最差的個體補滿剩下的若干個位置末誓。

這樣妥協(xié)的方案可以有效解決上面兩個極端，且測試效果良好书蚪。

for (int i = 1; i <= talentNum; i++) {
    group.add(best);// 復(fù)制物種至新表
if (oldPoint == null || oldPoint.equals(best)) 
    group.add(origin.getLast());

由于從優(yōu)先級隊列取出的時候喇澡，每個個體只被取出一次，所以不會出現(xiàn)上面說的第二個極端殊校，且由于優(yōu)先級隊列出隊的順序保證了表現(xiàn)最好的個體一定會在新種群中晴玖，所以不會出現(xiàn)上面說的第一個極端。

這樣为流，在每一次迭代中呕屎，表現(xiàn)最優(yōu)的個體只會越來越好，也就是說敬察，最短路徑的長度只可能變短秀睛，不可能邊長，最壞的情況就是不變莲祸。

只不過這樣其實就只是按照從好倒壞的順序保留存活蹂安，超過種群數(shù)量的就直接認(rèn)為是表現(xiàn)過差，被淘汰锐帜。

事實上田盈，在測試的過程中，種群數(shù)量在200的時候缴阎，表現(xiàn)第200的已經(jīng)足夠差了允瞧，所以這個種群包含了各種情況的樣本，可以認(rèn)為是完備了。所以超過200的述暂，雖然更差痹升，但是同時也失去了意義，可以直接淘汰贸典。

模擬退火算法

模擬退火算法(Simulated Annealing视卢，SA)最早的思想是由N. Metropolis [1] 等人于1953年提出。

模擬退火算法來源于固體退火原理廊驼，將固體加溫至充分高，再讓其徐徐冷卻惋砂，加溫時妒挎，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大西饵，而徐徐冷卻時粒子漸趨有序酝掩，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)眷柔，內(nèi)能減為最小期虾。

模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解驯嘱，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)镶苞。

模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法鞠评。

根據(jù)Metropolis準(zhǔn)則茂蚓，粒子在溫度T時趨于平衡的概率為e(-ΔE/(kT))。

其中E為溫度T時的內(nèi)能剃幌，ΔE為其改變量聋涨，k為Boltzmann常數(shù)。

用固體退火模擬組合優(yōu)化問題负乡，將內(nèi)能E模擬為目標(biāo)函數(shù)值f牍白，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法抖棘。

/**
 * MetroPolis準(zhǔn)則
 * 
 * @param bestRoute
 *            最優(yōu)解
 * @param currentRoute
 *            當(dāng)前解
 * @param currentTemperature
 *            當(dāng)前溫度
 * @return MetroPolis準(zhǔn)則的評估值
 */
private static double metropolis(Route bestRoute, Route currentRoute, double currentTemperature) {
    double ret = Math.exp(-(currentRoute.getRouteLength() - bestRoute.getRouteLength()) / currentTemperature);
    return ret;
}

當(dāng)溫度較高的時候茂腥，接受劣解的概率比較大，在初始高溫下钉答，幾乎以100%的概率接受劣解础芍。

隨著溫度的下降，接受劣解的概率逐漸減少数尿。

直到當(dāng)溫度趨于0時仑性，接受劣解的概率也同時趨于0。

這樣將有利于算法從局部最優(yōu)解中跳出右蹦，求得問題的全局最優(yōu)解诊杆。

/**
 * 能夠接受劣解的概率
 * 
 * @param currentTemperature
 *            當(dāng)前溫度
 * @return 能夠接受劣解的概率
*/
private static double getProbabilityToAcceptWorseRoute(double currentTemperature) {
    return (currentTemperature - ConstantValue.CHILLING_TEMPERATURE)
        / (ConstantValue.INITIAL_TEMPERATURE - ConstantValue.CHILLING_TEMPERATURE);
}

image-20210402134719314

// 用shuffle隨機一條路徑作為初始解歼捐，并復(fù)制一份作為初始最優(yōu)解

while (ConstantValue.CHILLING_TEMPERATURE < currentTemperature) {
    double p = getProbabilityToAcceptWorseRoute(currentTemperature);
    for (int i = 0; i < ConstantValue.SIMULATE_ANNEA_ITERATION_TIMES; i++) 
        // 產(chǎn)生鄰域
        if (neighbourRoute.getRouteLength() <= bestRoute.getRouteLength()) {
            // 如果新解比當(dāng)前解優(yōu)，接受
        } else if (metropolis(bestRoute, neighbourRoute, currentTemperature) > p) {
            // 否則按照Metropolis準(zhǔn)則確定接受的概率
        }
    }
    // 按照給定的速率降溫
}

局部搜索

與模擬退火方法類似晨汹，區(qū)別在于當(dāng)且僅當(dāng)新解比當(dāng)前解更優(yōu)的時候接受新解豹储。

image-20210402134811363

while (successfullyChanged != 0 && changed != 0) {
    Route neighbour = route.generateNeighbour();
    if (neighbour.getRouteLength() <= route.getRouteLength()) {
        route = neighbour;
        successfullyChanged--;
    }
    changed--;
}

算法測試

正確性測試

考慮僅有4個城市的情況。

這4個城市分別位于(1,0)淘这、(2,0)剥扣、(1,1)、(2,1)铝穷。

顯然只有2種走法钠怯，起路徑長度分別為4和4.828。

三種算法都能求得正確的最優(yōu)解曙聂。

遺傳算法：
City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] -> City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] -> 
RouteLength = 4.0
局部搜索：
City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] -> City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] -> 
RouteLength = 4.0
模擬退火算法：
City [index=4, x=2, y=1] -> City [index=2, x=2, y=0] -> City [index=1, x=1, y=0] -> City [index=3, x=1, y=1] -> 
RouteLength = 4.0

大規(guī)模數(shù)據(jù)

下面給出10個城市的運行結(jié)果晦炊。

image-20210402135214257

下面給出144個城市的運行結(jié)果。

image-20210402135224037

算法比較

首先給出10個城市的數(shù)據(jù)宁脊。

10
1 0 0
2 12 32
3 5 25
4 8 45
5 33 17
6 25 7
7 15 15
8 15 25
9 25 15
10 41 12

這組數(shù)據(jù)的真正最優(yōu)解是147.34断国。

下面嘗試使用遺傳算法運行這組數(shù)據(jù)，分別運行10次榆苞，取這10次結(jié)果的平均值和最小值稳衬。

這10次結(jié)果分別為：147.3408465677464、147.3408465677464语稠、171.87473677989576宋彼、147.3408465677464、147.3408465677464仙畦、147.3408465677464输涕、147.3408465677464、162.19167266106012慨畸、147.3408465677464莱坎、147.3408465677464。

這10次結(jié)果的最小值是147.34寸士，完全命中最優(yōu)解檐什。

事實上，有80%的概率命中了最優(yōu)解弱卡。

剩下的2次乃正，一次是162，一次是171婶博，誤差較大瓮具。

但是從全局考慮，10組數(shù)據(jù)的平均值是150.9，也足夠接近最優(yōu)解了名党。

同樣叹阔，使用局部搜索和模擬退火算法，對這組數(shù)據(jù)進行測試传睹，得到了下面這張表格耳幢。

從這張表中可以看到，在小數(shù)據(jù)規(guī)模的時候欧啤，模擬退火的算法準(zhǔn)確度是最低的睛藻。

這可能是由于模擬退火是接受劣解導(dǎo)致的，所以在小數(shù)據(jù)規(guī)模上會出現(xiàn)不在最優(yōu)解的可能邢隧。

下面給出更大數(shù)據(jù)規(guī)模的測試修档，并且下表僅列出各種算法在10次測試中出現(xiàn)的最小值。

可以看到盹牧，數(shù)據(jù)規(guī)模較大的時候，三種算法都能夠比較接近最優(yōu)解励幼。

但是由于數(shù)值變大汰寓，所以絕對誤差也隨之增加。如果計算相對誤差苹粟，可以看到相對誤差仍舊處于一個很小的范圍有滑。

同時可以看到，模擬退火的準(zhǔn)確度高于了局部搜索嵌削，局部搜索在大數(shù)據(jù)下顯得誤差最大毛好，這是由于局部搜索是最原始的，難以跳出局部最優(yōu)解苛秕，而模擬退火等算法能夠從局部最優(yōu)解中跳出肌访。

采用與上面相同的方法，對三種算法進行測試，得到下表衣摩。

同樣的董虱，每組數(shù)據(jù)呢堰，分別對每種算法運行10次旨剥，取10次中運行時間最快的咧欣，單位為毫秒。

完整代碼

https://gitlab.jxtxzzw.com/jxtxzzw/tsp

https://github.com/jxtxzzw/tsp

旅行商問題的近似最優(yōu)解（局部搜索轨帜、模擬退火魄咕、遺傳算法）

關(guān)鍵字：旅行商問題，TSP蚌父，局部搜索哮兰，模擬退火，遺傳算法

TSP問題（Traveling Salesman Problem）是一個組合優(yōu)化問題苟弛。該問題可以被證明具有NPC計算復(fù)雜性喝滞。

迄今為止，這類問題中沒有一個找到有效算法膏秫。

也就是說右遭，沒有一個算法能夠在多項式時間內(nèi)解得TSP問題的最優(yōu)解，所以只能通過我們介紹的方法缤削，即遺傳算法窘哈、模擬退火算法、局部搜索亭敢，來尋求近似最優(yōu)解滚婉。

遺傳算法

遺傳算法（Genetic Algorithm, GA）起源于對生物系統(tǒng)所進行的計算機模擬研究。

它是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法帅刀，借鑒了達(dá)爾文的進化論和孟德爾的遺傳學(xué)說让腹。

其本質(zhì)是一種高效、并行扣溺、全局搜索的方法骇窍，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最佳解娇妓。

image-20210402133435682

<pre mdtype="fences" cid="n27" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> private double fitness; // 適應(yīng)度
private double selectedRate; // 被選中的概率像鸡，歸一化處理
@Override
public int compareTo(Species o) {
if (getRouteLength() < o.getRouteLength()) {
return -1;
} else if (getRouteLength() == o.getRouteLength()) {
return 0;
} else {
return 1;
}
}</pre>

對個體的操作有可能會影響到適應(yīng)度，所以在關(guān)鍵操作之前必須更新適應(yīng)度哈恰。

由于距離越短只估，表現(xiàn)越好，那么適應(yīng)度就越高着绷，所以可以定義適應(yīng)度為距離的倒數(shù)蛔钙。

<pre mdtype="fences" cid="n34" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> /**

• 獲得適應(yīng)度
• @return 適應(yīng)度
  /
  public double getFitness() {
  updateFiness(); // 返回之前必須先更新（如果需要）
  return fitness;
  }
  /*
• 計算并設(shè)置適應(yīng)度
  */
  private void calculateAndSetFitness() {
  updateLength(); // 計算適應(yīng)度之前必須更新長度
  this.fitness = 1.0 / getRouteLength();
  }</pre>

后面用到輪盤賭，被選中的概率必須歸一化處理荠医。

<pre mdtype="fences" cid="n41" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> /**

• 設(shè)置被選中的概率吁脱，歸一化處理
• @param selectedRate 被選擇的概率桑涎，歸一化處理
  */
  public void setSelectedRate(double selectedRate) {
  this.selectedRate = selectedRate;
  }</pre>

后面用到變異，設(shè)計到一個逆轉(zhuǎn)給定區(qū)間兼贡，即1-2-3-4攻冷，逆轉(zhuǎn)2-3，就變成1-3-2-4遍希。為方便起見等曼，封裝成了一個方法。

<pre mdtype="fences" cid="n46" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> /**

• 逆轉(zhuǎn)給定區(qū)間
• @param left 左端點（包含）
• @param right 右端點（包含）
  */
  public void reverse(int left, int right) {
  // 逆轉(zhuǎn)
  while (left < right) {
  City c = routeList.get(left);
  routeList.set(left, routeList.get(right));
  routeList.set(right, c);
  ++left;
  --right;
  } </pre>

雜交和變異都是以一定概率進行的凿蒜，下面省略隨機數(shù)生成和比較的部分禁谦，只給出核心代碼，完整代碼參見第4部分废封。

隨機選擇一對父母州泊，隨機選擇一段基因。

直接把這一段父親的基因復(fù)制到孩子對應(yīng)的部分漂洋，孩子缺少的基因從母親那里拿遥皂，已經(jīng)重復(fù)的基因跳過。

image-20210402134106439

那么可以得到核心部分的代碼刽漂。

<pre mdtype="fences" cid="n59" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> // 直接把這一段父親的基因復(fù)制到孩子對應(yīng)的部分
for (int i = beginIndex; i < endIndex; ++i)
list.set(i, father.get(i));

// 孩子缺少的基因從母親那里拿
int i = 0;
// 從頭開始遍歷母親的基因
for (int j = 0; j < size; ++j) {
if (i == beginIndex)
i = endIndex; // 跳過父親那一段
City c = mother.get(j); // 獲取母親的基因
// 如果母親的基因已經(jīng)在孩子身上渴肉，就跳過，否則加入
if (!list.contains(c)) {
list.set(i, c);
i++;
}
}</pre>

在實現(xiàn)的過程中爽冕，需要保證父母不是同一個個體，需要保證隨機一段的序列左端點小于右端點……

得到了孩子的序列以后披蕉，構(gòu)造一個對象颈畸，加入到種群中。

變異對每一個個體都有概率没讲，以一定的概率變異

這里的處理有很多種方法眯娱，例如，隨機交換任意兩個城市的位置爬凑，又如徙缴，隨機逆序一段路徑，再如嘁信，隨機選擇若干個奇數(shù)位的城市重新隨機打亂以后按順序放回……

這里采用了隨機逆序一段路徑的方法于样。

事實上，也僅對收尾2個城市（4段路徑）影響較大潘靖。

image-20210402134139209

同樣穿剖，可以得到核心代碼。

<pre mdtype="fences" cid="n78" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> // 隨機選擇一段基因卦溢，逆序
int left = (int) (Math.random() * sp.size());
int right = (int) (Math.random() * sp.size());
if (left > right) {
int tmp = left;
left = right;
right = tmp;
}
sp.reverse(left, right);</pre>

物競天擇糊余，適者生存秀又。

所有表現(xiàn)不好的個體都應(yīng)該被淘汰。

考慮到表現(xiàn)越好贬芥，意味著路徑長度越短吐辙，那么容易想到的是，把種群中所有的個體拿出來看看蘸劈，按照路徑長度排個序昏苏，取最短的若干名，其他淘汰昵时。

由于個體Species已經(jīng)實現(xiàn)了Comparable接口捷雕，所以直接放進優(yōu)先級隊列PriorityQueue，然后一個個取出來壹甥，要么取到取完救巷，要么取到種群最大容量。

<pre mdtype="fences" cid="n87" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> // 直接把個體丟掉優(yōu)先級隊列中句柠，由于個體實現(xiàn)了Comparable接口浦译，所以距離短的方案表現(xiàn)好，優(yōu)先級高
PriorityQueue<Species> pq = new PriorityQueue<Species>();
pq.addAll(group);
// 清空種群溯职，然后按照個體的表現(xiàn)從好到差放到種群中
group.clear();
while (!pq.isEmpty()) { // 要么放完
group.add(pq.poll());
if (group.size() == capacity) // 要么超過了最大容量就不放了
break;</pre>

為方便起見精盅，我采用的是這樣的方法，并且實踐證明效果能夠接受谜酒。

其主要思想是叹俏，表現(xiàn)越好的個體越有可能活著（當(dāng)然也可能會被淘汰，只是概率太低了以至于可以認(rèn)為小概率事件不發(fā)生）僻族，而表現(xiàn)差的個體存活的可能性就小粘驰，極有可能被淘汰（當(dāng)然也可能活著）。

具體的做法是述么，隨機選擇一個概率蝌数，然后看是不是滿足這個個體被選中的概率，如果是度秘，那么就把這個個體放入到新的種群中顶伞，如果不是，就用歸一化的概率減去隨機概率剑梳，用新的概率檢查下一個個體唆貌。

所有個體檢查完，如果仍沒有放滿種群容量垢乙，就再次循環(huán)挠锥，再比較每一個個體，于是侨赡，表現(xiàn)較好的個體就可能會被放入新種群2次蓖租、3次甚至更多次粱侣，直到種群容量滿了。

事實上蓖宦，更常見的做法是輪盤賭齐婴。

下面給出核心部分代碼。

<pre mdtype="fences" cid="n104" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> double rate = Math.random() / 100.0;
Species oldPoint = origin.get(i);
while (oldPoint != null && !oldPoint.equals(best))
{
if (rate <= oldPoint.getSelectedRate()) {
group.add(oldPoint);
break;
} else {
rate = rate - oldPoint.getSelectedRate();
}
}</pre>

這樣有可能會走到兩個極端稠茂。

第一個極端柠偶，很有可能表現(xiàn)最好的個體被淘汰了。

盡管表現(xiàn)最好的個體存活的概率非常非常大睬关，但是如果不幸發(fā)生小概率事件诱担，把表現(xiàn)最好的個體淘汰了，那么就會丟失最優(yōu)解电爹。

當(dāng)循環(huán)次數(shù)足夠多的時候蔫仙，原來的表現(xiàn)第二的個體會在若干次的雜交和變異中變得越來越好，并進一步優(yōu)于原來表現(xiàn)最好的個體丐箩。

但是這樣明顯會使程序工作效率下降摇邦，并且，很可能若干次以后表現(xiàn)最好的個體再次被淘汰屎勘。

我們希望的是施籍，表現(xiàn)最好的那一個，或者那兩個概漱，以1的概率一定存活丑慎。

第二個極端，表現(xiàn)最好的個體存活概率很大瓤摧，后面的個體大多數(shù)都被淘汰了立哑，那么整個新種群就可能會出現(xiàn)90%甚至更多的都是來自最好的那一個或者那兩個個體，后面10%是第三姻灶、第五、第十表現(xiàn)好的個體诈茧。

這樣就會導(dǎo)致其實很多時候父親和母親都是一樣的产喉，或者說，就是自交而不是雜交敢会，會明顯地降低效率曾沈。

綜合上面這兩個極端，可以給出一種妥協(xié)的方案——表現(xiàn)最好的個體以1的概率一定存活鸥昏，但是塞俱，最多不能超過新種群的四分之一，剩下的部分按照標(biāo)準(zhǔn)輪盤賭的方案進行吏垮，但是當(dāng)輪盤賭了若干次以后還沒有填滿種群障涯，不再反復(fù)進行罐旗，而是直接用表現(xiàn)最差的個體補滿剩下的若干個位置。

這樣妥協(xié)的方案可以有效解決上面兩個極端唯蝶，且測試效果良好九秀。

<pre mdtype="fences" cid="n119" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> for (int i = 1; i <= talentNum; i++) {
group.add(best);// 復(fù)制物種至新表
if (oldPoint == null || oldPoint.equals(best))
group.add(origin.getLast());</pre>

由于從優(yōu)先級隊列取出的時候，每個個體只被取出一次粘我，所以不會出現(xiàn)上面說的第二個極端鼓蜒，且由于優(yōu)先級隊列出隊的順序保證了表現(xiàn)最好的個體一定會在新種群中，所以不會出現(xiàn)上面說的第一個極端征字。

這樣都弹，在每一次迭代中，表現(xiàn)最優(yōu)的個體只會越來越好匙姜，也就是說畅厢，最短路徑的長度只可能變短，不可能邊長搁料，最壞的情況就是不變或详。

只不過這樣其實就只是按照從好倒壞的順序保留存活，超過種群數(shù)量的就直接認(rèn)為是表現(xiàn)過差郭计，被淘汰霸琴。

事實上，在測試的過程中昭伸，種群數(shù)量在200的時候梧乘，表現(xiàn)第200的已經(jīng)足夠差了，所以這個種群包含了各種情況的樣本庐杨，可以認(rèn)為是完備了选调。所以超過200的，雖然更差灵份，但是同時也失去了意義仁堪，可以直接淘汰。

模擬退火算法

模擬退火算法(Simulated Annealing填渠，SA)最早的思想是由N. Metropolis [1] 等人于1953年提出弦聂。

模擬退火算法來源于固體退火原理，將固體加溫至充分高氛什，再讓其徐徐冷卻莺葫，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀枪眉，內(nèi)能增大捺檬，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)贸铜，最后在常溫時達(dá)到基態(tài)堡纬，內(nèi)能減為最小聂受。

模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解隐轩，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)饺饭。

模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法职车。

根據(jù)Metropolis準(zhǔn)則瘫俊，粒子在溫度T時趨于平衡的概率為e(-ΔE/(kT))。

其中E為溫度T時的內(nèi)能悴灵，ΔE為其改變量扛芽，k為Boltzmann常數(shù)。

用固體退火模擬組合優(yōu)化問題积瞒，將內(nèi)能E模擬為目標(biāo)函數(shù)值f川尖，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法茫孔。

<pre mdtype="fences" cid="n145" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> /**

• MetroPolis準(zhǔn)則
• @param bestRoute

•        最優(yōu)解
  

• @param currentRoute

•        當(dāng)前解
  

• @param currentTemperature

•        當(dāng)前溫度
  

• @return MetroPolis準(zhǔn)則的評估值
  */
  private static double metropolis(Route bestRoute, Route currentRoute, double currentTemperature) {
  double ret = Math.exp(-(currentRoute.getRouteLength() - bestRoute.getRouteLength()) / currentTemperature);
  return ret;
  }</pre>

當(dāng)溫度較高的時候叮喳，接受劣解的概率比較大，在初始高溫下缰贝，幾乎以100%的概率接受劣解馍悟。

隨著溫度的下降，接受劣解的概率逐漸減少剩晴。

直到當(dāng)溫度趨于0時锣咒，接受劣解的概率也同時趨于0。

這樣將有利于算法從局部最優(yōu)解中跳出赞弥，求得問題的全局最優(yōu)解毅整。

<pre mdtype="fences" cid="n154" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> /**

• 能夠接受劣解的概率
• @param currentTemperature

•        當(dāng)前溫度
  

• @return 能夠接受劣解的概率
  */
  private static double getProbabilityToAcceptWorseRoute(double currentTemperature) {
  return (currentTemperature - ConstantValue.CHILLING_TEMPERATURE)
  / (ConstantValue.INITIAL_TEMPERATURE - ConstantValue.CHILLING_TEMPERATURE);
  }</pre>

image-20210402134719314

<pre mdtype="fences" cid="n158" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> // 用shuffle隨機一條路徑作為初始解，并復(fù)制一份作為初始最優(yōu)解

while (ConstantValue.CHILLING_TEMPERATURE < currentTemperature) {
double p = getProbabilityToAcceptWorseRoute(currentTemperature);
for (int i = 0; i < ConstantValue.SIMULATE_ANNEA_ITERATION_TIMES; i++)
// 產(chǎn)生鄰域
if (neighbourRoute.getRouteLength() <= bestRoute.getRouteLength()) {
// 如果新解比當(dāng)前解優(yōu)绽左，接受
} else if (metropolis(bestRoute, neighbourRoute, currentTemperature) > p) {
// 否則按照Metropolis準(zhǔn)則確定接受的概率
}
}
// 按照給定的速率降溫
}</pre>

局部搜索

與模擬退火方法類似悼嫉，區(qū)別在于當(dāng)且僅當(dāng)新解比當(dāng)前解更優(yōu)的時候接受新解。

image-20210402134811363

<pre mdtype="fences" cid="n167" lang="java" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> while (successfullyChanged != 0 && changed != 0) {
Route neighbour = route.generateNeighbour();
if (neighbour.getRouteLength() <= route.getRouteLength()) {
route = neighbour;
successfullyChanged--;
}
changed--;
}</pre>

算法測試

正確性測試

考慮僅有4個城市的情況拼窥。

這4個城市分別位于(1,0)戏蔑、(2,0)、(1,1)闯团、(2,1)。

顯然只有2種走法仙粱，起路徑長度分別為4和4.828房交。

三種算法都能求得正確的最優(yōu)解。

<pre mdtype="fences" cid="n179" lang="" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> 遺傳算法：
City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] -> City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] ->
RouteLength = 4.0
局部搜索：
City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] -> City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] ->
RouteLength = 4.0
模擬退火算法：
City [index=4, x=2, y=1] -> City [index=2, x=2, y=0] -> City [index=1, x=1, y=0] -> City [index=3, x=1, y=1] ->
RouteLength = 4.0</pre>

大規(guī)模數(shù)據(jù)

下面給出10個城市的運行結(jié)果伐割。

image-20210402135214257

下面給出144個城市的運行結(jié)果候味。

image-20210402135224037

算法比較

首先給出10個城市的數(shù)據(jù)刃唤。

<pre mdtype="fences" cid="n208" lang="" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> 10
1 0 0
2 12 32
3 5 25
4 8 45
5 33 17
6 25 7
7 15 15
8 15 25
9 25 15
10 41 12</pre>

這組數(shù)據(jù)的真正最優(yōu)解是147.34。

下面嘗試使用遺傳算法運行這組數(shù)據(jù)白群，分別運行10次尚胞，取這10次結(jié)果的平均值和最小值胀葱。

這10次結(jié)果分別為：147.3408465677464贮匕、147.3408465677464、171.87473677989576憎夷、147.3408465677464粱玲、147.3408465677464躬柬、147.3408465677464、147.3408465677464抽减、162.19167266106012允青、147.3408465677464、147.3408465677464卵沉。

這10次結(jié)果的最小值是147.34颠锉，完全命中最優(yōu)解。

事實上史汗，有80%的概率命中了最優(yōu)解琼掠。

剩下的2次，一次是162淹办，一次是171眉枕，誤差較大。

但是從全局考慮怜森，10組數(shù)據(jù)的平均值是150.9速挑，也足夠接近最優(yōu)解了。

同樣副硅，使用局部搜索和模擬退火算法姥宝，對這組數(shù)據(jù)進行測試，得到了下面這張表格恐疲。

從這張表中可以看到腊满，在小數(shù)據(jù)規(guī)模的時候，模擬退火的算法準(zhǔn)確度是最低的培己。

這可能是由于模擬退火是接受劣解導(dǎo)致的碳蛋，所以在小數(shù)據(jù)規(guī)模上會出現(xiàn)不在最優(yōu)解的可能。

下面給出更大數(shù)據(jù)規(guī)模的測試省咨，并且下表僅列出各種算法在10次測試中出現(xiàn)的最小值肃弟。

可以看到身坐，數(shù)據(jù)規(guī)模較大的時候，三種算法都能夠比較接近最優(yōu)解芳绩。

但是由于數(shù)值變大掀亥，所以絕對誤差也隨之增加。如果計算相對誤差妥色，可以看到相對誤差仍舊處于一個很小的范圍搪花。

同時可以看到，模擬退火的準(zhǔn)確度高于了局部搜索嘹害，局部搜索在大數(shù)據(jù)下顯得誤差最大撮竿，這是由于局部搜索是最原始的，難以跳出局部最優(yōu)解笔呀，而模擬退火等算法能夠從局部最優(yōu)解中跳出幢踏。

采用與上面相同的方法，對三種算法進行測試许师，得到下表房蝉。

同樣的，每組數(shù)據(jù)微渠，分別對每種算法運行10次搭幻，取10次中運行時間最快的，單位為毫秒逞盆。

完整代碼

https://gitlab.jxtxzzw.com/jxtxzzw/tsp

https://github.com/jxtxzzw/tsp