做的好的旅游网站,暴雪网易2023后不代理了,百度自动搜索关键词软件,淘宝客网站备案信息怎么写一、基本步骤
遗传算法求解旅行商问题#xff08;TSP#xff09;的一般步骤如下#xff1a; 编码#xff1a; 通常采用整数编码#xff0c;将城市的访问顺序表示为一个染色体。例如#xff0c;假设有 5 个城市#xff0c;编码为[1, 3, 5, 2, 4]#xff0c;表示旅行商的…一、基本步骤
遗传算法求解旅行商问题TSP的一般步骤如下 编码 通常采用整数编码将城市的访问顺序表示为一个染色体。例如假设有 5 个城市编码为[1, 3, 5, 2, 4]表示旅行商的访问顺序为城市 1、城市 3、城市 5、城市 2、城市 4最后回到出发城市 1。 初始化种群 随机生成一定数量的染色体作为初始种群。 适应度评估 计算每个染色体所代表的路径长度路径长度越短适应度越高。适应度函数可以是路径长度的倒数或其他与路径长度相关的函数。 选择操作 基于适应度选择一定比例的染色体进入下一代种群。常见的选择方法有轮盘赌选择、锦标赛选择等。 交叉操作 对选中的染色体进行交叉生成新的染色体。例如单点交叉随机选择一个交叉点交换两个染色体在交叉点之后的部分。 变异操作 以一定的概率对染色体中的基因进行变异例如随机交换两个城市的位置。 重复步骤 3 - 6 直到满足终止条件如达到预定的迭代次数或找到满意的解。
通过不断迭代种群中的染色体逐渐优化最终得到较优的 TSP 路径。需要注意的是遗传算法的参数如种群大小、交叉概率、变异概率等需要根据具体问题进行调整和优化以获得更好的求解效果。
二、代码
#!/usr/bin/env python
# coding: utf-8# In[32]:import numpy as np
import copy
import matplotlib
import matplotlib.pyplot as plt
from matplotlib.pyplot import MultipleLocator
import random# In[33]:#准备好距离矩阵
city_num 5
city_dist_mat np.zeros([city_num, city_num])
city_dist_mat[0][1] city_dist_mat[1][0] 1165
city_dist_mat[0][2] city_dist_mat[2][0] 1462
city_dist_mat[0][3] city_dist_mat[3][0] 3179
city_dist_mat[0][4] city_dist_mat[4][0] 1967
city_dist_mat[1][2] city_dist_mat[2][1] 1511
city_dist_mat[1][3] city_dist_mat[3][1] 1942
city_dist_mat[1][4] city_dist_mat[4][1] 2129
city_dist_mat[2][3] city_dist_mat[3][2] 2677
city_dist_mat[2][4] city_dist_mat[4][2] 1181
city_dist_mat[3][4] city_dist_mat[4][3] 2216
#标号说明
#list_city [0_北京, 1_西安, 2_上海, 3_昆明, 4_广州]# In[34]:#1.定义个体类包括基因城市路线和适应度
num_person_idx 0
num_person 0
dis_list []
class Individual:def __init__(self, genes None):global num_personglobal dis_listglobal num_person_idxnum_person_idx 1if num_person_idx % 20 0:num_person 1self.genes genesif self.genes None:genes [0]*5temp [0]*4temp [i for i in range(1,city_num)]########################################################################random.shuffle(temp)genes[1:] tempgenes[0] 0self.genes genesself.fitness self.evaluate_fitness()else:self.fitness float(self.evaluate_fitness())#2. #计算个体的适应度def evaluate_fitness(self):dis 0for i in range(city_num - 1):dis city_dist_mat[self.genes[i]][self.genes[i1]]if i city_num - 2:dis city_dist_mat[self.genes[i 1]][0]#回到0if num_person_idx % 20 0:dis_list.append(dis)return 1/dis# In[35]:def copy_list(old):new []for element in old:new.append(element)return new
def sort_win_num(group):for i in range(len(group)):for j in range(len(group) - i - 1):
# print(group[j].fitness_type, type(group[j].fitness))if group[j].fitness group[j1].fitness:temp group[j]group[j] group[j1]group[j1] tempreturn group
#定义Ga类
#3~5交叉、变异、更新种群全部在Ga类中实现
class Ga:#input_为城市间的距离矩阵def __init__(self, input_):#声明一个全局变量global city_dist_matcity_dist_mat input_#当代的最佳个体########################################此处做了更改#self.best Noneself.best Individual(None)
# print(BBBBBBbest.fitness,self.best.fitness)#种群self.individual_list []#每一代的最佳个体self.result_list []#每一代个体对应的最佳适应度self.fitness_list []#交叉,这里采用交叉变异def cross(self):new_gen []#随机选取一段含有num_cross个数字城市num_cross 3#后期可能需要调试的参数,考虑到实际问题里只有5个城市所以认为3较为合适for i in range(0, len(self.individual_list) - 1, 2):parent_gen1 copy_list(self.individual_list[i].genes)parent_gen2 copy_list(self.individual_list[i1].genes)
# print(parent_gen1,parent_gen1)
# print(parent_gen2,parent_gen2) index1_1 0index1_2 0index2_1 0index2_2 0#定义一个下表列表index_list [0]*3for i in range(city_num - 3):#就是2即01index_list[i] i 1index1_1 random.choice(index_list)index1_2 index1_1 2index2_1 random.choice(index_list)index2_2 index2_1 2choice_list1 parent_gen1[index1_1:index1_2 1]choice_list2 parent_gen2[index2_1:index2_2 1]
# print(choice_list1,choice_list1)
# print(choice_list2,choice_list2)#利用这一段生成两个子代,下面的赋值只是为了获取长度所以用哪个父代能可以#也可以直接用city_num直接代替son_gen1 [0]*city_numson_gen2 [0]*city_num
# print(son_gen1_size ,len(son_gen1))
# print(son_gen2_size ,len(son_gen2))
# print(index1_1 ,index1_1)
# print(index1_2 ,index1_2)
# print(index2_1 ,index2_1)
# print(index2_2 ,index2_2)#找到之后进行交叉分别得到son_gen1,son_gen2#先把选中的段复制进去son_gen1[index1_1: index1_2 1] choice_list1son_gen2[index2_1: index2_2 1] choice_list2
# print(now, son_gen1 , son_gen1)
# print(now, son_gen2 , son_gen2)#然后左、右“查漏补缺”temp1 choice_list1temp2 choice_list2if index1_1 0:passelse: for i in range(index1_1):for j in range(city_num):#如果父代2里面的这个当初没被选中那就加入son_gene1if parent_gen2[j] not in choice_list1:son_gen1[i] parent_gen2[j]#这个时候要扩增choice_list1, 这样parent_gen2里面未被选中的元素才会一个个被遍历到#1choice_list1.append(parent_gen2[j])#找到之后马上break防止被覆盖breakchoice_list1 temp1if index1_2 city_num - 1:passelse:for i in range(index1_2 1, city_num):for j in range(city_num):if parent_gen2[j] not in choice_list1:son_gen1[i] parent_gen2[j]#这个时候要扩增choice_list1, 这样parent_gen2里面未被选中的元素才会一个个被遍历到#2choice_list1.append(parent_gen2[j])#找到之后马上break防止被覆盖break#son_gen2亦是如此if index2_1 0:passelse:for i in range(index2_1):for j in range(city_num):#如果父代1里面的这个当初没被选中那就加入son_gen2if parent_gen1[j] not in choice_list2:son_gen2[i] parent_gen1[j]#这个时候要扩增choice_list2, 这样parent_gen1里面未被选中的元素才会一个个被遍历到#3choice_list2.append(parent_gen1[j])#找到之后马上break防止被覆盖breakchoice_list2 temp2if index2_2 city_num - 1:passelse:for i in range(index2_2 1, city_num):for j in range(city_num):if parent_gen1[j] not in choice_list2:
# print(i , i)son_gen2[i] parent_gen1[j]#这个时候要扩增choice_list2, 这样parent_gen1里面未被选中的元素才会一个个被遍历到#4choice_list2.append(parent_gen1[j])#找到之后马上break防止被覆盖break#新生成的子代基因加入new_gene列表
# print(son_gen1 ,son_gen1)
# print(son_gen2 ,son_gen2)new_gen.append(Individual(son_gen1))#print(new_gen[-1].genes, new_gen[-1].genes)new_gen.append(Individual(son_gen2))return new_gen#变异def mutate(self, new_gen):mutate_p 0.02#待调参数index_list [0]*(city_num-1)index_1 1index_2 1for i in range(city_num - 1):index_list[i] i 1for individual in new_gen:if random.random() mutate_p:
# change 1#如果变异采用基于位置的变异,方便起见直接使用上面定义的index列表index_l random.choice(index_list)
# index_2 (index_1 2) % city_num#这里让间隔为2的两个城市进行交换index_2 random.choice(index_list)while index_1 index_2:index_2 random.choice(index_list)#交换temp individual.genes[index_1]individual.genes[index_1] individual.genes[index_2]individual.genes[index_2] temp#变异结束与老一代的进行合并self.individual_list new_gen#选择def select(self):#在此选用轮盘赌算法#考虑到5的阶乘是120所以可供选择的个体基数应该适当大一些#在此每次从种群中选择6个进行轮盘赌初始化60个个体同时适当调高变异的概率select_num 6select_list []for i in range(select_num):gambler random.choice(self.individual_list)gambler Individual(gambler.genes)select_list.append(gambler)#求出这些fitness之和sum 0for i in range(select_num):sum select_list[i].fitnesssum_m [0]*select_num#实现概率累加for i in range(select_num):for j in range(i1):sum_m[i] select_list[j].fitnesssum_m[i] / sumnew_select_list []p_num 0#随机数for i in range(select_num):p_num random.uniform(0,1)if p_num0 and p_num sum_m[0]:new_select_list.append(select_list[0])elif p_num sum_m[0] and p_num sum_m[1]:new_select_list.append(select_list[1])elif p_num sum_m[1] and p_num sum_m[2]:new_select_list.append(select_list[2])elif p_num sum_m[2] and p_num sum_m[3]:new_select_list.append(select_list[3])elif p_num sum_m[3] and p_num sum_m[4]:new_select_list.append(select_list[4])elif p_num sum_m[4] and p_num sum_m[5]:new_select_list.append(select_list[5])else:pass#将新生成的一代替代父代种群self.individual_list new_select_list#更新种群def next_gen(self):#交叉new_gene self.cross()#变异self.mutate(new_gene)#选择self.select()#获得这一代的最佳个体
# print(**************************************)
# print(self.best.fitness , self.best.fitness)
# print(now, best.fitness , self.best.fitness)for individual in self.individual_list:if individual.fitness self.best.fitness:self.best individual
# print(更换了最优路径)
# print(now, best.fitness , self.best.fitness)def train(self):#随机出初代种群#individual_num 60self.individual_list [Individual() for _ in range(individual_num)]#迭代gen_num 100for i in range(gen_num):#从当代种群中交叉、变异、选择出适应度最佳的个体获得子代产生新的种群self.next_gen()#连接首位
# print(i , i)result copy.deepcopy(self.best.genes)result.append(result[0])self.result_list.append(result)self.fitness_list.append(self.best.fitness)print(self.result_list[-1])print(距离总和是, 1/self.fitness_list[-1])
# return self.result_list, self.fitness_listdef draw(self):x_list [i for i in range(num_person)]y_list dis_listplt.rcParams[figure.figsize] (60, 45)plt.plot(x_list, y_list, color g)plt.xlabel(Cycles,size 50)plt.ylabel(Route,size 50)x np.arange(0, 910, 20)y np.arange(7800, 12000, 100)plt.xticks(x)plt.yticks(y)plt.title(Trends in distance changes, size 50)plt.tick_params(labelsize30)
# plt.savefig(D:\AI_pictures\遗传算法求解TSP问题_1_轮盘赌算法)plt.show()
route Ga(city_dist_mat)
route.train()
route.draw()
