The basic idea of ant colony algorithm:
Basic principles 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.
Comparison between human worker ant colony and real ant colony:
Basic ant colony algorithm based on TSP problem:
In the TSP solution, it is assumed that each ant in the ant colony algorithm is a simple agent with the following characteristics:
On each trip, each ant leaves pheromones on its path (I, J).
The probability of the ant choosing a city is related to the distance between cities and the pheromone allowance contained in the current connection branch.
ƒ in order to enforce legal travel of ants, the ant shall not be allowed to travel to the city visited until the completion of a trip (this can be controlled by a prohibited table).
Two basic ant colony processes:
(1) State transfer
(2) Pheromone update
(1) State transfer
In order to avoid drowning the heuristic information with too many residual pheromones, the residual information should be updated after each ant completes a step or traverses all N cities (i.e., the end of a cycle).
Thus, the amount of information on path (I,j) at t+n moment can be adjusted according to the following rules:
(2) Pheromone updating model
Ant Cycle model
Ant Quantity model
Ant Density model
The difference between:
1. Ant cycle model uses global information, that is, ants update pheromones on all paths after completing a cycle;
2. Ant quantity and ant density model uses local information, that is, ants update pheromones on the path after completing one step.
The basic flow of ant colony algorithm:
Selection of main parameters in ant colony algorithm:
The ideal selection of main parameters in ant colony algorithm is as follows:
At home and abroad, there are many research achievements on the improvement of discrete domain ant colony algorithm, such as adaptive ant colony algorithm, ant colony algorithm based on pheromone diffusion, etc. Here, only the adaptive ant colony algorithm of discrete domain optimization problem is introduced.
Adaptive ant colony algorithm: the ant colony algorithm adopts adaptive adjustment strategy for the state transition probability, pheromone volatilization factor, information amount and other factors of the ant colony algorithm.
The two most classical methods of adaptive AntColony algorithm are AntColony System (ACS) and max-minant System (MMAS).
Ant colony system to improve the basic ant colony algorithm:
① The state transition rules of ants are different;
② Different global update rules;
③ A local update rule is added to adjust the information amount of each path
Python %{ant colony algorithm to solve VRP problem [algorithm description] First implement an Ant class, use this ant class to implement the search. The algorithm follows the TSP problem, but there is a difference in the final path calculation. For example, if there are 10 bank branches, and branch 1 is the bank center, the path searched by ant is 1,3,5,9,4,10,2,6,8,7. When calculating the path, put the dot into the distribution line in turn. Before each dot, check whether the dot will exceed the maximum load of the armored car after it is put in. If not, put it in. %} % clear all variables and class definitions clear; clear classes; % Ant colony algorithm parameters (global variables) global ALPHA; % global BETA; % expectation factor global ANT_COUNT; % count global CITY_COUNT; % number of outlets global RHO; % pheromone residual coefficient!! global IT_COUNT; % number of iterations global DAry; % The distance between two branches % Two or two outlets of pheromone global CITYWAry; % point goods demand global VW; % vans weight % = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = % set parameters variable values ALPHA = 1.0; BETA = 2.0; RHO = 0.95; IT_COUNT=1000; VW=100; % = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = % read data and based on the data set other parameters load of reading data. TXT. City_xy_ary =data(:,2:3); CITYWAry=data(:,4); X_label =data(:,2); % second column y_label=data(:,3); % C=[x_label y_label]; CITY_COUNT=length(CITYWAry); ANT_COUNT=round(CITY_COUNT*2/3)+1; % The number of ants is set according to the number of dot, generally set as 2/3 of the number of dot MMAS pheromone parameter % To calculate the ratio between the maximum pheromone and the minimum pheromone PBest=0.05; % probability of ant finding optimal solution temp=PBest^(1/CITY_COUNT); TRate=(1-temp)/((CITY_COUNT/2-1)*temp); % The ratio between the maximum pheromone and the minimum pheromone % The maximum pheromone and the minimum pheromone is set to whatever the initial value is % The first search will generate an optimal solution, which will then be used to reproduce the maximum and minimum value Tmax=1; % maximum pheromone Tmin=Tmax*TRate; % pheromone minimum % Calculates the distance between two nodes DAry=zeros(CITY_COUNT); for i=1:CITY_COUNT for j=1:CITY_COUNT DAry(i,j)=sqrt((city_xy_ary(i,1)-city_xy_ary(j,1))^2+(city_xy_ary(i,2)-city_xy_ary(j,2))^2); End end % TAry=zeros(CITY_COUNT); TAry=TAry+Tmax; % = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = % to initialize the random seed rand (' state ', the sum (100 * clock)); %rand('twister',sum(100*clock)) % defines ant mayi=ant(); Best_Path_Length=10e9; % Optimal path length, set to a large value tm1=datenum(clock); FoundBetter=0; L_best=zeros(IT_COUNT,1); % start search for I =1:IT_COUNT fprintf(' start search %d, remaining %d ', I,IT_COUNT-i); FoundBetter=0; For j=1:ANT_COUNT % ant Search once mayi=Search(mayi); Length_Ary(j)=get(mayi,'path_length'); % get ant search path Path_Ary{j}=get(mayi,'path'); Length_Ary(j) < Best_Path_Length; Best_Path_Length=Length_Ary(j); Best_Path=Path_Ary{j}; % FoundBetter=1; end %L_best(i)=max(Length_Ary); end L_best(i)=Best_Path_Length; If (FoundBetter == 1) fprintf(', FoundBetter == 1) '); Best_Path=opt2(Best_Path); Best_Path_Length=PathLength(Best_Path); End % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - % all ants search out a pheromone update environment TAry = TAry * RHO; % Only globally optimal ants release pheromone dbQ=1/Best_Path_Length; for k=2:CITY_COUNT m=Best_Path(k-1); % n=Best_Path(k); TAry(m,n)=TAry(m,n)+dbQ; TAry(n,m)=TAry(m,n); TAry(n,1)=TAry(n,1)+dbQ; TAry(1,n)=TAry(n,1); % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - % finish updating pheromone, border checks Tmax = 1 / ((1 - RHO) * Best_Path_Length); % maximum pheromone Tmin=Tmax*TRate; For m=1:CITY_COUNT for n=1:CITY_COUNT if (m,n)>Tmax) TAry(m,n)=Tmax; end if (TAry(m,n)<Tmin) TAry(m,n)=Tmin; End end end % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - % line fprintf (' \ n '); end tm2=datenum(clock); Fprintf ('\n \n[1]',(TM2)*86400,Best_Path_Length); fprintf('\n \n[1]',(TM2)*86400,Best_Path_Length); % = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = % output dbW = 0; for i=2:CITY_COUNT m=Best_Path(i-1); % n=Best_Path(I); % if the current branch (dbW + CITYWAry (n) > VW) % shipped more than limit fprintf (' (utilised: % 1 f % % \ n [1] - % d ', dbW * 100 / VW, n); dbW=CITYWAry(n); % % the amount of money for transportation is equal to the amount of demand in the city else % the limit is not exceeded; dbW=dbW+CITYWAry(n); DbW *100/VW); end end fprintf(' (full load: %.1f%%)',dbW*100/VW); fprintf('\n\n'); % = = = = = = [end] = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = figure (1) % for iterative convergence curves of x = linspace (0, IT_COUNT, IT_COUNT); y=L_best(:,1); plot(x,y); Xlabel (' number of iterations '); Ylabel (' shortest path length '); ` ` `Copy the code
The complete code to download www.cnblogs.com/ttmatlab/p/…