目錄
1.遺傳算法簡要介紹
2.tsp問題簡要介紹
3.遺傳算法解決tsp問題的幾個特殊點
4.源碼
1.遺傳算法簡要介紹
????????簡單來說，遺傳算法是用于解決最優(yōu)化問題的一種搜索算法。其核心基于自然界種群進化的規(guī)律，即初始種群進行交配，在基因?qū)用嫔希渲袝l(fā)生交叉互換、基因突變等變異，產(chǎn)生新一批的種群，在種群不斷繁衍的過程中，“適者生存，不適者滅亡”，更符合環(huán)境要求的個體的基因保留下來的可能性更大，不適應(yīng)環(huán)境的個體的基因往往不會延續(xù)下去。漫長的時間后，會篩選出一批最適應(yīng)環(huán)境的種群。
? ? ? ? 基于此，當我們在解決最優(yōu)化問題時，采取上述思想，將問題的解看作是“個體”，這些個體組成一個抽象的“種群”，這些解被映射成為相應(yīng)的編碼，于是我們就能得到由各種編碼組成的“種群”。這些編碼可以進行片段的交叉互換，或者其中某些數(shù)字發(fā)生“基因突變”，從而進行種群的更新。那么如何篩選更合適的個體呢？根據(jù)實際的需要與限制，我們基于編碼，通過特定的函數(shù)，計算出每個個體的“適應(yīng)度”，適應(yīng)度更大的個體的基因（編碼）被選中并保留下來的概率更大。這樣經(jīng)過上百次迭代后，就能得到一個接近最優(yōu)解的一個種群。
? ? ? ? 詳細的介紹大家可以參照這篇文章遺傳算法詳解 附python代碼實現(xiàn)_重學(xué)CS的博客-CSDN博客_python遺傳算法?，文章作者將一般公式的最優(yōu)化講解到令人發(fā)指的詳細與通俗易懂。如果能將這篇文章掌握，基本上可以通過遺傳算法，求任何公式（n元n次方程）的最值。其中的內(nèi)涵是將解從十進制數(shù)字映射成為二進制串，這其中的編碼與解碼過程很重要。
? ? ? ? 在這里就不展開敘述更多細節(jié)了，上面那篇文章講的很清楚，本篇重點在于解決tsp問題。
2.tsp問題簡要介紹
? ? ? ? 根據(jù)百度百科的介紹，t旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
3.遺傳算法解決tsp問題的幾個特殊點
這也是本篇的重點
3.1如何編碼
首先要明白我們解的形式是什么，我們需要得到一條距離最短的路徑。因此將這些城市編碼（0、1、2........n），以10座城市為例，我們希望得到的解或許是3 5 4 8 6 7 9 0 2 1，因此，在遺傳算法中，每個個體的形式就應(yīng)該是10個不重復(fù)數(shù)字的排列。好消息是這樣一來不需要進行二進制編碼解碼了。
#初始化種群
def generate_population(self):
path=np.array(range(self.num))
self.pop=[]
for i in range(self.size_pop):
x=path.copy()
np.random.shuffle(x) #隨機洗牌
self.pop.append(x)3.2距離矩陣的建立
我們該如何評價一個解的適應(yīng)度？顯然我們希望每個個體的路徑距離越小越好，所以我們需要先得到每座城市之間的距離，將其記錄在一個矩陣當中，當后續(xù)需要求一條完整路徑的距離時，任意兩點的距離可以直接轉(zhuǎn)化為坐標（比如說，(2,6)）從這個矩陣中取出。
3.3交叉互換
如果直接確定一條染色體上的一個位置，將父本母本從這個位置開始直接交叉互換，這顯然是不合理的，假如父本是 1 3 2 4，母本是 2 4 1 3，兩者正好在中點切割進行交叉互換后的子代分別是1 3 1 3和 2 4 2 4，這顯然是錯誤的！旅行商每座城市只能經(jīng)過一次！所以在交換染色體片段的時候，必須要經(jīng)過一個操作，就是去除重復(fù)堿基對。
TSP、MTSP問題遺傳算法詳細解讀及python實現(xiàn)，這篇文章的博主給出了tsp問題遺傳算法交叉互換的三種方式，這里我們選擇第二種?
Order Crossover（順序交叉）
??
3.4基因突變
在二進制編碼的情況下，要想完成基因突變，只需要將選中的染色體隨機替換掉一個堿基對即可。但是在tsp問題中，如果這樣做，一定會導(dǎo)致被選中染色體堿基對的重復(fù)！因此我們需要做的是將被選中染色體的任意兩堿基對進行互換，這樣就避免了重復(fù)
3.5適應(yīng)度計算
我們該如何評價一個個體的基因是否適合被遺傳下來呢？這就需要計算個體的適應(yīng)度，適應(yīng)度越高的個體，被選擇的概率就越大。在tsp問題中，我們希望一個個體的路徑長度越短越好，即路徑越短，適應(yīng)度越大，在這里，采用文章基于遺傳算法求解TSP問題（旅游路徑規(guī)劃，Python實現(xiàn)，超詳細，可視化，結(jié)果分析中的適應(yīng)度公式來計算適應(yīng)度
?
?適應(yīng)度越大的個體被選中的可能性越大，用numpy.choice來實現(xiàn)
idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,
p=(self.fitness)/(fitness_sum) )4.源碼
import numpy as np
class TSP:
def __init__(self, citys, maxgen=500,
size_pop=200, cross_rate=0.8,
muta_rate=0.005
):
self.maxgen = maxgen # 最大進化次數(shù)
self.size_pop = size_pop # 種群大?。ㄈ旧w個數(shù)）
self.cross_rate = cross_rate # 交叉概率
self.muta_rate = muta_rate # 變異概率
self.citys = citys # 城市的坐標數(shù)據(jù)
self.num = citys.shape[0] # 城市的個數(shù)(染色體長度)
#獲得距離矩陣
def matrix_distance(self):
self.distance_m=np.zeros((self.num,self.num))
for i in range(self.num):
for j in range(self.num):
self.distance_m[i][j]=np.sqrt((self.citys[i][0]-self.citys[j][0])**2+(self.citys[i][1]-self.citys[j][1])**2)
#計算某條路徑的距離
def get_total_distance(self,one_path):
distance=0
for i in range(self.num-1):
distance +=self.distance_m[one_path[i]][one_path[i+1]]
distance += self.distance_m[one_path[-1]][one_path[0]]
return distance
#初始化種群
def generate_population(self):
path=np.array(range(self.num))
self.pop=[]
for i in range(self.size_pop):
x=path.copy()
np.random.shuffle(x) #隨機洗牌
self.pop.append(x)
#交叉互換
def crossover(self):
self.new_pop=[]
for father in self.pop:
child=father #初步讓子代獲得父本染色體
if np.random.rand()<self.cross_rate:
#隨機選擇一個染色體作為母本
mother_index = np.random.randint(0, self.size_pop)
mother=self.pop[mother_index]
#確定切割點
left = np.random.randint(0, self.num-2)
right = np.random.randint(left + 1, self.num-1)
mother=mother.tolist()
father=father.tolist()
#切割片段
gene = mother[left:right]
child1_c = father[right:]+father[:right]
child1 = child1_c.copy()
#去除重復(fù)基因
for o in gene:
child1_c.remove(o)
child1[left:right] = gene
child1[right:] = child1_c[0:len(child1) - right]
child1[:left] = child1_c[(len(child1) - right):]
child=np.array(child1)
self.new_pop.append(child)
self.pop=self.new_pop
#變異
def mutation(self):
for i in range(self.size_pop):
if np.random.rand() < self.muta_rate:
child = self.pop[i]
u = np.random.randint(0,self.num - 2)
v = np.random.randint(u+1,self.num- 1)
child_x = child[u+1:v]
child_x=child_x[::-1]
child = np.concatenate((child[0:u+1] , child_x , child[v:]))
self.pop[i]=child
#自然選擇，種群根據(jù)適應(yīng)度進行更新
def select(self):
#計算每條路徑的長度，放入列表
self.dis=[]
for i in range(self.size_pop):
self.dis.append(self.get_total_distance(one_path=self.pop[i]))
#根據(jù)路徑長度計算每個個體的適應(yīng)度
self.fitness=[]
for i in range(self.size_pop):
self.fitness.append(1/(self.dis[i]**15))
#適應(yīng)度總和
fitness_sum=0
for i in range(self.size_pop):
fitness_sum+=self.fitness[i]
#根據(jù)適應(yīng)度進行選擇，適應(yīng)度大的被選擇概率大
idx = np.random.choice(np.arange(self.size_pop), size=self.size_pop, replace=True,
p=(self.fitness)/(fitness_sum) )
self.new_pop=[]
for i in idx:
self.new_pop.append(self.pop[i])
self.pop=self.new_pop
#輸出當前種群中最優(yōu)路徑
def result_path(self):
self.index=np.argmax(self.fitness)
a="the shortest path is:"
for i in range(self.num-1):
a+=str(self.pop[self.index][i])
a+="-->"
a+=str(self.pop[self.index][-1])
print(a)
print("the total distance is",self.dis[self.index])
#主函數(shù)進行迭代
def main(citys):
SL=TSP(citys)
SL.matrix_distance()
SL.generate_population()
for i in range (SL.maxgen):
SL.crossover()
SL.mutation()
SL.select()
SL.result_path()
if __name__ == '__main__':
citys = 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]])
main(citys)
結(jié)果分析
如果每一次迭代都輸出結(jié)果，可以清楚地看到路徑最終都收斂。事實上，每次收斂的結(jié)果與種群大小size_pop息息相關(guān)，一開始我將種群大小設(shè)置為?200，結(jié)果每次運行雖然收斂，但是得到的結(jié)果各不相同，基本上毫無關(guān)聯(lián)，說明結(jié)果陷入了局部最優(yōu)解，而非全局最優(yōu)解。解決方法就是把size_pop設(shè)置為500，才使得結(jié)果誤差較小，趨近于全局最優(yōu)解。
事實上，要想使結(jié)果更直觀，最好用坐標圖使結(jié)果可視化，將路線顯示出來。本文僅僅展示了數(shù)字結(jié)果，這樣有兩個問題，一是可能起始城市不同，如8 2 3 6 和 2 3 6 8，二是順序不同，如8 2 3 6和 6 3 2 8，其實結(jié)果的路線本質(zhì)是一樣的，但直觀看上去不利于結(jié)果統(tǒng)計。
參考文章：
http://t.csdn.cn/eJZmK
http://t.csdn.cn/0fYtK
http://t.csdn.cn/VFPLr文章來源：http://www.zghlxwxcb.cn/news/detail-411383.html
http://t.csdn.cn/2oWZt文章來源地址http://www.zghlxwxcb.cn/news/detail-411383.html
到了這里，關(guān)于遺傳算法解決tsp問題（基于python）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
