了却一个心愿

        遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。相信对于路径规划来说，这种方法其实也是一种目前较好的寻找最优解的方法。

---

一、遗传算法原理

        原理都是一样的，有很多博客都写得很好，其理论的都是万变不离其宗。

二、主要内容

        虽然理论摆在那里，有人能够看懂，有人看不懂，我也是只能看懂一点点，这就使得理论运用到代码当中就变得相当困难了，所以对于路径规划这样的题目，我想自己编出一个合适的遗传算法几乎就不可能了，还好在github里面发现了一个关于遗传算法TSP问题的代码，代码简单易懂（注释多)，我自己试着运行了一下，发现效果也还不错，运行时间短，结果也不会总变来变去（几乎就是正确答案）。

GItHub链接

大哥的视频讲解

三、使用步骤

1.将压缩包下载解压

会发现有如下三个代码文件：

config.py：各参数配置
ga.py：遗传算法实现
main.py：程序入口，数据预处理，效果展示

 ga.py：就用了Python的一两个基础库，强我只能说。

from config import ConfigParser
import randomcity_dist_mat = None
Cf = ConfigParser(city_nums=101, gen_nums=10000)
config = Cf.get_config()
# 各项参数
gene_len = config.city_num
individual_num = config.individual_num
gen_num = config.gen_num
mutate_prob = config.mutate_probdef 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 = genesself.fitness = self.evaluate_fitness()def evaluate_fitness(self):# 计算个体适应度fitness = 0.0for 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 fitnessclass Ga:def __init__(self, input_):global city_dist_matcity_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)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):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, jpos2_recorder[value1], pos2_recorder[value2] = j, pos2new_gen.append(Individual(genes1))new_gen.append(Individual(genes2))return new_gendef 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_gendef select(self):# 锦标赛group_num = 10  # 小组数group_size = 10  # 每小组人数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@staticmethoddef 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 groupdef 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 = individualdef train(self, ifplot=False):# 初代种群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

 config.py:我为了运行时调参，将其改为类帮助我不用每次都要到隔壁去修改参数

# -*- coding: utf-8 -*-
import argparseclass ConfigParser:def __init__(self, city_nums=101, pos_dimensions=2, individual_nums=60, gen_nums=1000, mutate_probs=0.25):'''参数调整,默认值可修改:param city_num: 城市数量:param pos_dimension: 坐标维度:param individual_num: 个体数:param gen_num: 迭代轮数:param mutate_prob: 变异概率:return: 参数说明'''self.parser = argparse.ArgumentParser(description='Configuration file')self.arg_lists = []# Datadata_arg = self.add_argument_group('Data')data_arg.add_argument('--city_num', type=int, default=city_nums, help='city num')  # 城市数量data_arg.add_argument('--pos_dimension', type=int, default=pos_dimensions, help='city num')  # 坐标维度data_arg.add_argument('--individual_num', type=int, default=individual_nums, help='individual num')  # 个体数data_arg.add_argument('--gen_num', type=int, default=gen_nums, help='generation num')  # 迭代轮数data_arg.add_argument('--mutate_prob', type=float, default=mutate_probs, help='probability of mutate')  # 变异概率def add_argument_group(self, name):arg = self.parser.add_argument_group(name)self.arg_lists.append(arg)return argdef get_config(self):self.config, self.unparsed = self.parser.parse_known_args()return self.configdef print_config(self):print('\n')print('Data Config:')print('* city num:', self.config.city_num)print('* individual num:', self.config.individual_num)print('* generation num:', self.config.gen_num)print('* probability of mutate:', self.config.mutate_prob)if __name__ == '__main__':Cf = ConfigParser(city_nums=101, gen_nums=10000)config = Cf.get_config()print("路径个数：", config.city_num)print("迭代次数：", config.gen_num)

main.py:我将ga.py里的代码拷到这里来了，所以没有调用ga,py，方便调参 

import numpy as np
import sys
sys.path.append(r'D:\86176\PycharmProjects\pythonProject\Interesting argrism\ga-tsp-main')
from config import ConfigParser
import matplotlib.pyplot as plt
# 解决中文显示问题
plt.rcParams['font.sans-serif'] = ['KaiTi']  # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题
from haversine import haversine
import time
import randomCf = ConfigParser(city_nums=101, gen_nums=10000)
config = Cf.get_config()
print("路径个数：", config.city_num)
print("迭代次数：", config.gen_num)
# 各项参数
gene_len = config.city_num
individual_num = config.individual_num
gen_num = config.gen_num
mutate_prob = config.mutate_probdef build_dist_mat(input_list):n = config.city_numdist_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] = np.dot(d, d)dist_mat[j, i] = dist_mat[i, j]return dist_matdef dist_ance(sj):n = config.city_numdistance = np.zeros([n, n])for i in range(n):for j in range(i + 1, n):distance[i, j] = haversine(sj[i, :], sj[j, :])distance[j, i] = distance[i, j]return distance#######################################
# 遗传算法主要部分GA
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 = genesself.fitness = self.evaluate_fitness()def evaluate_fitness(self):# 计算个体适应度fitness = 0.0for 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 fitnessclass Ga:def __init__(self, input_):global city_dist_matcity_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)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):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, jpos2_recorder[value1], pos2_recorder[value2] = j, pos2new_gen.append(Individual(genes1))new_gen.append(Individual(genes2))return new_gendef 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_gendef select(self):# 锦标赛group_num = 10  # 小组数group_size = 10  # 每小组人数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@staticmethoddef 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 groupdef 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 = individualdef train(self):# 初代种群self.individual_list = [Individual() for _ in range(individual_num)]self.best = self.individual_list[0]# 迭代# plt.figure()# plt.ion()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)# plt.plot(self.fitness_list)# plt.pause(0.01)# plt.title(u"适应度曲线")# plt.legend()return self.result_list, self.fitness_listif __name__ == '__main__':Start = time.time()# 城市坐标# 读取数据city_pos_list = np.loadtxt(r'D:\86176\PycharmProjects\pythonProject\sj.txt', dtype=np.float32)city_pos_list = np.vstack([city_pos_list[:, [2 * i, 2 * i + 1]]for i in range(4)])d0 = np.array([70, 40])city_pos_list = np.vstack([d0, city_pos_list])# 城市距离矩阵city_dist_mat = dist_ance(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]idx = result.index(0)result = result[idx:-1]result.extend(result_list[-1][:idx])result.append(0)result_pos_list = city_pos_list[result, :]# fig = plt.figure()# plt.plot(result_pos_list[:, 0], result_pos_list[:, 1], 'o-r')# plt.title(u"路线")# plt.legend()# fig.show()# 画图# plt.figure()# plt.ion()# # plt.plot(fitness_list)# xx = [fitness_list[0]]# for i in range(1, len(fitness_list)):#     xx.append(fitness_list[i])#     plt.plot(xx)#     plt.pause(0.01)# plt.title(u"适应度曲线")# plt.legend()# plt.show()plt.figure()plt.ion()xs = [result_pos_list[0, 0]]ys = [result_pos_list[0, 1]]for i in range(1, len(result_pos_list)):xs.append(result_pos_list[i, 0])ys.append(result_pos_list[i, 1])plt.plot(xs, ys, '-o')plt.pause(0.1)End = time.time()print("用时", End - Start, '秒')print('运行路线为：')for i in result:print(i, end=' ')print("\n最短总距离为：", fitness_list[-1])

