旅行商問題（TSP）系列(2)

旅行商問題（TSP）系列(1)

續(xù)篇：繼續(xù)對例題的討論

第二問：模擬退火算法

(2) 在第一問的基礎(chǔ)上，求四條回路鉴扫，它們加起來能遍歷每一個節(jié)點，并且令這四條回路的總長度盡可能小澈缺。

第二問用數(shù)學(xué)語言來描述比較繁瑣涉波，字面含義已經(jīng)足夠清晰命满。它就是想要這種感覺的一個解：

Figure_4.png

我試著在上一問已經(jīng)寫好的模擬退火算法的基礎(chǔ)上做一些改動。

首先，將回路集合\{\Gamma_0 = v_{i_0} ... v_{i_{n_0}} v_{i_0}, \Gamma_1 = v_{j_0} ... v_{j_{n_1}} v_{j_0}, \Gamma_2 = v_{k_0} ... v_{k_{n_2}} v_{k_0}, \Gamma_3 = v_{l_0} ... v_{l_{n_3}} v_{l_0} \}表示為：x = [[i_0, ..., i_n_0], [j_0, ..., j_n_1], [k_0, ..., k_n_2], [l_0, ..., l_n_3]拦耐；將“x在附近鄰域隨機(jī)擾動”轩猩，設(shè)為令x中多個元素隨機(jī)交換位置（可以跨組別）曙旭，以及一定概率地令一些元素跳到另一個組別中去（會改變不同組別的頂點數(shù)）茧球，這樣x的取值范圍就覆蓋了整個解空間。（只要覆蓋了整個解空間枪狂，剩下的就交給上天安排了）

# 核心改動在于擾動函數(shù)
def get_next_x(x):
    x_next = deepcopy(x)
    # 多次交換
    for i in range(int(T / T_0 * 8 + 2)):
        # 任選兩點悉抵，交換
        g_1, g_2 = randint(0, num_group - 1), randint(0, num_group - 1)
        i_1, i_2 = randint(0, len(x_next[g_1]) - 1), randint(0, len(x_next[g_2]) - 1)
        x_next[g_1][i_1], x_next[g_2][i_2] = x_next[g_2][i_2], x_next[g_1][i_1]
    # 多次跳動
    for i in range(int(T / T_0 * 8) + 1):
        # 任選一點和一邊，將點移至該邊上摘完，
        g_1, g_2 = randint(0, num_group - 1), randint(0, num_group - 1)
        # 不能令某一組變空姥饰，邊需在另一組
        if len(x_next[g_1]) == 1 or g_1 == g_2:
            continue
        i_1, i_2 = randint(0, len(x_next[g_1]) - 1), randint(0, len(x_next[g_2]))
        x_next[g_2].insert(i_2, x_next[g_1][i_1])
        del x_next[g_1][i_1]
    return x_next

此外，像這種從一維加到二維時時孝治，還要注意淺拷貝和深拷貝的坑列粪，因為以前被坑過所以很怕。

完整代碼如下：

# q_2_1.py
# 模擬退火算法求解最短哈密頓回路
from basic import *
from random import randint, uniform, shuffle
from math import exp, log
from copy import deepcopy

num_group = 4

# 計算回路長度
def get_path_length(x):
    length = 0
    for path in x:
        for i in range(len(path) - 1):
            length += dist[path[i]][path[i + 1]]
        length += dist[len(path) - 1][0]
    return length

# 給予x一個隨機(jī)位移
def get_next_x(x):
    x_next = deepcopy(x)
    # 多次交換
    for i in range(int(T / T_0 * 8 + 2)):
        # 任選兩點谈飒，交換
        g_1, g_2 = randint(0, num_group - 1), randint(0, num_group - 1)
        i_1, i_2 = randint(0, len(x_next[g_1]) - 1), randint(0, len(x_next[g_2]) - 1)
        x_next[g_1][i_1], x_next[g_2][i_2] = x_next[g_2][i_2], x_next[g_1][i_1]
    # 多次跳動
    for i in range(int(T / T_0 * 8) + 1):
        # 任選一點和一邊岂座，將點移至該邊上，
        g_1, g_2 = randint(0, num_group - 1), randint(0, num_group - 1)
        # 不能令某一組變空杭措，邊需在另一組
        if len(x_next[g_1]) == 1 or g_1 == g_2:
            continue
        i_1, i_2 = randint(0, len(x_next[g_1]) - 1), randint(0, len(x_next[g_2]))
        x_next[g_2].insert(i_2, x_next[g_1][i_1])
        del x_next[g_1][i_1]
    return x_next

# 采納概率
# 自己瞎搗鼓出來的
def get_accpectable_probability(y, y_next, T):
    return exp(-T_0 / T * (y_next - y) / y)



# # 溫度初值
T_0 = 100000
T = T_0
# 溫度終止值
T_min = 25
# x: 回路
# 例: v_0-v_1-v_2-v_0: x = [0, 1, 2]
# x初值隨機(jī)
x_0 = list(range(num_pos))
shuffle(x_0)
x = [x_0[0: 7], x_0[7: 15], x_0[15: 22], x_0[22: 30]]
# y: 回路長度
y = get_path_length(x)
# 內(nèi)循環(huán)次數(shù)
k = 200
# 計數(shù)器
t = 0       

# 存儲求解過程
x_list = [x]
y_list = [y]

x_best = deepcopy(x)
y_best = get_path_length(x)

# 開始模擬退火
while T > T_min:
    # 內(nèi)循環(huán)
    for i in range(k):
        y = get_path_length(x)

        # 給予x隨機(jī)位移
        x_next = get_next_x(x)

        # 試探新解
        y_next = get_path_length(x_next)
        if y_next < y:
            # 更優(yōu)解费什，一定接受新解
            x = x_next
            # 更新最優(yōu)記錄
            if y_next < y_best:
                y_best = y_next
                x_best = deepcopy(x_next)
        else:
            # 更劣解，一定概率接受新解
            p = get_accpectable_probability(y, y_next, T)
            r = uniform(0, 1)
            if r < p:
                x = x_next

    # 做記錄
    x_list.append(x)
    y_list.append(y_next)

    t += 1
    if t % 1000 == 0:
        print(T)

    # 降溫
    T = T_0 / (1 + t) # 快速降溫
    # T = T_0 / log(1 + t) # 經(jīng)典降溫

for path in x_best:
    path += [path[0]]

# 輸出解
print('min length:', y_best)
print('path:', x_best)

plt.figure(1)
ax1 = plt.subplot(1, 2, 1)
ax2 = plt.subplot(1, 2, 2)

# 繪制連線圖
plt.sca(ax1)
for path in x_best:
    show_path(path)

# 繪制退火圖
plt.sca(ax2)
x = np.linspace(1, k * len(x_list), len(x_list))
y = np.linspace(1, len(x_list), len(x_list))
for i in range(len(x_list)):
    y[i] = y_list[i]
plt.plot(x, y)

plt.title('模擬退火進(jìn)程', fontproperties = 'SimHei')
plt.xlabel('遍歷次數(shù)', fontproperties = 'SimHei')
plt.ylabel('回路長度', fontproperties = 'SimHei')

plt.show()

多次運行手素，得到以下結(jié)果：

運行次數(shù) 運行時間 回路總長度
1 44.7s 447.0
2 43.5s 438.3
3 42.9s 503.0
4 43.4s 466.6
5 43.8s 515.8
6 44.1s 459.1
… … …

時間上可以接受鸳址，以下為一些解的形狀：

Figure_5_1.png
Figure_5_2.png
Figure_5_3.png

跑了大概二十次不到，得到的最優(yōu)解總長度為444.7泉懦，形狀如下：（v_{20} v_5 v_{20}回路的長度按邊長兩次算稿黍，單個點的回路長度記為零）

Figure_5_4.png

大體上，這個解勉強(qiáng)可以令人滿意（感覺最優(yōu)解應(yīng)該要把點7孤立崩哩，圖中沒有做到）巡球。但我們也發(fā)現(xiàn)一個問題言沐，就是MTSP問題中沒有其他條件加以限定的話，很容易往孤立點酣栈、孤立邊這種奇怪的方向發(fā)展险胰。換言之，這種問題通常缺乏現(xiàn)實意義矿筝。

第二問：遺傳算法[1]

為了找到更好看的解起便，我覺得嘗試用過都說好的遺傳算法。

遺傳算法（Genetic Algorithm, GA）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型跋涣，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法缨睡。

其主要特點是直接對結(jié)構(gòu)對象進(jìn)行操作鸟悴，不存在求導(dǎo)和函數(shù)連續(xù)性的限定陈辱；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法细诸，不需要確定的規(guī)則就能自動獲取和指導(dǎo)優(yōu)化的搜索空間沛贪，自適應(yīng)地調(diào)整搜索方向。

遺傳算法以一種群體中的所有個體為對象震贵，并利用隨機(jī)化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效搜索利赋。其中，選擇猩系、交叉和變異構(gòu)成了遺傳算法的遺傳操作媚送；參數(shù)編碼、初始群體的設(shè)定寇甸、適應(yīng)度函數(shù)的設(shè)計塘偎、遺傳操作設(shè)計、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容拿霉。

遺傳算法在我看來吟秩，是一個遠(yuǎn)比模擬退火復(fù)雜的算法，一個是因為它是一個種群（一群粒子）在同時隨機(jī)绽淘，而退火是一個粒子在隨機(jī)涵防。另一個是因為它的效果好壞很大程度上取決于建模的結(jié)構(gòu)（尤其是編碼規(guī)則）是否與其機(jī)理（交叉和變異）相吻合。相比之下沪铭，退火只要能取值范圍能覆蓋解空間就基本完事了（沒錯我就是過河拆橋）壮池。

在這道題中，我認(rèn)為最困難的地方就在于設(shè)定遺傳算法的編碼模式杀怠，使之能適應(yīng)交叉互換這一過程火窒。為了簡化思路，我決定讓每一組回路所包含的頂點數(shù)固定驮肉。顯然熏矿，這樣的處理比較差勁，這樣直接就ban掉了很大一部分解空間，但我一時半會兒也沒有好的辦法票编，只好先做著試試褪储。

設(shè)置染色體編碼和解讀規(guī)則

設(shè)染色體編碼gene = [i_0, i_1, i_2, ..., i_29]為一個長度為30的整數(shù)序列，再設(shè)一個長度為30的整數(shù)序列group_index = [g_0, g_1, g_2, ..., g_29]表示一個每個位置的屬于哪個組別慧域。

# 將整數(shù)基因序列轉(zhuǎn)換為回路列表
def get_path_list(gene):
    path_list = [[] for i in range(num_group)]
    for i in range(len(gene)):
        path_list[group_index[i]].append(gene[i])
    return path_list

令種群內(nèi)所有染色體共用同一個group_index來解讀鲤竹，這樣它們所表示的回路總長度便不會在微小的編碼距離內(nèi)發(fā)生巨大變化。

計算基因的適應(yīng)度

每個基因（個體）都會表現(xiàn)出對環(huán)境不同的適應(yīng)度昔榴，適應(yīng)度低的基因更容易被淘汰辛藻，適應(yīng)度高的基因更容易保留到下一代。在這里互订，適應(yīng)度可取4條回路的總長度length的倒數(shù)吱肌。

# 計算4條回路的總長度
def get_length(path_list):
    length = 0
    for path in path_list:
        for i in range(len(path) - 1):
            length += dist[path[i]][path[i + 1]]
        length += dist[path[-1]][path[0]]
    return length

# 獲取該基因的適應(yīng)度，適應(yīng)度越高越容易存活
def get_gene_fitness(gene):
    # 返回對應(yīng)4條回路的總長度的倒數(shù)
    path_list = get_path_list(gene)
    length = get_length(path_list)
    return 1 / length

自然選擇過程

自然選擇下仰禽，適應(yīng)度低的個體所占比例會下降氮墨，適應(yīng)度高的個體所占比例會上升（有些優(yōu)勢基因會重復(fù)出現(xiàn)），總種群數(shù)保持不變吐葵。

其中规揪，選擇方式為輪盤選擇，每個基因（個體）被選中的概率等同于其適應(yīng)度在適應(yīng)度總和中所占比例温峭。因此一般來說猛铅，優(yōu)勢個體和劣勢個體的概率差距并不大，需要很多代才能看出一個大致的進(jìn)化方向凤藏，這也因而保留了基因多樣性奸忽。

# 根據(jù)適應(yīng)度選擇，隨機(jī)淘汰低適應(yīng)度基因清笨，復(fù)制高適應(yīng)度基因
# 返回gene_lib_next
def selection(gene_lib, gene_lib_fitness):
    # 輪盤選擇月杉，根據(jù)適應(yīng)度分配被選中的概率
    sum_gene_lib_fitness = sum(gene_lib_fitness)
    gene_lib_next = []

    for i in range(len(gene_lib)):
        # 向新基因庫添加基因，種群總數(shù)不變
        r = uniform(0, sum_gene_lib_fitness)
        for i in range(len(gene_lib)):
            r -= gene_lib_fitness[i]
            if r <= 0:
                # 選中i基因抠艾，加入新基因庫
                gene_lib_next.append(gene_lib[i].copy())
                break

    return gene_lib_next

交叉互換

交叉互換是遺傳算法中獨一無二的部分苛萎。兩個基因（個體）通過交叉互換彼此的一部分的方式產(chǎn)生新的基因進(jìn)入后續(xù)的演化進(jìn)程。這個操作的效果需要從編碼上給予配合才能發(fā)揮100%的潛力检号，在當(dāng)前的這個編碼中其實效果等同于彼此隨機(jī)交換腌歉。

這一部分的核心思想（對不合法情況進(jìn)行修正）是從網(wǎng)上借鑒的[2]，我覺得非常巧妙齐苛。

# 對基因交叉互換后產(chǎn)生的不合法情況進(jìn)行修正
def gene_amend(gene, low, high):
    # 已知gene = gene_dad[0: low] + gene_mon[low: high] + gene_dad[high:]
    # 其中中段可能出現(xiàn)與前后段重復(fù)的基因翘盖，不符合約束條件
    # 保證中段不變，對前后段不合法情況進(jìn)行修復(fù)
    cross_gene = gene[low: high]
    raw_gene = gene[0: low] + gene[high:]
    # raw_gene中重復(fù)的下標(biāo)
    repeated_index = [
        i for i in range(len(raw_gene))
        if raw_gene[i] in cross_gene
        ]
    # 缺失的基因值
    missed_g = [
        g for g in range(1, 30)
        if g not in gene
        ]
    shuffle(missed_g)
    # 一一填補(bǔ)
    for j in range(len(missed_g)):
        raw_gene[repeated_index[j]] = missed_g[j]

    return raw_gene[0: low] + cross_gene + raw_gene[low:]


# 以gene_dad, gene_mom做染色體交叉凹蜂，返回得到的2個新子代基因
def gene_crossover(gene_dad, gene_mom):
    cut_1, cut_2 = randint(0, len(gene_dad) - 1), randint(0, len(gene_mom) - 1)
    if cut_1 > cut_2:
        cut_1, cut_2 = cut_2, cut_1
    # 交叉互換
    if cut_1 == cut_2:
        gene_son, gene_daughter = gene_dad.copy(), gene_mom.copy()
    else:
        gene_son = gene_dad[0: cut_1] + gene_mom[cut_1: cut_2] + gene_dad[cut_2:]
        gene_daughter = gene_dad[0: cut_1] + gene_mom[cut_1: cut_2] + gene_dad[cut_2:]
        # 修復(fù)不合法情況
        gene_son = gene_amend(gene_son, cut_1, cut_2)
        gene_daughter = gene_amend(gene_daughter, cut_1, cut_2)

    return gene_son, gene_daughter

突變

突變較交叉來說比較簡單馍驯，但是是基因多樣性的根本來源阁危。如果突變概率或突變能力設(shè)置過低，則演化一定時間后所有基因?qū)口呁踔料嗤保Ч麡O差狂打。

