自重啟偽遺傳改良算法解決TSP問題（matlab實現(xiàn)）
說明：解決旅行商問題。所有代碼和數(shù)據(jù)上傳到github矾芙，可自行下載和修改誉己。
地址：代碼和數(shù)據(jù)
1.實驗數(shù)據(jù)說明
實驗數(shù)據(jù)為ch130.mat，格式如下：
| 序號 | x坐標(biāo) | y坐標(biāo) |
|---|---|---|
| 1 | 100.312 | 140.213 |
| 2 | 122.343 | 124.343 |
| 3 | 563.378 | 123.676 |
| ... | ... | ... |
表示130個點(diǎn)的序號襟锐，x坐標(biāo)和y坐標(biāo)肃弟。
2.算法概述
本算法的靈感來自改良圈算法，可參考該博客中對改良圈的描述。改良圈算法描述
改良圈算法運(yùn)用了一個巧妙的思路组底，將初始隨機(jī)路徑快速地改良為一個較為良好的路徑，然后經(jīng)過遺傳算法筐骇，繼續(xù)收斂债鸡。但是我們在實驗中發(fā)現(xiàn)，由于改良圈算法得到的路徑已經(jīng)很優(yōu)秀铛纬，遺傳算法很難收斂下去厌均。于是有了將改良圈算法與遺傳算法結(jié)合的想法。之所以在算法的名稱中加入“自啟”和“偽”兩個詞告唆，是因為針對傳統(tǒng)遺傳算法做了修改棺弊。“自啟”指算法在可能收斂到局部最小值擒悬，無法再收斂下去的時候模她，自行重啟整個流程《粒“偽”指這個算法中將交叉率和變異率都設(shè)為了1侈净，且做了較大的改動。
算法流程圖：
算法流程圖
3.算法優(yōu)勢
快。
4.實驗結(jié)果
ch130在網(wǎng)站上給出的最優(yōu)解為6110.8畜侦，目前的程序能在較短時間內(nèi)快速收斂到6110.7元扔。用其他數(shù)據(jù)集測試的時候效果也比較良好。
最優(yōu)路徑圖
代碼附錄：
（1）改良圈
function [ A ] = circle_modification( initial_population, rows, L, distance_matrix )
% 改良圈改良一個初始種群initial_population旋膳，返回改良后的種群A
A = zeros([rows, L]);
for i=1:rows
c = initial_population(i, :);
flag = 1;
while flag > 0
flag = 0;
for m = 1:L-3
for n = m+2:L-1
if distance_matrix(c(m), c(n))+distance_matrix(c(m+1), c(n+1)) < distance_matrix(c(m), c(m+1))+distance_matrix(c(n), c(n+1))
flag=1;
c(m+1:n) = c(n:-1:m+1);
end
end
end
end
A(i,c) = 1:L;
end
end
（2）歸一化
function [ A ] = normalization( A, L )
% 對A進(jìn)行歸一化
A = A / L;
A(:, 1) = 0;
A(:, L) = 1;
end
（3）產(chǎn)生初始種群
function [ initial_population ] = generate_population( n, L )
% 產(chǎn)生指定數(shù)量n的種群
initial_population = zeros([n, L]);
for i=1:n
c = randperm(L - 2); % 生成1---(L-2)的亂序排列, 本題中為1-129
current_path = [1, c+1, L]; % 生成真正的個體澎语，最后一個數(shù)為c的第一個數(shù)，c1范圍為1-131
initial_population(i, :) = current_path;
end
end
（4）獲取距離矩陣
function [ distance_matrix ] = get_distance_matrix( point_info )
% 獲取距離矩陣
number_of_point = length(point_info);
D = pdist(point_info,'euclidean'); % 每兩點(diǎn)之間的歐式距離验懊，矩陣大小為(1,n)
distance_matrix = zeros(number_of_point + 1); % 每次都要回到起點(diǎn)咏连，因此，最后一列為到起點(diǎn)的距離
sum = 0;
for i = 1:number_of_point
if i < number_of_point
sum = sum + number_of_point - i;
distance_matrix(i, i+1:number_of_point) = D(1, sum-(number_of_point-i-1):sum); % 將已知的D距離改為矩陣形式
end
end
distance_matrix = distance_matrix + distance_matrix';
distance_matrix(1:number_of_point, number_of_point+1) = distance_matrix(1:number_of_point, 1); % 對最后一列進(jìn)行填值
distance_matrix(number_of_point+1, :) = distance_matrix(1, :); % 對最后一行進(jìn)行填值鲁森，完整的距離矩陣
end
（5）變異
function [ C ] = mutation( A, w, L, distance_matrix )
% A變異產(chǎn)生子代C
C = A;
% 對變異行的元素重新排列
for i=1:w
mutation_location = 2 + floor((L-2)*rand(1,3));
mutation_location = sort(mutation_location);
C(i,:)=C(i,[1:mutation_location(1)-1, mutation_location(2)+1:mutation_location(3), mutation_location(1):mutation_location(2), mutation_location(3)+1:L]); % 對該個體重新排列組合
end
[~, mutation_path_table] = sort(C, 2); % 對每一行的元素進(jìn)行排序祟滴，獲取所有的路徑
C = normalization(circle_modification(mutation_path_table, w, L, distance_matrix), L);
end
（6）交叉
function [ B ] = cross( A, w, L, distance_matrix )
% A交叉產(chǎn)生子代B
B = A(randperm(w), :);
for i = 1:2:w
cross_position = 2 + floor((L-2) * rand(1, 2)); % 2<F<L-1,為整數(shù)[2, L-1],首尾的點(diǎn)不去改變
sort(cross_position);
cp1 = cross_position(1);
cp2 = cross_position(2);
temp = B(i, cp1:cp2); % 交換第i個和第i+1個子代的F:L列
B(i, cp1:cp2) = B(i+1, cp1:cp2);
B(i+1, cp1:cp2) = temp;
end % 交換完畢，產(chǎn)生w個新個體
[~, cross_path_table] = sort(B, 2); % 對每一行的元素進(jìn)行排序歌溉，獲取所有的路徑
B = normalization(circle_modification(cross_path_table, w, L, distance_matrix), L);
end
（7）選取子代
function [ A_next, optimal_path, optimal_path_length ] = select_next_generation( A, B, C, w, L, distance_matrix )
% 選擇遺傳的下一代
fp = 0.3; % 外來人口比例
np = 0.2; % 非最優(yōu)比例
G = [A;B;C]; % A為原始的垄懂，B為交叉后的，C為變異后的
total_length = size(G, 1); % 父代和子代的總長度
%在父代和子代中選擇優(yōu)良品種作為新的父代
[~, path_table] = sort(G,2); % 對每一行的元素進(jìn)行排序痛垛，獲取所有的路徑
all_path_length = [];
all_path_length(1:total_length) = 0; % 初始化所有路徑的長度為0
for path_index = 1:total_length % 計算每條路徑的長度
for i = 1:L-1
all_path_length(path_index) = all_path_length(path_index) + distance_matrix(path_table(path_index, i), path_table(path_index, i+1));
end
end
[sorted_length, sorted_index] = sort(all_path_length);
A_next = G(sorted_index(1:w), :); %選出距離最短的w個子代
optimal_path = path_table(sorted_index(1), :); % 此時的最短路徑為第1個個體
optimal_path_length = sorted_length(1); % Dz為該最短路徑的實際距離
% 人人能娶老婆
up_n = w*(1-np-fp);
for i = up_n+1:w*(1-fp)
r = up_n + unidrnd(w - up_n);
A_next(i) = G(r);
end
% 加入外來人口草慧，但是前提是要對外來人口進(jìn)行優(yōu)化
A_next(int16(w*(1-fp))+1:w, :) = normalization(circle_modification(generate_population(int16(w*fp), L), int16(w*fp), L, distance_matrix), L);
（8）獲取路徑長度
function [ path_length ] = get_path_length( path, L, distance_matrix )
% 獲取路徑長度
path_length = 0;
for i = 1:L-1
path_length = path_length + distance_matrix(path(i), path(i+1));
end
end
（9）畫出路徑
function [ ] = plot_path( point_position_x_and_y, path, length )
% ?????·???·
x_=point_position_x_and_y(path,1);
y_=point_position_x_and_y(path,2);
plot(x_,y_,'-o');
title(length);
drawnow;
end
（10）主函數(shù)
tic
clc,clear
rng('shuffle'); %改變隨機(jī)數(shù)的初始狀態(tài)
% -----------------參數(shù)------------------
w = 500; % 種群規(guī)模
restart_times = 200; % 重啟次數(shù)
iterations = 300; % 迭代次數(shù)
repeat_time_threshold = 100; % 重復(fù)次數(shù)閾值
% ---------------------------------------
% 從文件中讀取信息
load ch130.mat % 載入數(shù)據(jù)集
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; % 為了保證最終能回到起點(diǎn)，實際的個體長度設(shè)為L匙头，L的最后一個數(shù)和第一個數(shù)相同漫谷，保證回到起點(diǎn)
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; % 記錄單次遺傳算法中上一次最佳路徑長度，用于判斷是否陷入局部最優(yōu)解
same_time = 0; % 單次遺傳算法陷入局部最優(yōu)解的次數(shù)
% 產(chǎn)生初始種群
initial_population = generate_population(w, L);
% 改良圈改良初始種群
A = circle_modification(initial_population, w, L, distance_matrix);
% 歸一化
A = normalization(A, L);
% 以下為遺傳算法實現(xiàn)過程
for k=1:iterations
% 交叉產(chǎn)生子代 B
B = cross(A, w, L, distance_matrix);
% 變異產(chǎn)生子代 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);
% 更新全局最優(yōu)路徑長度
if current_optimal_path_length < optimal_path_length
optimal_path_length = current_optimal_path_length;
optimal_path = current_optimal_path;
end
% 繪制最優(yōu)路徑圖
plot_path(point_position_x_and_y, current_optimal_path, current_optimal_path_length)
% 輸出每次迭代的信息
fprintf('第%0d次重啟蹂析，迭代次數(shù)%04d舔示，最優(yōu)路徑長度%.5f，全局最優(yōu)路徑長度%.5f\n' , r_index, k, current_optimal_path_length, optimal_path_length);
% 記錄重復(fù)次數(shù)（重復(fù)次數(shù)過高表示陷入局部最優(yōu)解）
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 % 輸出程序運(yùn)行的時間
