"""---------*- coding: utf-8 -*------------------
File Name: main
Author: kingsCat
date: 2021/11/17 10:45
Description:
----------------------------------------------"""
import copy
import random
import numpy as np
import math
import matplotlib.pyplot as plt
import os
class City:
# 城市数和量num,城市的坐标loc,城市距离矩阵mat
def __init__(self, num=10, loc=None):
self.num = num
if loc is None:
self.loc = [] # 用来存储所有城市点的坐标
for i in range(num):
dot = []
x = random.randint(-100, 100)
y = random.randint(-100, 100)
dot = [x, y] # 一个城市点
self.loc.append(dot)
else:
self.loc = loc
self.mat = self.getMat() # 城市的距离矩阵
def getMat(self):
# 计算距离矩阵
dis_mat = np.zeros([self.num, self.num])
for i in range(self.num):
x1, y1 = self.loc[i]
for j in range(self.num):
x2, y2 = self.loc[j]
dis_mat[i][j] = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
return dis_mat
class Individual:
# 一个个体有 基因genes(排列),适应度fitness(距离)
def __init__(self, genes=None):
if (genes == None): # suiji chushihua
genes = [i for i in range(city.num)]
random.shuffle(genes)
self.genes = genes
self.fitness = self.evaluateFitness()
def evaluateFitness(self): # 计算适应度，就是整个序列的长度，越短越好
sum = 0
genes = self.genes
for i in range(city.num - 1):
x, y = genes[i], genes[i + 1]
sum += city.mat[x][y]
x, y = genes[-1], genes[0]
sum += city.mat[x][y]
return sum
class Ga:
def __init__(self, individual_num=60, mutate_prob=0.1): # 还得加个函数,若是没有给individual数量,应该怎么办,数量点位置应该随机初始化
self.individual_num = individual_num # 一代个体个数
# 这句话应该写在self。indi的下面吧？？待会试试
self.individual_list = [Individual() for _ in range(self.individual_num)] # 随机初始化这么多个体#每一代的个体列表
self.best_individual = self.individual_list[0] # 每一代最佳个体
self.mutate_prob = mutate_prob # 变异概率
self.year = 0 # 此种群一年只繁殖一次
def train(self, gen_num=50, thr_year=10):
# 初始化的时候就已经创建好这么多的个体了。
if(city.num>20):
thr_year=1000
elif(city.num>10):
city.num=200
else:
thr_year=thr_year*city.num#城市数量越多，迭代停止年数的阈值就越高，这主意太妙了
if (gen_num == -1): # 无限迭代
flag = 1
while (True):
old_individual_fit = self.best_individual.fitness
self.nextGene()
if (old_individual_fit == self.best_individual.fitness):
flag += 1
else:
flag = 1
if (flag > thr_year):
path = ""
for i in self.best_individual.genes:
path += str(i) + "->"
path += str(self.best_individual.genes[0])
print("*********************************\n遗传算法最短路径长度为:", self.best_individual.fitness, "最优解路径为:",
path)
# self.plotting()
break
else:
for i in range(gen_num): # 默认一次train迭代50代
self.nextGene()
def nextGene(self):
self.year += 1
new_individual_list = self.cross() # 交叉,交叉产生的新个体存在这里
self.mutate(new_individual_list) # 变异,传入新个体,进行变异,然后把所有新个体都加到self.个体列表中
self.select() # self.individual_list中只保留优秀个体
for individual in self.individual_list:
if (individual.fitness < self.best_individual.fitness):
self.best_individual = copy.deepcopy(individual)
# 打印
path = ""
for i in self.best_individual.genes:
path += str(i) + "->"
path += str(self.best_individual.genes[0])
print("第", self.year, "代", "最优解长度为:", self.best_individual.fitness, "最优解路径为:", path)
def cross(self): # 交叉
new_individual_list = [] # 下一代个体
individual_list = copy.deepcopy(self.individual_list)
random.shuffle(individual_list)
for i in range(0, self.individual_num - 1, 2): # 用减一吗,不见也行吧 这么多个体,两两交叉
genes1 = copy.deepcopy(self.individual_list[i].genes)
genes2 = copy.deepcopy(self.individual_list[i + 1].genes)
# begin 和 end 分别为交叉的起点和终点
begin = random.randint(0, city.num - 2) # 这个左右都是闭区间,很反常
end = random.randint(begin, city.num - 1)
genes1_recorder = {value: idx for idx, value in enumerate(genes1)} # recorder来存储对应的值在genes哪个位置上
genes2_recorder = {value: idx for idx, value in enumerate(genes2)}
for j in range(begin, end + 1): # end得加一,左闭右开,不然取不到genes[city.num-1]即最后一位
# 交换顺序
value1, value2 = genes1[j], genes2[j]
idx1, idx2 = genes1_recorder[value2], genes2_recorder[value1]
genes1[j], genes1[idx1] = genes1[idx1], genes1[j]
genes2[j], genes2[idx2] = genes2[idx2], genes2[j]
# 哦对,recorder也得更新
genes1_recorder[value1], genes1_recorder[value2] = idx1, j
genes2_recorder[value1], genes2_recorder[value2] = j, idx2
new_individual_list.append(Individual(genes1))
new_individual_list.append(Individual(genes2))
return new_individual_list # 新一代
def mutate(self, new_individual_list): # 传入交叉产生的新一代,进行变异
for individual in new_individual_list: # random.random生成[0,1)的一个实数
# for i in w:i循环遍历w里面的参数,i会影响到w里面的内容改变
if random.random() < self.mutate_prob: # 按概率变异
old_genes = individual.genes
id_begin = random.randint(0, len(old_genes) - 2) # 虽然都一样,但是感觉写len比用city数量更好些,不知道对不对,到底哪种才是规范呢?
id_end = random.randint(id_begin, len(old_genes))
mutate_genes = copy.deepcopy(old_genes[id_begin:id_end])
mutate_genes.reverse()
individual.genes = old_genes[:id_begin] + mutate_genes + old_genes[id_end:]
self.individual_list += new_individual_list # 父子两代放到一起,准备参与选择 +=是合并,append是将一个list整体作为一个元素加入到另外一个list中
def select(self, group_num=10, group_size=10):
# 自然选择,随机从整体中抽出来group_size个,在这里面选group_winner_num个胜利者,加入到胜利者集合winner_list里面
# 要分组进行选拔,默认是group_num=10组
group_winner_num = self.individual_num // group_num # 一共要选这么多个,每组就要选这么多个
winner_list = []
for i in range(group_num):
group_winner_list = []
for j in range(group_size):
player = copy.deepcopy(random.choice(self.individual_list))
group_winner_list.append(player)
group_winner_list = Ga.rank(group_winner_list)
winner_list += group_winner_list[:group_winner_num] # 只取这一组中优秀的个体
self.individual_list = copy.deepcopy(winner_list)
@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
@staticmethod
def plotting(self):
# 画图
loc = city.loc
x = []
y = []
for dot in loc:
a, b = dot
x.append(x)
y.append(y)
# plt.cla()
plt.plot(x, y, "o")
plt.plot(x, y, linewidth=1, color="red")
plt.show()
flag0 = True
while (flag0):
print("********************\n请输入选项:")
print("pyqt5图形化界面没有写出来.所以只能用命令行来显示程序了.一个个输入城市位置太麻烦,推荐老师使用随机初始化")
print("输入0随机初始化城市,输入1自定义城市坐标,输入2结束程序:")
a = input()
print(a)
if (a.isdigit() and int(a) == 1): # 自定义城市
num_input = input("********************\n请输入城市个数:")
if (num_input.isdigit() and int(num_input) > 0):
city_num = int(num_input)
city_loc = []
for i in range(city_num):
flag = True
while (flag):
print("请输入点的坐标:")
print("请输入第", i, "个点的横坐标")
x = input()
print("请输入第", i, "个点的纵坐标")
y = input()
if (x.isdigit() and y.isdigit()):
city_dot = []
city_dot.append(int(x))
city_dot.append(int(y))
city_loc.append(city_dot)
flag = False
else:
print("输入有误,请重新输入:")
city = City(city_num, city_loc)
print("--------------------------初始化城市成功!\n城市数量为:", city.num, "城市位置为:", city.loc, "城市距离矩阵为:\n")
print(city.mat)
flag0 = False
else:
print("输入的城市个数不是整数!")
elif (a.isdigit() and int(a) == 0): # 随机初始化城市
num_input = input("********************\n请输入随机初始化的城市个数:")
if (num_input.isdigit() and int(num_input) > 0):
city_num = int(num_input)
city = City(city_num)
print("--------------------------初始化城市成功!\n城市数量为:", city.num, "城市位置为:", city.loc, "城市距离矩阵为:\n")
print(city.mat)
flag0 = False
else:
print("输入的城市个数不是整数!")
elif (a.isdigit() and int(a) == 2):
print("退出程序")
exit(1)
else:
print("输入有误,请重新输入!")
flag0 = True
ga = Ga()
ga.train(-1) # 无限迭代
os.system("pause")
更多推荐
TSP算法解决旅行商最短路径问题
发布评论