怎么用Python遺傳算法解決旅行商問(wèn)題

這篇文章主要講解了“怎么用Python遺傳算法解決旅行商問(wèn)題”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“怎么用Python遺傳算法解決旅行商問(wèn)題”吧！

TSP問(wèn)題

那么這個(gè)問(wèn)題的其實(shí)簡(jiǎn)單，是這樣子的：

在我們的N維平面是，咱們今天的話是拿這個(gè)二維平面來(lái)的，在這個(gè)平面上有很多個(gè)城市，城市之間是彼此聯(lián)通的，我們現(xiàn)在要找出一條最短的路徑可以將全部城市都走完。例如我們有城市A，B，C，D，E?，F(xiàn)在知道了城市間的坐標(biāo)，也就是相當(dāng)于知道了城市之間的距離，那么現(xiàn)在找到一個(gè)順序，能夠使得走完A，B，C，D，E所有城市的路徑和最短。比如計(jì)算完之后可能是B－－＞Ａ－－＞Ｃ－－＞Ｅ－－＞Ｄ。換一句話說(shuō)找到這個(gè)順序。

枚舉

首先要解決這個(gè)問(wèn)題的話，其實(shí)方案有很多，說(shuō)變白了，咱們就是要找到一個(gè)順序，能夠讓路徑之和最小，那么最容易想到的自然就是枚舉，例如讓?zhuān)料茸呷缓罂淳嚯xＡ最近的假設(shè)是Ｂ，那么就走Ｂ，然后從Ｂ走。當(dāng)然這個(gè)是局部貪心策略，很容易走到局部最優(yōu)，那么這個(gè)時(shí)候我們可以考慮ＤＰ，也就是說(shuō)依然假設(shè)從Ａ開(kāi)始，然后確保2個(gè)城市最短，3個(gè)城市最短，4個(gè)5個(gè)。最后在假設(shè)從B開(kāi)始同理?；蛘咧苯?枚舉全部情況，計(jì)算距離。但是無(wú)論如何，隨著城市數(shù)量的上升，他們的復(fù)雜度都會(huì)增加，所以這個(gè)時(shí)候我們就要想辦法讓計(jì)算能不能發(fā)揮一下咱們?nèi)祟?lèi)的專(zhuān)長(zhǎng)了。我稱(chēng)之為“瞎蒙”。

智能算法

現(xiàn)在我們來(lái)聊聊這個(gè)智能算法，以及為什么要用著玩意，剛剛咱們說(shuō)了前面的方案對(duì)于大量的數(shù)據(jù)計(jì)算量會(huì)很大，也不見(jiàn)得編寫(xiě)簡(jiǎn)單。那么這個(gè)時(shí)候，首先單單對(duì)于TSP問(wèn)題來(lái)說(shuō)，我們要的就是一個(gè)序列，一個(gè)不會(huì)重復(fù)的序列。那么這個(gè)時(shí)候，有什么一個(gè)更加簡(jiǎn)便的方案，而且在數(shù)據(jù)足夠大的情況下，我們也不見(jiàn)得需要一個(gè)完全精準(zhǔn)，完全最小的解，只要接近就好。那么這個(gè)時(shí)候，采用傳統(tǒng)的那些算法的話，一就是一，他只會(huì)按照我們的規(guī)則去計(jì)算，而且我們也確實(shí)不知道標(biāo)準(zhǔn)答案是什么，對(duì)傳統(tǒng)算法也比較難去設(shè)定一個(gè)閾值去停止運(yùn)算。但是對(duì)我們?nèi)藖?lái)說(shuō)，有一種東西叫做“運(yùn)氣”，有的人運(yùn)氣賊好，可能一發(fā)入魂，一下子就懵出了答案。那么我們的智能算法其實(shí)就是有點(diǎn)類(lèi)似于“蒙”。但是人家蒙是講究技巧的，例如經(jīng)驗(yàn)告訴我們，三長(zhǎng)一短選最短，通過(guò)這個(gè)技巧可以去蒙一下答案，或者找男盆友的時(shí)候像博主一樣帥氣的男孩紙，只要一張40系（30也可以）顯卡就可以輕松帶走一樣。蒙是要技巧的，我們管這個(gè)叫做策略。

