直接說基礎(chǔ)語法，也許大家不會(huì)感興趣。前言之后的這一章，給大家介紹一下我最近寫出來的一個(gè)小功能。用python語言實(shí)現(xiàn)GA算法來解決TSP問題，希望以此來激發(fā)大家學(xué)習(xí)python的興趣。

何為GA，何為TSP問題，我將會(huì)在以后準(zhǔn)備寫的算法專題里詳細(xì)解釋，這里不再贅述，文章將主要講述算法思路，以及實(shí)現(xiàn)效果，并內(nèi)附重要代碼。

程序思路

python3.6+pycharm+Anaconda3.6外加了一個(gè)basemap包是我的編程環(huán)境。

遺傳算法流程圖.jpg

首先我創(chuàng)建了一個(gè)GA.py,用來實(shí)現(xiàn)解決TSP問題的GA算法。算法流程如上圖大致所述。有關(guān)TSP問題的解決算法有很多，近似算法，模擬退火，遺傳算法等等，已經(jīng)是造好了的輪子，可以拿來就用，也可以自己實(shí)現(xiàn)一邊，還是蠻有意思的。最重要的是要領(lǐng)會(huì)算法思想，體會(huì)它解決問題的思路。

實(shí)現(xiàn)算法核心后，再來實(shí)現(xiàn)程序主體TSP.py，即用算法將讀取的城市信息進(jìn)行處理計(jì)算，并最后可視化呈現(xiàn)出來。

程序整體架構(gòu).jpg

如圖所示，先從txt文件中讀取34個(gè)城市的經(jīng)緯度，然后根據(jù)地球弧度以及角度計(jì)算出34個(gè)城市兩兩之間距離。將這個(gè)數(shù)據(jù)傳遞給GA算法類，類內(nèi)部有一個(gè)適配函數(shù)計(jì)算，通過距離數(shù)據(jù)，進(jìn)行交叉，變異，產(chǎn)生下一代等一系列操作。最終產(chǎn)生一個(gè)最優(yōu)秀的個(gè)體，也就是遍歷了34個(gè)城市后使路程距離最短的那個(gè)序列。

其實(shí)所謂交叉，變異等等就是說，在這個(gè)算法中，我們把一個(gè)數(shù)組當(dāng)作個(gè)體，這個(gè)數(shù)組代表什么含義呢？就是城市先后順序。交叉就是讓兩個(gè)數(shù)組交換一部分序列產(chǎn)生新數(shù)組，變異就是一個(gè)數(shù)組部分序列改變，自己變成新數(shù)組。注意的是，第一代個(gè)體中，要特意保留下來本來路徑就是最短的數(shù)組，直接放到下一代中，如此循環(huán)往復(fù)，以求尋找到最佳數(shù)組序列。

在這里我設(shè)置了一個(gè)全局?jǐn)?shù)組，即迭代足夠多的次數(shù)后，將最后得到的個(gè)體，或者說數(shù)組儲(chǔ)存在里面，再在畫圖函數(shù)中使用它，以求將最優(yōu)數(shù)組展現(xiàn)在由basemap勾勒出的地圖上。

最短路徑實(shí)現(xiàn)圖.jpeg

代碼實(shí)現(xiàn)

    def __init__(self, aLifeCount=100, ):
        self.initCitys()
        self.lifeCount = aLifeCount
        self.ga = GA(aCrossRate=0.7,
                     aMutationRage=0.02,
                     aLifeCount=self.lifeCount,
                     aGeneLenght=len(self.citys),
                     aMatchFun=self.matchFun())
        self.bestcityorder = []

這是初始化函數(shù)，其中self.bestcityorder即是我所說的全局?jǐn)?shù)組，它起到一個(gè)在各個(gè)函數(shù)中間傳遞數(shù)據(jù)的中樞作用。此外，該初始化函數(shù)還初始化了GA算法的交叉概率，變異概率，以及適配函數(shù)等等。

