這篇文章主要敘述我用基因遺傳演算法解旅行推銷員問題，用的語言是Python。
這邊會一步一步帶過程式碼，之後也會上傳到Github。
演算法參考：https://towardsdatascience.com/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35
我大概看過上面的文章就開始動手寫了，在Crossover的地方會比較類似。其餘Code的實現跟一些調整應該還是讓這篇文章滿值得一看的。
先上成果圖：

文章架構為：

• 略述基因遺傳演算法
• 略述旅行推銷員問題
• 基因遺傳演算法在送貨員問題的實現
• 程式碼解說 ＋ 視覺化
• 結語

一、基因遺傳演算法

1. 核心概念：既然名為基因遺傳演算法，核心概念就是先隨機生成一個群體，然後從其中選出基因最為優良的個體。接著讓這些個體去繁衍，產生他們的子代，不斷重複這樣的動作以確保最優良的基因能一直傳承下去。
2. 重要名詞定義：
   • 種群數量：一個群體裡個體的數量
   • 染色體長度：顧名思義，就是基因的長度，某方面可以反映基因的複雜度
   • 菁英個體：一個群體裡被評估為菁英的個體可以進行繁衍或直接進入到下一個子代
   • 繁衍(crossover)：兩個個體產生基因和他們有共同點的子代的過程
   • 突變(mutation)：突變也是演化當中很重要的一環，透過隨機替換染色體我們有可能得到更好的子代
   • 進化次數：子代的代數
     注意：這邊名詞定義可能不完全精準，但表達的概念是通用的

二、旅行推銷員問題

1. 問題： 給定數個城市和各個城市在地圖上的座標，求解從某一城市出發，經過所有其餘城市恰一次後回到原城市所花費的最短距離及路徑。
2. 難度： 可以大概想一下，如果有五座城市，可能的路徑就有5!也就是120種，感覺不多。但是到十座城市，可能的路徑就有10!也就是3,628,800種。二十座城市就有20!也就是121,645,100,408,832,000種。而目前這個問題是NP-Hard，也就是說目前並不存在一個可在polynomial time解出此問題的演算法，因此便出現了各種近似演算法希望能求解這個問題。

三、基因遺傳演算法在送貨員問題的實現

1. 重新定義名詞：我們可以把一個又一個可行的路徑想成是一個“個體”，而這些路徑所經過的城市就是他的染色體。那麼我們原本的名詞定義就有了新的詮釋：
   • 種群數量：一個群體（可行路徑們）裡個體（可行路徑）的數量
   • 染色體長度：個體（可行路徑）所經過的城市的數量
   • 菁英個體：群體（可行路徑們）中較短的那些路徑
   • 繁衍(crossover)：兩個個體（可行路徑）產生染色體（城市）和他們有共同點的子代（可行路徑）的過程
   • 突變(mutation)：突變也是演化當中很重要的一環，透過隨機替換染色體（城市）我們有可能得到更好的子代（可行路徑）
   • 進化次數：子代的代數
2. 如何實現：因此我們要做的步驟如下
   A. 產生一堆隨機的可行路徑
   B. 從中挑出較短的路徑進行繁衍
   C. 一定比率進行突變
   D. 新的路徑們誕生（子代路徑們 + 突變路徑們）
   然後重覆B ~ D的次數取決於我們的進化次數

四、用Python實現

1. 首先 import 一些我們會用到的模組

import random as rd
import copy
from matplotlib import pyplot as plt

• random 是因為在挑選子代跟染色體的時候隨機性是很重要的
• copy 是因為python裡面有些類似pass by reference的行為，用copy可以避免一些問題
• matplotlib 純粹是為了最後視覺化需要

2. 定義兩個重要的Class

class Location:
    def __init__(self, name, x, y):
        self.name = name
        self.loc = (x, y)

    def distance_between(self, location2):
        assert isinstance(location2, Location)
        return ((self.loc[0] - location2.loc[0]) ** 2 + (self.loc[1] - location2.loc[1]) ** 2) ** (1 / 2)

這邊Location指的就是城市。

• name是城市的名稱，用於我們最後輸出路徑的時候知道到底經過了哪些路徑
• loc就是城市的xy座標（這邊我們就當成整個地圖是xy平面）
• distance_between 用於計算兩個Location（城市)物件之間的距離

class Route:
    def __init__(self, path):
        # path is a list of Location obj
        self.path = path
        self.length = self._set_length()

    def _set_length(self):
        total_length = 0
        path_copy = self.path[:]
        from_here = path_copy.pop(0)
        init_node = copy.deepcopy(from_here)
        while path_copy:
            to_there = path_copy.pop(0)
            total_length += to_there.distance_between(from_here)
            from_here = copy.deepcopy(to_there)
        total_length += from_here.distance_between(init_node)
        return total_length

這邊Route指的就是路徑。

