目錄
前言
編碼初始化種群
計(jì)算適應(yīng)度
選擇
交叉
變異
完整代碼
總結(jié)
前言
這次的算法有一點(diǎn)不能確定是否正確，希望有大佬能夠批評(píng)指正。
遺傳算法的一般步驟
編碼初始化種群
種群（population）指同一時(shí)間生活在一定自然區(qū)域內(nèi)，同種生物的所有個(gè)體。
所以種群是由個(gè)體組成的，所以先需要得到個(gè)體，然后再隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體。
在本算法中個(gè)體采用的是實(shí)數(shù)編碼（表示城市的編號(hào)，對(duì)應(yīng)列表的下標(biāo)，按照順序就是在城市之間的移動(dòng)路線）。
先對(duì)城市的位置進(jìn)行初始化，采用的是用列表來(lái)表示城市的坐標(biāo)，可以單個(gè)定義，也可以隨機(jī)生成。
先生成一串有序的數(shù)字用來(lái)表示城市的編號(hào)，再每次隨機(jī)進(jìn)行打亂后儲(chǔ)存到pop列表中，pop表示種群，里面裝著的是列表用來(lái)表示個(gè)體。（個(gè)體表示城市的編號(hào)，種群表示編號(hào)打亂后所有個(gè)體的集合）
群體規(guī)模太小，不能提供足夠的采樣點(diǎn),以致算法性能很差，易陷入局部最優(yōu)解。
群體規(guī)模太大，盡管可以增加優(yōu)化信息,阻止早熟收斂的發(fā)生,但無(wú)疑會(huì)增加計(jì)算量,造成收斂時(shí)間太長(zhǎng),表現(xiàn)為收斂速度緩慢。
City_Map = 100 * np.random.rand(20, 2) # 隨機(jī)產(chǎn)生20個(gè)城市（20行2列，數(shù)值乘以100)
DNA_SIZE = len(City_Map) # 編碼長(zhǎng)度（返回行的個(gè)數(shù))
POP_SIZE = 100 # 種群大小
# 生成初代種群pop
pop = []
list = list(range(DNA_SIZE)) # 生成[0,DNA_SIZE)的列表
for i in range(POP_SIZE): # POP_SIZE是指種群大小，在程序中是一個(gè)固定的值(打亂POP_SIZE次之后把結(jié)果儲(chǔ)存到pop列表中
random.shuffle(list) # 隨機(jī)打亂list，進(jìn)行初始化操作
l = list.copy() # 把list中的數(shù)據(jù)拷貝到l中
pop.append(l) # 將l添加到pop列表中計(jì)算適應(yīng)度
適應(yīng)度函數(shù)值只能是正值，越大越好。
DNA表示個(gè)體，根據(jù)個(gè)體的值（表示城市的編號(hào)）來(lái)計(jì)算距離。
旅行商問(wèn)題要求距離越短越好，所以距離越大越不滿足要求，故而可以通過(guò)對(duì)距離求倒數(shù)來(lái)表示適應(yīng)度。
在最后減去適應(yīng)度最小的值，可以保證適應(yīng)度都為正值。（如果有負(fù)數(shù)，減去一個(gè)更小的負(fù)數(shù)，會(huì)變成正值）
適應(yīng)度表示的是個(gè)體對(duì)種群的適應(yīng)程度，distance函數(shù)返回的是按照pop[i]路線計(jì)算出來(lái)的路徑距離大小，故而getfitness函數(shù)返回的列表表示的是每一個(gè)個(gè)體pop[i]通過(guò)distance函數(shù)計(jì)算出來(lái)距離的倒數(shù)歸一化（減去最小的距離的倒數(shù)）之后的結(jié)果。
distance求出來(lái)的距離不是兩個(gè)城市之間的距離，而是某條路線經(jīng)過(guò)城市的距離之和（是所有的距離）。
def distance(DNA): # 根據(jù)DNA的路線計(jì)算距離
dis = 0
temp = City_Map[DNA[0]]
for i in DNA[1:]:
# sqrt(pow(x-x0,2)+pow(y-y0,2))
dis = dis + ((City_Map[i][0] - temp[0]) ** 2 + (City_Map[i][1] - temp[1]) ** 2) ** 0.5
temp = City_Map[i]
return dis + ((temp[0] - City_Map[DNA[0]][0]) ** 2 + (temp[1] - City_Map[DNA[0]][1]) ** 2) ** 0.5
def getfitness(pop): # 計(jì)算種群適應(yīng)度，這里適應(yīng)度用距離的倒數(shù)表示
temp = []
for i in range(len(pop)):
temp.append(1 / (distance(pop[i])))
# 減去最小值是為了防止適應(yīng)度出現(xiàn)負(fù)值
return temp - np.min(temp)選擇
選擇操作也稱為復(fù)制（ reproduction） 操作：從當(dāng)前群體中按照一定概率選出優(yōu)良的個(gè)體， 使它們有機(jī)會(huì)作為父代繁殖下一代子孫。
判斷個(gè)體優(yōu)良與否的準(zhǔn)則是各個(gè)個(gè)體的適應(yīng)度值：個(gè)體適應(yīng)度越高， 其被選擇的機(jī)會(huì)就越多。
在程序中個(gè)體的選擇方法采用的是輪盤賭的方法：
按個(gè)體的選擇概率產(chǎn)生一個(gè)輪盤，輪盤每個(gè)區(qū)的角度與個(gè)體的選擇概率成比例。
產(chǎn)生一個(gè)隨機(jī)數(shù)， 它落入轉(zhuǎn)盤的哪個(gè)區(qū)域就選擇相應(yīng)的個(gè)體交叉。
適應(yīng)度的小的個(gè)體也有可能被選中。
def select(pop, fitness): # 根據(jù)適應(yīng)度選擇，以賭輪盤的形式，適應(yīng)度越大的個(gè)體被選中的概率越大
# print(fitness)
s = fitness.sum()
# np.random.choice(a,size,replace,p=None)隨機(jī)抽取樣本a,表示范圍，replace=True被抽中后仍有機(jī)會(huì)被再次抽中，p沒(méi)抽中的概率
temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True, p=(fitness / s))
p = []
for i in temp:
p.append(pop[i])
return p交叉
程序中交叉采用部分匹配交叉，如果直接采用兩點(diǎn)交叉會(huì)導(dǎo)致一個(gè)個(gè)體中出現(xiàn)兩個(gè)重復(fù)的城市，顯然是和題目要求是不符合的。
部分匹配交叉保證了每個(gè)染色體中的基因僅出現(xiàn)一次，通過(guò)該交叉策略在一個(gè)染色體中不會(huì)出現(xiàn)重復(fù)的基因，所以部分匹配交叉經(jīng)常用于旅行商（TSP）或其他排序問(wèn)題編碼。部分匹配交叉類似于兩點(diǎn)交叉，通過(guò)隨機(jī)選擇兩個(gè)交叉點(diǎn)確定交叉區(qū)域。執(zhí)行交叉后一般會(huì)得到兩個(gè)無(wú)效的染色體，個(gè)別基因會(huì)出現(xiàn)重復(fù)的情況，為了修復(fù)染色體，可以在交叉區(qū)域內(nèi)建立每個(gè)染色體的匹配關(guān)系，然后在交叉區(qū)域外對(duì)重復(fù)基因應(yīng)用此匹配關(guān)系就可以消除沖突。
交叉概率太大時(shí),種群中個(gè)體更新很快,會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉;
概率太小時(shí),交叉操作很少進(jìn)行,從而會(huì)使搜索停滯不前,造成算法的不收斂。
def crossmuta(pop, CROSS_RATE): # 交叉變異
new_pop = []
for i in range(len(pop)): # 遍歷種群中的每一個(gè)個(gè)體，將該個(gè)體作為父代
n = np.random.rand()
if n >= CROSS_RATE: # 大于交叉概率時(shí)不發(fā)生變異，該子代直接進(jìn)入下一代
temp = pop[i].copy()
new_pop.append(temp) # 直接進(jìn)行拷貝
if n < CROSS_RATE: # 小于交叉概率時(shí)發(fā)生變異
list1 = pop[i].copy()
list2 = pop[np.random.randint(POP_SIZE)].copy() # 選取種群中另一個(gè)個(gè)體進(jìn)行交叉(隨機(jī)選擇)
status = True
while status: # 產(chǎn)生2個(gè)不相等的節(jié)點(diǎn)，中間部分作為交叉段，采用部分匹配交叉(直到k1<k2的時(shí)候才會(huì)跳出循環(huán))
k1 = random.randint(0, len(list1) - 1)
k2 = random.randint(0, len(list2) - 1)
if k1 < k2:
status = False
k11 = k1 # 保存切片起始的下標(biāo)
# 先對(duì)部分片段進(jìn)行切片，把切片出來(lái)的內(nèi)容進(jìn)行交換（完全交換)
fragment1 = list1[k1: k2]
fragment2 = list2[k1: k2]
list1[k1: k2] = fragment2
list2[k1: k2] = fragment1
del list1[k1: k2] # 刪除list1中[k1,k2)的內(nèi)容
left1 = list1
# 進(jìn)行部分匹配的交叉
offspring1 = []#后代
#對(duì)left1中的每一個(gè)位置pos遍歷
for pos in left1:
#檢查它是否存在于frag2中
if pos in fragment2:
#從fragment1中找到對(duì)應(yīng)的基因
pos = fragment1[fragment2.index(pos)]
#直到基因不再fragment2中為止（遍歷fragment2，確保每一個(gè)基因都和pos不同)
while pos in fragment2:
pos = fragment1[fragment2.index(pos)]
offspring1.append(pos)
continue
#如何pos不存在fragment2中，那么就直接將其添加到新的后代中
offspring1.append(pos)
# 插入新片段
for i in range(0, len(fragment2)):
offspring1.insert(k11, fragment2[i])
k11 += 1
temp = offspring1.copy()
mutation(temp, MUTA_RATE) # 進(jìn)行變異
new_pop.append(temp) # 把部分匹配交叉后形成的合法個(gè)體加入到下一代種群
return new_pop變異
互換變異：隨機(jī)選取染色體的兩個(gè)基因進(jìn)行簡(jiǎn)單互換。
采用隨機(jī)的形式，在[0,DNA_SIZE)的范圍內(nèi)生成兩個(gè)下標(biāo)（確保兩個(gè)位置不一致），在將兩個(gè)位置上面的值進(jìn)行交換。
變異概率太小則很難產(chǎn)生新模式,變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。
def mutation(DNA, MUTA_RATE): # 進(jìn)行變異
# 兩點(diǎn)變異
if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率進(jìn)行變異
mutate_point1 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置
mutate_point2 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置
while (mutate_point1 == mutate_point2): # 保證2個(gè)所選位置不相等
mutate_point2 = np.random.randint(0, DNA_SIZE) #如果相等將mutate_point2重新進(jìn)行隨機(jī)生成位置
DNA[mutate_point1], DNA[mutate_point2] = DNA[mutate_point2], DNA[mutate_point1] # 2個(gè)所選位置進(jìn)行互換
逆轉(zhuǎn)變異：在個(gè)體碼串中隨機(jī)選擇兩點(diǎn)（ 逆轉(zhuǎn)點(diǎn)） ，然后將兩點(diǎn)之間的基因值以逆向排序插入到原位置中。
隨機(jī)生成兩個(gè)下標(biāo)，如x1，x2（確保x1<x2），對(duì)列表進(jìn)行[x1,x2)的切片，在原始的列表中刪除切片的部分，將切片的部分翻轉(zhuǎn)之后添加到原始的位置。
def mutation(DNA, MUTA_RATE): # 進(jìn)行變異
# 逆轉(zhuǎn)變異
if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率進(jìn)行變異
status = True
while status: # 產(chǎn)生2個(gè)不相等的節(jié)點(diǎn)，中間部分作為交叉段，采用部分匹配交叉(直到mutate_point1<mutate_point2的時(shí)候才會(huì)跳出循環(huán))
mutate_point1 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因片段的起始的位置
mutate_point2 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因片段的結(jié)束的位置
if mutate_point1 < mutate_point2:
status = False
k1 = mutate_point1 # 保存切片起始的下標(biāo)
temp = DNA[mutate_point1:mutate_point2] # 把需要逆轉(zhuǎn)的片段先提取出來(lái)
del DNA[mutate_point1:mutate_point2] # 先暫時(shí)刪除這段片段
temp.reverse() # 反轉(zhuǎn)基因序列
# 插入翻轉(zhuǎn)后的新片段
for i in range(0, len(temp)):
DNA.insert(k1, temp[i])
k1 += 1
插入變異：在個(gè)體碼串中隨機(jī)選擇一個(gè)碼， 然后將此碼插入隨機(jī)選擇的插入點(diǎn)中間。
隨機(jī)生成兩個(gè)實(shí)數(shù)，這次不是交換，是插入的方式，也就是插入點(diǎn)之后的元素的位置都會(huì)發(fā)生改變。
def mutation(DNA, MUTA_RATE): # 進(jìn)行變異
#插入變異
if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率進(jìn)行變異
mutate_point1 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置（選中一個(gè)基因）
mutate_point2 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置（插入點(diǎn)）
while (mutate_point1 == mutate_point2): # 保證2個(gè)所選位置不相等
mutate_point2 = np.random.randint(0, DNA_SIZE)
temp=DNA[mutate_point1]#先保存mutate_point1對(duì)應(yīng)的值
del DNA[mutate_point1]#刪除mutate_point1對(duì)應(yīng)的值
DNA.insert(mutate_point2,temp)#重新插入到列表中完整代碼
import time
import numpy as np
import random
import matplotlib.pyplot as plt
# 各個(gè)城市的坐標(biāo)
City_Map = 100 * np.random.rand(10, 2) # 隨機(jī)產(chǎn)生10個(gè)城市（10行2列，數(shù)值乘以100)
DNA_SIZE = len(City_Map) # 編碼長(zhǎng)度（返回行的個(gè)數(shù))
POP_SIZE = 100 # 種群大小
CROSS_RATE = 0.85 # 交叉率
MUTA_RATE = 0.15 # 變異率
Iterations = 500 # 迭代次數(shù)
def distance(DNA): # 根據(jù)DNA的路線計(jì)算距離
dis = 0
temp = City_Map[DNA[0]]
for i in DNA[1:]:
# sqrt(pow(x-x0,2)+pow(y-y0,2))
dis = dis + ((City_Map[i][0] - temp[0]) ** 2 + (City_Map[i][1] - temp[1]) ** 2) ** 0.5
temp = City_Map[i]
return dis + ((temp[0] - City_Map[DNA[0]][0]) ** 2 + (temp[1] - City_Map[DNA[0]][1]) ** 2) ** 0.5
def getfitness(pop): # 計(jì)算種群適應(yīng)度，這里適應(yīng)度用距離的倒數(shù)表示
temp = []
for i in range(len(pop)):
temp.append(1 / (distance(pop[i])))
# 減去最小值是為了防止適應(yīng)度出現(xiàn)負(fù)值
return temp - np.min(temp)
def select(pop, fitness): # 根據(jù)適應(yīng)度選擇，以賭輪盤的形式，適應(yīng)度越大的個(gè)體被選中的概率越大
# print(fitness)
s = fitness.sum()
# np.random.choice(a,size,replace,p=None)隨機(jī)抽取樣本a,表示范圍，replace=True被抽中后仍有機(jī)會(huì)被再次抽中，p沒(méi)抽中的概率
temp = np.random.choice(np.arange(len(pop)), size=POP_SIZE, replace=True, p=(fitness / s))
p = []
for i in temp:
p.append(pop[i])
return p
def mutation(DNA, MUTA_RATE): # 進(jìn)行變異
# 兩點(diǎn)變異
if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率進(jìn)行變異
mutate_point1 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置
mutate_point2 = np.random.randint(0, DNA_SIZE) # 隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，代表要變異基因的位置
while (mutate_point1 == mutate_point2): # 保證2個(gè)所選位置不相等
mutate_point2 = np.random.randint(0, DNA_SIZE) #如果相等將mutate_point2重新進(jìn)行隨機(jī)生成位置
DNA[mutate_point1], DNA[mutate_point2] = DNA[mutate_point2], DNA[mutate_point1] # 2個(gè)所選位置進(jìn)行互換
def crossmuta(pop, CROSS_RATE): # 交叉變異
new_pop = []
for i in range(len(pop)): # 遍歷種群中的每一個(gè)個(gè)體，將該個(gè)體作為父代
n = np.random.rand()
if n >= CROSS_RATE: # 大于交叉概率時(shí)不發(fā)生變異，該子代直接進(jìn)入下一代
temp = pop[i].copy()
new_pop.append(temp) # 直接進(jìn)行拷貝
if n < CROSS_RATE: # 小于交叉概率時(shí)發(fā)生變異
list1 = pop[i].copy()
list2 = pop[np.random.randint(POP_SIZE)].copy() # 選取種群中另一個(gè)個(gè)體進(jìn)行交叉(隨機(jī)選擇)
status = True
while status: # 產(chǎn)生2個(gè)不相等的節(jié)點(diǎn)，中間部分作為交叉段，采用部分匹配交叉(直到k1<k2的時(shí)候才會(huì)跳出循環(huán))
k1 = random.randint(0, len(list1) - 1)
k2 = random.randint(0, len(list2) - 1)
if k1 < k2:
status = False
k11 = k1 # 保存切片起始的下標(biāo)
# 先對(duì)部分片段進(jìn)行切片，把切片出來(lái)的內(nèi)容進(jìn)行交換（完全交換)
fragment1 = list1[k1: k2]
fragment2 = list2[k1: k2]
list1[k1: k2] = fragment2
list2[k1: k2] = fragment1
del list1[k1: k2] # 刪除list1中[k1,k2)的內(nèi)容
left1 = list1
# 進(jìn)行部分匹配的交叉
offspring1 = []#后代
#對(duì)left1中的每一個(gè)位置pos遍歷
for pos in left1:
#檢查它是否存在于frag2中
if pos in fragment2:
#從fragment1中找到對(duì)應(yīng)的基因
pos = fragment1[fragment2.index(pos)]
#直到基因不再fragment2中為止（遍歷fragment2，確保每一個(gè)基因都和pos不同)
while pos in fragment2:
pos = fragment1[fragment2.index(pos)]
offspring1.append(pos)
continue
#如何pos不存在fragment2中，那么就直接將其添加到新的后代中
offspring1.append(pos)
# 插入新片段
for i in range(0, len(fragment2)):
offspring1.insert(k11, fragment2[i])
k11 += 1
temp = offspring1.copy()
mutation(temp, MUTA_RATE) # 進(jìn)行變異
new_pop.append(temp) # 把部分匹配交叉后形成的合法個(gè)體加入到下一代種群
return new_pop
def print_info(pop): # 用于輸出結(jié)果
fitness = getfitness(pop)
maxfitness = np.argmax(fitness) # 得到種群中最大適應(yīng)度個(gè)體的索引
# 打印結(jié)果
print("最優(yōu)的基因型：", pop[maxfitness])
print("最短距離：", distance(pop[maxfitness]))
# 按最優(yōu)結(jié)果順序把地圖上的點(diǎn)加入到best_map列表中
best_map = []
for i in pop[maxfitness]:
best_map.append(City_Map[i])
best_map.append(City_Map[pop[maxfitness][0]])
X = np.array((best_map))[:, 0]
Y = np.array((best_map))[:, 1]
# 繪制地圖以及路線
plt.figure()
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.scatter(X, Y)
for dot in range(len(X) - 1):
plt.annotate(pop[maxfitness][dot], xy=(X[dot], Y[dot]), xytext=(X[dot], Y[dot]))
plt.annotate('start', xy=(X[0], Y[0]), xytext=(X[0] + 1, Y[0]))
plt.plot(X, Y)
if __name__ == "__main__": # 主循環(huán)
# 生成初代種群pop
pop = []
list = list(range(DNA_SIZE)) # 生成[0,DNA_SIZE)的列表
for i in range(POP_SIZE): # POP_SIZE是指種群大小，在程序中是一個(gè)固定的值(打亂POP_SIZE次之后把結(jié)果儲(chǔ)存到pop列表中
random.shuffle(list) # 隨機(jī)打亂list，進(jìn)行初始化操作
l = list.copy() # 把list中的數(shù)據(jù)拷貝到l中
pop.append(l) # 將l添加到pop列表中
best_dis = []
# 最好適應(yīng)度
#goodFitness = 0
# 最差適應(yīng)度（如果進(jìn)行歸一化處理之后，適應(yīng)度都減去最小值，那么他的最差適應(yīng)度不都就是0了)
#chaFitness = 0
# 總體適應(yīng)度
#sumFitness = 0
# 所有數(shù)量
#sumCount = 0
# 平均適應(yīng)度
#averageFitness = 0
# 獲取當(dāng)前時(shí)間(算法開始時(shí)間)
start_time = time.time()
# 進(jìn)行選擇，交叉，變異，并把每代的最優(yōu)個(gè)體保存在best_dis中
for i in range(Iterations): # 迭代N代
pop = crossmuta(pop, CROSS_RATE) # CROSS_RATE交叉率
fitness = getfitness(pop) # 得到適應(yīng)度種群的適應(yīng)度
# 更新最差適應(yīng)度
# print(np.min(fitness))
tmpfitness = np.max(fitness)
# 更新最好適應(yīng)度
#if tmpfitness > goodFitness:
# goodFitness = tmpfitness
# print(goodFitness)
# 記錄所有適應(yīng)度的值
#sumFitness = np.sum(fitness) + sumFitness
# 記錄所有適應(yīng)度的個(gè)數(shù)
#sumCount = sumCount + np.size(fitness)
maxfitness = np.argmax(fitness) # 返回?cái)?shù)值最大的索引
best_dis.append(distance(pop[maxfitness]))
pop = select(pop, fitness) # 選擇生成新的種群（適應(yīng)度最大的)
print("iteration", i)
#averageFitness = sumFitness / sumCount
# 獲取當(dāng)前時(shí)間(算法結(jié)束時(shí)間)
end_time = time.time()
print_info(pop) # 打印信息
print('逐代的最小距離：', best_dis)
#print(f'最好適應(yīng)度：{goodFitness:.4f}')
#print(f'最差適應(yīng)度：{chaFitness:.4f}')
#print(f'平均適應(yīng)度：{averageFitness:.4f}')
print(f'程序運(yùn)行時(shí)間：{(end_time - start_time):.4f}秒')
#print(pop)
# 畫圖
plt.figure()
plt.plot(range(Iterations), best_dis)
plt.show()
plt.close()
參考信息
遺傳算法入門詳解 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/100337680遺傳算法python進(jìn)階理解+論文復(fù)現(xiàn)（純干貨，附前人總結(jié)引路）_python神經(jīng)網(wǎng)絡(luò)遺傳算法_不想禿頭的夜貓子的博客-CSDN博客https://blog.csdn.net/golden_knife/article/details/128510731通俗易懂地解釋遺傳算法 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/136393730遺傳算法解決旅行商問(wèn)題（詳細(xì)解釋+代碼分享） - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/344588977用遺傳算法求解旅行商問(wèn)題_中國(guó)旅行商問(wèn)題,34個(gè)省會(huì)-CSDN博客https://blog.csdn.net/breeze_blows/article/details/102992997遺傳算法（三）——適應(yīng)度與選擇_遺傳算法適應(yīng)度函數(shù)-CSDN博客https://blog.csdn.net/weixin_30239361/article/details/101540896
總結(jié)
這個(gè)最好適應(yīng)度，最差適應(yīng)度以及平均適應(yīng)度的概念沒(méi)完全掌握，不知道是不是這一個(gè)意思，所以在程序中注釋了，大家可以根據(jù)自己的理解來(lái)添加。
我理解到的：
最好適應(yīng)度就是每一次的迭代都會(huì)有一個(gè)適應(yīng)度最高的個(gè)體，把每一代適應(yīng)度最高的個(gè)體進(jìn)行比較選出最大的那個(gè)，得到的就是整體適應(yīng)度最好的。
最差適應(yīng)度就是0，因?yàn)槊恳淮味歼M(jìn)行了歸一化操作。
平均適應(yīng)度就是保存每一代的適應(yīng)度以及個(gè)體的數(shù)量，最后進(jìn)行求平均值。
運(yùn)行時(shí)間就是在算法運(yùn)行前記錄當(dāng)前系統(tǒng)的時(shí)間，算法運(yùn)行后記錄當(dāng)前系統(tǒng)的時(shí)間，所形成的差值（運(yùn)行后-運(yùn)行前）就是程序運(yùn)行的時(shí)間。
適應(yīng)度因?yàn)椴捎玫氖蔷嚯x的倒數(shù)，加上還進(jìn)行了歸一化的處理，隨機(jī)生成城市的的坐標(biāo)*100，導(dǎo)致兩點(diǎn)之間的距離較大，如果想得到較大一點(diǎn)的適應(yīng)度，可以縮小城市之間的距離。
City_Map = 100 * np.random.rand(20, 2)
改
City_Map =? np.random.rand(20, 2)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-817720.html
遺傳算法的思路是“適者生存，優(yōu)勝劣汰”，模擬生物的進(jìn)化，以一個(gè)初始生物群體為起點(diǎn)，經(jīng)過(guò)競(jìng)爭(zhēng)后，一部分個(gè)體被淘汰而無(wú)法再進(jìn)入這個(gè)循環(huán)圈，而另一部分則勝出成為種群。對(duì)于算法的選擇的個(gè)體，適應(yīng)度高的并不一定進(jìn)入種群，只是進(jìn)入種群的可能性比較大；而適應(yīng)度低的個(gè)體并不一定被淘汰，只是進(jìn)入種群的可能性比較小，模擬生物進(jìn)化的過(guò)程。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-817720.html
到了這里，關(guān)于遺傳算法求解旅行商問(wèn)題（含python源代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
