最近在学习算法设计这门课，老师在讲遗传算法解决旅行商问题，所以找了些资料学习下，也算是自己转专业来一个入门的实践，先把我资料的网址贴上：https://www.bilibili/video/BV17Z4y1w7qF?from=search&seid=4612262847067450332&spm_id_from=333.337.0.0https://www.bilibili/video/BV17Z4y1w7qF?from=search&seid=4612262847067450332&spm_id_from=333.337.0.0
另外，我所用的数据： 我用的是Berlin52http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/旅行商问题表示一个人要不重复的走完地图中所有的点在返回原地，怎样距离最短？
上代码
首先配置文件：表示的是一些默认的数值，这里我设置每一代个体30，总共2000代，52则表示城市的数量
# -*- coding: utf-8 -*-
import argparse
parser = argparse.ArgumentParser(description='Configuration file')
arg_lists = []
def add_argument_group(name):
arg = parser.add_argument_group(name)
arg_lists.append(arg)
return arg
# Data
data_arg = add_argument_group('Data')
data_arg.add_argument('--city_num', type=int, default=52, help='city num') # 城市数量
data_arg.add_argument('--pos_dimension', type=int, default=2, help='city num') # 坐标维度
data_arg.add_argument('--individual_num', type=int, default=30, help='individual num') # 个体数
data_arg.add_argument('--gen_num', type=int, default=2000, help='generation num') # 迭代轮数
data_arg.add_argument('--mutate_prob', type=float, default=0.3, help='probability of mutate') # 变异概率
def get_config():
config, unparsed = parser.parse_known_args()
return config
def print_config():
config = get_config()
print('\n')
print('Data Config:')
print('* city num:', config.city_num)
print('* individual num:', config.individual_num)
print('* generation num:', config.gen_num)
print('* probability of mutate:', config.mutate_prob)
主文件：
import math
import numpy as np
import config as conf
from ga import Ga
import matplotlib.pyplot as plt
config = conf.get_config()
def read_tsp(path): #打开tsp文件
lines = open(path, 'r').readlines()
assert 'NODE_COORD_SECTION\n' in lines
index = lines.index('NODE_COORD_SECTION\n')
data = lines[index + 1:-1]
tmp = []
for line in data:
line = line.strip().split(' ')
if line[0] == 'EOF':
continue
tmpline = []
for x in line:
if x == '':
continue
else:
tmpline.append(float(x))
if tmpline == []:
continue
tmp.append(tmpline)
data = tmp
data = np.array(data)
data = data[:, 1:]
data = np.array(data)
return data
def build_dist_mat(input_list):
n,m=input_list.shape
dist_mat = np.zeros([n, n])
for i in range(n):
for j in range(i + 1, n):
d = input_list[i, :] - input_list[j, :]
# 计算点积
dist_mat[i, j] =math.sqrt(np.dot(d, d))
dist_mat[j, i] = dist_mat[i, j]
return dist_mat
# 城市坐标
city_pos_list = read_tsp(r"C:\Users\XXX\OneDrive\桌面\资料\上课\berlin52.tsp")
# 城市距离矩阵
city_dist_mat = build_dist_mat(city_pos_list)
#
print(city_pos_list)
print(city_dist_mat)
# 遗传算法运行
ga = Ga(city_dist_mat)
result_list, fitness_list = ga.train()
result = result_list[-1]
result_pos_list = city_pos_list[result, :]
# 绘图
# 解决中文显示问题
plt.rcParams['font.sans-serif'] = ['KaiTi'] # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题
fig = plt.figure()
plt.plot(result_pos_list[:, 0], result_pos_list[:, 1], 'o-r')
plt.title(u"路线")
plt.legend()
fig.show()
fig = plt.figure()
plt.plot(fitness_list)
plt.title(u"适应度曲线")
plt.legend()
fig.show()
print(fitness_list[-1])
最主要的算法文件：
import config as conf
import random
city_dist_mat = None
config = conf.get_config()
# 各项参数
gene_len = config.city_num
individual_num = config.individual_num
gen_num = config.gen_num
mutate_prob = config.mutate_prob
def copy_list(old_arr: [int]):
new_arr = []
for element in old_arr:
new_arr.append(element)
return new_arr
# 个体类
class Individual:
def __init__(self, genes=None):
# 随机生成序列
if genes is None:
genes = [i for i in range(gene_len)]
random.shuffle(genes)
self.genes = genes
self.fitness = self.evaluate_fitness() #随机生成初始单个基因
def evaluate_fitness(self):
# 计算个体适应度
fitness = 0.0
for i in range(gene_len - 1):
# 起始城市和目标城市
from_idx = self.genes[i]
to_idx = self.genes[i + 1]
fitness += city_dist_mat[from_idx, to_idx]
# 连接首尾
fitness += city_dist_mat[self.genes[-1], self.genes[0]]
return fitness #计算路程距离
class Ga: #基因函数 很重要
def __init__(self, input_):
global city_dist_mat #全局变量 在模块内、在所有函数外面、在class外面，这就是全局变量。
city_dist_mat = input_ #将输入数据转化为距离矩阵
self.best = None # 每一代的最佳个体
self.individual_list = [] # 所有个体
self.result_list = [] # 路线结果
self.fitness_list = [] # 每一代对应的适应度
def cross(self):
new_gen = []
random.shuffle(self.individual_list) #打乱所有基因个体列表
for i in range(0, individual_num - 1, 2):
# 父代基因
genes1 = copy_list(self.individual_list[i].genes) #父亲基因
genes2 = copy_list(self.individual_list[i + 1].genes)#母亲基因
index1 = random.randint(0, gene_len - 2) #随机生成基因index 保证index1小于index2 [index1，index2]代表交叉过程中的基因片段
index2 = random.randint(index1, gene_len - 1) #
pos1_recorder = {value: idx for idx, value in enumerate(genes1)} #记录初始基因中每个点的位置到字典中
pos2_recorder = {value: idx for idx, value in enumerate(genes2)}
# 交叉
for j in range(index1, index2): #此处方法非常巧妙 建议61-70行单独拿出逐行分析，将j的取值范围从小变大挨个分析。
value1, value2 = genes1[j], genes2[j]
pos1, pos2 = pos1_recorder[value2], pos2_recorder[value1]
genes1[j], genes1[pos1] = genes1[pos1], genes1[j]
genes2[j], genes2[pos2] = genes2[pos2], genes2[j]
pos1_recorder[value1], pos1_recorder[value2] = pos1, j
pos2_recorder[value1], pos2_recorder[value2] = j, pos2
new_gen.append(Individual(genes1)) #生成个体1和2
new_gen.append(Individual(genes2))
return new_gen
def mutate(self, new_gen):
for individual in new_gen:
if random.random() < mutate_prob:
# 翻转切片
old_genes = copy_list(individual.genes)
index1 = random.randint(0, gene_len - 2)
index2 = random.randint(index1, gene_len - 1)
genes_mutate = old_genes[index1:index2]
genes_mutate.reverse()
individual.genes = old_genes[:index1] + genes_mutate + old_genes[index2:]
# 两代合并
self.individual_list += new_gen
def select(self):
# 锦标赛
group_num =10 # 小组数
group_size = 20 # 每小组人数
group_winner = individual_num // group_num # 每小组获胜人数
winners = [] # 锦标赛结果
for i in range(group_num):
group = []
for j in range(group_size):
# 随机组成小组
player = random.choice(self.individual_list)
player = Individual(player.genes)
group.append(player)
group = Ga.rank(group)
# 取出获胜者
winners += group[:group_winner]
self.individual_list = winners
@staticmethod
def rank(group):
# 冒泡排序
for i in range(1, len(group)):
for j in range(0, len(group) - i):
if group[j].fitness > group[j + 1].fitness:
group[j], group[j + 1] = group[j + 1], group[j]
return group
def next_gen(self):
# 交叉
new_gen = self.cross()
# 变异
self.mutate(new_gen)
# 选择
self.select()
# 获得这一代的结果
for individual in self.individual_list:
if individual.fitness < self.best.fitness:
self.best = individual
def train(self):
# 初代种群
self.individual_list = [Individual() for _ in range(individual_num)]
self.best = self.individual_list[0]
# 迭代
for i in range(gen_num):
self.next_gen()
# 连接首尾
result = copy_list(self.best.genes)
result.append(result[0])
self.result_list.append(result)
self.fitness_list.append(self.best.fitness)
return self.result_list, self.fitness_list
这个Berlin52的最优解7542
但是我最好也就是7800左右
更多推荐
遗传算法解决TSP（旅行商问题）
发布评论