# 對gene做基因突變處理，返回突變得到的新基因
def mutation(gene):
    # 重復(fù)多次混弥，強(qiáng)化突變的影響力
    for j in range(i_mutation):
        # 基因突變觸發(fā)概率
        if uniform(0, 1) > p_mutation:
            return gene.copy()
        i_1, i_2 = randint(0, len(gene) - 1), randint(0, len(gene) - 1)
        # 突變：兩個點位位置互換
        gene_next = gene.copy()
        gene[i_1], gene[i_2] = gene[i_2], gene[i_1]

    return gene_next

繁衍得到子代

一一配對趴乡，得到子代，簡單粗暴蝗拿。

# 獲取該群體繁衍得到的子代
def get_offspring(gene_lib):
    half = int(len(gene_lib) / 2)
    gene_dad = gene_lib[0: half]
    gene_mom = gene_lib[half:]
    shuffle(gene_dad)
    offspring = []

    for j in range(half):
        # 交叉互換概率
        if uniform(0, 1) > p_crossover:
            gene_son, gene_daughter = gene_dad[j].copy(), gene_mom[j].copy()
        else:
            gene_son, gene_daughter = gene_crossover(gene_dad[j], gene_mom[j])
        offspring.append(gene_son)
        offspring.append(gene_daughter)

    return offspring