2.读入数据

        用的是一个飞机要经过的100个城市坐标（经纬度）,所以在做的过程中要考虑经纬度之间距离的直接转化。飞机的起始坐标是（70,40），要经过下面的所有地点并回到起点。

经纬度坐标

经度	纬度	经度	纬度	经度	纬度	经度	纬度
53.7121	15.3046	51.1758	0.0322	46.3253	28.2753	30.3313	6.9348
56.5432	21.4188	10.8198	16.2529	22.7891	23.1045	10.1584	12.4819
20.105	15.4562	1.9451	0.2057	26.4951	22.1221	31.4847	8.964
26.2418	18.176	44.0356	13.5401	28.9836	25.9879	38.4722	20.1731
28.2694	29.0011	32.191	5.8699	36.4863	29.7284	0.9718	28.1477
8.9586	24.6635	16.5618	23.6143	10.5597	15.1178	50.2111	10.2944
8.1519	9.5325	22.1075	18.5569	0.1215	18.8726	48.2077	16.8889
31.9499	17.6309	0.7732	0.4656	47.4134	23.7783	41.8671	3.5667
43.5474	3.9061	53.3524	26.7256	30.8165	13.4595	27.7133	5.0706
23.9222	7.6306	51.9612	22.8511	12.7938	15.7307	4.9568	8.3669
21.5051	24.0909	15.2548	27.2111	6.207	5.1442	49.243	16.7044
17.1168	20.0354	34.1688	22.7571	9.4402	3.92	11.5812	14.5677
52.1181	0.4088	9.5559	11.4219	24.4509	6.5634	26.7213	28.5667
37.5848	16.8474	35.6619	9.9333	24.4654	3.1644	0.7775	6.9576
14.4703	13.6368	19.866	15.1224	3.1616	4.2428	18.5245	14.3598
58.6849	27.1485	39.5168	16.9371	56.5089	13.709	52.5211	15.7957
38.43	8.4648	51.8181	23.0159	8.9983	23.644	50.1156	23.7816
13.7909	1.951	34.0574	23.396	23.0624	8.4319	19.9857	5.7902
40.8801	14.2978	58.8289	14.5229	18.6635	6.7436	52.8423	27.288
39.9494	29.5114	47.5099	24.0664	10.1121	27.2662	28.7812	27.6659
8.0831	27.6705	9.1556	14.1304	53.7989	0.2199	33.649	0.398
1.3496	16.8359	49.9816	6.0828	19.3635	17.6622	36.9545	23.0265
15.732	19.5697	11.5118	17.3884	44.0398	16.2635	39.7139	28.4203
6.9909	23.1804	38.3392	19.995	24.6543	19.6057	36.998	24.3992
4.1591	3.1853	40.14	20.303	23.9876	9.403	41.1084	27.7149

        求最短路径。

3.最终结果

        只需修改运行main.py中的文件就行了

        将结果坐标放入直角坐标中展示

迭代结果：

 

实时迭代结果的展示可能会使得算法在计算时速度会减慢，如果电脑好那就另说了，不建议实时结果展示。

运行路线为：
0 44 66 1 91 81 47 71 13 26 9 83 17 39 78 76 30 96 84 64 63 10 93 69 18 62 61 25 28 33 65 89 85 7 38 77 46 56 27 87 60 48 67 6 24 22 57 80 21 70 36 31 23 12 72 11 52 88 5 95 54 55 20 98 99 43 37 53 4 74 32 3 40 90 15 68 75 59 8 14 49 79 97 50 41 19 29 73 82 86 58 100 51 45 92 42 35 94 34 2 16 0 
最短总距离为： 40546.764132575256

---

总结

        这是我在之前国赛训练训练时的一个题目，虽然很简单，但是当时是真的觉得很难，记录一下，希望对有需要的同学有帮助，其实我现在是对这个算法理解的也还算深了，因为和它对抗了很久，总是想找一个合适的Python算法没找到，自己写的也不尽人意，这也算是我对自己这一模块结束的标志了吧。