蟻群算法

??????蟻群算法原理
萬字長(zhǎng)文帶你了解蟻群算法及求解復(fù)雜約束問題【源碼實(shí)現(xiàn)】

?????上面這篇博文的蟻群算法是實(shí)數(shù)編碼。今天講解下離散編碼的蟻群算法。
?????算法原理不再解釋，直接上算例。

旅行商問題

????? 旅行商問題(TSP 問題)。假設(shè)有一個(gè)旅行商人要拜訪全國31個(gè)省會(huì)城市，他需要選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪-一次， 而且最后要回到原來出發(fā)的城市。路徑的選擇要求是:所選路徑的路程為所有路徑之中的最小值。

matlab求解

%%%%%%%%%%%%%%%%%%%%蟻群算法解決TSP問題%%%%%%%%%%%%%%%%%%%%%%%%%%clear all; %清除所有變量 close all; %清圖 citys=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...2370 2975]; %31個(gè)省會(huì)城市坐標(biāo)%%%%%%%%%%%%%%%%%%%%%%%計(jì)算城市間相互距離%%%%%%%%%%%%%%%%%%%%%%% %% 計(jì)算距離 n = size(citys,1);%n=31 D = zeros(n,n);%因?yàn)槭怯?jì)算兩兩之間的距離，所以矩陣為31*31 for i = 1:nfor j = 1:nif i ~= jD(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));elseD(i,j) = 1e-4; %對(duì)角矩陣 距離為0，我將對(duì)角矩陣賦值一個(gè)很小的距離，不影響計(jì)算。因?yàn)榍拔膱D中公式里有距離的倒數(shù) endend end%%%%%%%%%%%%%%%%%%%%%%%%%初始化參數(shù)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% 初始化參數(shù) m = 50; % 螞蟻數(shù)量 alpha = 1; % 信息素重要程度因子 beta = 5; % 啟發(fā)函數(shù)重要程度因子 rho = 0.1; % 信息素?fù)]發(fā)因子 Q = 1; % 常系數(shù) Eta = 1./D; % 啟發(fā)函數(shù) Tau = ones(n,n); % 信息素矩陣 Table = zeros(m,n); % 路徑記錄表 iter = 1; % 迭代次數(shù)初值 iter_max = 200; % 最大迭代次數(shù) Route_best = zeros(iter_max,n); % 各代最佳路徑 Length_best = zeros(iter_max,1); % 各代最佳路徑的長(zhǎng)度 Length_ave = zeros(iter_max,1); % 各代路徑的平均長(zhǎng)度 %%%%%%%%%%%%%%%%%%%%%%%%%迭代%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% 迭代尋找最佳路徑 while iter <= iter_max% 隨機(jī)產(chǎn)生各個(gè)螞蟻的起點(diǎn)城市start = zeros(m,1);for i = 1:m %遍歷每一個(gè)螞蟻temp = randperm(n);%randperm(n)產(chǎn)生1-n的隨機(jī)序列start(i) = temp(1); %起始點(diǎn)賦值endTable(:,1) = start; %% Table路徑記錄表 citys_index = 1:n;% 逐個(gè)螞蟻路徑選擇for i = 1:m% 逐個(gè)城市路徑選擇for j = 2:ntabu = Table(i,1:(j - 1)); % 已訪問的城市集合(禁忌表)allow_index = ~ismember(citys_index,tabu);%取出未訪問過的城市索引 allow = citys_index(allow_index); % 待訪問的城市集合P = allow;% 計(jì)算城市間轉(zhuǎn)移概率for k = 1:length(allow)P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;endP = P/sum(P);% 輪盤賭法選擇下一個(gè)訪問城市Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1));Table(i,j) = target;endend% 計(jì)算各個(gè)螞蟻的路徑距離Length = zeros(m,1);for i = 1:mRoute = Table(i,:);for j = 1:(n - 1)Length(i) = Length(i) + D(Route(j),Route(j + 1));endLength(i) = Length(i) + D(Route(n),Route(1));end% 計(jì)算最短路徑距離及平均距離if 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_LengthRoute_best(iter,:) = Table(min_index,:);elseRoute_best(iter,:) = Route_best((iter-1),:);endend% 更新信息素Delta_Tau = zeros(n,n);% 逐個(gè)螞蟻計(jì)算for i = 1:m% 逐個(gè)城市計(jì)算for 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);endDelta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);endTau = (1-rho) * Tau + Delta_Tau;% 迭代次數(shù)加1，清空路徑記錄表iter = iter + 1;Table = zeros(m,n); end%% VI. 結(jié)果顯示 [Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距離:' num2str(Shortest_Length)]); disp(['最短路徑:' num2str([Shortest_Route Shortest_Route(1)])]);%% VII. 繪圖 figure(1) plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on for i = 1:size(citys,1)text(citys(i,1),citys(i,2),[' ' num2str(i)]); end text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起點(diǎn)'); text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 終點(diǎn)'); xlabel('城市位置橫坐標(biāo)') ylabel('城市位置縱坐標(biāo)') title(['蟻群算法優(yōu)化路徑(最短距離:' num2str(Shortest_Length) ')']) figure(2) plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距離','平均距離') xlabel('迭代次數(shù)') ylabel('距離') title('各代最短距離與平均距離對(duì)比')

