程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> Python >> 用遺傳算法解旅行商問題

用遺傳算法解旅行商問題

日期:2017/1/13 14:59:57      編輯:Python

旅行商問題(Travelling Salesman Problem,即TSP問題)是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市,他必須選擇所要走的路徑,路經的限制是每個城市只能拜訪一次,而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。

TSP問題是一個組合優化問題,也是一個NP完全問題,使用通常的解法往往需要耗費大量的時間,不過我們也可以使用遺傳算法,在較短的時間裡找到一個可接受(不一定是最優)的解。

下面是我的代碼,一共有三個文件。

1、TSP.py
 

# -*- coding: utf-8 -*-

"""TSP.py

TSP問題
"""

import sys
import random
import math
import Tkinter
import threading

from GA import GA

class MyTSP(object):
"TSP"

def __init__(self, root, width = 800, height = 600, n = 32):
self.root = root
self.width = width
self.height = height
self.n = n
self.canvas = Tkinter.Canvas(
root,
width = self.width,
height = self.height,
bg = "#ffffff",
xscrollincrement = 1,
yscrollincrement = 1
)
self.canvas.pack(expand = Tkinter.YES, fill = Tkinter.BOTH)
self.title("TSP")
self.__r = 5
self.__t = None
self.__lock = threading.RLock()

self.__bindEvents()
self.new()

def __bindEvents(self):
self.root.bind("q", self.quite)
self.root.bind("n", self.new)
self.root.bind("e", self.evolve)
self.root.bind("s", self.stop)

def title(self, s):
self.root.title(s)

def new(self, evt = None):
self.__lock.acquire()
self.__running = False
self.__lock.release()

self.clear()
self.nodes = [] # 節點坐標
self.nodes2 = [] # 節點圖片對象
for i in range(self.n):
x = random.random() * (self.width - 60) + 30
y = random.random() * (self.height - 60) + 30
self.nodes.append((x, y))
node = self.canvas.create_oval(x - self.__r,
y - self.__r, x + self.__r, y + self.__r,
fill = "#ff0000",
outline = "#000000",
tags = "node",
)
self.nodes2.append(node)

self.ga = GA(
lifeCount = 50,
mutationRate = 0.05,
judge = self.judge(),
mkLife = self.mkLife(),
xFunc = self.xFunc(),
mFunc = self.mFunc(),
save = self.save()
)
self.order = range(self.n)
self.line(self.order)

def distance(self, order):
"得到當前順序下連線總長度"
distance = 0
for i in range(-1, self.n - 1):
i1, i2 = order[i], order[i + 1]
p1, p2 = self.nodes[i1], self.nodes[i2]
distance += math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

return distance

def mkLife(self):
def f():
lst = range(self.n)
random.shuffle(lst)
return lst
return f

def judge(self):
"評估函數"
return lambda lf, av = 100: 1.0 / self.distance(lf.gene)

def xFunc(self):
"交叉函數"
def f(lf1, lf2):
p1 = random.randint(0, self.n - 1)
p2 = random.randint(self.n - 1, self.n)
g1 = lf2.gene[p1:p2] + lf1.gene
# g2 = lf1.gene[p1:p2] + lf2.gene
g11 = []
for i in g1:
if i not in g11:
g11.append(i)
return g11
return f

def mFunc(self):
"變異函數"
def f(gene):
p1 = random.randint(0, self.n - 2)
p2 = random.randint(self.n - 2, self.n - 1)
gene[p1], gene[p2] = gene[p2], gene[p1]
return gene
return f

def save(self):
def f(lf, gen):
pass
return f

def evolve(self, evt = None):
self.__lock.acquire()
self.__running = True
self.__lock.release()

while self.__running:
self.ga.next()
self.line(self.ga.best.gene)
self.title("TSP - gen: %d" % self.ga.generation)
self.canvas.update()

self.__t = None

def line(self, order):
"將節點按 order 順序連線"
self.canvas.delete("line")
def line2(i1, i2):
p1, p2 = self.nodes[i1], self.nodes[i2]
self.canvas.create_line(p1, p2, fill = "#000000", tags = "line")
return i2

reduce(line2, order, order[-1])

def clear(self):
for item in self.canvas.find_all():
self.canvas.delete(item)