策略

那么我們剛剛說(shuō)的這個(gè)技巧，這個(gè)蒙的技巧。在智能算法里面，這個(gè)蒙，就是我們的一種策略。我們要怎么去蒙才能夠讓我們的解更加合理。那么這個(gè)時(shí)候，就開(kāi)始百花齊放了，這里我就不念經(jīng)了，我們拿最金典的兩個(gè)算法為例子，一個(gè)是遺傳算法，一個(gè)是粒子群算法（PSO）。為例子，他們就是采用了一種策略去蒙，例如遺傳算法，通過(guò)模擬物競(jìng)天擇，一開(kāi)始先隨機(jī)蒙出一堆解，一堆序列，然后按照咱們的這個(gè)物競(jìng)天擇的策略出篩選這些解，然后通過(guò)這些解再去蒙出新的更好的解。如此往復(fù)，之后蒙出不錯(cuò)的解。粒子群也是類(lèi)似的，這些部分咱們用的時(shí)候再詳細(xì)說(shuō)明。

算法

現(xiàn)在咱們已經(jīng)知道了這個(gè)策略，那么算法是啥，其實(shí)就是實(shí)現(xiàn)這些策略的步驟啊，就是咱們的代碼，咱們的循環(huán)，數(shù)據(jù)結(jié)構(gòu)。我們要去實(shí)現(xiàn)剛剛說(shuō)的例如物競(jìng)天擇，例如咱們TSP，如何隨機(jī)生成一堆解。

數(shù)據(jù)樣例

ok,到這里咱們已經(jīng)說(shuō)完了，基本的一些概念，那么這個(gè)時(shí)候的話，咱們來(lái)看看咱們?nèi)绾伪硎具@個(gè)TSP的問(wèn)題，這個(gè)其實(shí)很簡(jiǎn)單，咱們這邊的話就簡(jiǎn)單的準(zhǔn)備一個(gè)測(cè)試數(shù)據(jù)，我們這里假設(shè)有14個(gè)城市，那么我們的這些城市的數(shù)據(jù)如下：

    data = np.array([16.47, 96.10, 16.47, 94.44, 20.09, 92.54,
                     22.39, 93.37, 25.23, 97.24, 22.00, 96.05, 20.47, 97.02,
                     17.20, 96.29, 16.30, 97.38, 14.05, 98.12, 16.53, 97.38,
                     21.52, 95.59, 19.41, 97.13, 20.09, 92.55]).reshape((14, 2))

我們后面都用這組數(shù)據(jù)進(jìn)行測(cè)試，現(xiàn)在在上面已經(jīng)有了14個(gè)城市。

那么接下來(lái)我們開(kāi)始我們的解決方案

遺傳算法

ok,那么我們來(lái)說(shuō)一說(shuō)咱們的這個(gè)遺傳算法是怎么一回事，之后的話，咱們用這個(gè)來(lái)解決這個(gè)TSP問(wèn)題。

那么現(xiàn)在的話，我們來(lái)看看我們的遺傳算法是怎么蒙的。

算法流程

遺傳算法其實(shí)是在用計(jì)算機(jī)模擬我們的物種進(jìn)化。其實(shí)更加通俗的說(shuō)法是篩選，這個(gè)就和我們?cè)蠣敔敺N植水稻一樣。有些個(gè)體發(fā)育良好，有些個(gè)體發(fā)育不好，那么我就先篩選出發(fā)育好的，然后讓他們?nèi)シ毖芎蟠缓笤俸Y選，最后得到高產(chǎn)水稻。其實(shí)也和我們社會(huì)一樣，不努力就木有女朋友就不能保留自己的基因，然后剩下的人就是那些優(yōu)秀的人和富二代的基因，這就是現(xiàn)實(shí)呀。所以得好好學(xué)習(xí)，天天向上！

