A list,

1 Origin and development history of Ant Colony Algorithm (ACA) Marco Dorigo et al. found that ant colonies can quickly find targets by secreting biohormones called pheromones to communicate foraging information when searching for food. Therefore, in his doctoral dissertation in 1991, he first systematically proposed a new intelligent optimization algorithm “Ant System” (AS for short) based on Ant population. Later, the proposer and many researchers made various improvements to the algorithm and applied it to a wider range of fields. Figure coloring problem, secondary assignment problem, workpiece sequencing problem, vehicle routing problem, job shop scheduling problem, network routing problem, large-scale integrated circuit design and so on. In recent years, M.Dorigo et al. further developed Ant algorithm into a general Optimization technology “Ant Colony Optimization (ACO)”, and called all the algorithms conforming to ACO framework “ACO algorithm”.



Specifically, individual ants start looking for food without first telling them where it is. When an ant finds food, it releases a volatile pheromone (called a pheromone, it evaporates over time and its concentration indicates how far the path is) into the environment that other ants sense as a guide. Generally, when there are pheromones on multiple paths, the ant will preferentially choose the path with high pheromone concentration, so that the pheromone concentration of the path with high pheromone concentration will be higher, forming a positive feedback. Some ants do not repeat the same route as others. They take a different route. If the alternative path is shorter than the original one, gradually more ants are attracted to the shorter path. Finally, after some time of running, there may be a shortest path repeated by most ants. In the end, the path with the highest pheromone concentration is the optimal one selected by the ant.

Compared with other algorithms, ant colony algorithm is a relatively young algorithm, characteristics, such as distributed computing center control and asynchronous indirect communication between individuals, and is easy to be combined with other optimization algorithms, through many healthyenterprise continuously explore, to today has developed a variety of improved ant colony algorithm, but the principle of ant colony algorithm is still the main.

2. Solving principle of ant colony algorithm

Based on the above description of ant colony foraging behavior, the algorithm mainly simulates foraging behavior from the following aspects:

(1) The simulated graph scene contains two pheromones, one representing home and one representing food location, and both pheromones are volatilized at a certain rate.

(2) Each ant can perceive information only in a small part of the area around it. Ants searching for food, if within the scope of the perception, can directly in the past, if is beyond the scope of awareness, will be toward more than pheromones, ants can have a small probability pheromone many places don’t go, and instead, it is very important to the small probability event, represents a way of innovation, is very important to find a better solution.

(3) Ants return to the nest using the same rules as when they find food.

(4) When ants move, they will first follow the guidance of pheromone. If there is no guidance of pheromone, they will follow the direction of their moving inertia, but there is a certain probability of changing direction. Ants can also remember the path they have already walked, so as to avoid repeating the same place.

(5) The ants leave the most pheromones when they find food, and then the farther away they are from the food, the less pheromone they leave. The rules for finding nest pheromones are the same as for food. Ant colony algorithm has the following characteristics: positive feedback algorithm, concurrency algorithm, strong robustness, probabilistic global search, does not rely on strict mathematical properties, long search time, easy to stop phenomenon.

Ant transfer probability formula:



In the formula, is the probability of ant K transferring from city I to city J; α and β were the relative importance of pheromones and heuristic factors, respectively. Is the pheromone quantity on edge (I, j); Is the heuristic factor; The next step for Ant K allows the selection of cities. The above formula is the pheromone update formula in the ant system, and is the pheromone quantity on the edge (I,j). ρ is the evaporation coefficient of pheromone, 0<ρ<1; Is the pheromone quantity left by the KTH ant on the edge (I,j) in this iteration; Q is a normal coefficient; Is the path length of the k ant during this tour.

In ant system, pheromone update formula is:



3. Solving steps of ant colony algorithm:

(1) Initialization parameters At the beginning of calculation, it is necessary to initialize related parameters, such as ant colony size (ant number) m, pheromone importance factor α, heuristic function importance factor β, pheromone will emit money ρ, total pheromone release Q, maximum iteration times iter_max, initial value of iteration times iter=1.

(2) construct solution space and randomly place each ant at different starting points. For each ant k (k=1,2,3… M), calculate the next city to be visited according to (2-1) until all ants have visited all cities.

(3) update information su to calculate the path length of each ant Lk(k=1,2… , m), record the optimal solution (shortest path) in the current iteration number. At the same time, pheromone concentration on the connection path of each city was updated according to Equations (2-2) and (2-3).

(4) Determine whether to terminate if iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2; Otherwise, the calculation is terminated and the optimal solution is output.

