人工智能与机器学习——大学实验：遗传算法解决tsp旅行商问题（代码+环境配置）
下面介绍一下这几个库。
-
简介
旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。
-
图片示意：
-
代码
该实验我用的是vscode+tython做的，csdn上有教程，不多赘述；
此外，numpy等环境要在电脑上配置上，最后再说。
代码文件GA.py
GA源代码：
# -*- coding: utf-8 -*-
import random
from Life import Life
class GA(object):
"""遗传算法类"""
def __init__(self, aCrossRate, aMutationRage, aLifeCount, aGeneLenght, aMatchFun = lambda life : 1):
self.croessRate = aCrossRate
self.mutationRate = aMutationRage
self.lifeCount = aLifeCount
self.geneLenght = aGeneLenght
self.matchFun = aMatchFun # 适配函数
self.lives = [] # 种群
self.best = None # 保存这一代中最好的个体
self.generation = 1
self.crossCount = 0
self.mutationCount = 0
self.bounds = 0.0 # 适配值之和，用于选择是计算概率
self.initPopulation()
def initPopulation(self):
"""初始化种群"""
self.lives = []
for i in range(self.lifeCount):
gene = [ x for x in range(0,self.geneLenght) ]
#random.shuffle(gene)
life = Life(gene)
self.lives.append(life)
def judge(self):
"""评估，计算每一个个体的适配值"""
self.bounds = 0.0
self.best = self.lives[0]
for life in self.lives:
life.score = self.matchFun(life)
self.bounds += life.score
if self.best.score < life.score:
self.best = life
def cross(self, parent1, parent2):
"""交叉"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(index1, self.geneLenght - 1)
tempGene = parent2.gene[index1:index2] # 交叉的基因片段
newGene = []
p1len = 0
for g in parent1.gene:
if p1len == index1:
newGene.extend(tempGene) # 插入基因片段
p1len += 1
if g not in tempGene:
newGene.append(g)
p1len += 1
self.crossCount += 1
return newGene
def mutation(self, gene):
"""突变"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(0, self.geneLenght - 1)
newGene = gene[:] # 产生一个新的基因序列，以免变异的时候影响父种群
newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
self.mutationCount += 1
return newGene
def getOne(self):
"""选择一个个体"""
r = random.uniform(0, self.bounds)
for life in self.lives:
r -= life.score
if r <= 0:
return life
raise Exception("选择错误", self.bounds)
def newChild(self):
"""产生新后的"""
parent1 = self.getOne()
rate = random.random()
# 按概率交叉
if rate < self.croessRate:
# 交叉
parent2 = self.getOne()
gene = self.cross(parent1, parent2)
else:
gene = parent1.gene
# 按概率突变
rate = random.random()
if rate < self.mutationRate:
gene = self.mutation(gene)
return Life(gene)
def next(self):
"""产生下一代"""
self.judge()
newLives = []
newLives.append(self.best) #把最好的个体加入下一代
while len(newLives) < self.lifeCount:
newLives.append(self.newChild())
self.lives = newLives
self.generation += 1
# -*- coding: utf-8 -*-
import random
from Life import Life
class GA(object):
"""遗传算法类"""
def __init__(self, aCrossRate, aMutationRage, aLifeCount, aGeneLenght, aMatchFun = lambda life : 1):
self.croessRate = aCrossRate
self.mutationRate = aMutationRage
self.lifeCount = aLifeCount
self.geneLenght = aGeneLenght
self.matchFun = aMatchFun # 适配函数
self.lives = [] # 种群
self.best = None # 保存这一代中最好的个体
self.generation = 1
self.crossCount = 0
self.mutationCount = 0
self.bounds = 0.0 # 适配值之和，用于选择是计算概率
self.initPopulation()
def initPopulation(self):
"""初始化种群"""
self.lives = []
for i in range(self.lifeCount):
gene = [ x for x in range(0,self.geneLenght) ]
#random.shuffle(gene)
life = Life(gene)
self.lives.append(life)
def judge(self):
"""评估，计算每一个个体的适配值"""
self.bounds = 0.0
self.best = self.lives[0]
for life in self.lives:
life.score = self.matchFun(life)
self.bounds += life.score
if self.best.score < life.score:
self.best = life
def cross(self, parent1, parent2):
"""交叉"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(index1, self.geneLenght - 1)
tempGene = parent2.gene[index1:index2] # 交叉的基因片段
newGene = []
p1len = 0
for g in parent1.gene:
if p1len == index1:
newGene.extend(tempGene) # 插入基因片段
p1len += 1
if g not in tempGene:
newGene.append(g)
p1len += 1
self.crossCount += 1
return newGene
def mutation(self, gene):
"""突变"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(0, self.geneLenght - 1)
newGene = gene[:] # 产生一个新的基因序列，以免变异的时候影响父种群
newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
self.mutationCount += 1
return newGene
def getOne(self):
"""选择一个个体"""
r = random.uniform(0, self.bounds)
for life in self.lives:
r -= life.score
if r <= 0:
return life
raise Exception("选择错误", self.bounds)
def newChild(self):
"""产生新后的"""
parent1 = self.getOne()
rate = random.random()
# 按概率交叉
if rate < self.croessRate:
# 交叉
parent2 = self.getOne()
gene = self.cross(parent1, parent2)
else:
gene = parent1.gene
# 按概率突变
rate = random.random()
if rate < self.mutationRate:
gene = self.mutation(gene)
return Life(gene)
def next(self):
"""产生下一代"""
self.judge()
newLives = []
newLives.append(self.best) #把最好的个体加入下一代
while len(newLives) < self.lifeCount:
newLives.append(self.newChild())
self.lives = newLives
self.generation += 1
# -*- coding: utf-8 -*-
import random
from Life import Life
class GA(object):
"""遗传算法类"""
def __init__(self, aCrossRate, aMutationRage, aLifeCount, aGeneLenght, aMatchFun = lambda life : 1):
self.croessRate = aCrossRate
self.mutationRate = aMutationRage
self.lifeCount = aLifeCount
self.geneLenght = aGeneLenght
self.matchFun = aMatchFun # 适配函数
self.lives = [] # 种群
self.best = None # 保存这一代中最好的个体
self.generation = 1
self.crossCount = 0
self.mutationCount = 0
self.bounds = 0.0 # 适配值之和，用于选择是计算概率
self.initPopulation()
def initPopulation(self):
"""初始化种群"""
self.lives = []
for i in range(self.lifeCount):
gene = [ x for x in range(0,self.geneLenght) ]
#random.shuffle(gene)
life = Life(gene)
self.lives.append(life)
def judge(self):
"""评估，计算每一个个体的适配值"""
self.bounds = 0.0
self.best = self.lives[0]
for life in self.lives:
life.score = self.matchFun(life)
self.bounds += life.score
if self.best.score < life.score:
self.best = life
def cross(self, parent1, parent2):
"""交叉"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(index1, self.geneLenght - 1)
tempGene = parent2.gene[index1:index2] # 交叉的基因片段
newGene = []
p1len = 0
for g in parent1.gene:
if p1len == index1:
newGene.extend(tempGene) # 插入基因片段
p1len += 1
if g not in tempGene:
newGene.append(g)
p1len += 1
self.crossCount += 1
return newGene
def mutation(self, gene):
"""突变"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(0, self.geneLenght - 1)
newGene = gene[:] # 产生一个新的基因序列，以免变异的时候影响父种群
newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
self.mutationCount += 1
return newGene
def getOne(self):
"""选择一个个体"""
r = random.uniform(0, self.bounds)
for life in self.lives:
r -= life.score
if r <= 0:
return life
raise Exception("选择错误", self.bounds)
def newChild(self):
"""产生新后的"""
parent1 = self.getOne()
rate = random.random()
# 按概率交叉
if rate < self.croessRate:
# 交叉
parent2 = self.getOne()
gene = self.cross(parent1, parent2)
else:
gene = parent1.gene
# 按概率突变
rate = random.random()
if rate < self.mutationRate:
gene = self.mutation(gene)
return Life(gene)
def next(self):
"""产生下一代"""
self.judge()
newLives = []
newLives.append(self.best) #把最好的个体加入下一代
while len(newLives) < self.lifeCount:
newLives.append(self.newChild())
self.lives = newLives
self.generation += 1
Life.py源代码：
# -*- encoding: utf-8 -*-
SCORE_NONE = -1
class Life(object):
"""个体类"""
def __init__(self, aGene = None):
self.gene = aGene
self.score = SCORE_NONE
tsp问题描述源代码：TSP.py
# -*- coding: utf-8 -*-
import random
import copy
import time
import sys
import math
import tkinter #//GUI模块
import threading
from functools import reduce
# 参数
'''
ALPHA:信息启发因子，值越大，则蚂蚁选择之前走过的路径可能性就越大
，值越小，则蚁群搜索范围就会减少，容易陷入局部最优
BETA:Beta值越大，蚁群越就容易选择局部较短路径，这时算法收敛速度会
加快，但是随机性不高，容易得到局部的相对最优
'''
(ALPHA, BETA, RHO, Q) = (1.0,2.0,0.5,100.0)
# 城市数，蚁群
(city_num, ant_num) = (50,50)
distance_x = [
178,272,176,171,650,499,267,703,408,437,491,74,532,
416,626,42,271,359,163,508,229,576,147,560,35,714,
757,517,64,314,675,690,391,628,87,240,705,699,258,
428,614,36,360,482,666,597,209,201,492,294]
distance_y = [
170,395,198,151,242,556,57,401,305,421,267,105,525,
381,244,330,395,169,141,380,153,442,528,329,232,48,
498,265,343,120,165,50,433,63,491,275,348,222,288,
490,213,524,244,114,104,552,70,425,227,331]
#城市距离和信息素
distance_graph = [ [0.0 for col in range(city_num)] for raw in range(city_num)]
pheromone_graph = [ [1.0 for col in range(city_num)] for raw in range(city_num)]
#----------- 蚂蚁 -----------
class Ant(object):
# 初始化
def __init__(self,ID):
self.ID = ID # ID
self.__clean_data() # 随机初始化出生点
# 初始数据
def __clean_data(self):
self.path = [] # 当前蚂蚁的路径
self.total_distance = 0.0 # 当前路径的总距离
self.move_count = 0 # 移动次数
self.current_city = -1 # 当前停留的城市
self.open_table_city = [True for i in range(city_num)] # 探索城市的状态
city_index = random.randint(0,city_num-1) # 随机初始出生点
self.current_city = city_index
self.path.append(city_index)
self.open_table_city[city_index] = False
self.move_count = 1
# 选择下一个城市
def __choice_next_city(self):
next_city = -1
select_citys_prob = [0.0 for i in range(city_num)] #存储去下个城市的概率
total_prob = 0.0
# 获取去下一个城市的概率
for i in range(city_num):
if self.open_table_city[i]:
try :
# 计算概率：与信息素浓度成正比，与距离成反比
select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
total_prob += select_citys_prob[i]
except ZeroDivisionError as e:
print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = self.ID, current = self.current_city, target = i))
sys.exit(1)
# 轮盘选择城市
if total_prob > 0.0:
# 产生一个随机概率,0.0-total_prob
temp_prob = random.uniform(0.0, total_prob)
for i in range(city_num):
if self.open_table_city[i]:
# 轮次相减
temp_prob -= select_citys_prob[i]
if temp_prob < 0.0:
next_city = i
break
# 未从概率产生，顺序选择一个未访问城市
# if next_city == -1:
# for i in range(city_num):
# if self.open_table_city[i]:
# next_city = i
# break
if (next_city == -1):
next_city = random.randint(0, city_num - 1)
while ((self.open_table_city[next_city]) == False): # if==False,说明已经遍历过了
next_city = random.randint(0, city_num - 1)
# 返回下一个城市序号
return next_city
# 计算路径总距离
def __cal_total_distance(self):
temp_distance = 0.0
for i in range(1, city_num):
start, end = self.path[i], self.path[i-1]
temp_distance += distance_graph[start][end]
# 回路
end = self.path[0]
temp_distance += distance_graph[start][end]
self.total_distance = temp_distance
# 移动操作
def __move(self, next_city):
self.path.append(next_city)
self.open_table_city[next_city] = False
self.total_distance += distance_graph[self.current_city][next_city]
self.current_city = next_city
self.move_count += 1
# 搜索路径
def search_path(self):
# 初始化数据
self.__clean_data()
# 搜素路径，遍历完所有城市为止
while self.move_count < city_num:
# 移动到下一个城市
next_city = self.__choice_next_city()
self.__move(next_city)
# 计算路径总长度
self.__cal_total_distance()
#----------- TSP问题 -----------
class TSP(object):
def __init__(self, root, width = 800, height = 600, n = city_num):
# 创建画布
self.root = root
self.width = width
self.height = height
# 城市数目初始化为city_num
self.n = n
# tkinter.Canvas
self.canvas = tkinter.Canvas(
root,
width = self.width,
height = self.height,
bg = "#EBEBEB", # 背景白色
xscrollincrement = 1,
yscrollincrement = 1
)
self.canvas.pack(expand = tkinter.YES, fill = tkinter.BOTH)
self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
self.__r = 5
self.__lock = threading.RLock() # 线程锁
self.__bindEvents()
self.new()
# 计算城市之间的距离
for i in range(city_num):
for j in range(city_num):
temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
temp_distance = pow(temp_distance, 0.5)
distance_graph[i][j] =float(int(temp_distance + 0.5))
# 按键响应程序
def __bindEvents(self):
self.root.bind("q", self.quite) # 退出程序
self.root.bind("n", self.new) # 初始化
self.root.bind("e", self.search_path) # 开始搜索
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(len(distance_x)):
# 在画布上随机初始坐标
x = distance_x[i]
y = distance_y[i]
self.nodes.append((x, y))
# 生成节点椭圆，半径为self.__r
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.canvas.create_text(x,y-10, # 使用create_text方法在坐标（302，77）处绘制文字
text = '('+str(x)+','+str(y)+')', # 所绘制文字的内容
fill = 'black' # 所绘制文字的颜色为灰色
)
# 顺序连接城市
#self.line(range(city_num))
# 初始城市之间的距离和信息素
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = 1.0
self.ants = [Ant(ID) for ID in range(ant_num)] # 初始蚁群
self.best_ant = Ant(-1) # 初始最优解
self.best_ant.total_distance = 1 << 31 # 初始最大距离
self.iter = 1 # 初始化迭代次数
# 将节点按order顺序连线
def line(self, 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
# order[-1]为初始值
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()
self.root.destroy()
print (u"\n程序已退出...")
sys.exit()
# 停止搜索
def stop(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
# 开始搜索
def search_path(self, evt = None):
# 开启线程
self.__lock.acquire()
self.__running = True
self.__lock.release()
while self.__running:
# 遍历每一只蚂蚁
for ant in self.ants:
# 搜索一条路径
ant.search_path()
# 与当前最优蚂蚁比较
if ant.total_distance < self.best_ant.total_distance:
# 更新最优解
self.best_ant = copy.deepcopy(ant)
# 更新信息素
self.__update_pheromone_gragh()
print (u"迭代次数：",self.iter,u"最佳路径总距离：",int(self.best_ant.total_distance))
# 连线
self.line(self.best_ant.path)
# 设置标题
self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
# 更新画布
self.canvas.update()
self.iter += 1
# 更新信息素
def __update_pheromone_gragh(self):
# 获取每只蚂蚁在其路径上留下的信息素
temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
for ant in self.ants:
for i in range(1,city_num):
start, end = ant.path[i-1], ant.path[i]
# 在路径上的每两个相邻城市间留下信息素，与路径总距离反比
temp_pheromone[start][end] += Q / ant.total_distance
temp_pheromone[end][start] = temp_pheromone[start][end]
# 更新所有城市之间的信息素，旧信息素衰减加上新迭代信息素
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
# 主循环
def mainloop(self):
self.root.mainloop()
#----------- 程序的入口处 -----------
if __name__ == '__main__':
print (u"""
--------------------------------------------------------
程序：蚁群算法解决TPS问题程序
作者：许彬
日期：2015-12-10
语言：Python 2.7
--------------------------------------------------------
""")
TSP(tkinter.Tk()).mainloop()
遗传算法和tsp问题结合后，源代码：TSP_GA.py
# -*- encoding: utf-8 -*-
import random
import math
from GA import GA
import matplotlib.pyplot as plt
class TSP(object):
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())
def initCitys(self):
self.citys = []
"""
for i in range(34):
x = random.randint(0, 1000)
y = random.randint(0, 1000)
self.citys.append((x, y))
"""
#中国34城市经纬度
self.citys.append((1,1))
self.citys.append((9,9))
self.citys.append((8,0))
self.citys.append((3,1))
self.citys.append((7,8))
self.citys.append((8,1))
self.citys.append((1,9))
self.citys.append((1,5))
self.citys.append((8,5))
self.citys.append((8,6))
for i in range(len(self.citys)-1):
plt.plot((self.citys[i][0],self.citys[i+1][0]),(self.citys[i][1],self.citys[i+1][1]))
plt.plot((self.citys[0][0],self.citys[len(self.citys)-1][0]),(self.citys[0][1],self.citys[len(self.citys)-1][1]))
#plt.show()
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)
"""
R = 6371.004
Pi = math.pi
LatA = city1[1]
LatB = city2[1]
MLonA = city1[0]
MLonB = city2[0]
C = math.sin(LatA*Pi / 180) * math.sin(LatB * Pi / 180) + math.cos(LatA * Pi / 180) * math.cos(LatB * Pi / 180) * math.cos((MLonA - MLonB) * Pi / 180)
D = R * math.acos(C) * Pi / 100
distance += D
"""
return distance
def matchFun(self):
return lambda life: 1.0 / self.distance(life.gene)
def run(self, n = 0):
while n > 0:
self.ga.next()
distance = self.distance(self.ga.best.gene)
print (("%d : %f") % (self.ga.generation, distance))
n -= 1
print('路径顺序为')
for i in self.ga.best.gene:
print(self.citys[i],end='->')
print(self.citys[0])
print (("迭代次数为%d 路径总长为: %f") % (self.ga.generation, distance))
self.show(self.ga.best.gene)
def show(self,v):
figure, ax = plt.subplots()
for i in range(len(v)-1):
plt.plot((self.citys[v[i]][0],self.citys[v[i+1]][0]),(self.citys[v[i]][1],self.citys[v[i+1]][1]))
plt.plot((self.citys[v[0]][0],self.citys[v[len(v)-1]][0]),(self.citys[v[0]][1],self.citys[v[len(v)-1]][1]))
plt.show()
def main():
tsp = TSP()
tsp.run(200)
if __name__ == '__main__':
main()
运行结果
代码环境配置：
- numpy库配置： 在电脑上按键 win+r，会弹出一个“运行的窗口”。在这个窗口里输入 cmd，这样就能打开 命令提示符窗口，能借助各种命令执行各种任务。在该窗口里输入 pip install numpy ,这样就能借助pip命令 ，安装numpy库。
- scikit-learn 库配置： 在上述窗口中，输入pip install-U scikit-learn 可以安装 scikit库
- matplotlib库配置：同样的，输入 pip install matplotlib 可以安装 matplotlib库。
库介绍：
下面介绍一下这几个库
numpy：
一个用python实现的科学计算的库，最常用，可以说是做实验必备。
numpy包括：
1、一个强大的N维数组对象Array；
2、比较成熟的（广播）函数库；
3、用于整合C/C++和Fortran代码的工具包；
4、实用的线性代数、傅里叶变换和随机数生成函数。numpy和稀疏矩阵运算包scipy配合使用更加方便。
numPy（Numeric Python）提供了许多高级的数值编程工具，如：矩阵数据类型、矢量处理，以及精密的运算库。专为进行严格的数字处理而产生。多为很多大型金融公司使用，以及核心的科学计算组织如：Lawrence Livermore，NASA用其处理一些本来使用C++，Fortran或Matlab等所做的任务。
Matplotlib：
Matplotlib 是一个 Python 的 2D绘图库，它以各种硬拷贝格式和跨平台的交互式环境生成出版质量级别的图形。
Scikit-learn（以前称为scikits.learn，也称为sklearn）是针对Python 编程语言的免费软件机器学习库 [1]。它具有各种分类，回归和聚类算法，包括支持向量机，随机森林，梯度提升，k均值和DBSCAN，并且旨在与Python数值科学库NumPy和SciPy联合使用。
Scikit-learn
Scikit-learn主要是用Python编写的，并且广泛使用numpy进行高性能的线性代数和数组运算。此外，用Cython编写了一些核心算法来提高性能。支持向量机由围绕LIBSVM的Cython包装器实现 ; 逻辑回归和线性支持向量机的相似包装围绕LIBLINEAR。在这种情况下，可能无法使用Python扩展这些方法。Scikit-learn与许多其他Python库很好地集成在一起，例如matplotlib和plotly用于绘图，numpy用于数组矢量化，pandas数据帧，scipy等。
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)