那么回到主題，我們的遺傳算法就是在模擬這一個(gè)過(guò)程，模擬一個(gè)物競(jìng)天擇的過(guò)程。

所以在我們的算法里面也是分為幾大塊

繁殖

首先我們的種群需要先繁殖。這樣才能不斷產(chǎn)生優(yōu)良基于，那么對(duì)應(yīng)我們的算法，假設(shè)我們需要求取

Y = np.sin(10 * x) * x + np.cos(2 * x) * x

的最大值（在一個(gè)范圍內(nèi)）那么我們的個(gè)體就是一組（X1）的解。好的個(gè)體就會(huì)被保留，不好的就會(huì)被pass，選擇標(biāo)準(zhǔn)就是我們的函數(shù) Y 。那么問(wèn)題來(lái)了如何模擬這個(gè)過(guò)程？我們都知道在繁殖后代的時(shí)候我們是通過(guò)DNA來(lái)保留我們的基因信息，在這個(gè)過(guò)程當(dāng)中，父母的DNA交互，并且在這個(gè)過(guò)程當(dāng)中會(huì)產(chǎn)生變異，這樣一來(lái)，父母雙方的優(yōu)秀基于會(huì)被保存，并且產(chǎn)生的變異有可能誕生更加優(yōu)秀的后代。

所以接下來(lái)我們需要模擬我們的ＤＮＡ，進(jìn)行交叉和變異。

交叉

這個(gè)交叉過(guò)程和我們的生物其實(shí)很像，當(dāng)然我們?cè)谖覀兊挠?jì)算機(jī)里面對(duì)于數(shù)字我們可以將其轉(zhuǎn)化為二進(jìn)制，當(dāng)做我們的DNA

交叉的方式有很多，我們這邊選擇這一個(gè)，進(jìn)行交叉。

變異

那這個(gè)在我們這里就更加簡(jiǎn)單了

我們只需要在交叉之后，再隨機(jī)選擇幾個(gè)位置進(jìn)行改變值就可以了。當(dāng)然變異的概率是很小的，并且是隨機(jī)的，這一點(diǎn)要注意。并且由于變異是隨機(jī)的，所以不排除生成比原來(lái)還更加糟糕的個(gè)體。

選擇

最后我們按照一定的規(guī)則去篩選這個(gè)些個(gè)體就可以了，然后淘汰原來(lái)的個(gè)體。那么在我們的計(jì)算機(jī)里面是使用了兩個(gè)東西，首先我們要把原來(lái)二進(jìn)制的玩意，給轉(zhuǎn)化為我們?cè)瓉?lái)的十進(jìn)制然后帶入我們的函數(shù)運(yùn)算，然后保存起來(lái)，之后再每一輪統(tǒng)一篩選一下就好了。

逆轉(zhuǎn)

這個(gè)咋說(shuō)呢，說(shuō)好聽(tīng)點(diǎn)叫逆轉(zhuǎn)，難聽(tīng)點(diǎn)就算，對(duì)于一些新的生成的不好的解，我們是要舍棄的。

代碼

那么這部分用代碼描述的話就是這樣的：

import numpy as np
import matplotlib.pyplot as plt
Population_Size = 100
Iteration_Number = 200
Cross_Rate = 0.8
Mutation_Rate = 0.003
Dna_Size = 10
X_Range=[0,5]
def F(x):
    '''
    目標(biāo)函數(shù)，需要被優(yōu)化的函數(shù)
    :param x:
    :return:
    '''
    return np.sin(10 * x) * x + np.cos(2 * x) * x
def CrossOver(Parent,PopSpace):
    '''
    交叉DNA，我們直接在種群里面選擇一個(gè)交配
    然后就生出孩子了
    :param parent:
    :param PopSpace:
    :return:
    '''
    if(np.random.rand()) < Cross_Rate:
        cross_place = np.random.randint(0, 2, size=Dna_Size).astype(np.bool)
        cross_one = np.random.randint(0, Population_Size, size=1) #選擇一位男/女士交配
        Parent[cross_place] = PopSpace[cross_one,cross_place]
    return Parent
def Mutate(Child):
    '''
    變異
    :param Child:
    :return:
    '''
    for point in range(Dna_Size):
        if np.random.rand() < Mutation_Rate:
            Child[point] = 1 if Child[point] == 0 else 0
    return Child
def TranslateDNA(PopSpace):
    '''
    把二進(jìn)制轉(zhuǎn)化為十進(jìn)制方便計(jì)算
    :param PopSpace:
    :return:
    '''
    return PopSpace.dot(2 ** np.arange(Dna_Size)[::-1]) / float(2 ** Dna_Size - 1) * X_Range[1]
def Fitness(pred):
    '''
    這個(gè)其實(shí)是對(duì)我們得到的F(x)進(jìn)行換算，其實(shí)就是選擇的時(shí)候
    的概率，我們需要處理負(fù)數(shù)，因?yàn)楦怕什荒転樨?fù)數(shù)呀
    pred 這是一個(gè)二維矩陣
    :param pred:
    :return:
    '''
    return pred + 1e-3 - np.min(pred)
def Select(PopSpace,Fitness):
    '''
    選擇
    :param PopSpace:
    :param Fitness:
    :return:
    '''
    '''
    這里注意的是，我們先按照權(quán)重去選擇我們的優(yōu)良個(gè)體，所以我們這里選擇的時(shí)候允許重復(fù)的元素出現(xiàn)
    之后我們就可以去掉這些重復(fù)的元素，這樣才能實(shí)現(xiàn)保留良種去除劣種。100--》70（假設(shè)有30個(gè)重復(fù)）
    如果不允許重復(fù)的話，那你相當(dāng)于沒(méi)有篩選
    '''
    Better_Ones = np.random.choice(np.arange(Population_Size), size=Population_Size, replace=True,
                           p=Fitness / Fitness.sum())
    # np.unique(Better_Ones) #這個(gè)是我后面加的
    return PopSpace[Better_Ones]
if __name__ == '__main__':
    PopSpace = np.random.randint(2, size=(Population_Size, Dna_Size))  # initialize the PopSpace DNA
    plt.ion() 
    x = np.linspace(X_Range, 200)
    # plt.plot(x, F(x))
    plt.xticks([0,10])
    plt.yticks([0,10])
    for _ in range(Iteration_Number):
        F_values = F(TranslateDNA(PopSpace))  
        # something about plotting
        if 'sca' in globals():
            sca.remove()
        sca = plt.scatter(TranslateDNA(PopSpace), F_values, s=200, lw=0, c='red', alpha=0.5)
        plt.pause(0.05)
        # GA part (evolution)
        fitness = Fitness(F_values)
        print("Most fitted DNA: ", PopSpace[np.argmax(fitness)])
        PopSpace = Select(PopSpace, fitness)
        PopSpace_copy = PopSpace.copy()
        for parent in PopSpace:
            child = CrossOver(parent, PopSpace_copy)
            child = Mutate(child)
            parent[:] = child
    plt.ioff()
    plt.show()

這個(gè)代碼是以前寫(xiě)的，逆轉(zhuǎn)沒(méi)有寫(xiě)上（下面的有）

TSP遺傳算法

ok,剛剛的例子是拿的解方程，也就是說(shuō)是一個(gè)連續(xù)問(wèn)題吧，當(dāng)然那個(gè)連續(xù)處理的話并不是很好，只是一個(gè)演示。那么我們這個(gè)的話其實(shí)類(lèi)似的。首先我們的ＤＮＡ，是城市的路徑，也就是A-B-C-D等等，當(dāng)然我們用下標(biāo)表示城市。