def quite(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
sys.exit()

def stop(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()

def mainloop(self):
self.root.mainloop()

if __name__ == "__main__":
MyTSP(Tkinter.Tk()).mainloop()

 

2、2、GA.py

# -*- coding: utf-8 -*-

"""GA.py

遺傳算法類
"""

import random
from Life import Life

class GA(object):

def __init__(self, xRate = 0.7, mutationRate = 0.005, lifeCount = 50, geneLength = 100, judge = lambda lf, av: 1, save = lambda: 1, mkLife = lambda: None, xFunc = None, mFunc = None):
self.xRate = xRate
self.mutationRate = mutationRate
self.mutationCount = 0
self.generation = 0
self.lives = []
self.bounds = 0.0 # 得分總數
self.best = None
self.lifeCount = lifeCount
self.geneLength = geneLength
self.__judge = judge
self.save = save
self.mkLife = mkLife # 默認的產生生命的函數
self.xFunc = (xFunc, self.__xFunc)[xFunc == None] # 自定義交叉函數
self.mFunc = (mFunc, self.__mFunc)[mFunc == None] # 自定義變異函數

for i in range(lifeCount):
self.lives.append(Life(self, self.mkLife()))

def __xFunc(self, p1, p2):
# 默認交叉函數
r = random.randint(0, self.geneLength)
gene = p1.gene[0:r] + p2.gene[r:]
return gene

def __mFunc(self, gene):
# 默認突變函數
r = random.randint(0, self.geneLength - 1)
gene = gene[:r] + ("0", "1")[gene[r:r] == "1"] + gene[r + 1:]
return gene

def __bear(self, p1, p2):
# 根據父母 p1, p2 生成一個後代
r = random.random()
if r < self.xRate:
# 交叉
gene = self.xFunc(p1, p2)
else:
gene = p1.gene

r = random.random()
if r < self.mutationRate:
# 突變
gene = self.mFunc(gene)
self.mutationCount += 1

return Life(self, gene)

def __getOne(self):
# 根據得分情況,隨機取得一個個體,機率正比於個體的score屬性
r = random.uniform(0, self.bounds)
for lf in self.lives:
r -= lf.score
if r <= 0:
return lf

def __newChild(self):
# 產生新的後代
return self.__bear(self.__getOne(), self.__getOne())

def judge(self, f = lambda lf, av: 1):
# 根據傳入的方法 f ,計算每個個體的得分
lastAvg = self.bounds / float(self.lifeCount)
self.bounds = 0.0
self.best = Life(self)
self.best.setScore(-1.0)
for lf in self.lives:
lf.score = f(lf, lastAvg)
if lf.score > self.best.score:
self.best = lf
self.bounds += lf.score

def next(self, n = 1):
# 演化至下n代
while n > 0:
# self.__getBounds()
self.judge(self.__judge)
newLives = []
newLives.append(Life(self, self.best.gene)) # 將最好的父代加入競爭
# self.bestHistory.append(self.best)
while (len(newLives) < self.lifeCount):
newLives.append(self.__newChild())
self.lives = newLives
self.generation += 1
#print("gen: %d, mutation: %d, best: %f" % (self.generation, self.mutationCount, self.best.score))
self.save(self.best, self.generation)

n -= 1

 

3、Life.py

# -*- coding: utf-8 -*-

"""Life.py

生命類
"""

import random

class Life(object):

def __init__(self, env, gene = None):
self.env = env

if gene == None:
self.__rndGene()
elif type(gene) == type([]):
self.gene = []
for k in gene:
self.gene.append(k)
else:
self.gene = gene

def __rndGene(self):
self.gene = ""
for i in range(self.env.geneLength):
self.gene += str(random.randint(0, 1))

def setScore(self, v):
self.score = v

def addScore(self, v):
self.score += v

運行TSP.py,即可開始程序。幾個快捷鍵說明如下:
n: 開始新的計算(隨機產生32個新的城市)
e: 開始進化
s: 停止
q: 退出

程序沒有設置終止進化條件,進化一旦開始,如果不手動停止,會一直計算下去。

遺傳算法主要是一種思想,並沒有很具體的代碼,在解決大多數問題時,最難解決的部分主要是編碼(如何將問題轉化為合適的方便操作的“基因”)、評價(如何評價各個“基因”的得分)部分。在本例中,我們將城市的順序做為基因編碼,路徑總長度的倒數為基因的得分。這種做法不一定是最好的,不過是有效的。

下面是我運行時的一次截圖:

初始狀態
  初始狀態。

第153代
  第153代。

第624代
  第624代,可以看到,已經比初始狀態好多了。

第2331代
  第2331代,除了下方有一些交叉外,已經基本差不多了。

第3710代
  第3710代,完成。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved