怎么使用Python?PSO算法處理TSP問(wèn)題

這篇文章主要介紹了怎么使用Python PSO算法處理TSP問(wèn)題的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇怎么使用Python PSO算法處理TSP問(wèn)題文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

PSO算法

那么開(kāi)始之前，我們還是來(lái)聊聊基本的PSO算法。核心就一個(gè)：

來(lái)我們來(lái)解釋一下這個(gè)公式，你就懂了。

老規(guī)矩我們假設(shè)有一個(gè)方程 y=sin(x1)+cos(x2)

PSO算法通過(guò)模擬鳥(niǎo)類(lèi)遷移來(lái)實(shí)現(xiàn)咱們的優(yōu)化，這個(gè)怎么來(lái)的，就不說(shuō)了，就說(shuō)說(shuō)這個(gè)核心。

我們剛剛的方程當(dāng)中，有兩個(gè)變量，x1,x2。由于是模擬鳥(niǎo)兒，所有為了實(shí)現(xiàn)瞎蒙大法，這里引入了速度的概念，x自然就是咱們的可行域，也就是解的空間。通過(guò)改變速度，來(lái)讓x進(jìn)行移動(dòng)，也就是改變x的值。其中Pbest，表示這個(gè)鳥(niǎo)自己走過(guò)的位置里面最優(yōu)的解，Gbest表示整個(gè)種群的最優(yōu)解。什么意思，也就是說(shuō)隨著移動(dòng)，這個(gè)鳥(niǎo)可能會(huì)走到更差的位置，因?yàn)楹瓦z傳不一樣，他是不好的就干掉了，而這個(gè)不會(huì)。當(dāng)然這里面涉及到很多局部問(wèn)題，咱們這里都不討論，沒(méi)有哪一個(gè)算法是完美的，這個(gè)就對(duì)了。

算法流程

算法的主要流程：

第一步：對(duì)粒子群的隨機(jī)位置和速度進(jìn)行初始設(shè)定，同時(shí)設(shè)定迭代次數(shù)。

第二步：計(jì)算每個(gè)粒子的適應(yīng)度值。

第三步：對(duì)每個(gè)粒子，將其適應(yīng)度值與所經(jīng)歷的最好位置pbest i的適應(yīng)度值進(jìn)行比較，若較好，則將其作為當(dāng)前的個(gè)體最優(yōu)位置。

第四步：對(duì)每個(gè)粒子，將其適應(yīng)度值與全局所經(jīng)歷的最好位置gbestg的適應(yīng)度值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最優(yōu)位置。

第五步：根據(jù)速度、位置公式對(duì)粒子的速度和位置進(jìn)行優(yōu)化，從而更新粒子位置。

第六步：如未達(dá)到結(jié)束條件（通常為最大循環(huán)數(shù)或最小誤差要求），則返回第二步

優(yōu)點(diǎn)：

PSO算法沒(méi)有交叉和變異運(yùn)算，依靠粒子速度完成搜索，并且在迭代進(jìn)化中只有最優(yōu)的粒子把信息傳遞給其它粒子，搜索速度快。

PSO算法具有記憶性，粒子群體的歷史最好位置可以記憶并傳遞給其它粒子。

需調(diào)整的參數(shù)較少，結(jié)構(gòu)簡(jiǎn)單，易于工程實(shí)現(xiàn)。

采用實(shí)數(shù)編碼，直接由問(wèn)題的解決定，問(wèn)題解的變量數(shù)直接作為粒子的維數(shù)。

缺點(diǎn)：

缺乏速度的動(dòng)態(tài)調(diào)節(jié)，容易陷入局部最優(yōu)，導(dǎo)致收斂精度低和不易收斂。

不能有效解決離散及組合優(yōu)化問(wèn)題。

參數(shù)控制，對(duì)于不同的問(wèn)題，如何選擇合適的參數(shù)來(lái)達(dá)到最優(yōu)效果。