• path 是一個list 裡面裝著一個個Location物件
• length 是這條路徑的長度
• _set_length 只是透過path來計算路徑長度的函式
  Note: 這邊有用到一些像是self.path[:]或是copy等等，是因為python裡面的list是mutable，這樣做可以避免我們在計算路徑的過程中不小心pop到self.path

到這邊我們的染色體（城市）和個體（路徑）就定義完成了。
3. 定義GeneticAlgo
注意：這點的function都是定義在GeneticAlgo這個class底下的
Step1. 初始化重要參數：

class GeneticAlgo:
    def __init__(self, locs, level=10, populations=100, variant=3, mutate_percent=0.01, elite_save_percent=0.1):
        self.locs = locs
        self.level = level
        self.variant = variant
        self.populations = populations
        self.mutates = int(populations * mutate_percent)
        self.elite = int(populations * elite_save_percent)

• locs 要走的城市有哪些（注意locs是一個list裡面裝著Location物件）
• level 子代的代數（進化次數）
• population 指的就是由幾個不同路徑組成一個群體
• variant 這個後面會詳細解釋，現在先把它當成父母代跟子代的變異度
• mutate_percent 是說一個群體當中有多少比例是突變來的
• elite_save_percent 是說在一群路徑當中，最短的幾％路徑被視為精英路徑（這邊是0.1=10%）

Step2. 建立第一代的路徑群體

    def _find_path(self):
        # locs is a list containing all the Location obj
        locs_copy = self.locs[:]
        path = []
        while locs_copy:
            to_there = locs_copy.pop(locs_copy.index(rd.choice(locs_copy)))
            path.append(to_there)
        return path

    def _init_routes(self):
        routes = []
        for _ in range(self.populations):
            path = self._find_path()
            routes.append(Route(path))
        return routes

這邊我們需要兩個function:

• _find_path(self):
  負責從self.locs(要走的城市)當中隨機生成可行的路徑（每個都要走到），然後回傳這個路徑回來
  注意: 這個回傳的path 也是一個list裡面裝著Location物件
• _init_routes(self):
  那這個function就會負責呼叫_find_path來取得路徑，再用這個路徑來生成Route物件。生成的次數就取 決於self.populations(群體的數量)是多少囉。
  到這邊先整理一下資料型別，確保我們進度一致:
• Location: 一個class，表示城市
• Route: 一個class，表示個體（路徑）
• Route.path: 一個list，裡面裝著許多Location物件
• path: 一個list，裡面裝著許多Location物件
• routes: 一個list（群體），裡面裝著許多的Route物件
  所以這邊就把routes想成是群體（可行路徑們），其中有許多的個體（可行路徑）

Step3. 產生下一代

    def _get_next_route(self, routes):
        routes.sort(key=lambda x: x.length, reverse=False)
        elites = routes[:self.elite][:]
        crossovers = self._crossover(elites)
        return crossovers[:] + elites

    def _crossover(self, elites):
        # Route is a class type
        normal_breeds = []
        mutate_ones = []
        for _ in range(self.populations - self.mutates):
            father, mother = rd.choices(elites[:4], k=2)
            index_start = rd.randrange(0, len(father.path) - self.variant - 1)
            # list of Location obj
            father_gene = father.path[index_start: index_start + self.variant]
            father_gene_names = [loc.name for loc in father_gene]
            mother_gene = [gene for gene in mother.path if gene.name not in father_gene_names]
            mother_gene_cut = rd.randrange(1, len(mother_gene))
            # create new route path
            next_route_path = mother_gene[:mother_gene_cut] + father_gene + mother_gene[mother_gene_cut:]
            next_route = Route(next_route_path)
            # add Route obj to normal_breeds
            normal_breeds.append(next_route)

            # for mutate purpose
            copy_father = copy.deepcopy(father)
            idx = range(len(copy_father.path))
            gene1, gene2 = rd.sample(idx, 2)
            copy_father.path[gene1], copy_father.path[gene2] = copy_father.path[gene2], copy_father.path[gene1]
            mutate_ones.append(copy_father)
        mutate_breeds = rd.choices(mutate_ones, k=self.mutates)
        return normal_breeds + mutate_breeds

這邊也是兩個function:

• _get_next_route(self, routes):
  這個函式會把一個群體（路徑們）按照他們的路徑長度做排序。(line 1)
  接著取出前面幾％的路徑做為菁英群體。(line 2)
  接著呼叫_crossover來取得繁衍後的子代。(line 3)
  最後生成新的子代。(line 4)
  注意：我們這邊為確保有更多好的基因流傳下去，我們直接讓菁英群體保送到下一代