種群表示

首先我們確定了使用城市的序號(hào)作為我們的個(gè)體DNA，例如咱們種群大小為100，有ＡＢＣＤ四個(gè)城市，那么他就是這樣的，我們先隨機(jī)生成種群，長(zhǎng)這個(gè)樣：

1 2 3 4
2 3 4 5
3 2 1 4
...

那個(gè)1,2,3,4是ABCD的序號(hào)。

交叉與變異

這里面的話，值得一提的就是，由于暫定城市需要是不能重復(fù)的，且必須是完整的，所以如果像剛剛那樣進(jìn)行交叉或者變異的話，那么實(shí)際上會(huì)出點(diǎn)問(wèn)題，我們不允許出現(xiàn)重復(fù)，且必須完整，對(duì)于我們的DNA，也就是咱們瞎蒙的個(gè)體。

代碼

由于咱們每一步在代碼里面都有注釋?zhuān)缘脑捲蹅冊(cè)谶@里就不再進(jìn)行復(fù)述了。

from math import floor
import numpy as np
import matplotlib.pyplot as plt
class Gena_TSP(object):
    """
    使用遺傳算法解決TSP問(wèn)題
    """
    def __init__(self, data, maxgen=200,
                 size_pop=200, cross_prob=0.9,
                 pmuta_prob=0.01, select_prob=0.8
                 ):
        self.maxgen = maxgen            # 最大迭代次數(shù)
        self.size_pop = size_pop        # 群體個(gè)數(shù)，（一次性瞎蒙多少個(gè)解）
        self.cross_prob = cross_prob    # 交叉概率
        self.pmuta_prob = pmuta_prob    # 變異概率
        self.select_prob = select_prob  # 選擇概率
        self.data = data        # 城市的坐標(biāo)數(shù)據(jù)
        self.num = len(data)    # 有多少個(gè)城市，對(duì)應(yīng)多少個(gè)坐標(biāo)，對(duì)應(yīng)染色體的長(zhǎng)度（我們的解叫做染色體）
        """
        計(jì)算城市的距離，我們用矩陣表示城市間的距離
        """
        self.__matrix_distance = self.__matrix_dis()
        self.select_num = int(self.size_pop * self.select_prob)
        # 通過(guò)選擇概率確定子代的選擇個(gè)數(shù)
        """
        初始化子代和父代種群，兩者相互交替
        """
        self.parent = np.array([0] * self.size_pop * self.num).reshape(self.size_pop, self.num)
        self.child = np.array([0] * self.select_num * self.num).reshape(self.select_num, self.num)
        """
        負(fù)責(zé)計(jì)算每一個(gè)個(gè)體的（瞎蒙的解）最后需要多少距離
        """
        self.fitness = np.zeros(self.size_pop)
        self.best_fit = []
        self.best_path = []
        # 保存每一步的群體的最優(yōu)路徑和距離
    def __matrix_dis(self):
        """
        計(jì)算14個(gè)城市的距離，將這些距離用矩陣存起來(lái)
        :return: 
        """
        res = np.zeros((self.num, self.num))
        for i in range(self.num):
            for j in range(i + 1, self.num):
                res[i, j] = np.linalg.norm(self.data[i, :] - self.data[j, :])
                res[j, i] = res[i, j]
        return res
    def rand_parent(self):
        """
        初始化種群
        :return:
        """
        rand_ch = np.array(range(self.num))
        for i in range(self.size_pop):
            np.random.shuffle(rand_ch)
            self.parent[i, :] = rand_ch
            self.fitness[i] = self.comp_fit(rand_ch)
    def comp_fit(self, one_path):
        """
        計(jì)算，咱們這個(gè)路徑的長(zhǎng)度，例如A-B-C-D
        :param one_path:
        :return:
        """
        res = 0
        for i in range(self.num - 1):
            res += self.__matrix_distance[one_path[i], one_path[i + 1]]
        res += self.__matrix_distance[one_path[-1], one_path[0]]
        return res
    def out_path(self, one_path):
        """
        輸出我們的路徑順序
        :param one_path:
        :return:
        """
        res = str(one_path[0] + 1) + '-->'
        for i in range(1, self.num):
            res += str(one_path[i] + 1) + '-->'
        res += str(one_path[0] + 1) + '\n'
        print(res)
    def Select(self):
        """
        通過(guò)我們的這個(gè)計(jì)算的距離來(lái)計(jì)算出概率，也就是當(dāng)前這些個(gè)體DNA也就瞎蒙的解
        之后我們?cè)谕ㄟ^(guò)概率去選擇個(gè)體，放到child里面
        :return:
        """
        fit = 1. / (self.fitness)  # 適應(yīng)度函數(shù)
        cumsum_fit = np.cumsum(fit)
        pick = cumsum_fit[-1] / self.select_num * (np.random.rand() + np.array(range(self.select_num)))
        i, j = 0, 0
        index = []
        while i < self.size_pop and j < self.select_num:
            if cumsum_fit[i] >= pick[j]:
                index.append(i)
                j += 1
            else:
                i += 1
        self.child = self.parent[index, :]
    def Cross(self):
        """
        模仿DNA交叉嘛，就是交換兩個(gè)瞎蒙的解的部分的解例如
        A-B-C-D
        C-D-A-B
        我們選幾個(gè)交叉例如這樣
        A-D-C-B
        1,3號(hào)交換了位置，當(dāng)然這里注意可不能重復(fù)啊
        :return:
        """
        if self.select_num % 2 == 0:
            num = range(0, self.select_num, 2)
        else:
            num = range(0, self.select_num - 1, 2)
        for i in num:
            if self.cross_prob >= np.random.rand():
                self.child[i, :], self.child[i + 1, :] = self.intercross(self.child[i, :],
                                                                             self.child[i + 1, :])
    def intercross(self, ind_a, ind_b):
        """
        這個(gè)是我們兩兩交叉的具體實(shí)現(xiàn)
        :param ind_a:
        :param ind_b:
        :return:
        """
        r1 = np.random.randint(self.num)
        r2 = np.random.randint(self.num)
        while r2 == r1:
            r2 = np.random.randint(self.num)
        left, right = min(r1, r2), max(r1, r2)
        ind_a1 = ind_a.copy()
        ind_b1 = ind_b.copy()
        for i in range(left, right + 1):
            ind_a2 = ind_a.copy()
            ind_b2 = ind_b.copy()
            ind_a[i] = ind_b1[i]
            ind_b[i] = ind_a1[i]
            x = np.argwhere(ind_a == ind_a[i])
            y = np.argwhere(ind_b == ind_b[i])
            if len(x) == 2:
                ind_a[x[x != i]] = ind_a2[i]
            if len(y) == 2:
                ind_b[y[y != i]] = ind_b2[i]
        return ind_a, ind_b
    def Mutation(self):
        """
        之后是變異模塊，這個(gè)就是按照某個(gè)概率，去替換瞎蒙的解里面的其中幾個(gè)元素。
        :return:
        """
        for i in range(self.select_num):
            if np.random.rand() <= self.cross_prob:
                r1 = np.random.randint(self.num)
                r2 = np.random.randint(self.num)
                while r2 == r1:
                    r2 = np.random.randint(self.num)
                self.child[i, [r1, r2]] = self.child[i, [r2, r1]]
    def Reverse(self):
        """
        近化逆轉(zhuǎn)，就是說(shuō)下一次瞎蒙的解如果沒(méi)有更好的話就不進(jìn)入下一代，同時(shí)也是隨機(jī)選擇一個(gè)部分的
        我們不是一次性全部替換
        :return: 
        """
        for i in range(self.select_num):
            r1 = np.random.randint(self.num)
            r2 = np.random.randint(self.num)
            while r2 == r1:
                r2 = np.random.randint(self.num)
            left, right = min(r1, r2), max(r1, r2)
            sel = self.child[i, :].copy()
            sel[left:right + 1] = self.child[i, left:right + 1][::-1]
            if self.comp_fit(sel) < self.comp_fit(self.child[i, :]):
                self.child[i, :] = sel
    def Born(self):
        """
        替換，子代變成新的父代
        :return:
        """
        index = np.argsort(self.fitness)[::-1]
        self.parent[index[:self.select_num], :] = self.child