不能有效求解一些非直角坐標(biāo)系描述問(wèn)題，

簡(jiǎn)單實(shí)現(xiàn)

ok,我們來(lái)看一下最簡(jiǎn)單的實(shí)現(xiàn)：

import numpy as np
import random
class PSO_model:
    def __init__(self,w,c1,c2,r1,r2,N,D,M):
        self.w = w # 慣性權(quán)值
        self.c1=c1
        self.c2=c2
        self.r1=r1
        self.r2=r2
        self.N=N # 初始化種群數(shù)量個(gè)數(shù)
        self.D=D # 搜索空間維度
        self.M=M # 迭代的最大次數(shù)
        self.x=np.zeros((self.N,self.D))  #粒子的初始位置
        self.v=np.zeros((self.N,self.D))  #粒子的初始速度
        self.pbest=np.zeros((self.N,self.D))  #個(gè)體最優(yōu)值初始化
        self.gbest=np.zeros((1,self.D))  #種群最優(yōu)值
        self.p_fit=np.zeros(self.N)
        self.fit=1e8 #初始化全局最優(yōu)適應(yīng)度
# 目標(biāo)函數(shù)，也是適應(yīng)度函數(shù)（求最小化問(wèn)題）
    def function(self,x):
        A = 10
        x1=x[0]
        x2=x[1]
        Z = 2 * A + x1 ** 2 - A * np.cos(2 * np.pi * x1) + x2 ** 2 - A * np.cos(2 * np.pi * x2)
        return Z
     # 初始化種群
    def init_pop(self):
        for i in range(self.N):
            for j in range(self.D):
                self.x[i][j] = random.random()
                self.v[i][j] = random.random()
            self.pbest[i] = self.x[i] # 初始化個(gè)體的最優(yōu)值
            aim=self.function(self.x[i]) # 計(jì)算個(gè)體的適應(yīng)度值
            self.p_fit[i]=aim # 初始化個(gè)體的最優(yōu)位置
            if aim < self.fit:  # 對(duì)個(gè)體適應(yīng)度進(jìn)行比較，計(jì)算出最優(yōu)的種群適應(yīng)度
                self.fit = aim
                self.gbest = self.x[i]
    # 更新粒子的位置與速度
    def update(self):
        for t in range(self.M): # 在迭代次數(shù)M內(nèi)進(jìn)行循環(huán)
            for i in range(self.N): # 對(duì)所有種群進(jìn)行一次循環(huán)
                aim=self.function(self.x[i]) # 計(jì)算一次目標(biāo)函數(shù)的適應(yīng)度
                if aim<self.p_fit[i]: # 比較適應(yīng)度大小，將小的負(fù)值給個(gè)體最優(yōu)
                    self.p_fit[i]=aim
                    self.pbest[i]=self.x[i]
                    if self.p_fit[i]<self.fit: # 如果是個(gè)體最優(yōu)再將和全體最優(yōu)進(jìn)行對(duì)比
                        self.gbest=self.x[i]
                        self.fit = self.p_fit[i]
            for i in range(self.N): # 更新粒子的速度和位置
                self.v[i]=self.w*self.v[i]+self.c1*self.r1*(self.pbest[i]-self.x[i])+ self.c2*self.r2*(self.gbest-self.x[i])
                self.x[i]=self.x[i]+self.v[i]
        print("最優(yōu)值：",self.fit,"位置為：",self.gbest)
if __name__ == '__main__':
    # w,c1,c2,r1,r2,N,D,M參數(shù)初始化
    w=random.random()
    c1=c2=2#一般設(shè)置為2
    r1=0.7
    r2=0.5
    N=30
    D=2
    M=200
    pso_object=PSO_model(w,c1,c2,r1,r2,N,D,M)#設(shè)置初始權(quán)值
    pso_object.init_pop()
    pso_object.update()

解決TSP

數(shù)據(jù)表示

