[TSP problem] matlab source code for solving TSP problem based on ant colony algorithm
1 Introduction to algorithm
1.1 principle of ant colony algorithm
Ant colony algorithm is inspired by the research on the foraging behavior of real ant colony. Biological studies have shown that a group of cooperative ants can find the shortest path between food and nest, while a single ant cannot. Biologists have found through a lot of careful observation and research that the behavior of ant individuals is interactive. In the process of movement, an ant can leave a substance called pheromone on its path, which is the carrier of information transmission and communication between ants. Ants can sense this substance when moving, and are used to tracking this substance. Of course, pheromones will be released during crawling. The thicker the pheromone trace on a road, the higher the probability that other ants will follow and crawl this path, so the pheromone trace on this path will be strengthened. Therefore, the collective behavior of ant colony composed of a large number of ants will show a positive information feedback phenomenon. The more ants walk along a path, the greater the possibility of latecomers choosing the path. It is through this indirect communication mechanism that ant individuals achieve the goal of collaborative search for the shortest path. We give a brief example of ant foraging behavior:
As shown in a, B and C above:
A is the original state. The starting point of the ant is A. to reach E, there are obstacles on the way, and it can only be reached by bypassing. BC and BH are two paths around obstacles (assuming only two). The distance d of each path has been calibrated.
b graph is the ant state at t=0, and there are equal pheromone concentrations on each edge, assuming 15;
Fig. c shows the state after the ant passes at t=1, and the pheromone concentration on each side changes; Because the selection probability of a large number of ants will be different, and the selection probability is related to the path length. Therefore, the shorter the path, the greater the concentration will be, and more ants will reach their destination through this short path than other paths. In this way, a large number of ants find the shortest path after practice. Therefore, the essence of this process can be summarized as follows:
1. Path probability selection mechanism the more pheromone traces, the greater the probability of being selected
2. The shorter the pheromone update mechanism path is, the faster the pheromone trace on the path grows
3. Cooperative working mechanism ant individuals exchange information through pheromones.
It can be seen from the principle of ant foraging that the behavior of a single individual is very simple. Ants only know to track pheromones, crawl and release pheromones, but the combined swarm intelligence is very high. Ant colonies can easily find the shortest path between ant nests and food sources under the condition of complex geographical distribution. This characteristic is exactly consistent with the characteristics of meta heuristic algorithm. Ant colony optimization algorithm is inspired by this ecological phenomenon and imitated and improved. Foraging ants are replaced by artificial ants, and the pheromone released by ants becomes artificial pheromone. Ant crawling and pheromone evaporation are no longer continuous, but in discrete time and space.
In a deep sense, ant colony algorithm, as one of the optimization methods, belongs to the field of artificial cluster intelligence. Artificial swarm intelligence is mostly inspired by natural swarm intelligence, such as insects and animals. In addition to its unique and powerful cooperative search ability, it can also use a series of computing agents to deal with problems distributed, so as to greatly improve the search efficiency.
1.2 basic flow of ant colony algorithm
We still use the PPT of Gu Junfeng of Dalian University of technology to illustrate the problem, calculate and explain the screenshots of important formulas, and explain the difficult parts of the PPT separately:
1.2.1 basic mathematical model
First, let's look at the basic mathematical model of the basic TSP problem:
The problem is actually very simple. The objective function is the total length of each path. Note that the length of the distance matrix is different according to the actual problem.
1.2.2 description of ant colony algorithm
Before explaining the ant colony algorithm process, we describe the algorithm principle and several points for attention:
1. In the artificial ant colony algorithm of TSP problem, it is assumed that m ants move between adjacent nodes of the graph, so as to obtain the solution of the problem cooperatively and asynchronously. The one-step transition probability of each ant is determined by two kinds of parameters on each edge of the graph: 1. Pheromone value is also known as pheromone trace. 2. Visibility, i.e. a priori value. 2. There are two ways to update pheromones. One is volatilization, that is, pheromones on all paths are reduced at a certain rate to simulate the process of pheromone volatilization of natural ant colony over time; The second is enhancement, adding pheromone to the edge with "good" evaluation value (with ants walking). 3. The movement of ants to the next target is realized through a random principle, that is, using the information stored in the current node, calculate the probability of reaching the node in the next step, and move one step according to this probability, reciprocating one step by one, getting closer and closer to the optimal solution. 4. In the search process or after finding a solution, the ant will evaluate the optimization degree of the solution or part of the solution, and save the evaluation information in the relevant connected pheromones.
1.2.3 core steps of ant colony algorithm
According to our previous principle and the above description, the two core steps of swarm ant algorithm are path construction and pheromone update. We will focus on these two steps.
1 path construction
Each ant randomly selects a city as its starting city, and maintains a path memory vector to store the cities that the ant passes through in turn. In each step of constructing the path, the ant selects the next city to arrive according to a random proportion rule. The random probability is calculated according to the following formula:
The above formula is to calculate the probability from the current point to each possible next node. The numerator is the power product of pheromone intensity and visibility, and the denominator is the sum of all molecules. This is not easy to understand at the beginning. We can see it clearly when calculating the final example, and then understand the formula in turn. Note that each time a node is selected, the selected node is removed from the available nodes.
2 pheromone update
Pheromone updating is the core of swarm ant algorithm. It is also the core of the whole algorithm. The algorithm has a fixed concentration value in the initial period. After each iteration, after all the ants come back, they will calculate the route, and then update the pheromone concentration of the corresponding edge. Obviously, this value must be related to the length of the ant. After iteration after iteration, the concentration of the short-distance line will be very high, so as to obtain the approximate optimal solution. Let's look at the pheromone update process.
If the initial pheromone concentration C(0) is too small, the algorithm is easy to precocious, and the ants will quickly focus on a local optimal path, because it can be thought that if the value of C is too small, it is almost the same as the value of each volatilization and enhancement, then in the case of random, some small probability events will increase the pheromone concentration of the non optimal path; If C is too large, the guiding effect of pheromone on the search direction will be reduced and the performance of the algorithm will be affected. In general, we can use greedy algorithm to obtain a path value Cnn, and then calculate C(0) = m / Cnn according to the number of ants, where m is the number of ants
After each round, the pheromones on all paths in the problem space will evaporate. Then, all ants release pheromones on the edges they pass through according to the path length constructed by themselves. The formula is as follows:
The role of pheromone update: 1. Pheromone volatilization the volatilization process of pheromone trace is a process in which the concentration of pheromone trace on each connection decreases automatically and gradually. This volatilization process is mainly used to avoid the algorithm from concentrating too quickly to the local optimal region, which is conducive to the expansion of the search region. 2. 2. Pheromone enhancement process is an optional part of ant colony optimization algorithm, which is called offline update mode (and online update mode). In this way, centralized action that cannot be achieved by a single ant can be realized. The offline update method of the basic ant colony algorithm is to update the residual information uniformly after all m ants in the ant colony complete the access to n cities.
3 iteration and stop
The conditions for stopping the iteration can be stopped after selecting the appropriate number of iterations and outputting the optimal path. You can also see whether the specified optimal conditions are met and stop after finding the satisfied solution. Most importantly, when I first understood the algorithm, I thought that each ant walking one side was an iteration. In fact, it was wrong. The meaning of each iteration of the algorithm here is that the m ants in each iteration have completed their own path process and the whole process after returning to the origin.
4 calculation example of ant colony algorithm
Using a case in PPT, it is very intuitive. Several symbol errors are modified, mainly calculating the multiplier of probability. There is no error in the result:
The overall process is still relatively simple. Pay attention to understanding the formula, and then combine the formula with examples. It's best to take a pen and animate with your own hand, which is easy to understand.
Part 2 code
%% Clear environment variables clear all clc %% Import data load citys_data.mat %% Calculate the distance between cities n = size(citys,1); D = zeros(n,n); for i = 1:n for j = 1:n if i ~= j D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2)); else D(i,j) = 1e-4; end end end %% Initialization parameters m = 50; % Ant number alpha = 1; % Pheromone importance factor beta = 5; % Heuristic function importance factor rho = 0.1; % Pheromone volatilization factor Q = 1; % Constant coefficient Eta = 1./D; % Heuristic function Tau = ones(n,n); % Pheromone matrix Table = zeros(m,n); % Path record form iter = 1; % Initial value of iteration times iter_max = 200; % Maximum number of iterations Route_best = zeros(iter_max,n); % Best path of each generation Length_best = zeros(iter_max,1); % Length of the best path of each generation Length_ave = zeros(iter_max,1); % Average length of paths of each generation %% Iterative search for the best path while iter <= iter_max % Randomly generate the starting city of each ant start = zeros(m,1); for i = 1:m temp = randperm(n); start(i) = temp(1); end Table(:,1) = start; % Constructing solution space citys_index = 1:n; % Ant by ant path selection for i = 1:m % City by city route selection for j = 2:n tabu = Table(i,1:(j - 1)); % Visited city collection(Taboo list) allow_index = ~ismember(citys_index,tabu); allow = citys_index(allow_index); % Collection of cities to be visited P = allow; % Calculate the transfer probability between cities for k = 1:length(allow) P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta; end P = P/sum(P); % Roulette to choose the next city to visit Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; end end % Calculate the path distance of each ant Length = zeros(m,1); for i = 1:m Route = Table(i,:); for j = 1:(n - 1) Length(i) = Length(i) + D(Route(j),Route(j + 1)); end Length(i) = Length(i) + D(Route(n),Route(1)); end % Calculate the shortest path distance and average distance if iter == 1 [min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_index,:); else [min_Length,min_index] = min(Length); Length_best(iter) = min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length Route_best(iter,:) = Table(min_index,:); else Route_best(iter,:) = Route_best((iter-1),:); end end % Update pheromone Delta_Tau = zeros(n,n); % Ant by ant calculation for i = 1:m % City by city calculation for j = 1:(n - 1) Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i); end Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end Tau = (1-rho) * Tau + Delta_Tau; % Add 1 to the number of iterations to clear the path record table iter = iter + 1; Table = zeros(m,n); end %% The results show that [Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['Shortest distance:' num2str(Shortest_Length)]); disp(['Shortest path:' num2str([Shortest_Route Shortest_Route(1)])]); %% mapping figure(1) plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on for i = 1:size(citys,1) text(citys(i,1),citys(i,2),[' ' num2str(i)]); end text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' starting point'); text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' End'); xlabel('Abscissa of city location') ylabel('City Location ordinate') title(['Ant colony algorithm optimization path(Shortest distance:' num2str(Shortest_Length) ')']) figure(2) plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('Shortest distance','Average distance') xlabel('Number of iterations') ylabel('distance') title('Comparison of shortest distance and average distance of each generation') %%
3 simulation results
 Wu Huafeng, Chen Xinqiang, Mao Qihuang, et al. Ant colony algorithm based on natural selection strategy to solve TSP problem [J]. Journal of communications, 2013, 000 (004): 165-170