這里面的self要特別提一下，它是一個(gè)關(guān)鍵字，它的意思是該類的一個(gè)實(shí)例化對(duì)象。相當(dāng)于一個(gè)指針，才讓全局?jǐn)?shù)組起到暢通無阻的中樞作用。

    def distance(self, order):
        distance = 0.0
        for i in range(-1, len(self.citys) - 1):
            index1, index2 = order[i], order[i + 1]
            city1, city2 = self.citys[index1], self.citys[index2]
            distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
        return distance

這個(gè)是距離計(jì)算函數(shù)，沒什么好說的。

    def run(self, n=0):
        while n > 0:
            self.ga.next()
            distance = self.distance(self.ga.best.gene)
            print(self.ga.best.gene)
            print(("%d : %f") % (self.ga.generation-1, distance))
            n -= 1

這是整個(gè)代碼的核心關(guān)鍵，self.ga.next()即實(shí)現(xiàn)通過遺傳變異以及接受上一代最優(yōu)秀的個(gè)體組合形成下一代。n是迭代次數(shù)，我取的是100，即循環(huán)迭代一百次以尋求最優(yōu)個(gè)體。最后將最有個(gè)體輸出，并將該個(gè)體存儲(chǔ)在全局?jǐn)?shù)組中。

 def mappath(self):
        citylon1 = []
        citylat1 = []
        citylon2 = []
        citylat2 = []

        for i in self.bestcityorder:
            temp = i[0]
            i[0] = i[1]
            i[1] = temp
        # create new figure, axes instances.
        fig = plt.figure()
        ax = fig.add_axes([0, 0, 1, 1])

        # setup mercator map projection.
        m = Basemap(llcrnrlon=73.33, llcrnrlat=14.01, urcrnrlon=138.16, urcrnrlat=54.123, resolution='i',
                    projection='merc', lat_0=42.5, lon_0=120)
        # nylat, nylon are lat/lon of New York
        for i in self.bestcityorder:
            citylon1.append(i[0])
            citylat1.append(i[1])
        for i in range(len(self.bestcityorder)):
            if i == len(self.bestcityorder)-1:
                citylon2.append(self.bestcityorder[0][0])
                citylat2.append(self.bestcityorder[0][1])
            else:
                citylon2.append(self.bestcityorder[i + 1][0])
                citylat2.append(self.bestcityorder[i + 1][1])

        x, y = m(citylon1, citylat1)
        m.scatter(x, y, marker='D', color='m')


        # draw great circle route between NY and London
        for i in range(len(self.bestcityorder)):
            lon1 = citylon1[i]
            lat1 = citylat1[i]
            lon2 = citylon2[i]
            lat2 = citylat2[i]
            m.drawgreatcircle(lon1, lat1, lon2, lat2, linewidth=2, color='r')
        m.drawcoastlines()
        m.readshapefile('CHN_adm_shp/CHN_adm1', 'comarques', drawbounds=True)
        #m.fillcontinents()
        m.drawcountries()
        # draw parallels
        m.drawparallels(np.arange(10, 90, 20), labels=[1, 1, 0, 1])
        # draw meridians
        m.drawmeridians(np.arange(-180, 180, 30), labels=[1, 1, 0, 1])
        ax.set_title('Great Circle the shortest path')
        plt.show()

這個(gè)可以說是最長(zhǎng)的一個(gè)函數(shù)了，其實(shí)它很簡(jiǎn)單，因?yàn)閎asemap畫地圖比較繁雜，所以代碼也顯得比較冗余。它實(shí)現(xiàn)了先在中國地圖上用散點(diǎn)圖函數(shù)標(biāo)出34個(gè)城市，在利用傳遞過來的全局?jǐn)?shù)組將里面的城市一個(gè)一個(gè)連起來。

大功告成，python是不是很簡(jiǎn)單？

可改進(jìn)的地方

這個(gè)程序肯定不夠?qū)嵱?，畢竟它?jì)算的是直線距離。所以下一步我打算調(diào)用百度地圖API爬取鐵路數(shù)據(jù)，這個(gè)工程比較浩大，敬請(qǐng)期待哦～

大家也可以嘗試一下，體驗(yàn)一把將代碼融入生活的樂趣。

需要源碼可以私信我，不要做伸手黨，點(diǎn)個(gè)贊再來哦～