首先這個(gè)使用PSO的話(huà)，其實(shí)是和我們的這個(gè)先前使用遺傳是類(lèi)似的，我們依然通過(guò)一個(gè)矩陣表示種群，一個(gè)矩陣表示城市之間的距離。

      # 群體的初始化和路徑的初始化
        self.population = np.array([0] * self.num_pop * self.num).reshape(
            self.num_pop, self.num)
        self.fitness = [0] * self.num_pop
        """
        計(jì)算城市的距離，我們用矩陣表示城市間的距離
        """
        self.__matrix_distance = self.__matrix_dis()

區(qū)別

和我們?cè)瓉?lái)的PSO的最大區(qū)別是啥呢，其實(shí)和簡(jiǎn)單，在與我們速度的更新。我們?cè)谶B續(xù)問(wèn)題的時(shí)候其實(shí)是這樣的：

同樣的我們可以把X表示城市的編號(hào)，但是顯然我們不能使用這種方案進(jìn)行速度的更新。

那么這個(gè)時(shí)候，我們對(duì)于速度的更新的話(huà)，我們是需要使用到一種新的方案，那么這個(gè)方案的話(huà)其實(shí)就是套用遺傳算算法的X更新。我們之所以需要速度說(shuō)白了就是為了更新X，讓X往好的方向進(jìn)行瞎蒙?，F(xiàn)在單純使用速度更新是不行了，那么反正都是更新X，選擇一個(gè)可以很好更新這個(gè)X的方案不就行了嘛。所以的話(huà)這里可直接使用遺傳啊，我們的速度更新是參考Pbest和Gbest，之后按照一定的權(quán)重進(jìn)行“學(xué)習(xí)”這樣一來(lái)這個(gè)V就具備了Pbest和Gbest的一種“特征”。所以既然如此，那么我直接仿造遺傳交叉的時(shí)候和Best進(jìn)行交叉不就可以學(xué)習(xí)到一些對(duì)應(yīng)的“特征”嘛。

    def cross_1(self, path, best_path):
        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)
        cross = best_path[left:right + 1]
        for i in range(right - left + 1):
            for k in range(self.num):
                if path[k] == cross[i]:
                    path[k:self.num - 1] = path[k + 1:self.num]
                    path[-1] = 0
        path[self.num - right + left - 1:self.num] = cross
        return path

同時(shí)我們依然可以引入變異。

    def mutation(self,path):
        r1 = np.random.randint(self.num)
        r2 = np.random.randint(self.num)
        while r2 == r1:
            r2 = np.random.randint(self.num)
        path[r1],path[r2] = path[r2],path[r1]
        return path

完整代碼

ok,現(xiàn)在我們來(lái)看到完整的代碼：

import numpy as np
import matplotlib.pyplot as plt
class HybridPsoTSP(object):
    def __init__(self ,data ,num_pop=200):
        self.num_pop = num_pop  # 群體個(gè)數(shù)
        self.data = data        # 城市坐標(biāo)
        self.num =len(data)     # 城市個(gè)數(shù)
        # 群體的初始化和路徑的初始化
        self.population = np.array([0] * self.num_pop * self.num).reshape(
            self.num_pop, self.num)
        self.fitness = [0] * self.num_pop
        """
        計(jì)算城市的距離，我們用矩陣表示城市間的距離
        """
        self.__matrix_distance = self.__matrix_dis()
    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 cross_1(self, path, best_path):
        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)
        cross = best_path[left:right + 1]
        for i in range(right - left + 1):
            for k in range(self.num):
                if path[k] == cross[i]:
                    path[k:self.num - 1] = path[k + 1:self.num]
                    path[-1] = 0
        path[self.num - right + left - 1:self.num] = cross
        return path
    def mutation(self,path):
        r1 = np.random.randint(self.num)
        r2 = np.random.randint(self.num)
        while r2 == r1:
            r2 = np.random.randint(self.num)
        path[r1],path[r2] = path[r2],path[r1]
        return path
    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 init_population(self):
        """
        初始化種群
        :return:
        """
        rand_ch = np.array(range(self.num))
        for i in range(self.num_pop):
            np.random.shuffle(rand_ch)
            self.population[i, :] = rand_ch
            self.fitness[i] = self.comp_fit(rand_ch)