(5) Determine whether to terminate if iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2; Otherwise, the calculation is terminated and the optimal solution is output. 3. Determine whether to terminate. If iter<iter_max, set iter=iter+1 to clear the record table of ant paths and return to Step 2. Otherwise, the calculation is terminated and the optimal solution is output.

Ii. Source code

CLC % Clear command line window clear % Remove all variables from the current workspace and free them from system memory Close All % Remove all Windows whose handles are not hidden Tic % Save the current time %% Ant Colony algorithm solve CDVRP % Input: %City Demand point longitude and latitude %Distance Distance matrix %Demand Demand of each Demand point %AntNum population number %Alpha pheromone importance factor %Beta heuristics importance factor %Rho pheromone volatile factor %Q constant coefficient %Eta Heurist function %Tau pheromone matrix %MaxIter Maximum number of iterations % Output: %bestroute shortest path %mindisever Path length %% Load data'City.mat') % latitude and longitude of the demand point, used to draw the XY coordinates of the actual path load('Distance.mat'% distance matrix load('Demand.mat'% demand load('Travelcon.mat'% travel constraint load('Capacity.mat'CityNum = size(City,1)- 1; % Number of demand points %% Initialization parameter AntNum =8; % Ant count Alpha =1; % pheromone importance factor Beta =5; % heuristic function importance factor Rho =0.1; % pheromone volatile factor Q =1; % constant coefficient Eta =1./Distance; Tau = ones(CityNum+1);                  % (CityNum+1)*(CityNum+1) pheromone matrix initialization is all1
Population = zeros(AntNum,CityNum*2+1); % AntNum line, (CityNum *2+1) column MaxIter =100; % Max iteration bestind = ones(1,CityNum*2+1); % optimal path for each generation MinDis = zeros(MaxIter,1); % The length of the optimal path of each generation %% Iterates to find the optimal path Iter =1; % Initial number of iterationswhileIter <= MaxIter % Select ant paths one by one when the maximum number of iterations %% is not reachedfor i = 1:AntNum
        TSProute=2:CityNum+1; % generates an ascending TSP route that does not include the first and last bits. % Initializes the VRP pathwhile~isempty(TSProute)% Open a new subpath subpath=1; % First place the distribution center at the start of the sub-path DisTraveled=0; % The subpath distance is initialized to zero delivery=0; % The vehicle distributable capacity of this subpath is initialized to zerodelete=subpath; %delete(end)=1For the first time inwhileThe first term of P of k is usedwhile~isempty(TSProute) % sets demand points %% for the second and subsequent locations of the subpathwhileP = TSProute; % establishes a vector equal to the length of the remaining number of cities to pass through for roulettefor k = 1:length(TSProute)
                    %delete(end) is the city just passed, and TSProute(k) is the remaining possible city P(k) = Tau(delete(end),TSProute(k))^Alpha * Eta(delete(end),TSProute(k))^Beta; % omits the same denominatorend
                function DrawPath(route,City)%% Draw path function % Enter % route to draw path % City coordinates of each City figure hold on % Retain the drawing in the current coordinate area, So that a new drawing added to the coordinate area will not delete the existing drawing box on % by setting the box property of the current coordinate area to 'on' to display the box outline around the coordinate areaxlim([min(City(:,1)0.01),max(City(:,1) +0.01)])% Manually set the X-axis range xlimitylim([min(City(:,2)0.01),max(City(:,2) +0.01)])% Manually set the Y-axis range % draw the distribution center pointplot(City(1.1),City(1.2),'bp'.'MarkerFaceColor'.'r'.'MarkerSize'.15) %plot(x coordinate,y coordinate, circle, color, RGB triplet of some color)Draw the demand pointsplot(City(2:end,1),City(2:end,2),'o'.'color'[0.5.0.5.0.5].'MarkerFaceColor'.'g') %plot(x coordinate,y coordinate, circle, color, RGB triplet of some color)% Add point numberfor i=1:size(City,1)
    text(City(i,1) +0.002,City(i,2)0.002,num2str(i- 1)); % number points text(x coordinates,y coordinates, circle, color, red RGB triplet)end
function TextOutput(Distance,Demand,route,Capacity)%% Output path function % Input: route path % Output: P path text %% Total path len=length(route); % Path length disp('Best Route:')

p=num2str(route(1)); % Distribution center bit first entry path firstfor i=2:len
    p=[p,'- >',num2str(route(i))]; % the path is added to the next passing pointend
disp(p)
Copy the code

3. Operation results





Fourth, note

Version: 2014 a