1 简介
旅行者问题是在理论研究和实际应用领域具有重要研究价值的经典组合优化问题.本文通过变异率的自适应策略平衡算法的全局性和局部性，提出了一种自适应遗传算法，并利用外部归档策略为种群进化提供全局指导信息，提高了算法的收敛速度.通过对TSPLIB测试标准库中的实例，验证了算法的可行性和有效性.
在理论计算机科学和运筹学研究中，旅行者问题是一种复杂的组合优化问题。问题易于描述但难以求解，是典型的NP难问题。旅行者问题的目标通常是最小化总行程，所有节点必须访问一次。可应用于电路板设计、无线传感器网络、交通网络、物流配送等各个领域。解决旅行者问题的算法包括遗传算法、爬山算法、模拟退火算法、蚁群算法、禁忌搜索算法、粒子群算法等。
2 部分代码
tic clc,clear rng('shuffle'); 随机数变随机数的初始状态 % -----------------参数------------------ w=500; % 种群规模 restart_times=200; % 重启次数 iterations=300; % 迭代次数 repeat_time_threshold=100; % 重复次数阈值 % --------------------------------------- % 从文件中读取信息 loadch130.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; % 为确保最终能回到起点，实际的个体长度设定为L，L最后一个数和第一个数一样，保证回到起点 optimal_path=zeros([1,L]); % 记录全球最佳路径 optimal_path_length=999999; % 记录全球最佳路径的长度 forr_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); % 以下是遗传算法实现的过程 fork=1: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); % 更新全局最优路径长度 ifcurrent_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('第 次重启，迭代次数d，最优路径长度%%.5f，全局最优路径长度%%.5f\n',r_index,k,current_optimal_path_length,optimal_path_length); % 记录重复次数(重复次数过高意味着局部最优解) ifcurrent_optimal_path_length==last_optimal_path_length same_time=same_time 1; ifsame_time>=repeat_time_threshold break; end else same_time=0; % 重置same_time end % 更新last_optimal_path_length last_optimal_path_length=&nbs;current_optimal_path_length;
end
end
toc % 输出程序运行的时间
3 仿真结果
4 参考文献
[1]刘景鑫, 李林林, 李治华,等. 一种求解旅行商问题的基于外部存档的自适应遗传算法[J]. 计算机时代, 2019(7):3.