A list,
1 profileAn algorithm designed to simulate ant foraging behavior (shortest path principle). Take the characteristics of ant foraging and abstract them into a mathematical description.
• Ant Colony Algorithm (ACA) was first proposed by Marco Dorigo in 1992 in his doctoral thesis. • Ants release a pheromone in their path as they search for a food source and are able to sense the pheromone released by other ants. The pheromone concentration represents the distance of the path. The higher the pheromone concentration, the shorter the corresponding path distance. • In general, ants preferentially choose the path with a higher pheromone concentration, and release a certain amount of pheromone to enhance the pheromone concentration in that path, thus creating a positive feedback. Eventually, the ants are able to find the best route from the nest to the food source, which is the shortest distance. • Biologists have also found that pheromone concentrations along the pathway decline over time. • Ant colony algorithm is applied to solve optimization problems. The basic idea is that the feasible solution of the problem to be optimized is represented by the ant walking path, and all the paths of the entire ant colony constitute the solution space of the problem to be optimized. With the advance of time, the concentration of pheromone accumulated on the short path gradually increased, and the number of ants choosing the short path also increased. Finally, the entire ant will concentrate on the best path under the action of positive feedback, and then the corresponding optimal solution of the problem to be optimized. Analogizing GA (genetic algorithm) crossover, selection, mutation, PSO (particle swarm optimization) of individual, population extreme value optimization, ANT colony algorithm also has its own optimization strategy: positive feedback information mechanism, pheromone concentration update, ants can access the path selection.
2. Basic IdeasThe basic principle of ant colony algorithm comes from the shortest path principle of ants foraging in nature. According to the observation of entomologists, it is found that although the natural ant vision is underdeveloped, it can find the shortest path from the food source to the nest without any hint, and can adapt to search for the best new path when the environment changes (such as obstacles on the original path). How do ants do this? It turns out that ants in search of a food source can place pheromones, or pheromones, which are unique to ants, along their path, so that other ants within a certain range can detect them and influence their future behavior. When their ants’ through some path, its left by more and more, so that the pheromone strength increase (of course, with the passage of time will gradually weaken, so the ant chooses the path of the probability is higher, thus increased the path pheromone intensity, the selection process is referred to as the catalytic behavior of ants. Since the principle is a positive feedback mechanism, the ant kingdom can also be understood as a so-called enhanced learning system. Here we use a diagram to illustrate the principle of ants’ shortest path selection for foraging, as shown in the figure. In, suppose there is an obstacle between point A and point B, which is the ant’s nest, and point B, which is the food, then the ant going from point A to point B must decide whether to go left or right, and the ant going from point B to point A must also decide which path to take. This decision is influenced by the concentration of previous pheromones (known as residual pheromone concentrations) left by ants along each path. If the pheromone concentration on the right path was higher, the right path was more likely to be selected by the ant. But the first group of ants, with little or no pheromone influence, were just as likely to go left or right, as the figure shows. With the progress of foraging process, pheromone intensity on each road began to change, some lines were strong, some lines were weak. Let’s take an ant going from point A to point B (the process is basically the same for an ant going from point B to point A). Since the path ADB is shorter than the path ACB, the first ant that chooses ADB arrives at point B sooner than the first ant that chooses ACB. At this point, from point B to point A, the pheromone concentration on path BDA A is larger than that on path BCA. Therefore, from the next moment, the ants from point B to point A are more likely to choose THE BDA path than the BCA path, which further enhances the pheromone on the ABDA route. As A result, the ants that choose the path based on the pheromone intensity of D gradually prefer the path ADB, as shown in the figure. Over time, almost all the ants chose the ADB(or BDA) path to carry the food, and we also found that the ADB path was actually the shortest path. The principle of this colony path finding can be simply understood as follows: for individual ants, there is no subjective intention to find the shortest path; But for the entire ant colony, they do have the visual effect of finding the shortest path. In nature, the process of ant colony searching for a path is a positive feedback process, and the “ant colony algorithm” is derived by simulating the principle of ants foraging for the shortest path in biology. For example, if we consider work units with simple functions as “ants”, then the process of path finding can be used to explain the optimization process of human worker ant colony in ant colony algorithm. That’s the basic idea of ant colony algorithm.
4 Mathematical Model
Ii. Source code
% % % % % % % % % % % % % % % % % % % % of ant colony algorithm to solve TSP problem % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % initialization % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % clear all; % clear all variables 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 strength 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 spacing matrix of the 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 heuristic factor, here Tau=ones(n,n); %Tau is the pheromone matrix Tabu= Zeros (m,n); % Store and record the generated NC= of path1; % iteration counter R_best=zeros(G_max,n); L_best=inf.*ones(G_max,1); The length of the best route for each generation1); % 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 tour %%%%%% for j=2:n for I =1:m visited=Tabu(I,1:(j-1)); J=zeros(1,(n- J +1)); % Cities 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 end if NC>=2 Tabu(1,:)=R_best(NC-1,:); End % % % % % % % % % % % % % % % % % % % the fourth step: record the iterative optimal route % % % % % % % % % % % % % % % % % % L = zeros (m, 1); for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1)); end L(i)=L(i)+D(R(1),R(n)); end L_best(NC)=min(L); pos=find(L==L_best(NC)); R_best(NC,:)=Tabu(pos(1),:); % % % % % % % % % % % % % % % % % % % % % % % % % step 5: update the pheromone % % % % % % % % % % % % % % % % % % % % % % Delta_Tau = zeros (n, n); for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=... Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); end Delta_Tau(Tabu(i,n),Tabu(i,1))=... Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); End % % % % % % % % % % % % % % % % % % % % % % % fitness function % % % % % % % % % % % % % % % % % % % % % % % function value = func (x, y) value * (x ^ 2 = 20 - y ^ 2) ^ 2 - (1 - y) ^ 2-3 * (1 + y) ^ 2 + 0.3;Copy the codeThird, the operation result
Fourth, note
Version: 2014 a