A list,

1 profileAn algorithm designed to simulate ant foraging behavior (shortest path principle). The characteristics of ant foraging are abstracted and transformed into a mathematical description.

• Ant Colony Algorithm (ACA) was first proposed by Marco Dorigo in his doctoral thesis in 1992. • Ants in search of a food source release a pheromone in their path and can sense the pheromone released by other ants. The pheromone concentration indicates the distance of the path. The higher the pheromone concentration, the shorter the corresponding path distance. • In general, ants will preferentially select the path with high pheromone concentration with a high probability and release a certain amount of pheromone to enhance the pheromone concentration on the path, thus forming a positive feedback. Ultimately, the ants are able to find the best route, the shortest distance, from the nest to the food source. • The biologists also found that pheromone concentrations along the path decay over time. • Ant colony algorithm is applied to solve optimization problems. The basic idea is: the feasible solution of the problem to be optimized is represented by the walking path of ants, and the solution space of the problem to be optimized is formed by all the paths of the entire ant colony. Ants with shorter paths released more pheromones. As time went on, the accumulation of pheromone concentration along the shorter paths gradually increased, and the number of ants choosing the path also increased. Finally, the whole ant will focus on the optimal path under the action of positive feedback, and the corresponding path is the optimal solution of the problem to be optimized. Similar to GA (genetic algorithm) crossover, selection and variation, and PSO (particle swarm optimization) individual and population optimization, ant colony algorithm also has its own optimization strategies: information mechanism of positive feedback, pheromone concentration update, ant selection of access paths.

2 Basic IdeasThe basic principle of ant colony algorithm comes from the shortest path principle of ants foraging in nature. According to the observation of entomologists, it is found that the ants in nature can find the shortest path from the food source to the nest without any hints, and can adaptively search for the best new path when the environment changes (for example, there are obstacles on the original path). How do ants do this? It turns out that when ants are looking for a food source, they place in their path a special ant-secreted pheromone, or pheromone, that can be detected by other ants within a certain range and thus influence their future behavior. When their ants’ through some path, its left by more and more, so that the pheromone strength increase (of course, with the passage of time will gradually weaken, so the ant chooses the path of the probability is higher, thus increased the path pheromone intensity, the selection process is referred to as the catalytic behavior of ants. Since its principle is a positive feedback mechanism, the ant kingdom can also be understood as a so-called enhanced learning system. Here, we use a graph to illustrate the principle of shortest path selection for ant foraging, as shown in the figure. In, if point A is the ant’s nest, point B is food, and there is an obstacle between point A and point B, then the ant from point A to point B must decide whether to go left or right, and the ant from point B to point A must also decide which path to take. This decision is influenced by the concentration of pheromones left behind by previous ants along each path, known as residual pheromones. If there is a higher concentration of pheromones in the path to the right, the ant is more likely to choose the path to the right. But for the first batch of pathfinding ants, there was no pheromone effect or less, so they were equally likely to go left or right, as shown in the picture. As the foraging process progressed, pheromone intensity on each road began to change, with some lines stronger and some lines weaker. Let’s take an example of an ant going from point A to point B (from point B to point A, the process is basically the same) and then what happens. Because path ADB is shorter than path ACB, the first ant that takes ADB gets to point B earlier than the first ant that takes ACB. At this point, from point B to point A, the pheromone concentration on path BDA A is higher than the pheromone concentration on path BCA. Therefore, from the next moment, ants from point B to point A are more likely to choose THE BDA path than the BCA path, which further increases the pheromone on the ABDA path. Thus, ants that choose the path depending on pheromone intensity gradually prefer to choose ADB, as shown in the figure. Over time, almost all ants choose the ADB(or BDA) path to carry food, and we find that the ADB path is in fact the shortest path. The principle of ant colony pathfinding can be simply understood as follows: for a single ant, it has no subjective intention to find the shortest path; But for the entire ant colony system, they do achieve the visual effect of finding the shortest path. In nature, the path seeking process of ant colonies is a positive feedback process. “Ant colony algorithm” is derived from the principle of ant colony foraging to find the shortest path in biology. For example, we regard the work unit with simple function as “ant”, then the process of finding path above can be used to explain the optimization process of human worker ant colony in ant colony algorithm. So that’s the basic idea of ant colony algorithms. 3. Process of algorithm designHere in the TSP problem, for example, the algorithm design process is as follows: step 1: initialize the related parameters, including ant colony size, pheromone factor, heuristic function factor, pheromone volatilization factor, information used to number and maximum number of iterations, as well as the data is read in the program, and preprocessing, such as the city information is converted to the coordinates of the distance between the matrix. Step 2: Randomly place ants at different starting points and calculate the next city for each ant to visit until all the cities are visited by ants. Step 3: Calculate the path length Lk of each ant, record the optimal solution of the current iteration number, and update the pheromone concentration on the path. Step 4: Check whether the maximum number of iterations is reached. If not, return to Step 2. If yes, end the program. Step 5: Output the results, and output the relevant indexes in the optimization process, such as running time, convergence iterations, etc.

4 Mathematical Model

Ii. Source code

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 parameter m =50; % 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./D; Tau = ones(n,n); % pheromone matrix Table = Zeros (m,n); % Path record table iter =1; % Initial number of iterations iter_max =200; Route_best = zeros(iter_max,n); Route_best = zeros(iter_max,n); Length_best = zeros(iter_max,1); Length_ave = zeros(iter_max,1); % Average path length of each generation %% Iterate to find the best pathwhileIter <= iter_max % start = zeros(m,1);
      for i = 1:m
          temp = randperm(n);
          start(i) = temp(1);
      end
      Table(:,1) = start; % Build solution space citys_index =1:n; % Ant by ant path selectionfor i = 1:m % Select a city-by-city pathfor j = 2:n
             tabu = Table(i,1:(j - 1)); Allow_index = ~ismember(citys_index,tabu); allow = citys_index(allow_index); % Set of cities to be accessed P = allow; % Calculate the transfer probability between citiesfor k = 1:length(allow) P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta; end P = P/sum(P); % roulette method select next visit city Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; End end % = 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 % calculates the shortest path distance and the average distanceif 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 % Count each antfor i = 1:m % City by cityfor 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), Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
      end
      Tau = (1-rho) * Tau + Delta_Tau; % Number of iterations plus1To clear the path record table iter = iter +1; Table = zeros(m,n); End %% results show [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)]]);Copy the code

3. Operation results

Fourth, note

Version: 2014 a