完整代碼

# q_3_1.py
# 模擬退火算法求解最短哈密頓回路
from basic import *
from random import randint, uniform, shuffle
from copy import deepcopy

'''
1. 隨機(jī)產(chǎn)生種群晾捏。
2. 根據(jù)策略判斷個體的適應(yīng)度，是否符合優(yōu)化準(zhǔn)則哀托，若符合惦辛，輸出最佳個體及其最優(yōu)解，結(jié)束萤捆。否則裙品，進(jìn)行下一步俗批。
3. 依據(jù)適應(yīng)度選擇父母俗或，適應(yīng)度高的個體被選中的概率高，適應(yīng)度低的個體被淘汰岁忘。
4. 用父母的染色體按照一定的方法進(jìn)行交叉辛慰，生成子代。
5. 對子代染色體進(jìn)行變異干像。
'''


# 將整數(shù)基因序列轉(zhuǎn)換為回路列表
def get_path_list(gene):
    path_list = [[] for i in range(num_group)]
    for i in range(len(gene)):
        path_list[group_index[i]].append(gene[i])
    return path_list


# 計算4條回路的總長度
def get_length(path_list):
    length = 0
    for path in path_list:
        for i in range(len(path) - 1):
            length += dist[path[i]][path[i + 1]]
        length += dist[path[-1]][path[0]]
    return length


