tsp_demo.zip_DEMO_免疫算法_免疫算法TSp

function varargout = tsp_demo(xy,dmat,pop_size,num_iter,show_prog,show_res) % Input: % XY (float) 每點的XY座標Nx2矩陣 % DMAT (float) 點對點得NxN距離矩陣 % POP_SIZE (scalar integer) 母體數 (should be divisible by 4) % NUM_ITER (scalar integer) 疊代次數is the number of desired iterations for the algorithm to run % SHOW_PROG (scalar logical) shows the GA progress if true % SHOW_RES (scalar logical) shows the GA results if true % Output: % OPT_RTE (integer array) 最佳路徑 % MIN_DIST (scalar float) 最佳路徑的total距離 % Process Inputs and Initialize Defaults nargs = 6; for k = nargin:nargs-1 %步驟 switch k case 0 xy %隨機輸入50個點各為x、y(2)距離 用excell輸入node case 1 N = size(xy,1); %判斷xy列表示有幾點(城市) a = meshgrid(1:N); %求算距離用(排列方式) dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);%求兩點矩陣距離，並將其轉回網格型態 (a'=轉置矩陣)reshape 矩?變? case 2 pop_size = 100; case 3 num_iter = 1e4; case 4 show_prog = 1; case 5 show_res = 1; otherwise end end % Verify Inputs %辨別輸入矩陣是否合乎網格型態 [N,dims] = size(xy); [nr,nc] = size(dmat); if N ~= nr || N ~= nc error('Invalid XY or DMAT inputs!') end n = N; % Sanity Checks pop_size = 4*ceil(pop_size/4); %pop_size = 100 num_iter = max(1,round(real(num_iter(1)))); %num_iter = 1e4 最大疊代 show_prog = logical(show_prog(1)); %show_prog = 1 show_res = logical(show_res(1)); %show_res = 1 % Initialize the Population pop = zeros(pop_size,n); %形成一個n點(行)疊代(列)的矩陣 for k = 1:pop_size pop(k,:) = randperm(n) %形成K列的舉陣元素為n(行為n)=n點path {pop為一個rand 100種的路徑} end % Run the tsp global_min = Inf; total_dist = zeros(1,pop_size); %將各組距離形成列n點行便於辨識第n組為最佳解 dist_history = zeros(1,num_iter); %num_iter = max(1,round(real(num_iter(1)))); %num_iter = 1e4 tmp_pop = zeros(4,n); new_pop = zeros(pop_size,n); if show_prog pfig = figure('Name','TSP_demo | Current Best Solution','Numbertitle','off'); end for iter = 1:num_iter % Evaluate Each Population Member (Calculate Total Distance) for p = 1:pop_size d = dmat(pop(p,n),pop(p,1)); % Closed Path %pop = zeros(pop_size,n) %dmat距離矩陣 終點到起點的距離連成封閉path距離 for k = 2:n d = d + dmat(pop(p,k-1),pop(p,k)); %各組起點到終點的路徑距離 end total_dist(p) = d; %各組起點到終點形成一個cycle的path距離共(P組) end % Find the Best Route in the Population [min_dist,index] = min(total_dist); dist_history(iter) = min_dist; %最後疊代要是最小距離組 if min_dist < global_min %替換全域最佳解 global_min = min_dist; opt_rte = pop(index,:); %顯示最佳路徑 if show_prog % Plot the Best Route figure(pfig); % pfig = figure('Name','TSP_GA | Current Best Solution','Numbertitle','off'); rte = opt_rte([1:n 1]); %最佳路徑的起始到目標點再到起始點 rte為最佳路徑矩陣 if dims == 2 plot(xy(rte,1),xy(rte,2),'r.-'); end %表畫2維的最佳路徑座標用red 虛線 title(sprintf('Total Distance = %1.4f, Iteration = %d',min_dist,iter));%特定輸出字串%讀取1.4位置滿格%讀取實數 end end % Genetic Algorithm Operators rand_pair = randperm(pop_size); for p = 4:4:pop_size %rand_pair(p-3:p)求亂數的每四個元素% rtes = pop(rand_pair(p-3:p),:); %pop = zeros(pop_size,n) %由p = 4:4:pop_size選擇pop中的一組路徑 dists = total_dist(rand_pair(p-3:p)); %抽中四組的path總距離 [ignore,idx] = min(dists); %四組中最短距離的path node best_of_4_rte = rtes(idx,:); ins_pts = sort(ceil(n*rand(1,2))); %Cei朝正無限大方向取整數 n點內隨機%sort 由小到大排序 %兩點交叉 I = ins_pts(1); J = ins_pts(2); for k = 1:4 % Mutate the Best to get Three New Routes tmp_pop(k,:) = best_of_4_rte; %複製4列最短路徑node switch k case 2 % Flip tmp_pop(k,I:J) = fliplr(tmp_pop(k,I:J));%fliplr 矩陣的左右翻轉%第K列元素I:J(I:J為隨機)%挑出K列I:J元素 case 3 % Swap tmp_pop(k,[I J]) = tmp_pop(k,[J I]);%挑出K列路徑J i 對應的兩個node case 4 % Slide tmp_pop(k,I:J) = tmp_pop(k,[I+1:J I]);%tmp_pop(k,[I+1:J I])=tmp_pop(k,[I+1:J,I])挑出I+1到j元素及I元素 otherwise % Do Nothing end end new_pop(p-3:p,:) = tmp_pop; end pop = new_pop; end if show_res % Plots the tsp Results figure('Name','TSP_demo | Results','Numbertitle','off'); subplot(2,2,1); %subplot 創建子視窗切成2X2畫圖1 if dims == 2 plot(xy(:,1),xy(:,2),'k.'); end title('City Locations'); subplot(2,2,2); imagesc(dmat(opt_rte,opt_rte));%opt_rte = pop(index,:); %顯示最佳路徑 %imagesc 顯示亮度影像 title('Distance Matrix'); subplot(2,2,3); rte = opt_rte([1:n 1]); if dims == 2 plot(xy(rte,1),xy(rte,2),'r.-'); end title(sprintf('Total Distance = %1.4f',min_dist)); subplot(2,2,4); plot(dist_history,'b','LineWidth',2);% dist_history = 遍歷的短暫最佳path title('Best Solution History'); set(gca,'XLim',[0 num_iter+1],'YLim',[0 1.1*max([1 dist_history])]); % set 建立對象特性 %握把=gca %每一代最大距離為其區間 end % Return Outputs if nargout varargout{1} = opt_rte varargout{2} = min_dist end