def main(data, max_n=200, num_pop=200):
    Path_short = HybridPsoTSP(data, num_pop=num_pop)  # 混合粒子群算法類(lèi)
    Path_short.init_population()  # 初始化種群
    # 初始化路徑繪圖
    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.population[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]))
    # 存儲(chǔ)個(gè)體極值的路徑和距離
    best_P_population = Path_short.population.copy()
    best_P_fit = Path_short.fitness.copy()
    min_index = np.argmin(Path_short.fitness)
    # 存儲(chǔ)當(dāng)前種群極值的路徑和距離
    best_G_population = Path_short.population[min_index, :]
    best_G_fit = Path_short.fitness[min_index]
    # 存儲(chǔ)每一步迭代后的最優(yōu)路徑和距離
    best_population = [best_G_population]
    best_fit = [best_G_fit]
    # 復(fù)制當(dāng)前群體進(jìn)行交叉變異
    x_new = Path_short.population.copy()
    for i in range(max_n):
        # 更新當(dāng)前的個(gè)體極值
        for j in range(num_pop):
            if Path_short.fitness[j] < best_P_fit[j]:
                best_P_fit[j] = Path_short.fitness[j]
                best_P_population[j, :] = Path_short.population[j, :]
        # 更新當(dāng)前種群的群體極值
        min_index = np.argmin(Path_short.fitness)
        best_G_population = Path_short.population[min_index, :]
        best_G_fit = Path_short.fitness[min_index]
        # 更新每一步迭代后的全局最優(yōu)路徑和解
        if best_G_fit < best_fit[-1]:
            best_fit.append(best_G_fit)
            best_population.append(best_G_population)
        else:
            best_fit.append(best_fit[-1])
            best_population.append(best_population[-1])
        # 將每個(gè)個(gè)體與個(gè)體極值和當(dāng)前的群體極值進(jìn)行交叉
        for j in range(num_pop):
            # 與個(gè)體極值交叉
            x_new[j, :] = Path_short.cross_1(x_new[j, :], best_P_population[j, :])
            fit = Path_short.comp_fit(x_new[j, :])
            # 判斷是否保留
            if fit < Path_short.fitness[j]:
                Path_short.population[j, :] = x_new[j, :]
                Path_short.fitness[j] = fit
            # 與當(dāng)前極值交叉
            x_new[j, :] = Path_short.cross_1(x_new[j, :], best_G_population)
            fit = Path_short.comp_fit(x_new[j, :])
            if fit < Path_short.fitness[j]:
                Path_short.population[j, :] = x_new[j, :]
                Path_short.fitness[j] = fit
            # 變異
            x_new[j, :] = Path_short.mutation(x_new[j, :])
            fit = Path_short.comp_fit(x_new[j, :])
            if fit <= Path_short.fitness[j]:
                Path_short.population[j] = x_new[j, :]
                Path_short.fitness[j] = fit
        if (i + 1) % 20 == 0:
            print('第' + str(i + 1) + '步后的最短的路程: ' + str(Path_short.fitness[min_index]))
            print('第' + str(i + 1) + '步后的最優(yōu)路徑:')
            Path_short.out_path(Path_short.population[min_index, :])  # 顯示每一步的最優(yōu)路徑
    Path_short.best_population = best_population
    Path_short.best_fit = best_fit
    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)

