西电杨丽英、王晓丽人工智能导论大作业

要求：遗传算法解决TSP问题。

文件：N个城市的距离矩阵（下三角矩阵）

注意：老师可能会给其他N个城市的下三角距离矩阵，修改一下和文件名即可。

import pandas as pd
import numpy as np#初始化种群
def Ini_pop(city_num, pop_num, pop, distance, matrix_distance):rand_ch = np.array(range(city_num))for i in range(pop_num):np.random.shuffle(rand_ch)pop[i, :] = rand_chdistance[i] = count_dis(city_num, matrix_distance, rand_ch)# 这里的适应度是距离#计算本次路径所有城市间的距离
def count_dis(city_num, matrix_distance, one_path):res = 0for i in range(city_num - 1):res += matrix_distance[one_path[i], one_path[i + 1]]res += matrix_distance[one_path[-1], one_path[0]]  # 最后一个城市和第一个城市的距离，需单独处理return res# 打印出当前路径
def print_path(city_num, one_path):res = str(one_path[0] + 1) + '-->'for i in range(1, city_num):res += str(one_path[i] + 1) + '-->'res += str(one_path[0] + 1)print("最佳路径为：")print(res)# 轮盘赌的方式选择子代
def select_lunpan(pop_num, pop, distance):fit = 1. / distance  # 适应度函数p = fit / sum(fit)q = p.cumsum()  # 累积概率select_id = []for i in range(pop_num):r = np.random.rand()  # 产生一个[0,1)的随机数for j in range(pop_num):if r < q[0]:select_id.append(0)breakelif q[j] < r <= q[j + 1]:select_id.append(j + 1)breaknext_gen = pop[select_id, :]return next_gen# 交叉操作-每个个体对的某一位置进行交叉
def cross_tran(city_num, pop_num, next_gen, cross_prob, evbest_path):for i in range(0, pop_num):best_gen = evbest_path.copy()if cross_prob >= np.random.rand():next_gen[i, :], best_gen = intercross(city_num, next_gen[i, :], best_gen)# 部分映射交叉
def intercross(city_num, inta, intb):r1 = np.random.randint(city_num)r2 = np.random.randint(city_num)while r2 == r1:r2 = np.random.randint(city_num)left, right = min(r1, r2), max(r1, r2)ind_a1 = inta.copy()ind_b1 = intb.copy()for i in range(left, right + 1):ind_a2 = inta.copy()ind_b2 = intb.copy()inta[i] = ind_b1[i]intb[i] = ind_a1[i]# 每个个体包含的城市序号是唯一的，因此交叉时若两个不相同，就会产生冲突x = np.argwhere(inta == inta[i])y = np.argwhere(intb == intb[i])# 产生冲突，将不是交叉区间的数据换成换出去的原数值，保证城市序号唯一if len(x) == 2:inta[x[x != i]] = ind_a2[i]if len(y) == 2:intb[y[y != i]] = ind_b2[i]return inta, intb# 变异方式：翻转变异
def mutation_sub(city_num, pop_num, next_gen, mut_prob):for i in range(pop_num):if mut_prob >= np.random.rand():r1 = np.random.randint(city_num)r2 = np.random.randint(city_num)while r2 == r1:r2 = np.random.randint(city_num)if r1 > r2:temp = r1r1 = r2r2 = tempnext_gen[i, r1:r2] = next_gen[i, r1:r2][::-1]#从最后元素到第一元素复制def main():city_num = 21read = pd.read_table('21.txt', header=None, sep='\s+')#read = pd.read_csv("rebuild.txt", sep=" ", header=None)res = np.zeros((21, 21))# 求两点距离矩阵row_index = 0col_index = 0read = read.valuesfor i in range(read.shape[0]):for j in range(read.shape[1]):if row_index == city_num:breakres[row_index][col_index] = read[i][j]res[col_index][row_index] = read[i][j]if res[row_index][col_index] == 0:row_index += 1col_index = 0else:col_index += 1matrix_distance = res#print(matrix_distance)city_num = 21  # 城市数量population_num = 100  # 群体个数cross_prob = 1  # 交叉概率mut_prob = 0.2  # 变异概率iteration = 600  # 迭代代数# 初始化初代种群和距离，个体为整数，距离为浮点数pop = np.array([0] * population_num * city_num).reshape(population_num, city_num)distance = np.zeros(population_num)# 初始化种群Ini_pop(city_num, population_num, pop, distance, matrix_distance)# draw_path(city_num, city_location, pop[0], distance)  # 绘制初代图像evbest_path = pop[0]evbest_distance = float("inf")best_path_list = []best_distance_list = []# 循环迭代遗传过程for i in range(iteration):# 选择next_gen = select_lunpan(population_num, pop, distance)# 交叉cross_tran(city_num, population_num, next_gen, cross_prob, evbest_path)# 变异mutation_sub(city_num, population_num, next_gen, mut_prob)# 更新每个个体距离值(1/适应度)for j in range(population_num):distance[j] = count_dis(city_num, matrix_distance, next_gen[j, :])index = distance.argmin()  # index 记录最小总路程# 为了防止曲线波动，每次记录最优值，如迭代后出现退化，则将当前最好的个体回退替换为历史最佳if distance[index] <= evbest_distance:evbest_distance = distance[index]evbest_path = next_gen[index, :]else:distance[index] = evbest_distancenext_gen[index, :] = evbest_path# 存储每一步的最优路径(个体)及距离best_path_list.append(evbest_path)best_distance_list.append(evbest_distance)best_distance = evbest_distancebest_path = evbest_pathprint_path(city_num, best_path)print(best_distance)if __name__ == '__main__':main()

注意：由于遗传算法有概率因素影响，不像暴力求解每次都是最优解，遗传算法TSP问题可能跑多次才可能跑出最优解（21个城市我跑了十几次才跑出最优解），因此，大家多跑几次跑出最优解就可以。