def main(data):
    Path_short = Gena_TSP(data)     # 根據(jù)位置坐標(biāo)，生成一個(gè)遺傳算法類(lèi)
    Path_short.rand_parent()        # 初始化父類(lèi)
    ## 繪制初始化的路徑圖
    fig, ax = plt.subplots()
    x = data[:, 0]
    y = data[:, 1]
    ax.scatter(x, y, linewidths=0.1)
    for i, txt in enumerate(range(1, len(data) + 1)):
        ax.annotate(txt, (x[i], y[i]))
    res0 = Path_short.parent[0]
    x0 = x[res0]
    y0 = y[res0]
    for i in range(len(data) - 1):
        plt.quiver(x0[i], y0[i], x0[i + 1] - x0[i], y0[i + 1] - y0[i], color='r', width=0.005, angles='xy', scale=1,
                   scale_units='xy')
    plt.quiver(x0[-1], y0[-1], x0[0] - x0[-1], y0[0] - y0[-1], color='r', width=0.005, angles='xy', scale=1,
               scale_units='xy')
    plt.show()
    print('初始染色體的路程: ' + str(Path_short.fitness[0]))
    # 循環(huán)迭代遺傳過(guò)程
    for i in range(Path_short.maxgen):
        Path_short.Select()     # 選擇子代
        Path_short.Cross()      # 交叉
        Path_short.Mutation()   # 變異
        Path_short.Reverse()    # 進(jìn)化逆轉(zhuǎn)
        Path_short.Born()      # 子代插入
        # 重新計(jì)算新群體的距離值
        for j in range(Path_short.size_pop):
            Path_short.fitness[j] = Path_short.comp_fit(Path_short.parent[j, :])
        index = Path_short.fitness.argmin()
        if (i + 1) % 50 == 0:
            print('第' + str(i + 1) + '步后的最短的路程: ' + str(Path_short.fitness[index]))
            print('第' + str(i + 1) + '步后的最優(yōu)路徑:')
            Path_short.out_path(Path_short.parent[index, :])  # 顯示每一步的最優(yōu)路徑
        # 存儲(chǔ)每一步的最優(yōu)路徑及距離
        Path_short.best_fit.append(Path_short.fitness[index])
        Path_short.best_path.append(Path_short.parent[index, :])
    return Path_short  # 返回遺傳算法結(jié)果類(lèi)
if __name__ == '__main__':
    data = np.array([16.47, 96.10, 16.47, 94.44, 20.09, 92.54,
                     22.39, 93.37, 25.23, 97.24, 22.00, 96.05, 20.47, 97.02,
                     17.20, 96.29, 16.30, 97.38, 14.05, 98.12, 16.53, 97.38,
                     21.52, 95.59, 19.41, 97.13, 20.09, 92.55]).reshape((14, 2))
    main(data)

運(yùn)行結(jié)果

ok,我們來(lái)看看運(yùn)行的結(jié)果：

感謝各位的閱讀，以上就是“怎么用Python遺傳算法解決旅行商問(wèn)題”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)怎么用Python遺傳算法解決旅行商問(wèn)題這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！