A list,

Travel salesman problem (TSP problem). Suppose there is a traveling businessman who wants to visit 31 capital cities in China, and he needs to choose the route he wants to take. The limit of the route is that he can visit each city only once, and he must return to the original city at the end. Path selection requires that the distance of the selected path is the minimum among all paths.



1. Ant colony algorithm is proposed

Ant Colony Optimization algorithm (ACO), also known as ant algorithm, is a probabilistic algorithm used to find optimal paths. It was proposed by Marco Dorigo in his PhD thesis in 1992 and was inspired by the behavior of ants in finding their way to food. Genetic algorithm has been applied in pattern recognition, neural network, machine learning, industrial optimal control, adaptive control, biological science, social science and so on.

2. Basic principles of the algorithm





Ii. Source code

% % % % % % % % % % % % % % % % % % % % % % % % % initialization % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % clear all; Close all; % qing figure CLC; CLS m = %50; % Number of ants Alpha=1; % Pheromone importance parameter Beta=5; % Heuristic factor importance parameter Rho=0.1; % pheromone evaporation coefficient G_max=200; % Maximum number of iterations Q=100; % pheromone increased intensity coefficient C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; .3238 1229;4196 1044;4312  790;4386  570;3007 1970;2562 1756; .2788 1491;2381 1676;1332  695;3715 1678;3918 2179;4061 2370; .3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376; .3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826; .2370 2975];                 %31A provincial city coordinates % % % % % % % % % % % % % % % % % % % % % % % % first step: variable initialization % % % % % % % % % % % % % % % % % % % % % % % % n = size (C,1); %n indicates the size of the problem (number of cities) D= Zeros (n,n); %D represents the distance interval matrix of two citiesfor i=1:n
    for j=1:n
        if i~=j
            D(i,j)=((C(i,1)-C(j,1)) ^2+(C(i,2)-C(j,2)) ^2) ^0.5;
        else
            D(i,j)=eps;
        end
        D(j,i)=D(i,j);
    end
end
Eta=1./D; %Eta is the inspiration factor, which is set as the reciprocal of distance Tau=ones(n,n); %Tau is the pheromone matrix Tabu= Zeros (m,n); % stores and records path generation NC=1; % iteration counter R_best=zeros(G_max,n); % L_best=inf.*ones(G_max,1); % Length of optimal route of each generation Figure (1); % optimization solutionwhileNC < = G_max % % % % % % % % % % % % % % % % % % in the second step: put m ant in n city on % % % % % % % % % % % % % % % % Randpos = [];for i=1: (ceil(m/n))
        Randpos=[Randpos,randperm(n)];
    end
    Tabu(:,1)=(Randpos(1.1:m))'; %%%%% Step 3: M ants select the next city according to the probability function and complete their respective tour %%%%%% for j=2:n for I =1:m visited=Tabu(I,1: J-1)); % Visited city J=zeros(1,(n-j+1)); % City to be visited P=J; % Selection probability distribution of cities to be visited Jc=1; for k=1:n if length(find(visited==k))==0 J(Jc)=k; Jc=Jc+1; End end % % % % % % % % % % % % % % % % % % calculation for the probability distribution of the city % % % % % % % % % % % % % % % % for k = 1: length (J) (k) = P (Tau (visited (end), J (k)) ^ Alpha)... *(Eta(visited(end),J(k))^Beta); end P=P/(sum(P)); % % % % % % % % % % % % % % % % according to probability principle of selecting the next city % % % % % % % % % % % % % % % % Pcum = cumsum (P); Select=find(Pcum>=rand); to_visit=J(Select(1)); Tabu(i,j)=to_visit; end endCopy the code

3. Operation results



Fourth, note

Version: 2014 a