1. Travel agent (TSP) and its derivation
Traveling Saleman Problem (TSP) is a special case of vehicle routing scheduling Problem (VRP). Since mathematicians have proved that TSP is NP Problem, VRP is also NP Problem. The travel salesman problem (TSP) is also translated as the travel salesman problem, the seller’s problem, referred to as THE TSP problem, is the most basic route problem, which is to seek a single traveler starting from the starting point, through all the given demand points, and finally back to the origin of the minimum path cost. — Encyclopedia of Travel Agent Problems
Obviously, when the number of nodes is small, most people would think that the problem is simple, just do it all, but in practice, the number of nodes is often too large to be possible. For example: for a travel salesman problem with only 16 cities, if we use the exhaustive method to find the optimal solution of the problem, the feasible solution to be compared is: 15! /2= 653,837,184,000. In 1993, it took 92 hours to solve the problem using the exhaustive method using the workstation at the time. Even though computers are fast now, they are not enough for complex problems. This is known as the “combinatorial explosion,” exponential growth, so scientists gradually look for approximate or heuristic algorithms that aim to find an acceptable optimal solution within a reasonable time frame.
The development of TSP problem solving algorithm can be divided into three parts:
1). Classical accurate algorithms: exhaustive algorithm, linear programming algorithm, dynamic programming algorithm, branch-and-bound algorithm and other traditional algorithms in operations research. These algorithms are generally of great complexity and are only suitable for solving small-scale problems.
2) approximation algorithm: when the problem size is larger, the time needed for its rise to exponential increases in both, we can not accept, this is the size of the algorithm to solve the problem by a lot of restrictions, a very natural idea is to sacrifice the precise solution of optimality, to look for a good time complexity we can tolerate, at the same time, we can accept the quality of the algorithm. Algorithms designed based on this idea are collectively called approximate algorithms. Such as insertion algorithm, nearest neighbor algorithm.
3). Intelligent algorithm: With the continuous development of science and technology and production, it is impossible to find the global optimal solution in a reasonable time range for many practical problems, which leads to the emergence of modern optimization problem solving methods. With the emergence of various heuristic algorithms with different search mechanisms, such as tabu search, genetic algorithm, simulated annealing algorithm, artificial neural network, evolutionary strategy, evolutionary programming, particle swarm optimization algorithm, ant colony optimization algorithm and immune computing, the research of heuristic algorithms has set off a high tide.
Each algorithm is no longer described in detail, you can find the corresponding information for understanding.
TSP problem in the actual production and life, more practical environment is different, there are a lot of derivative classic problems. The vehicle routing scheduling (VRP) expansion problem is formed by adding various constraints to the classical VRP. For example, the demand stochastic vehicle routing problem (SVRP) formed by demand constraints; Vehicle routing problem with time window (VRPTW) is obtained by adding time constraint. Distance constrained vehicle routing problem (DVRP) with distance constraint; According to other different conditions, there are multi-distribution center vehicle routing problem (MDVRP), sharable vehicle routing problem (SDVRP); Vehicle Routing problem (VRPB) and Vehicle routing problem (VRPPD); Fuzzy Vehicle Routing problem with Incomplete information (FVRP)[3].
Return to the directory
2. Basic principle of colony ant algorithm
2.1 Algorithm Overview
For VRP problem, solving algorithm can be roughly divided into two categories: accurate algorithm and artificial intelligence algorithm. The accuracy algorithm is based on strict mathematical means, and the quality of the solution is good if it can be solved. However, due to the strict algorithm and large amount of computation, especially large-scale problems can hardly be solved. Therefore, its application can only be small scale deterministic problems, facing small and medium scale problems, artificial intelligence algorithm is not dominant in accuracy. However, when the scale is larger, artificial intelligence methods can basically find acceptable satisfactory solutions in acceptable time, which is difficult for accurate algorithms to achieve. Due to the practical problems, all kinds of constraints are complex, artificial intelligence algorithm shows a great superiority, but also because of this, in practical application, artificial intelligence algorithm should be more extensive. The precise algorithms for vehicle routing scheduling include dynamic programming, branch and bound method and so on. And began to seek acceptable results of heuristic algorithm to deal with large-scale practical problems, some other disciplines of the new generation of optimization algorithms have emerged, such as tabu search algorithm, genetic algorithm, artificial neural network algorithm, and now more research ant colony algorithm.
2.2 Principle of colony ant algorithm
Ant colony algorithm is inspired by the foraging behavior of real ant colonies. Biological studies have shown that groups of cooperating ants can find the shortest route between food and the nest, while individual ants cannot. Biologists have discovered, through a lot of careful observation, that the behavior of individual ants interacts with each other. As ants move, they leave behind a substance called pheromone along their path, which is the carrier of information between ants. Ants sense it as they move and are used to tracking it as it crawls, releasing pheromones as it crawls. The stronger the pheromone trail on a path, the higher the probability that other ants will follow the path, and thus the pheromone trail on the path will be strengthened. Therefore, the collective behavior of the ant colony composed of a large number of ants shows a positive information feedback phenomenon. The more ants that walk along a path, the more likely it is that those who follow will choose it. It is through this indirect communication mechanism that ant individuals achieve the goal of searching the shortest path cooperatively. Let’s give a simple example of ant foraging behavior:
As shown in the schematic diagram of A, B and C above:
Figure A shows the original state. The ant starts at A and has to bypass the obstacle to reach E. BC and BH are two paths around the obstacle (assuming only two). The distance D of each path has been calibrated.
Figure B is the ant state at t=0, and there are equal pheromone concentrations on each side, assuming 15.
Figure C shows the state of ants passing by at t=1. Pheromone concentration of each side changes. Because a large number of ants have different probability of selection, and the probability of selection is dependent on the length of the path. So the shorter the path, the more dense it will be, the more ants will use it to reach their destination than any other path. So a lot of ants practice and then they find the shortest path. Therefore, the essence of this process can be summarized as follows:
1. The path probability selection mechanism The more abundant the path pheromone trail, the higher the probability of being selected
2. Pheromone update mechanism The shorter the path, the faster the pheromone trail grows
3. Cooperative working mechanism Ants communicate information through pheromones.
From the principle of ant foraging, it can be seen that the behavior of a single individual is very simple. Ants only know how to track pheromone crawling and releasing pheromones, but the swarm intelligence after combination is very high. Ants can easily find the shortest path between the nest and the food source in the complex geographical distribution. This characteristic is consistent with yuan the characteristics of heuristic algorithm, ant colony optimization algorithm is inspired by the phenomenon of ecology to imitate and modified, after foraging ants workers replaced by humans, the ants released pheromone became human pheromones, ants crawling and pheromone evaporation is not continuous, but in discrete time and space.
If the above examples are not easy to understand, I have posted a few PPT here, personally feel very good, is also I found a lot of materials to understand the best [source is Gu Junfeng of Dalian University of Technology], click here to provide download: ant colony algorithm basic knowledge. Rar.
In a deep sense, ant colony algorithm, as one of the optimization methods, belongs to the field of artificial swarm 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 capability, it can also use a series of computing agents to deal with the problem in a distributed manner, thus greatly improving the search efficiency.
Return to the directory
3. Basic flow of ant algorithm
We still use the PPT of Gu Junfeng from Dalian University of Technology to illustrate the problem. Important formulas are calculated and explained with screenshots, and the difficult parts of the PPT are explained separately:
3.1 Basic mathematical model
Let’s start with the basic mathematical model for the basic TSP problem:
In fact, the problem is very simple, the objective function is the total length of each path, notice that the distance matrix is different according to the actual problem, the length is different.
3.2 Colony ant algorithm description
Before explaining the flow of ant algorithm, we describe the algorithm principle and several points of attention:
1. In the man-worker ant colony algorithm for THE TSP problem, it is assumed that M ants move between adjacent nodes of the graph, so as to obtain the solution of the problem asynchronously and cooperatively. The one-step transition probability of each ant is determined by two kinds of parameters on each side of the graph: 1. Pheromone value is also called pheromone trace. 2. Visibility, the prior value. 2. Pheromones can be updated in two ways: one is volatilization, that is, pheromones on all paths are reduced at a certain rate to simulate the process of volatilization of pheromones in natural ant colonies over time; The other is enhancement, adding pheromones to edges that are rated as “good” (with ants walking by). 3. The next target movement of the ant is realized by a random principle, that is, the probability of the next reactable node is calculated by using the information stored in the node where the ant is currently located, and the next step of movement is realized according to this probability, which is repeated one by one, getting closer and closer to the optimal solution. 4. In the process of searching or after finding a solution, the ant will evaluate the optimization degree of the solution or part of the solution, and store the evaluation information in the pheromone of the related connection.
3.3 Core steps of the ant algorithm
In addition to our previous principles and the above description, the two core steps of the ant algorithm are path construction and pheromone update. We will focus on these two steps.
3.3.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 sequence. At each step of the construction path, the ants choose the next city to reach according to a rule of random proportion. The random probability is calculated according to the following formula:
The formula above is to calculate the probability of the current point to every possible next node. The numerator is a power product of pheromone intensity and visibility, while the denominator is the sum of all the molecules. And this is not easy to understand at first, but when we do the final example, we can see it very clearly, and then we can understand the formula in reverse. Note that each time a node is selected, the selected node is removed from the available nodes.
3.3.2 Pheromone update
Pheromone renewal is the core of ant algorithm. That’s the heart of the whole algorithm. The algorithm has a fixed concentration value during the initial period. After each iteration, all the ants that go out will come back and calculate the route taken, 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 close line will be high, so as to obtain an approximate optimal solution. So let’s look at pheromone renewal.
Initialization pheromone concentration C (0), if too small, the algorithm is easy to precocious, ants will soon be concentrated to a local optimal path, because you can think of, small C values, and each time the volatilization and enhance the value of about the same, then the random case, incidents of small probability will increase the optimal path pheromone concentration; If C is too large, the pheromone’s guiding effect on the search direction will be reduced and the algorithm performance 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 turn, pheromones on all the paths in the problem space evaporate, and then all the ants release pheromones on the sides of their round, according to the length of their own paths, as follows:
The function of pheromone update is as follows: 1. The evaporation process of pheromone evaporation (specific) pheromone trace is a process in which the concentration of pheromone trace at each connection gradually decreases automatically. This evaporation process is mainly used to avoid the algorithm concentrating too fast to the local optimal region, which is helpful for the expansion of the search area. The reinforcement process is an optional part of ANT colony optimization algorithm, which is called offline update mode (and online update mode). This allows for a concentration of action that a single ant cannot achieve. The offline update mode of the basic ant colony algorithm is to update the residual information uniformly after all m ants in the ant colony complete the visit of N city.
3.3.3 Iteration and stop
Iteration stop conditions can be selected after the appropriate number of iterations, to output the optimal path, or to check whether the specified optimal conditions are met, to find a satisfactory solution to stop. And most importantly, when I first started to understand this algorithm, I thought that each edge that an ant took was an iteration, which was a mistake. The meaning of each iteration of the algorithm here is that m ants in each iteration have completed their own path process and the whole process after returning to the origin.
Return to the directory
4. Calculation example of ant algorithm
Using a case in PPT, which is very intuitive, several symbol errors have been modified, mainly to calculate the multiplier of probability, and the result is no error:
The overall process is relatively simple, pay attention to understand the formula, and then the formula and examples together to see, it is best to take a pen to his hand animation, easy to understand. Let’s look at how to program the ant algorithm code to implement the TSP problem.
% 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