# 獲取該基因的適應(yīng)度帅腌，適應(yīng)度越高越容易存活
def get_gene_fitness(gene):
    # 返回對應(yīng)4條回路的總長度的倒數(shù)
    path_list = get_path_list(gene)
    length = get_length(path_list)
    return 1 / length
    

# 根據(jù)適應(yīng)度選擇，隨機(jī)淘汰低適應(yīng)度基因麻汰，復(fù)制高適應(yīng)度基因
# 返回gene_lib_next
def selection(gene_lib, gene_lib_fitness):
    # 輪盤選擇速客，根據(jù)適應(yīng)度分配被選中的概率
    sum_gene_lib_fitness = sum(gene_lib_fitness)
    gene_lib_next = []

    for i in range(len(gene_lib)):
        # 向新基因庫添加基因，種群總數(shù)不變
        r = uniform(0, sum_gene_lib_fitness)
        for i in range(len(gene_lib)):
            r -= gene_lib_fitness[i]
            if r <= 0:
                # 選中i基因五鲫，加入新基因庫
                gene_lib_next.append(gene_lib[i].copy())
                break

    return gene_lib_next

# 對基因交叉互換后產(chǎn)生的不合法情況進(jìn)行修正
def gene_amend(gene, low, high):
    # 已知gene = gene_dad[0: low] + gene_mon[low: high] + gene_dad[high:]
    # 其中中段可能出現(xiàn)與前后段重復(fù)的基因溺职，不符合約束條件
    # 保證中段不變，對前后段不合法情況進(jìn)行修復(fù)
    cross_gene = gene[low: high]
    raw_gene = gene[0: low] + gene[high:]
    # raw_gene中重復(fù)的下標(biāo)
    repeated_index = [
        i for i in range(len(raw_gene))
        if raw_gene[i] in cross_gene
        ]
    # 缺失的基因值
    missed_g = [
        g for g in range(1, 30)
        if g not in gene
        ]
    shuffle(missed_g)
    # 一一填補(bǔ)
    for j in range(len(missed_g)):
        raw_gene[repeated_index[j]] = missed_g[j]

    return raw_gene[0: low] + cross_gene + raw_gene[low:]


