Shulou(Shulou.com)06/01 Report--

This article mainly introduces "Python and Matlab how to achieve ant colony algorithm to solve the shortest path". In daily operation, I believe many people have doubts about how to achieve ant colony algorithm in Python and Matlab to solve the shortest path problem. Xiaobian consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for everyone to answer the doubt of "how to realize ant colony algorithm to solve the shortest path by Python and Matlab". Next, please follow the editor to study!

1 knowledge points

In this section, we only talk about the steps and process of solving the shortest path by ant colony algorithm.

1.1 Ant Colony algorithm steps

Suppose the number of ants is m, the number of places is n, the distance between location I and location j is Dij,t, the pheromone concentration on the path connected between location I and location j is Sij, and the pheromone concentration on the path between each location is equal at the initial time.

Ant k determines the next target location according to the pheromones on the connection path between locations. Pijk represents the probability of ant k transferring from location I at t time. The probability formula is as follows:

In the above style

For the heuristic function, it indicates the expected degree of the ant's transfer from location I to location j; for the collection of places that Ant k is about to visit, there is one element in the beginning (except the starting place). With the passage of time, each time the ant arrives at the next place, the element in it decreases by one until the empty set, which means that all sites have been visited. An is the importance factor of pheromone, the higher the value is, the greater the concentration of pheromone plays in the transfer, that is to say, the ant has a greater probability of choosing the next site close to the distance, and β is the importance factor of heuristic function.

While ants release pheromones, the pheromones on the connection path between each location gradually disappear, using parameters

Indicates the degree of volatilization of pheromones. Therefore, when all ants complete a cycle, the pheromone concentration on the connection path between each location needs to be updated, that is, ants pass by and leave pheromones, and the formula is as follows:

Among them, it represents the concentration of pheromone released by the k-th ant on the connection path between location I and j, the sum of the pheromone concentration released by all ants on the connection path between location I and j, Q is constant, which indicates the total amount of pheromone released by the ant cycle; Lk represents the length of the k-th ant through the path, generally speaking, the shorter the path, the higher the concentration of pheromone released, and finally choose the shortest path.

1.2 Ant Colony algorithm Program

(1) Parameter initialization

In order to find the shortest way money, each parameter of the program needs to be initialized, such as ant colony size m, pheromone importance factor α, heuristic function importance factor β, pheromone generation factor, the maximum number of iterations ddcs_max, the initial iteration value is ddcs=1.

(2) construct the solution space.

Each ant is randomly placed at a different starting place, and the next visit location is calculated according to the formula for the ant visit behavior, until all the ants have visited all the locations.

(3) updating pheromones

The total path length Lk of each ant is calculated, the optimal path in the current cycle is recorded, and the pheromone concentration on the connection path between locations is updated according to the formula.

(4) judging termination

Before the number of iterations reaches the maximum, clear the record of the ant and return to step (2).

2 Ant algorithm to solve the shortest path problem-- Python implementation 2.1 Source implementation

Intelligent Optimization algorithm-Ant Colony algorithm (Python implementation)

2.2 ACA_TSP implementation

Supplementary knowledge: scipy.spatial.distance.cdist

# = Import related library = import numpy as npfrom scipy import spatialimport pandas as pdimport matplotlib.pyplot as pltfrom sko.ACA import ACA_TSP num_points = 25 points_coordinate = np.random.rand (num_points, 2) # coordinate of the generated point distance_matrix = spatial.distance.cdist (points_coordinate, points_coordinate, metric='euclidean') # function is used to calculate the distance between two input sets def cal_total_distance (routine): num_points = routine.shape return sum ([distance_ Matrix [I% num_points], routine [(I + 1)% num_points]] for i in range (num_points)]) # = ACA_TSP solution = = aca = ACA_TSP (func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=200, distance_matrix=distance_matrix) best_x, best_y = aca.run () # = Visualization = = fig, ax = plt.subplots (1 2) best_points_ = np.concatenate ([best_x, [best_x [0]) best_points_coordinate = points_ cooperated [best _ points_,:] ax [0] .plot (best_points_coordinate [:, 0], best_points_coordinate [:, 1]) pd.DataFrame (aca.y_best_history) .cummin () .plot (ax=ax [1]) plt.show ()

3Ant algorithm for solving the shortest path problem-- flow chart of Matlab implementation

3.2 Code implementation

The following table shows some coordinate points to find out the shortest route:

% ant colony algorithm to find the shortest path program% clear environment variable clearclc%% import data, import method, see personal habit zuobiao= [1304 23123639 13154177 22443712 13993488 15353326 15563238 12294196 10044312 7904386 5703007 19702562 17562788 14912381 16761353715 16783918 21794061 23703780 227625784029 28384263 293134297 23673394 264339 32012935 32403140 3545 23572778 282623702975]% calculate the distance between cities n = size (zuobiao,1);% number of cities jl = zeros (n) % first calculate the distance of each coordinate point, here is the matrix initialization for I = 1if n if I = j% ~ = is not equal, each row in the zuobiao matrix has a coordinate, the coordinate is subtracted by I and j to distinguish different coordinate points, and then calculate the distance between two points jl (iMaginj) = sqrt (zuobiao (ifocus:)-zuobiao (jjcent:) ^ 2) % of the above operations such as a = [2magentin:)-a (2meme:)-a (2meme:) = > ans = 1 1, then the root sign else jl (iMague j) = 1eFet 4% equal point subtracts is exactly equal to 0, here is set to a very small number, in order to avoid errors in the later program operation, the end end end%% initialization parameter m = 50 % ant number, depending on the situation, if there are many coordinate points, it can appropriately increase the ant number a = 1;% pheromone importance factor b = 5;% heuristic function importance factor r = 0.1;% pheromone volatilization factor Q = 1;% constant qfhs = 1./jl % heuristic function to convert each element in the jl matrix to the reciprocal xxsjz = ones (n);% pheromone matrix initialization ljjl = zeros (mscore n);% path record table matrix initialization ddcs = 1;% initial iterations ddcs_max = 200;% maximum iterations Lujin_best = zeros (ddcs_max,n) % the best path of each generation L_best = zeros (ddcs_max,1);% the length of the best path of each generation L_ave = zeros (ddcs_max,1);% the average length of each generation path%% iterative search for the best path while ddcs = rand); yidong = allow (yidong_index (1)); ljjl (iMagnej) = yidong End end% calculates the path distance of each ant L = zeros (mpj1); for I = 1for m Lujin = ljjl (iMagne:); for j = 1: (n-1) L (I) = L (I) + jl (Lujin (j), Lujin (j + 1)) End L (I) = L (I) + jl (Lujin (n), Lujin (1)); end% calculates the shortest path distance and average distance if ddcs = = 1 [min_L,min_index] = min (L); L_best (ddcs) = min_L; L_ave (ddcs) = mean (L) Lujin_best (ddcs,:) = ljjl (min_index,:); else [min_L,min_index] = min (L); L_best (ddcs) = min (L_best (ddcs-1), min_L); L_ave (ddcs) = mean (L); if L_best (ddcs) = min_L Lujin_best (ddcs,:) = ljjl (min_index,:) Else Lujin_best (ddcs,:) = Lujin_best ((ddcs-1),:); end end%% update pheromone S = zeros (nQuinn) % Ant-by-ant calculation for I = 1 ljjl m% city-by-city calculation for j = 1: (n-1) S (ljjl (iLJ), ljjl (iLJ 1)) = S (ljjl (iGrainj), ljjl (iGrain1)) + Qmax L (I) End S (ljjl (iMagne), ljjl (iMagne1)) = S (ljjl (iMaginn), ljjl (iMagne)) + Q end%% L (I); end xxsjz = (1Methr) * xxsjz + S;% iterations plus 1, empty path record table ddcs = ddcs + 1; ljjl = zeros (mMagne n); end%% results show [Shortest_L,index] = min (L_best) Shortest_Lujin = Lujin_best (index,:); disp (['shortest distance:' num2str (Shortest_L)]); disp (['shortest path:' num2str ([Shortest_Lujin Shortest_Lujin (1)])]);% drawing figure (1) plot ([zuobiao (Shortest_Lujin,1); zuobiao (Shortest_Lujin (1), 1)],... [zuobiao (Shortest_Lujin,2); zuobiao (Shortest_Lujin (1), 2)], 'Omuri'); grid onfor i = 1:size (zuobiao,1) text (zuobiao (iL1), zuobiao (iL2), ['num2str (I)]); endtext (zuobiao (Shortest_Lujin (1), 1), zuobiao (Shortest_Lujin (1), 2),' starting point') Text (zuobiao (Shortest_Lujin (end), 1), zuobiao (Shortest_Lujin (end), 2), 'end') Xlabel ('Urban location Abscissa') ylabel ('Urban location ordinate') title (['Ant Colony algorithm optimizes the path (shortest distance:' num2str (Shortest_L)')] figure (2) plot (1title ddcsmaxmatical Lindbestmlbestlegmmatio) legend ('shortest distance') 'average distance') xlabel ('iterations') ylabel ('distance') title ('comparison of the shortest distance and average distance of each generation') 3.3 results

At this point, on the "Python and Matlab how to achieve ant colony algorithm to solve the shortest path" learning is over, I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.