• _crossover(self, elites, total_count, mutate_count):
  在談這個函式之前我們先來談談我們是如何讓兩個路徑「繁衍」出子代的。
  拿兩條路徑做例子：
  ㄅ路徑：A -> B -> D -> C -> E -> G -> F
  ㄆ路徑：C -> B -> A -> D -> E -> F -> G
  步驟1. 隨機取出ㄅ路徑中的一小截基因(基因的長度取決於self.variant)，例如 BDC
  步驟2. 移除ㄆ路徑中的BDC，得到ㄇ路徑：A -> E -> F -> G
  步驟3. 把BDC隨機放入ㄇ路徑當中，得到新路徑：A -> E -> B -> D -> C -> F -> G

  其實這麼做背後的原因很直覺，既然ㄅ路徑作為菁英路徑（較短的路徑們之一），那他之中勢必有一小段路徑或 是好幾小段的路徑是值得我們繼續使用的，因此我們希望這樣擷取這些小段的路徑作為子代的一部份可以幫助我 們產生路徑更短的子代。
  注意：這麼做的原因還有：按照問題要求，我們必須經過每個要求的城市，因此每個路徑所經過的城市數量都 要相同
  接著談談程式碼：

            father, mother = rd.choices(elites[:4], k=2)
            index_start = rd.randrange(0, len(father.path) - self.variant - 1)
            # list of Location obj
            father_gene = father.path[index_start: index_start + self.variant]
            father_gene_names = [loc.name for loc in father_gene]
            mother_gene = [gene for gene in mother.path if gene.name not in father_gene_names]
            mother_gene_cut = rd.randrange(1, len(mother_gene))
            # create new route path
            next_route_path = mother_gene[:mother_gene_cut] + father_gene + mother_gene[mother_gene_cut:]
            next_route = Route(next_route_path)

這段程式碼當中第1行我們從菁英路徑們當中的前四名隨機取出兩個作為父和母。
第2~4行我們隨機擷取父親染色體的一部分。
第6~8行我們移除母親染色體當中含有父親那小節染色體的部分，同時決定要從哪裡放入父親那小節染色體。
接著next_route_path就是子代路徑
然後我們用子代路徑建立Route物件。

再來是突變

            # for mutate purpose
            copy_father = copy.deepcopy(father)
            idx = range(len(copy_father.path))
            gene1, gene2 = rd.sample(idx, 2)
            copy_father.path[gene1], copy_father.path[gene2] = copy_father.path[gene2], copy_father.path[gene1]
            mutate_ones.append(copy_father)
        mutate_breeds = rd.choices(mutate_ones, k=self.mutates)

在第五行中我們隨機調換父路徑當中的兩座城市作為突變，加到mutate_ones裡頭。
最後一行是因為我們最後只要self.mutates這麼多個突變個數

Step4. 進化

     def evolution(self):
        routes = self._init_routes()
        for _ in range(self.level):
            routes = self._get_next_route(routes)
        routes.sort(key=lambda x: x.length)
        return routes[0].path, routes[0].length

這段程式碼就是我們的演化流程。
初始化群體 -> 繁衍新群體(重複self.level次（子代代數）) -> 得到最後的群體

Step5. 執行程式
在執行以前我們必須先生成一堆隨機的城市地點。

def create_locations():
    locations = []
    xs = [8, 50, 18, 35, 90, 40, 84, 74, 34, 40, 60, 74]
    ys = [3, 62, 0, 25, 89, 71, 7, 29, 45, 65, 69, 47]
    cities = ['Z', 'P', 'A', 'K', 'O', 'Y', 'N', 'X', 'G', 'Q', 'S', 'J']
    for x, y, name in zip(xs, ys, cities):
        locations.append(Location(name, x, y))
    return locations, xs, ys, cities

這部分我用random生成了，xs是x座標，ys是y座標，cities是城市名稱。
然後就是本體

if __name__ == '__main__':
    my_locs, xs, ys, cities = create_locations()
    my_algo = GeneticAlgo(my_locs, level=40, populations=150, variant=2, mutate_percent=0.02, elite_save_percent=0.15)
    best_route, best_route_length = my_algo.evolution()
    best_route.append(best_route[0])
    print([loc.name for loc in best_route], best_route_length)
    print([(loc.loc[0], loc.loc[1]) for loc in best_route], best_route_length)

這部分也不難理解，就是隨機生成城市後，讓GeneticAlgo去演化我們的可行路徑。
要注意的是因為ＴＳＰ要求起點終點要一樣所以我們補上終點。
以下部分可以視覺化最終結果：

    fig, ax = plt.subplots()
    ax.plot([loc.loc[0] for loc in best_route], [loc.loc[1] for loc in best_route], 'red', linestyle='-', marker='')
    ax.scatter(xs, ys)
    for i, txt in enumerate(cities):
        ax.annotate(txt, (xs[i], ys[i]))
    plt.show()

五、結語

其實這樣的演算法並不一定能達到最佳解，只是能在相對較短的時間內得到一個還不錯的解這樣。程式碼已經上傳到我的Github:https://github.com/blue0107/Genetic-Algorithm-for-TSP
有任何問題歡迎留言或寄信到我的信箱：b05703129@ntu.edu.tw
祝各位有美好的一天！