# 以gene_dad, gene_mom做染色體交叉位喂，返回得到的2個新基因
def gene_crossover(gene_dad, gene_mom):
    cut_1, cut_2 = randint(0, len(gene_dad) - 1), randint(0, len(gene_mom) - 1)
    if cut_1 > cut_2:
        cut_1, cut_2 = cut_2, cut_1
    # 交叉互換
    if cut_1 == cut_2:
        gene_son, gene_daughter = gene_dad.copy(), gene_mom.copy()
    else:
        gene_son = gene_dad[0: cut_1] + gene_mom[cut_1: cut_2] + gene_dad[cut_2:]
        gene_daughter = gene_dad[0: cut_1] + gene_mom[cut_1: cut_2] + gene_dad[cut_2:]
        # 修復(fù)不合法情況
        gene_son = gene_amend(gene_son, cut_1, cut_2)
        gene_daughter = gene_amend(gene_daughter, cut_1, cut_2)

    return gene_son, gene_daughter


# 對gene做基因突變處理浪耘，返回突變得到的新基因
def mutation(gene):
    # 重復(fù)多次，強(qiáng)化突變的影響力
    for j in range(i_mutation):
        # 基因突變觸發(fā)概率
        if uniform(0, 1) > p_mutation:
            return gene.copy()
        i_1, i_2 = randint(0, len(gene) - 1), randint(0, len(gene) - 1)
        # 突變：兩個點位位置互換
        gene_next = gene.copy()
        gene[i_1], gene[i_2] = gene[i_2], gene[i_1]

    return gene_next

