1. Origin and development of Ant Colony Algorithm (ACA)
Marco Dorigo et al., in the process of developing a new algorithm, found that ant colonies can quickly find a target by secreting biohormones called pheromones to communicate information about foraging 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.
Each ant can perceive information only in a small part of its surroundings. 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.
Ants return to their nest using the same rules as they do for finding food.
4. When ants move, they will first follow the guidance of pheromones. If there is no guidance of pheromones, they will follow the direction of their movement inertia, but there is a certain probability of changing direction, ants can also remember the road they have walked, so as to avoid repeating the same place.
5. The ants leave the most pheromones when they find the food, and 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.
1. 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.
2. 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).
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.
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. 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.
Simple case – steps based on ant colony algorithmSolving binary function minimum optimization binary function:
(4-1) Optimization idea: First of all, by solving the constraint conditions, we can get the search space composed of feasible solutions satisfying the constraint conditions. This is a two-dimensional convex space. If the range search of each component is equally divided into discrete points, the size of the whole space can be determined by the division thickness of component XI. Let’s say xi is divided into Ni parts, so the entire search space has 2 times Ni parts. In addition, in order to obtain the exact solution, the interval of component XI is divided very fine, so the search space will become very large, which is also the difficulty of solving the problem. Of course, this method of dividing the interval is also commonly adopted by many optimization algorithms.) If you divide the interval of values of each component equally into N points, then xi will have N choices and x will have N^2 choices. And regard the N value points of each component as N cities. You start with m ants Ant randomly placed on m cities in N of x1. After the search begins,Ant selects cities based on transition probability. On the first selection, the rand function is used to randomly select, after which the selection probability can be transferred.
The specific steps of this case are as follows :(1) the interval of each component is obtained by solving constraint conditions, and the meaning of the question is [-1,1]; (2) This case is subdivided into 73 parts,xi=[-1,-1+2/73… 1]; (3) Judge whether the accuracy meets the requirements, if so, output the optimal solution and end, otherwise continue (4); (4) Set the initial value of information on each path; (5) Randomly select the path to solve; (6) Each ant selects the path to solve according to the selection probability;
(7) If each ant finds the solution, continue (8), otherwise turn (4); (8) Further refine the components of the current optimal solution, and convert to (2).
clc; clear; %% initialization % Define the position of the robots %% Robot_position=[1,2;1,4;1,6;1,8;1,10]; % UAV_position = [5, 7, 3, 2, 7, 13, 6, 9, 5, 5); % % Define the target positions % Target_position=[3,6;5,4;5,6;5,8;8,6]; % Random position UAV_number=3; % The number of UAVs task_number=5; % The number of Target positions SizeofMap = [1 100]; % Map size size_UAV = 0; size_task = 0; % while (size_UAV<UAV_number && size_task < task_number) % UAV_position = randi(SizeofMap,UAV_number,3); % Target_position = randi(SizeofMap,task_number,3); % % UAV_position = unique(UAV_position,'rows'); % % Target_position = unique(Target_position,'rows'); % size_UAV = size(unique(UAV_position,'rows'),1); % size_task = size(unique(Target_position,'rows'),1); % end Target_position = [63,87,84; 22,24,100; 74,41,51; 44,59,4; 68,61,36]; UAV_position = [6,6,85; 88,6,3; 92,98,16]; % Initial the speed of UAVs UAV_speed=ones(UAV_number,1)*10; % Define the plot color for each UAV Color_all = [0 1 0; 0 0 1; 1 1 0; 1 0 1; 0 1 1; 0 0 0]; Color = zeros(UAV_number,3); % for i = 1 : UAV_number % Color(i,:) = Color_all(randi(6),:) ; % end Color(1,:)= [0 0 0]; Color(2,:)= [1 0 1]; Color(3,:)= [0 1 0]; maxT=10; % The maximum tasks can be done by a single worker task_fixed_number=1; % The number of workers are required for a single task % unfinishtask_number=task_number; ant_num_TA=30; % The numbder of ants in Task Allocation ant_num_PP=30; % The numbder of ants in Path Planning iteratornum_TA=30; % The iteration times in Task Allocation iteratornum_PP=30; % The iteration times in Path Planning %% The implementation of Hungrain Algorithm [time_cost_Hungrain, distance_cost_Hungrain, travelled_time_Hungrain] = HungrainAlgorithmMethod(UAV_position,Target_position,UAV_number,UAV_speed,task_number,... SizeofMap, Color); %% The implementation of Ant Colony Algorithm [time_cost_ant,distance_cost_ant, travelled_time_ant]=AntColonyAlgorithmMethod(UAV_position,Target_position,UAV_number,UAV_speed,task_number,... ant_num_TA, iteratornum_TA, maxT,task_fixed_number, ant_num_PP, iteratornum_PP,SizeofMap, Color); %% The implementation of Ant Colony Algorithm in real time [time_cost_ant_realtime, distance_cost_ant_realtime,travelled_time_ant_realtime] = AntColonyAlgorithmMethod_realtime(UAV_position,Target_position,UAV_number,UAV_speed,task_number,... ant_num_TA, iteratornum_TA, maxT,task_fixed_number, SizeofMap, Color); %% Comparision figure(4); % type = categorical({'Hungrain','Ant Colony','Ant Colony Real Time'}); time_cost = [time_cost_Hungrain, distance_cost_Hungrain, travelled_time_Hungrain;... time_cost_ant,distance_cost_ant, travelled_time_ant;... time_cost_ant_realtime, distance_cost_ant_realtime, travelled_time_ant_realtime]; % % bar(type, time_cost) % xlabel('Algorithms') % ylabel('Costs') % title('Comparision between different Algorithms applied on Task Allocation') % legend('Computational time (s)', 'Sum of UAVs Travelled Distance (m)', 'Sum of UAVs Travelled Time (m)'); bar(time_cost, 'grouped') set(gca, 'XTickLabel',{'Hungrain', 'Ant Colony', 'Ant Colony Real Time'}, 'FontSize', 18); set(gca, 'ygrid','on','GridLineStyle','-'); xlabel('Algorithms','FontSize',18) ylabel('The meansured data used to appraise algorithm performance','FontSize',18) title('Comparision of the performance between different algorithms in MRTA problem','FontSize',18) legend('Computational time (s)', 'Sum of UAVs Travelled Distance (m)', 'Sum of UAVs Traveled Time (s)','FontSize',18);Copy the code
[1] Chen, Xia, Yan zhi Qiao. “Summary of Unmanned Aerial Vehicle Task Allocation.” Journal of Shenyang Aerospace University 33.6 (2016) : 1-7.
[2] Wang, Jianping, Yuesheng Gu, and Xiaomin Li. “Multi-robot task allocation based on ant colony algorithm.” Journal of Computers 7.9 (2012): 2160-2167.
Complete code or simulation consultation QQ1575304183