| 數(shù)學(xué)建模 | 您所在的位置：網(wǎng)站首頁(yè) › 流年的算法叫什么算法 › 數(shù)學(xué)建模 |
數(shù)學(xué)建模
|
蟻群算法
1.什么是蟻群算法？1.1 算法概述生物現(xiàn)象由來
行為特征蟻群算法的應(yīng)用
算法特點(diǎn)ACA算法特點(diǎn)補(bǔ)充：?jiǎn)l(fā)式算法
2.算法實(shí)例2.1 旅行商問題（TSP）初始化參數(shù)構(gòu)建模型
1.什么是蟻群算法？
1.1 算法概述
蟻群算法(Ant Colony Algorithm, ACA)由Marco Dorigo于1992年在他的博士論文中首次提出。是一種靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，用來在圖中尋找優(yōu)化路徑的算法。 生物現(xiàn)象由來蟻群系統(tǒng)(Ant System(AS)或Ant Colony System(ACS))是由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代首先提出來的。他們?cè)谘芯课浵佉捠车倪^程中，發(fā)現(xiàn)蟻群整體會(huì)體現(xiàn)一些智能的行為，例如蟻群可以在不同的環(huán)境下，尋找最短到達(dá)食物源的路徑。后經(jīng)進(jìn)一步研究發(fā)現(xiàn)，這是因?yàn)槲浵仌?huì)在其經(jīng)過的路徑上釋放一種可以稱之為“信息素(pheromone)”的物質(zhì)，蟻群內(nèi)的螞蟻對(duì)“信息素”具有感知能力，其中信息素濃度與路徑長(zhǎng)度成反比，它們會(huì)沿著“信息素”濃度較高路徑行走，而每只路過的螞蟻都會(huì)在路上留下“信息素”，這就形成一種類似正反饋的機(jī)制，這樣經(jīng)過一段時(shí)間后，整個(gè)蟻群就會(huì)沿著最短路徑到達(dá)食物源了。 行為特征? 螞蟻在尋找食物源時(shí)，會(huì)在其經(jīng)過的路徑上釋放一種信息素，并能夠感知其它螞蟻釋放的信息素。信息素濃度的大小表征路徑的遠(yuǎn)近，信息素濃度越高，表示對(duì)應(yīng)的路徑距離越短。 ? 通常，螞蟻會(huì)以較大的概率優(yōu)先選擇信息素濃度較高的路徑，并釋放 一定量的信息素，以增強(qiáng)該條路徑上的信息素濃度，這樣，會(huì)形成一個(gè) 正反饋。最終，螞蟻能夠找到一條從巢穴到食物源的最佳路徑，即距離最短。 ? 生物學(xué)家同時(shí)發(fā)現(xiàn)， 路徑上的信息素濃度會(huì)隨著時(shí)間的推進(jìn)而逐漸衰減。 ? 將蟻群算法應(yīng)用于解決優(yōu)化問題，其基本思路為：用螞蟻的行走路徑表示待優(yōu)化問題的可行解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素量較多，隨著時(shí)間的推進(jìn)，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個(gè)數(shù)也愈來愈多。最終，整個(gè)螞蟻會(huì)在正反饋的作用下集中到最佳的路徑上，此時(shí)對(duì)應(yīng)的便是待優(yōu)化問題的最優(yōu)解。 類比GA（遺傳算法）的交叉、選擇、變異，PSO（粒子群算法）的個(gè)體、群體極值優(yōu)化，蟻群算法也有自己的優(yōu)化策略：正反饋的信息機(jī)制、信息素濃度的更新、螞蟻對(duì)能夠訪問的路徑的篩選。 由上述螞蟻找食物模式演變來的算法，即是蟻群算法。這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。 蟻群算法的應(yīng)用蟻群算法應(yīng)用廣泛，如旅行商問題(traveling salesman problem,簡(jiǎn)稱TSP)、指派問題、Job-shop調(diào)度問題、車輛路徑問題（vehicle routing problem）、圖著色問題(graph coloring problem)和網(wǎng)絡(luò)路由問題（network routing problem）等等。 ? 最近幾年，該算法在網(wǎng)絡(luò)路由中的應(yīng)用受到越來越多學(xué)者的關(guān)注，并提出了一些新的基于螞蟻算法的路由算法。同傳統(tǒng)的路由算法相比較，該算法在網(wǎng)絡(luò)路由中具有信息分布式性、動(dòng)態(tài)性、隨機(jī)性和異步性等特點(diǎn)，而這些特點(diǎn)正好能滿足網(wǎng)絡(luò)路由的需要。 1.2 數(shù)學(xué)原理
關(guān)于蟻群算法中釋放信息素的特點(diǎn)，定義了三種模型： 第一種模型假設(shè)信息素總量一定。信息素濃度和經(jīng)過路徑的長(zhǎng)度成反比。
第二種模型中不使用經(jīng)過的總路徑，而僅僅使用相鄰城市的路徑長(zhǎng)度。
第三種模型更簡(jiǎn)單，不管距離長(zhǎng)短，釋放的信息素都一樣。
本文下面設(shè)計(jì)的MATLAB程序，以第一種模型為例。 1.3 算法步驟
? 采用正反饋機(jī)制，使得搜索過程不斷收斂，最終逼近于最優(yōu)解； ? 每個(gè)個(gè)體可以通過釋放信息素來改變周圍的環(huán)境，且每個(gè)個(gè)體能夠感知周圍環(huán)境的實(shí)時(shí)變化，個(gè)體間通過環(huán)境（信息素）進(jìn)行間接地通訊。對(duì)比之下，粒子群優(yōu)化算法中采用局部最優(yōu)解、全局最優(yōu)解的廣播來實(shí)現(xiàn)通訊。 ? 搜索過程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的計(jì)算能力和運(yùn)行效率； ? 啟發(fā)式的概率搜索方式，不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解。 ACA中也采用輪盤賭法，和遺傳算法中的啟發(fā)方法一樣，即選擇最大的概率那個(gè)選項(xiàng)繼續(xù)前進(jìn)。 補(bǔ)充：?jiǎn)l(fā)式算法現(xiàn)代啟發(fā)式算法在優(yōu)化機(jī)制方面存在一定的差異，但在優(yōu)化流程上卻具有較大的相似性，均是一種“鄰域搜索”結(jié)構(gòu)。算法都是從一個(gè)(一組)初始解出發(fā)，在算法的關(guān)鍵參數(shù)的控制下通過鄰域函數(shù)產(chǎn)生若干鄰域解，按接受準(zhǔn)則(確定性、概率性或混沌方式)更新當(dāng)前狀態(tài)，而后按關(guān)鍵參數(shù)修改準(zhǔn)則調(diào)整關(guān)鍵參數(shù)。如此重復(fù)上述搜索步驟直到滿足算法的收斂準(zhǔn)則，最終得到問題的優(yōu)化結(jié)果。神經(jīng)網(wǎng)絡(luò)、禁忌搜索、模擬退火、和ACA，他們都是啟發(fā)式的搜索方法，共同的基本要素：（1）隨機(jī)初始可行解；（２）給定一個(gè)評(píng)價(jià)函數(shù)（常常與目標(biāo)函數(shù)值有關(guān)）；（３）鄰域，產(chǎn)生新的可行解；（４）選擇和接受解得準(zhǔn)則；（５）終止準(zhǔn)則。 沒有啟發(fā)的算法就是隨機(jī)搜索的算法，例如遺傳算法。后面的博文中會(huì)針對(duì)這個(gè)問題細(xì)講。 2.算法實(shí)例 2.1 旅行商問題（TSP）Traveling Salesman Problem, TSP 是一個(gè)非常經(jīng)典的問題 在N個(gè)城市中各經(jīng)歷一次后再回到出發(fā)點(diǎn)，使所經(jīng)過的路程最短。 若不考慮方向性和周期性，在給定N的條件下，可能存在的閉合路徑可達(dá)到1/2*N！數(shù)量級(jí)。當(dāng)N較大時(shí)，枚舉法的計(jì)算量之大難以想象。。 TSP問題經(jīng)常被視為驗(yàn)證優(yōu)化算法性能的一個(gè)“金標(biāo)準(zhǔn)” 初始化參數(shù)在計(jì)算的開始需要對(duì)一些相關(guān)的參數(shù)進(jìn)行初始化，如： 螞蟻數(shù)量，既然是蟻群算法，我們肯定要擁有自己的蟻群，由它們對(duì)問題的解進(jìn)行搜索，螞蟻數(shù)量根據(jù)經(jīng)驗(yàn)一般設(shè)定為目標(biāo)數(shù)的1.5倍比較好，當(dāng)螞蟻數(shù)量較多時(shí)，所有螞蟻不容易收斂于一個(gè)解，而數(shù)量較少時(shí)，解的效果可能不會(huì)讓人滿意。 信息素重要程度因子，這個(gè)參數(shù)是指在螞蟻移動(dòng)的過程種產(chǎn)生的信息素對(duì)螞蟻的影響程度，比較好理解，參數(shù)越大，螞蟻選擇以前走過路徑的可能性越大，會(huì)使蟻群更容易的收斂，導(dǎo)致搜索的隨機(jī)性減弱不利于尋找全局最優(yōu)解，過小的話就沒有了信息素的意義，此參數(shù)一般為[0,5]之間比較好。 啟發(fā)函數(shù)重要程度因子，它反映了啟發(fā)式信息在指導(dǎo)蟻群在路徑搜索中的相對(duì)重要程度，其大小反映的是蟻群尋優(yōu)過程種先驗(yàn)性、確定性因素作用的強(qiáng)度。當(dāng)它越大也是更容易導(dǎo)致收斂過快。一般設(shè)置為[0,5]。 信息素?fù)]發(fā)因子，它是指信息素的消失水平，它的大小直接關(guān)系到算法的全局搜索能力和收斂速度，過大導(dǎo)致信息素?fù)]發(fā)過快，一些較好的路徑會(huì)被排除，過小導(dǎo)致路徑殘留信息素較多，影響算法效率。一般設(shè)置為[0.2,0.5]。 信息素常量，它是指螞蟻在將路徑走完時(shí)總共釋放的信息素?cái)?shù)量，它往往和啟發(fā)函數(shù)一起作用，一般設(shè)置在[10,1000]，問題規(guī)模越大信息素越高較好。 迭代次數(shù)，它是指整個(gè)蟻群累積搜索了多少次，注意蟻群算法在搜索過程種是整個(gè)蟻群同時(shí)開始搜索，然后此蟻群循環(huán)迭代，此參數(shù)一般設(shè)置為[100,500]之間，迭代次數(shù)設(shè)置的過高對(duì)算法沒有實(shí)質(zhì)意義，一般使其能夠收斂即可。 構(gòu)建模型我們要知道目標(biāo)螞蟻是在固定的解空間內(nèi)尋找最優(yōu)解，首先肯定是將螞蟻放在各個(gè)不同的出發(fā)點(diǎn)，然后讓螞蟻根據(jù)選擇依據(jù)選擇下一個(gè)要訪問的城市，這個(gè)選擇依據(jù)我們一般使用輪盤賭的方法，其中第i只螞蟻到第j個(gè)城市的概率為：
Tij 為第i個(gè)目標(biāo)到第j個(gè)目標(biāo)直接的信息素 Dij表示第i個(gè)目標(biāo)到第j個(gè)目標(biāo)直接的距離。然后讓螞蟻根據(jù)此規(guī)則進(jìn)行搜索即可。 更新信息素計(jì)算各螞蟻經(jīng)過的路徑長(zhǎng)度，記錄當(dāng)前最優(yōu)解，之后將路徑上的信息素進(jìn)行更新，新的信息素量等于原本就有的信息素?fù)]發(fā)后剩下的量加上此螞蟻?zhàn)哌^留下的信息素。在迭代過程中始終對(duì)信息素進(jìn)行累加，以保證最終螞蟻能夠收斂到最優(yōu)解。其中增加的信息素為：
Q為之前設(shè)置的信息素常量，L為螞蟻?zhàn)哌^總距離的長(zhǎng)度，增加的信息素保證增加在此螞蟻?zhàn)哌^的所有路徑段上。即假如一只螞蟻?zhàn)哌^的路徑為：1->5->3->2->4->1,那么在1-5、5-3、3-2、2-4、4-1之間的路徑上都要加上
2.2 實(shí)例代碼（MATLAB） %% I. 清空環(huán)境變量 clear all clc %% II. 導(dǎo)入數(shù)據(jù) % load citys_data.mat citys = [16.4700 96.1000 16.4700 94.4400 20.0900 92.5400 22.3900 93.3700 25.2300 97.2400 22.0000 96.0500 20.4700 97.0200 17.2000 96.2900 16.3000 97.3800 14.0500 98.1200 16.5300 97.3800 21.5200 95.5900 19.4100 97.1300 20.0900 92.5500]; %% III. 計(jì)算城市間相互距離 n = size(citys,1); % 城市數(shù)量 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; %如果是0會(huì)導(dǎo)致矩陣對(duì)角線都是0 導(dǎo)致啟發(fā)函數(shù)無窮大 因此取個(gè)很小的值 end end end %% IV. 初始化參數(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); % 路徑記錄表,每一行代表一個(gè)螞蟻?zhà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)度 %% V. 迭代尋找最佳路徑 while iter = rand); target = allow(target_index(1)); Table(i,j) = target; end end % 計(jì)算各個(gè)螞蟻的路徑距離 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 % 計(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_Length Route_best(iter,:) = Table(min_index,:); else Route_best(iter,:) = Route_best((iter-1),:); end end % 更新信息素 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); end Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end Tau = (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ì)比')2.3 結(jié)果展示
參考博客： https://www.jianshu.com/p/e6a20de60797 |
a 其中為信息重要程度因子，b 為啟發(fā)函數(shù)重要程度因子，
【本文地址】
| 今日新聞 |
| 推薦新聞 |
| 專題文章 |