# 獲取該群體繁衍得到的子代
def get_offspring(gene_lib):
    half = int(len(gene_lib) / 2)
    gene_dad = gene_lib[0: half]
    gene_mom = gene_lib[half:]
    shuffle(gene_dad)
    offspring = []

    for j in range(half):
        # 交叉互換概率
        if uniform(0, 1) > p_crossover:
            gene_son, gene_daughter = gene_dad[j].copy(), gene_mom[j].copy()
        else:
            gene_son, gene_daughter = gene_crossover(gene_dad[j], gene_mom[j])
        offspring.append(gene_son)
        offspring.append(gene_daughter)

    return offspring



# 分組數(shù)量
num_group = 4

# 交叉互換觸發(fā)概率
p_crossover = 0.4
# 基因突變觸發(fā)概率
p_mutation = 0.1
# 基因突變的影響能力
i_mutation = 5
# 種群大小
population = 1000

# 初始化
# 基因庫（種群）
gene_lib = [list(range(0, num_pos)) for i in range(population)]
for gene in gene_lib:
    shuffle(gene)
# 基因解讀：各點所在組
group_index = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3]
shuffle(group_index)

# 遺傳迭代次數(shù)
iter_max = 1000

# 記錄歷史最優(yōu)
fitness_best = 0
gene_best = []


for iter_i in range(iter_max):  
    fitness_val = [get_gene_fitness(gene) for gene in gene_lib]

    # 記錄最優(yōu)解
    fitness_max = max(fitness_val)
    best_index = fitness_val.index(fitness_max)
    if fitness_max > fitness_best:
        fitness_best = fitness_max
        gene_best = gene_lib[best_index]
    # 輸出信息
    if iter_i % 50 == 0:
        print(min(fitness_val), max(fitness_val))

    # 自然選擇
    gene_lib_next = selection(gene_lib, fitness_val)

    # 交叉互換塑崖，產(chǎn)生后代
    offspring = get_offspring(gene_lib_next)
    offspring = deepcopy(gene_lib_next)

    # 基因突變
    offspring = [mutation(gene) for gene in offspring]
    gene_lib = offspring.copy()

# 輸出結(jié)果
path_list = get_path_list(gene_best)
length = get_length(path_list)
print('min length:', length)
print('path', path_list)
可視化
for path in path_list:
    path += [path[0]]
    show_path(path)
plt.show()

運行結(jié)果

運行次數(shù) 運行時間 回路總長度
1 80.2s 578.8
2 78.1s 664.0
3 79.8s 563.8
4 79.6s 528.4
5 78.3s 620.92
… … …

結(jié)果非常令人失望七冲，部分解如下：

Figure_6_1.png
Figure_6_2.png
Figure_6_3.png

可以看出，與模擬退火中縮環(huán)為點的情況有著質(zhì)的差別规婆，最小長度的差距穩(wěn)定在100以上澜躺。這相當(dāng)于給（在這種編碼下的）遺傳算法判了死刑蝉稳。

檢討：為什么不如人

明明是希望遺傳算法能憑借著更復(fù)雜的規(guī)則，更多的搜索粒子（基因群）掘鄙，來對模擬退火的結(jié)果進(jìn)行更上一層樓的優(yōu)化颠区，然而效果卻十分讓人失望，這是為什么呢通铲？

