The basic principle of ant colony algorithm
1. Ants release pheromones along the path.
Encounter hasn’t walked the intersection, randomly choose a road to go. At the same time, pheromones related to path length are released.
3. Pheromone concentration is inversely proportional to path length. When later ants come across the intersection again, they choose the path with higher pheromone concentration.
4. The pheromone concentration on the optimal path increases.
5. Finally, the ant colony finds the optimal feeding path.
There are more ants on the shorter side of the colony than on the longer side, leaving more pheromones behind, and over time the ants only go on the shorter side.
Ant colony algorithm has two main steps to solve TSP :(TSP problem is to find the shortest Hamilton loop)
1. Path construction
Random proportion rule in AS; For each ant K, the path memory vector R^ K records the serial number of all cities k has passed through according to the access order. Suppose ant K’s current city is I, then its probability of selecting city J as the next access object is:
2. Pheromone renewal
Here m is the number of ants, ρ is the evaporation rate of the pheromone, specified 0≤ ρ≤1, in AS usually set to ρ =0.5, δ τij is the amount of pheromone released by the KTH ant on the side it passes, which is equal to the inverse of the length of the construction path of ant K round. C to the k is the length of the path, which is the sum of the lengths of all the edges in R to the k.
Construction diagram: The construction diagram is consistent with the problem description diagram. The set C of components corresponds to the set of points (C=N), and the set of connecting corresponding edges (L=A), and each edge has A weight, representing the distance between points I and j.
Constraints: All cities must be visited and each city must be visited at most once.
Pheromone and heuristic information: The pheromone in the TSP problem represents the expectation of visiting city J directly after visiting city I. The heuristic information value is inversely proportional to the distance between city I and city J.
Solution construction: Each ant starts from a randomly selected city, and after each iteration, the ant adds a city that has not yet been visited to the solution. When all cities have been visited by ants, the construction of the solution terminates.
The ant colony algorithm has defects:
Ant colony algorithm can barely be used to solve small-scale TSP problems, and it takes a little time to find the optimal solution. However, if the problem is large, the performance of ant colony algorithm will be extremely low, or even stuck. So you can make improvements, like the Elite ant system.
The elite ant system is an improvement of the basic ant colony algorithm, which adds an enhancement method to the optimal path on the basis of the original AS pheromone updating principle. At the end of each pheromone update, the ant that has found the best path so far will add additional pheromones to the path. The introduction of such additional pheromone enhancement means in the elite ant system helps to better guide the bias of ant search and make the algorithm converge faster
Second, the code
% Ant main program clear all; close all; clc; tic; Ant=25; % ant count Ger=120; % number of iterations first_address = [100,10 150,10 180,30 200,10 200,200 200,220 180,240 180,270 150,270 100,240 80,240 50,270 200,300,300,270,240,200, 10,10 50,30, 100,10]; SumOfCity = size(first_address,1); Length_address =10000.*ones(SumOfCity,SumOfCity); Length_address (1,2)=377; length_address(1,2)=377; % indicates the distance between node 1 and node 2 length_address(2,4)=190; Length_address (2, 3) = 100; Length_address (3, 4) = 101; Length_address (4, 5) = 240; Length_address (5) in 2 = 1932; Length_address (5, 6) = 70; Length_address (6, 13) = 200; Length_address (6, 7) = 63.1; Length_address (7, 10) = 377; Length_address (7, 8) = 87.5; Length_address (8, 9) = 100; Length_address (10, 11) = 8; Length_address (9, 10) = 170.8; Length_address (9, 12) = 332.9; Length_address (11, 12) = 168.8; Length_address 16th (11) = 375.2; Length_address (12, 15) = 135.1; Length_address (13, 14) = 458; Length_address (14, 15) = 100; Length_address (15th and 16th) = 86.7; Length_address (16 or 17) = 187.5; Length_address (17, 18) = 639.8; Length_address (18, 20) = 510.5; Length_address (18th and 19th) = 200.1; Length_address (19, 20) = 246.8; for n=1:size(first_address) for m=1:size(first_address) if length_address(n,m)~=10000 length_address(m,n)=length_address(n,m); End end power=length_address; % distance [PM PN]=size(power); % distance matrix size, number of rows %% % draw the node distribution graph % figure(1); % grid on; % hold on; % scatter(first_address(:,1),first_address(:,2)); % for i=1:PN % for j=1:PN % if(length_address(i,j)~=10000) % line([first_address(i,1),first_address(j,1)],[first_address(i,2),first_address(j,2)],'Color','g'); Line % % text((first_address(i,1)+first_address(j,1))/2,(first_address(i,2)+first_address(j,2))/2,num2str(length_address(i,j))); % Mark line segment distance % end % end % End % Initialize Ant location v=init_population(Ant,PN); v(:,1)=1; % starting point v (:, PN) = 1; The finish fit = % short_road_fun (v, the power); % Find the distance between each path T0 = Max (fit)-fit; % Initialize vmFit =[]; vx=[]; P0 = 0.2; % P0---- Global transfer selection factor P=0.8; % P ---- pheromone evaporation coefficient %C=[]; For i_ger=1: lamda=1/i_ger; % transfer step parameter [T_Best(i_ger),BestIndex]= Max (T0); For j_g=1:Ant % r=T0(BestIndex) -t0 (j_g); Prob(i_ger,j_g)=r/T0(BestIndex); If Prob(i_ger,j_g_tr)<P0 M=rand(1,PN)<lamda; if Prob(i_ger,j_g_tr)<P0 M=rand(1,PN)<lamda; temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; else M=rand(1,PN)<P0; temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; end temp(:,1)=1; Temp (:,end)=1; % Determine whether the temporary path distance after transformation is smaller than the original path, If short_road_fun(temp,power)<short_road_fun(v(j_g_tr,:),power) v(j_g_tr,:)=temp; End End % Pheromone update [sol,indb]=min(fit); v(1,:)=v(indb,:); % First ant path save minimum path media=mean(fit); vx=[vx sol]; % vmfit=[vmfit media]; End % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % final result shows that the optimal solution and optimal value % v (indb, :) disp(sprintf('Code of shortroad is: %s',num2str(v(indb,:)))); disp(sprintf('\n')); Disp (sprintf('Shortroad is: %s',num2str(find(v(indb,:))))); disp(sprintf('Mininum is: %d',sol)); route=find(v(indb,:)); % Draw the node distribution figure figure(2); grid on; hold on; for i=1:PN-1 plot(first_address(i,1),first_address(i,2),'bo','MarkerSize',10); str=num2str(i); text(first_address(i,1)-10,first_address(i,2)+10,str,'Color','red','FontSize',15); end m=length(route); for i=1:m The plot (first_address (route (I), 1), first_address (route (I), 2), 'MarkerSize', 10, 'MarkerEdgeColor', 'k', 'MarkerFaceColor, [0.5, 0. 5,0.5]); hold on; end for i=1:PN for j=1:PN if(length_address(i,j)~=10000) line([first_address(i,1),first_address(j,1)],[first_address(i,2),first_address(j,2)],'Color','g','LineWidth',5); % crossed text((first_address(i,1)+first_address(j,1))/2,(first_address(i,2)+first_address(j,2))/2,num2str(length_address(i,j))); For p=1:m-1 if(route(p+1)~=20) line([first_address(route(p),1),first_address(route(p+1),1)],[first_address(route(p),2),first_address(route(p+1),2)],'Co lor','r','LineWidth',5); % crossed text((first_address(route(p),1)+first_address(route(p+1),1))/2,(first_address(route(p),2)+first_address(route(p+1),2))/2 ,num2str(length_address(route(p),route(p+1)))); % marks line segment distance else Line ([first_address (route (p), 1), first_address (1, 1)], [first_address (route (p), 2), first_address (1, 2)], 'Color', 'r', 'LineWidt h',5); % crossed The text ((first_address (route (p), 1) + first_address (1, 1)) / 2, (first_address (route (p), 2) + first_address (1, 2)) / 2, num2str (length_ad dress(route(p),route(p+1)))); Figure (3); End End Axis ([0 250 0 400]) % plot(vx); % title(' optimal, average function value trend '); % xlabel('Generations'); % ylabel('f(x)'); % hold on; % plot(vmfit,'r'); % hold off; runtime=tocCopy the code
The complete code to download www.cnblogs.com/ttmatlab/p/…