python求解

#!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Author: yudengwu(余登武） # @Date : 2021/5/28 #@email:1344732766@qq.com import numpy as np from tqdm import tqdm#進(jìn)度條設(shè)置 import matplotlib.pyplot as plt import matplotlib as mpl import matplotlib; matplotlib.use('TkAgg') mpl.rcParams['font.sans-serif'] = ['SimHei'] # 指定默認(rèn)字體 mpl.rcParams['axes.unicode_minus'] = False # 解決保存圖像是負(fù)號(hào)'-'顯示為方塊的問題 import math#====================距離文件================= C=[1304 ,2312,3639 ,1315,4177 ,2244,3712 ,1399,3488, 1535,3326, 1556,3238 ,1229,4196 ,1044,4312,790,4386,570,3007,1970,2562 ,1756,2788, 1491,2381 ,1676,1332,695,3715 ,1678,3918,2179,4061,2370,3780, 2212,3676, 2578,4029,2838,4263,2931,3429,1908,3507,2376,3394 ,2643,3439,3201,2935,3240,3140,3550,2545,2357,2778,2826,2370 ,2975] #31個(gè)省會(huì)城市坐標(biāo) C=np.array(C).reshape(-1,2)#shape=(31, 2)#===============蟻群算法 TSP求解==================== class ACA_TSP(object):def __init__(self,C):self.C = C # 城市坐標(biāo)self.AntCount = 100 #螞蟻數(shù)量self.city_count = self.C.shape[0] # 城市數(shù)量self.alpha = 1 # 信息素重要程度因子self.beta = 2 # 啟發(fā)函數(shù)重要程度因子self.rho = 0.1 # 揮發(fā)速度self.MAX_iter = 100 # 最大迭代次數(shù)self.Distance=self.calculate_distance(self.C[:,0], self.C[:,1])#任意兩個(gè)城市距離間隔矩陣 shape=(31, 31)self.Q = 1# 初始信息素矩陣，全是為1組成的矩陣self.pheromonetable = np.ones((self.city_count, self.city_count))# 候選集列表,存放100只螞蟻的路徑(一只螞蟻一個(gè)路徑),一共就Antcount個(gè)路徑，一共是螞蟻數(shù)量*31個(gè)城市數(shù)量self.candidate = np.zeros((self.AntCount, self.city_count)).astype(int)# path_best存放的是相應(yīng)的，每次迭代后的最優(yōu)路徑，每次迭代只有一個(gè)值self.path_best = np.zeros((self.MAX_iter, self.city_count))# 存放每次迭代的最優(yōu)距離self.distance_best = np.zeros(self.MAX_iter)#城市間的距離def calculate_distance(self,X, Y):"""建立一個(gè)citycount-citycount二維數(shù)組，存放每對(duì)城市之間的距離.注意，因?yàn)橐鶕?jù)距離矩陣求啟發(fā)函數(shù) η \eta ηij( η \eta ηij為城市i和城市j之間距離的倒數(shù)）,所有距離矩陣的對(duì)角線不能為0，我把對(duì)角線設(shè)置為inf，其實(shí)只要不為零就可以。計(jì)算城市兩輛之間的歐式距離，結(jié)果用numpy矩陣存儲(chǔ):param X: 城市的X坐標(biāo)，np.array數(shù)組:param Y: 城市的Y坐標(biāo)，np.array數(shù)組"""distance_matrix = np.zeros((self.city_count, self.city_count))for i in range(self.city_count):for j in range(self.city_count):if i == j:distance_matrix[i][j] = np.infelse:dis = np.sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2) # 歐式距離計(jì)算distance_matrix[i][j] = disreturn distance_matrixdef main(self):# 倒數(shù)矩陣etable = 1.0 / self.Distancefor iter in tqdm(range(self.MAX_iter)):#遍歷每一次迭代# first：螞蟻初始點(diǎn)選擇if self.AntCount <= self.city_count:# np.random.permutation隨機(jī)排列一個(gè)數(shù)組的self.candidate[:, 0] = np.random.permutation(range(self.city_count))[:self.AntCount]else:m = self.AntCount - self.city_countn = 2self.candidate[:self.city_count, 0] = np.random.permutation(range(self.city_count))[:]while m > self.city_count:self.candidate[self.city_count * (n - 1):self.city_count * n, 0] = np.random.permutation(range(self.city_count))[:]m = m - self.city_countn = n + 1self.candidate[self.city_count * (n - 1):self.AntCount, 0] = np.random.permutation(range(self.city_count))[:m]length = np.zeros(self.AntCount) # 每次迭代的N個(gè)螞蟻的距離值# second：選擇下一個(gè)城市選擇for i in range(self.AntCount):#遍歷每一次螞蟻# 移除已經(jīng)訪問的第一個(gè)元素unvisit = list(range(self.city_count)) # 列表形式存儲(chǔ)沒有訪問的城市編號(hào)visit = self.candidate[i, 0] # 當(dāng)前所在點(diǎn),第i個(gè)螞蟻在第一個(gè)城市unvisit.remove(visit) # 在未訪問的城市中移除當(dāng)前開始的點(diǎn)for j in range(1, self.city_count): # 訪問剩下的city_count個(gè)城市，city_count次訪問protrans = np.zeros(len(unvisit)) # 每次循環(huán)都更改當(dāng)前沒有訪問的城市的轉(zhuǎn)移概率矩陣1*30,1*29,1*28...# 下一城市的概率函數(shù)for k in range(len(unvisit)):# 計(jì)算當(dāng)前城市到剩余城市的（信息素濃度^alpha）*（城市適應(yīng)度的倒數(shù)）^beta# etable[visit][unvisit[k]],(alpha+1)是倒數(shù)分之一，pheromonetable[visit][unvisit[k]]是從本城市到k城市的信息素protrans[k] = np.power(self.pheromonetable[visit][unvisit[k]], self.alpha) * np.power(etable[visit][unvisit[k]], (self.alpha + 1))# 累計(jì)概率，輪盤賭選擇cumsumprobtrans = (protrans / sum(protrans)).cumsum()cumsumprobtrans -= np.random.rand()# 求出離隨機(jī)數(shù)產(chǎn)生最近的索引值k = unvisit[list(cumsumprobtrans > 0).index(True)]# 下一個(gè)訪問城市的索引值self.candidate[i, j] = kunvisit.remove(k)length[i] += self.Distance[visit][k]visit = k # 更改出發(fā)點(diǎn)，繼續(xù)選擇下一個(gè)到達(dá)點(diǎn)length[i] += self.Distance[visit][self.candidate[i, 0]] # 最后一個(gè)城市和第一個(gè)城市的距離值也要加進(jìn)去"""更新路徑等參數(shù)"""# 如果迭代次數(shù)為一次，那么無條件讓初始值代替path_best,distance_best.if iter == 0:self.distance_best[iter] = length.min()self.path_best[iter] = self.candidate[length.argmin()].copy()else:# 如果當(dāng)前的解沒有之前的解好，那么當(dāng)前最優(yōu)還是為之前的那個(gè)值；并且用前一個(gè)路徑替換為當(dāng)前的最優(yōu)路徑if length.min() > self.distance_best[iter - 1]:self.distance_best[iter] = self.distance_best[iter - 1]self.path_best[iter] = self.path_best[iter - 1].copy()else: # 當(dāng)前解比之前的要好，替換當(dāng)前解和路徑self.distance_best[iter] = length.min()self.path_best[iter] = self.candidate[length.argmin()].copy()"""信息素的更新"""# 信息素的增加量矩陣changepheromonetable = np.zeros((self.city_count, self.city_count))for i in range(self.AntCount):for j in range(self.city_count - 1):# 當(dāng)前路徑比如城市23之間的信息素的增量：1/當(dāng)前螞蟻行走的總距離的信息素changepheromonetable[self.candidate[i, j]][self.candidate[i][j + 1]] += self.Q / length[i]# Distance[candidate[i, j]][candidate[i, j + 1]]# 最后一個(gè)城市和第一個(gè)城市的信息素增加量changepheromonetable[self.candidate[i, j + 1]][self.candidate[i, 0]] += self.Q / length[i]# 信息素更新的公式：pheromonetable = (1 - self.rho) * self.pheromonetable + changepheromonetableprint("蟻群算法的最優(yōu)路徑", self.path_best[-1] + 1)print("迭代", self.MAX_iter, "次后", "蟻群算法求得最優(yōu)解", self.distance_best[-1])aca_tsp=ACA_TSP(C) aca_tsp.main()

算出來的不是最優(yōu)解，目前我對(duì)離散蟻群算法理解還不是很深，所以寫出來的代碼可能不是很好。先這樣吧。

作者：余登武。一個(gè)電氣專業(yè)的計(jì)算機(jī)選手。原創(chuàng)不易，禁止轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的离散蚁群算法实例（求解旅行商问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。