主要原因有二：

一是毕莱，把每個回路所包含的點數(shù)寫死了， 而且與模擬退火所呈現(xiàn)的最優(yōu)解方向大相徑庭颅夺，因此最優(yōu)解和較優(yōu)解根本就不在搜索范圍之內(nèi)朋截。這是編碼規(guī)則一開始就決定的。

二是：交叉互換的算法在這個編碼規(guī)則下吧黄，效果完全等同于不同組間的隨機(jī)點位互換部服，并沒有發(fā)揮出“交叉互換”真正的優(yōu)勢。在該算法中拗慨，交叉互換是不同組間隨機(jī)點位互換廓八，突變是同組內(nèi)隨機(jī)點位互換，它們加起來才跟模擬退火中的隨機(jī)互換等效赵抢。然而遺傳算法又做不到模擬退火中的跨組跳動剧蹂，不能該邊每一組的包含點數(shù)，因而只會表現(xiàn)得更差而不是更好烦却。

當(dāng)然宠叼，這不是說遺傳算法很差勁，而只是我的這個編碼很差勁其爵。這也體現(xiàn)了遺傳算法中編碼的重要性冒冬。

待續(xù)

參考資料

  1. 超詳細(xì)的遺傳算法(Genetic Algorithm)解析 番茄雞蛋炒飯被搶注啦 http://www.reibang.com/p/ae5157c26af9 ?

  2. 遺傳算法——解決M-TSP多旅行商問題（基于python基本實現(xiàn)） 一只黍離 https://blog.csdn.net/weixin_42201701/article/details/103746595 ?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市摩渺，隨后出現(xiàn)的幾起案子简烤，更是在濱河造成了極大的恐慌，老刑警劉巖摇幻，帶你破解...
    沈念sama閱讀 217,734評論 6贊 505
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件横侦，死亡現(xiàn)場離奇詭異，居然都是意外死亡囚企，警方通過查閱死者的電腦和手機(jī)丈咐，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,931評論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來龙宏，“玉大人棵逊，你說我怎么就攤上這事∫铮” “怎么了辆影？”我有些...
    開封第一講書人閱讀 164,133評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵徒像，是天一觀的道長。 經(jīng)常有香客問我蛙讥，道長锯蛀，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,532評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任次慢，我火速辦了婚禮旁涤，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘迫像。我一直安慰自己劈愚，他們只是感情好，可當(dāng)我...
    茶點故事閱讀 67,585評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布闻妓。 她就那樣靜靜地躺著菌羽，像睡著了一般。 火紅的嫁衣襯著肌膚如雪由缆。 梳的紋絲不亂的頭發(fā)上注祖，一...
    開封第一講書人閱讀 51,462評論 1贊 302
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音均唉，去河邊找鬼是晨。 笑死，一個胖子當(dāng)著我的面吹牛浸卦，可吹牛的內(nèi)容都是我干的署鸡。 我是一名探鬼主播案糙，決...
    沈念sama閱讀 40,262評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼限嫌，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了时捌？” 一聲冷哼從身側(cè)響起怒医，我...
    開封第一講書人閱讀 39,153評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎奢讨，沒想到半個月后稚叹，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,587評論 1贊 314
  • ?護(hù)林員之死
    正文 獨居荒郊野嶺守林人離奇死亡拿诸，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,792評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年扒袖，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片亩码。...
    茶點故事閱讀 39,919評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡季率，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出描沟，到底是詐尸還是另有隱情飒泻，我是刑警寧澤鞭光，帶...
    沈念sama閱讀 35,635評論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站泞遗，受9級特大地震影響惰许，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜史辙，卻給世界環(huán)境...
    茶點故事閱讀 41,237評論 3贊 329
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一汹买、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧聊倔，春花似錦卦睹、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,855評論 0贊 22
  • 一樁弒父案结序，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至纵潦，卻和暖如春徐鹤，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背邀层。 一陣腳步聲響...
    開封第一講書人閱讀 32,983評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工返敬， 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人寥院。 一個月前我還...
    沈念sama閱讀 48,048評論 3贊 370
  • 代替公主和親
    正文 我出身青樓劲赠，卻偏偏與公主長得像，于是被迫代替她去往敵國和親秸谢。 傳聞我的和親對象是個殘疾皇子凛澎，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,864評論 2贊 354