從本節開始，如果發現裡面的代碼已經看不懂了，沒關係，直接拖到文章的最後，有彩蛋……
問題說明TSM （旅行商問題(Travelling SalesMan problem)）在算法界是一個非常出名的問題，特別是在GIS界就更出名了。
簡單來說，Travelling Salesman Problem (TSP) 是最基本的路線規劃問題。它尋求的是旅行者由起點出發，通過所有給定的需求點後，再次返回起點，求在這個過程中，所花費的最小路徑成本。
這個問題後期加各種條件，比如是否有上山下山、不同的油料消耗，是不是有單行線等等，可以擴展為非常複雜的問題，但是原理上都是一樣的，下面我們來看個簡單的例子：
. . . . A . . .
. . B . . . . .
C . . . . . . .
. . . . . . H .
. D . . . . . .
. . . . . . . G
. . . . . F . .
. . . E . . . .上面這樣一批數據，我們設置行動的方式為直線，也就是不管行列，直接用幾何距離來計算，，比如F要到D，可以這樣走：
記錄的話，用一個二維數組來完成(左下角為原點坐標（0，0），比如：
A的坐標就是（x=4,y=7)
E的坐標就是（x=3,y=0)
類推
算法實現首先是初始化數據和最終結果：
idToLocationLookup = {
'A': [4, 7],
'B': [2, 6],
'C': [0, 5],
'D': [1, 3],
'E': [3, 0],
'F': [5, 1],
'G': [7, 2],
'H': [6, 4]}
optimalSequence = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']數據可視化結果先上面的示例。
如果要計算最短成本，所以就得有一個計算距離的函數：非常簡單的歐式距離計算方法。
def get_distance(locationA, locationB):
sideA = locationA[0] - locationB[0]
sideB = locationA[1] - locationB[1]
sideC = math.sqrt(sideA * sideA + sideB * sideB)
return sideC健壯性類和健壯性建議方法：健壯性檢驗方法就是累加經過的所有的點的距離，非常簡單，也就不解釋了。
class Fitness:
def __init__(self, totalDistance):
self.TotalDistance = totalDistance
def __gt__(self, other):
return self.TotalDistance < other.TotalDistance
def __str__(self):
return "{:0.2f}".format(self.TotalDistance)
def get_fitness(genes, idToLocationLookup):
fitness = get_distance(idToLocationLookup[genes[0]],
idToLocationLookup[genes[-1]])
for i in range(len(genes) - 1):
start = idToLocationLookup[genes[i]]
end = idToLocationLookup[genes[i + 1]]
fitness += get_distance(start, end)
return Fitness(round(fitness, 2))進化函數：非常簡單的過程：隨機交換兩個基因，然後對比健壯性是否有進步。
def mutate(genes, fnGetFitness):
count = random.randint(2, len(genes))
initialFitness = fnGetFitness(genes)
while count > 0:
count -= 1
indexA, indexB = random.sample(range(len(genes)), 2)
genes[indexA], genes[indexB] = genes[indexB], genes[indexA]
fitness = fnGetFitness(genes)
if fitness > initialFitness:
return前面十一節講遺傳算法的時候，講的都是直接對父本基因進行進化，也就是說，屬於生物遺傳裡面的無性繁殖，而且我們知道，無性繁殖一般比有性繁殖要低等。
到今天為止，我們從來沒有討論過遺傳算法裡面一個更加核心的內容：雜交。在真正的遺傳中，我們可以嘗試採用類似於雜交的方式來進行遺傳進化。
雜交的原理是利用兩個不同親本的特徵來創造新的子代。這個想法是每一個親本的基因都具有一部分的解，但它們都可能被卡在一個局部的最小或最大。所以，如果將兩者的隨機部分結合起來，可能會產生一個更好的解決方案。
在雜交的時候，有很多的注意事項和約束條件，比如不能是對基因進行簡單的複製，因為複製可能會導致健壯性變差，而浪費時間。比如在旅行商問題中，基因的組成是有所有的點形成的路線，所以我們在變化的時候，都是將這個路線打亂或者替換其中某一段，這樣帶來的效果可能會更好，也可能會更壞，但是一定不是簡單的複製。
所以我們在做雜交的時候，關鍵就在於如何更好的去實現這個進化的過程。
既然要做雜交，就最少需要兩個基因的來源——父本和母本。而以往算法裡面，都是只有一個父本，所以我們需要增加一個母本基因。
在算法中，我們採用「池化」技術，來實現雙親基因的來源，下面是我們常見的功能類，比如進化和迭代，看如下代碼中不一樣的地方：
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,
custom_mutate=None, custom_create=None, maxAge=None,
poolSize=1, crossover=None):
if custom_mutate is None:
def fnMutate(parent):
return _mutate(parent, geneSet, get_fitness)
else:
def fnMutate(parent):
return _mutate_custom(parent, custom_mutate, get_fitness)
if custom_create is None:
def fnGenerateParent():
return _generate_parent(targetLen, geneSet, get_fitness)
else:
def fnGenerateParent():
genes = custom_create()
return Chromosome(genes, get_fitness(genes), Strategies.Create)
strategyLookup = {
Strategies.Create: lambda p, i, o: fnGenerateParent(),
Strategies.Mutate: lambda p, i, o: fnMutate(p),
Strategies.Crossover: lambda p, i, o:
_crossover(p.Genes, i, o, get_fitness, crossover, fnMutate,
fnGenerateParent)
}
usedStrategies = [strategyLookup[Strategies.Mutate]]
if crossover is not None:
usedStrategies.append(strategyLookup[Strategies.Crossover])
def fnNewChild(parent, index, parents):
return random.choice(usedStrategies)(parent, index, parents)
else:
def fnNewChild(parent, index, parents):
return fnMutate(parent)
for improvement in _get_improvement(fnNewChild, fnGenerateParent,
maxAge, poolSize):
display(improvement)
f = strategyLookup[improvement.Strategy]
usedStrategies.append(f)
if not optimalFitness > improvement.Fitness:
return improvement
def _get_improvement(new_child, generate_parent, maxAge, poolSize):
bestParent = generate_parent()
yield bestParent
parents = [bestParent]
historicalFitnesses = [bestParent.Fitness]
for _ in range(poolSize - 1):
parent = generate_parent()
if parent.Fitness > bestParent.Fitness:
yield parent
bestParent = parent
historicalFitnesses.append(parent.Fitness)
parents.append(parent)
lastParentIndex = poolSize - 1
pindex = 1
while True:
pindex = pindex - 1 if pindex > 0 else lastParentIndex
parent = parents[pindex]
child = new_child(parent, pindex, parents)
if parent.Fitness > child.Fitness:
if maxAge is None:
continue
parent.Age += 1
if maxAge > parent.Age:
continue
index = bisect_left(historicalFitnesses, child.Fitness, 0,
len(historicalFitnesses))
proportionSimilar = index / len(historicalFitnesses)
if random.random() < exp(-proportionSimilar):
parents[pindex] = child
continue
bestParent.Age = 0
parents[pindex] = bestParent
continue
if not child.Fitness > parent.Fitness:
child.Age = parent.Age + 1
parents[pindex] = child
continue
child.Age = 0
parents[pindex] = child
if child.Fitness > bestParent.Fitness:
bestParent = child
yield bestParent
historicalFitnesses.append(bestParent.Fitness)在get_best方法裡面，增加了一個參數poolSize，默認是1，也就是只有一個父本。
而在_get_improvement方法裡面，我們通過下面方法初始化了若干個上代基因
def _get_improvement(new_child, generate_parent, maxAge, poolSize):
bestParent = generate_parent()
yield bestParent
parents = [bestParent]
historicalFitnesses = [bestParent.Fitness]然後在下面這一組語句裡面去按照父母池的大小，來生成新的基因，然後檢驗是否有更好的父母基因，如果更好則替換掉，以保持池中一直是歷史上最優秀的基因。
而因為我們有一整個池的父母基因，所以每次我們都可以選擇不同的父母基因來作為當前要進化的父母基因。
for _ in range(poolSize - 1):
parent = generate_parent()
if parent.Fitness > bestParent.Fitness:
yield parent
bestParent = parent
historicalFitnesses.append(parent.Fitness)
parents.append(parent)
lastParentIndex = poolSize - 1
pindex = 1
while True:
pindex = pindex - 1 if pindex > 0 else lastParentIndex
parent = parents[pindex]我們可以通過不斷循環池中的基因，以及不斷的生成新的基因，以及不斷更新成更優秀的基因，來保證池中的遺傳多樣性與優生性。
如果僅僅是每次都更換父本基因，那麼算法就類似於退火算法了（在這裡退火算法可能有比較糟糕的性能），所以我們可以設置一種更有效策略，即設置一個父母池和一個孩子池。
在對孩子池的基因的保留，可以有如下策略：
保留所有的子代基因
保留孩子池中優於父母池中的基因。
保留池中最優的基因為獨生子女基因
保留池中的中位數基因為獨生子女基因
而如果子池已經滿了，可以通過如下方式，來更新父母池：
\sqrt{child pool size} \rightleftharpoons \sqrt{parent pool size}childpoolsize
⇌parentpoolsize 在本節的算法中，在代碼裡面：我們可以看見，替換的時候，用的是parents[pindex]，而不是parents。
……
if random.random() < exp(-proportionSimilar):
parents[pindex] = child
continue
parents[pindex] = bestParent
parent.Age = 0
continue
……下面我們來看看雜交部分的代碼：
def crossover(parentGenes, donorGenes, fnGetFitness):
pairs = {Pair(donorGenes[0], donorGenes[-1]): 0}
for i in range(len(donorGenes) - 1):
pairs[Pair(donorGenes[i], donorGenes[i + 1])] = 0
tempGenes = parentGenes[:]
if Pair(parentGenes[0], parentGenes[-1]) in pairs:
found = False
for i in range(len(parentGenes) - 1):
if Pair(parentGenes[i], parentGenes[i + 1]) in pairs:
continue
tempGenes = parentGenes[i + 1:] + parentGenes[:i + 1]
found = True
break
if not found:
return None
runs = [[tempGenes[0]]]
for i in range(len(tempGenes) - 1):
if Pair(tempGenes[i], tempGenes[i + 1]) in pairs:
runs[-1].append(tempGenes[i + 1])
continue
runs.append([tempGenes[i + 1]])
initialFitness = fnGetFitness(parentGenes)
count = random.randint(2, 20)
runIndexes = range(len(runs))
while count > 0:
count -= 1
for i in runIndexes:
if len(runs[i]) == 1:
continue
if random.randint(0, len(runs)) == 0:
runs[i] = [n for n in reversed(runs[i])]
indexA, indexB = random.sample(runIndexes, 2)
runs[indexA], runs[indexB] = runs[indexB], runs[indexA]
childGenes = list(chain.from_iterable(runs))
if fnGetFitness(childGenes) > initialFitness:
return childGenes
return childGenes與傳統的進化函數不同，傳統進化函數僅需要輸入一個父本基因就可以了，但是這裡要輸入兩個基因，分別叫做父本基因和受體基因。
最前面兩句，定義的是一個前後點的查詢方法，定義出來是這個樣子的：
donorGenes: ['E', 'A', 'C', 'G', 'B', 'D', 'H', 'F']
parentGenes: ['G', 'C', 'D', 'F', 'E', 'H', 'A', 'B']
受體基因裡面的路徑裡面會包含如下關係（前後點的組合，是排列之後的，比如EA（E>A),CA(C>A),GC(G>C):
EA, CA, GC, GB, DB, HD, HF, FE我們發現，在父本基因裡面的路徑，也有GC和GB，但是其他的就沒有包含了。所以我們對受體基因進行如下向左轉移的copy：
tempGenes: ['D', 'F', 'E', 'H', 'A', 'B', 'G', 'C']下面這段代碼的意思是，如果父本基因和受體基因是一樣的話，直接就返回一個None，然後基因的進化直接從基因庫中處理就行。
tempGenes = parentGenes[:]
if Pair(parentGenes[0], parentGenes[-1]) in pairs:
……接下依據受體基因裡面的運行規律，把父本基因裡面的運行規律給切了，構造一個查找表，比如上面的tempGenes會被切分成下面這個樣子：
['D'],
['F', 'E'],(EF在受體基因裡面存在)
['H'],
['A'],
['B', 'G', 'C']（GB、GC在受體基因裡面存在）下面就進入遺傳算法的經典過程，隨機的交換某些路徑順序，以期待更好的健壯性。之後大部分的代碼就與以前是一樣的，如果健壯性更好，就使用新的基因序列代替以往的，否則不變……一直嘗試直到最大次數，放棄本輪進化，恢復到上一次最優的基因重新開始。（參考第八節，模擬退火算法原理）
兩個常規類，一個健壯性類，一個路徑規則
class Fitness:
def __init__(self, totalDistance):
self.TotalDistance = totalDistance
def __gt__(self, other):
return self.TotalDistance < other.TotalDistance
def __str__(self):
return "{:0.2f}".format(self.TotalDistance)
class Pair:
def __init__(self, node, adjacent):
if node < adjacent:
node, adjacent = adjacent, node
self.Node = node
self.Adjacent = adjacent
def __eq__(self, other):
return self.Node == other.Node and self.Adjacent == other.Adjacent
def __hash__(self):
return hash(self.Node) * 397 ^ hash(self.Adjacent)執行方法：
def solve(idToLocationLookup, optimalSequence):
geneset = [i for i in idToLocationLookup.keys()]
def fnCreate():
return random.sample(geneset, len(geneset))
def fnDisplay(candidate):
display(candidate, startTime)
def fnGetFitness(genes):
return get_fitness(genes, idToLocationLookup)
def fnMutate(genes):
mutate(genes, fnGetFitness)
def fnCrossover(parent, donor):
return crossover(parent, donor, fnGetFitness)
optimalFitness = fnGetFitness(optimalSequence)
startTime = datetime.datetime.now()
best = get_best(fnGetFitness, None, optimalFitness, None,
fnDisplay, fnMutate, fnCreate, maxAge=500,
poolSize=25, crossover=fnCrossover)
return best執行結果如下：
G C H E F D B A 36.64 Create 0:00:00
A B D C H G F E 27.50 Create 0:00:00.001000
G F H A B C D E 23.79 Create 0:00:00.001000
C E F G H A B D 23.78 Create 0:00:00.001995
H G E F D C B A 23.73 Create 0:00:00.003988
C D E F G H A B 20.63 Crossover 0:00:00.014960調用自己寫的繪製方法，用matplotlib:
彩蛋看到這裡的同學，都是鐵了心要學習和掌握遺傳算法的，不過看完這篇，可能很多同學都準備在心裡打退堂鼓了。
不過既然你看到了蝦神的彩蛋，就把退堂鼓扔掉吧，因為，上面那些複雜得讓人一頭霧水的程序，只是用於說明遺傳算法的過程，在你的實際工作中
完！全！不！需！要！
正如大家以前所知，蝦神可以手算插值，可以手算不代表每次遇上要插值的時候，我都得掏出紙筆來手動計算……這樣的話，算死也算不過來的說。
所以，重複造輪子這種事，一般我是堅決不提倡的，作為實戰，我們只需要一槍擊倒敵人就可以了，至於這把槍是自己造的，還是繳獲自敵人的，並不重要。
當然，你要成為槍械專家的另說……
下面介紹一些Python的非常強大的遺傳算法包，這些包在後面我都會逐漸的介紹。
DEAP地址：https://github.com/DEAP/deap簡介：Star:3.6K（這個數量就說明一切了）Geatpy地址：https://github.com/geatpy-dev/geatpy簡介：目前國內比較權威、高性能的Python遺傳和進化算法工具箱。
由華農、暨大、華工等碩博學生聯合團隊開源
簡單易學、功能強大。
支持豐富的遺傳和進化算法的經典算子
目前受到多所高校的實驗室以及一些公司的優化項目採用
並得到相關的Paper引用。pagmo2地址：https://github.com/esa/pagmo2簡介：ESA（European Space Agency 歐洲航天局）認證
源碼由C++編寫，提供Python接口。scikit-opt地址：https://github.com/guofei9987/scikit-opt/簡介：用了scikit這個名字，成功的吸引了我的注意。
一個封裝了7種啟發式算法的 Python 代碼庫
- 差分進化算法
- 遺傳算法
- 粒子群算法
- 模擬退火算法
- 蟻群算法
- 魚群算法
- 免疫優化算法除了Python以外，R語言也有大量的與遺傳算法相關的包，比如mcga包和genalg包，不過我們主要講Python，所以R的問題，以後再說（如果有空的話）。
到今天為止，Python實戰遺傳算法，已經進入了深水區，後面還有幾道算法題，我也會一一說明，不過如果我在文章中沒有說清楚（限於水平，後面未必能夠一次性講明白），或者小夥伴們看不懂的話 ，沒關係，我們以後還會用各種算法引擎包來進行實現。
待續未完。