遗传算法解决旅行商问题.zip

import random from individual import Individual import numpy as np # 城市数量(基因序列长度) city_num = 20 # 个体数量 individual_num = 60 # 迭代轮数 gen_num = 400 # 变异概率 mutate_prob = 0.25 # 城市维度 pos_dimension = 2 def build_dist_mat(input_list): # 城市数量20 global city_num dist_mat = np.zeros([city_num, city_num]) for i in range(city_num): for j in range(i + 1, city_num): 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_mat # 城市坐标矩阵 city_pos_list = np.random.rand(city_num, pos_dimension) # 城市距离矩阵 city_dist_mat = build_dist_mat(city_pos_list) def copy_list(old_arr: [int]): new_arr = [] for element in old_arr: new_arr.append(element) return new_arr 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 class Solution: def __init__(self, input_): global city_dist_mat 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, city_num - 2) index2 = random.randint(index1, city_num - 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): # 拿到对应位置的index和value 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(genes=genes1, city_num=city_num, city_dist_mat=city_dist_mat)) new_gen.append(Individual(genes=genes2, city_num=city_num, city_dist_mat=city_dist_mat)) 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, city_num - 2) index2 = random.randint(index1, city_num - 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 = 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(genes=player.genes, city_num=city_num, city_dist_mat=city_dist_mat) group.append(player) group = rank(group) # 取出获胜者 winners += group[:group_winner] self.individual_list = winners 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(city_num=city_num, city_dist_mat=city_dist_mat) 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