初始染色體的路程: 71.30211569672313
第20步后的最短的路程: 29.340520066994223
第20步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第40步后的最短的路程: 29.340520066994223
第40步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第60步后的最短的路程: 29.340520066994223
第60步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第80步后的最短的路程: 29.340520066994223
第80步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第100步后的最短的路程: 29.340520066994223
第100步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第120步后的最短的路程: 29.340520066994223
第120步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第140步后的最短的路程: 29.340520066994223
第140步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第160步后的最短的路程: 29.340520066994223
第160步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第180步后的最短的路程: 29.340520066994223
第180步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9
第200步后的最短的路程: 29.340520066994223
第200步后的最優(yōu)路徑:
9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9

可以看到收斂速度還是很快的。

特點(diǎn)分析

ok,到目前為止的話(huà)，我們介紹了兩個(gè)算法去解決TSP或者是優(yōu)化問(wèn)題。我們來(lái)分析一下，這些算法有什么特點(diǎn)，為啥可以達(dá)到我們需要的優(yōu)化效果。其實(shí)不管是遺傳還是PSO，你其實(shí)都可以發(fā)現(xiàn)，有一個(gè)東西，我們可以暫且叫它環(huán)境壓力。我們通過(guò)物競(jìng)天擇，或者鳥(niǎo)類(lèi)遷移，進(jìn)行模擬尋優(yōu)。而之所以需要這樣做，是因?yàn)槲覀冎付艘粋€(gè)規(guī)則，在我們的規(guī)則之下。我們讓模擬的種群有一種壓力去靠攏，其中物競(jìng)天擇和鳥(niǎo)類(lèi)遷移只是我們的一種手段，去應(yīng)對(duì)這樣的“壓力”。所以的對(duì)于這種算法而言，最核心的點(diǎn)就兩個(gè)：

設(shè)計(jì)環(huán)境壓力

我們需要做優(yōu)化問(wèn)題，所以我們必須要能夠讓我們的解往那個(gè)方向走，需要一個(gè)驅(qū)動(dòng)，需要一個(gè)壓力。因此我們需要設(shè)計(jì)這樣的一個(gè)環(huán)境，在遺傳算法，粒子群算法是通過(guò)種群當(dāng)中的生存，來(lái)進(jìn)行設(shè)計(jì)的它的壓力是我們的目標(biāo)函數(shù)。由種群和目標(biāo)函數(shù)（目標(biāo)指標(biāo)）構(gòu)成了一個(gè)環(huán)境和壓力。

設(shè)計(jì)壓力策略

之后的話(huà)，我們?cè)O(shè)計(jì)好了一個(gè)環(huán)境和壓力，那么未來(lái)應(yīng)對(duì)這種壓力，我們需要去設(shè)計(jì)一種策略，來(lái)應(yīng)付這種壓力。遺傳算法是通過(guò)PUA自己，也就是種群的優(yōu)勝略汰。PSO是通過(guò)學(xué)習(xí)，學(xué)習(xí)種群的優(yōu)秀粒子和過(guò)去自己家的優(yōu)秀“祖先”來(lái)應(yīng)對(duì)這種壓力的。

強(qiáng)化學(xué)習(xí)

所以的話(huà)，我們是否可以使用別的方案來(lái)實(shí)現(xiàn)這種優(yōu)化效果。，在強(qiáng)化學(xué)習(xí)的算法框架里面的話(huà)，我們明確的知道了為什么他們可以實(shí)現(xiàn)優(yōu)化，是環(huán)境壓力+壓力策略。恰好咱們強(qiáng)化學(xué)習(xí)是有環(huán)境的，適應(yīng)函數(shù)和環(huán)境恰好可以組成環(huán)境+壓力。本身的算法收斂過(guò)程就是我們的壓力策略。所以我們完全是可以直接使用強(qiáng)化學(xué)習(xí)進(jìn)行這個(gè)處理的。那么在這里咱們就來(lái)使用強(qiáng)化學(xué)習(xí)在下一篇文章當(dāng)中。

關(guān)于“怎么使用Python PSO算法處理TSP問(wèn)題”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“怎么使用Python PSO算法處理TSP問(wèn)題”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。