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;              % 为了保证最终能回到起点，实际的个体长度设为L，L的最后一个数和第一个数相同，保证回到起点

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 k=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);
       
       % 更新全局最优路径长度
       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仿真，有科研问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。