1 简介旅行商问题是一类经典的组合最优化问题,在理论研究和实际应用领域具有重要的研究价值.本文提出了一种自适应遗传算法,通过变异率的自适应策略平衡算法的全局性和局部性,同时利用外部存档策略为种群进化提供具有全局指导信息的父代个体,提高了算法的收敛速度.通过对TSPLIB标准库中实例的测试,验证了算法的可行性和有效性.旅行商问题是一类复杂的组合优化问题在理论计算机科学和运筹学研究中非常重要。问题易于描述但难以求解是典型的NP难问题。旅行商问题的目标通常是最小化总行程而且所有节点都必须访问一次。旅行商问题可以被应用与各个领域如电路板设计、无线传感器网络、交通网络、物流配送等领域。求解旅行商问题的算法包括遗传算法、爬山算法、模拟退火算法、蚁群算法、禁忌搜索算法、粒子群算法等。​2 部分代码tic clc,clear rng(shuffle); %改变随机数的初始状态 % -----------------参数------------------ w 500; % 种群规模 restart_times 200; % 重启次数 iterations 300; % 迭代次数 repeat_time_threshold 100; % 重复次数阈值 % --------------------------------------- % 从文件中读取信息 load ch130.mat % 载入数据集 point_info ch130(:, 2:3); point_position_x_and_y [point_info; point_info(1,:)]; distance_matrix get_distance_matrix(point_info); L length(ch130) 1; % 为了保证最终能回到起点实际的个体长度设为LL的最后一个数和第一个数相同保证回到起点 optimal_path zeros([1, L]); % 记录全局最佳路径 optimal_path_length 999999; % 记录全局最佳路径的长度 for r_index 1:restart_times current_optimal_path zeros([1, L]); % 记录每次重启的最佳路径 current_optimal_path_length 999999; % 记录每次重启的最佳路径长度 last_optimal_path_length current_optimal_path_length; % 记录单次遗传算法中上一次最佳路径长度用于判断是否陷入局部最优解 same_time 0; % 单次遗传算法陷入局部最优解的次数 % 产生初始种群 initial_population generate_population(w, L); % 改良圈改良初始种群 A circle_modification(initial_population, w, L, distance_matrix); % 归一化 A normalization(A, L); % 以下为遗传算法实现过程 for k1:iterations % 交叉产生子代 B B cross(A, w, L, distance_matrix); % 变异产生子代 C C mutation(A, w, L, distance_matrix); % 选择下一代 [A, current_optimal_path, current_optimal_path_length] select_next_generation(A, B, C, w, L, distance_matrix); % 更新全局最优路径长度 if current_optimal_path_length optimal_path_length optimal_path_length current_optimal_path_length; optimal_path current_optimal_path; end % 绘制最优路径图 plot_path(point_position_x_and_y, current_optimal_path, current_optimal_path_length) % 输出每次迭代的信息 fprintf(第%0d次重启迭代次数%04d最优路径长度%.5f全局最优路径长度%.5f\n , r_index, k, current_optimal_path_length, optimal_path_length); % 记录重复次数重复次数过高表示陷入局部最优解 if current_optimal_path_length last_optimal_path_length same_time same_time 1; if same_time repeat_time_threshold break; end else same_time 0; % 重置same_time end % 更新last_optimal_path_length last_optimal_path_length current_optimal_path_length; end end toc % 输出程序运行的时间3 仿真结果4 参考文献[1]刘景鑫, 李林林, 李治华,等. 一种求解旅行商问题的基于外部存档的自适应遗传算法[J]. 计算机时代, 2019(7):3.博主简介擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真有科研问题可私信交流。部分理论引用网络文献若有侵权联系博主删除。