蟻群加密算法是近些年來迅速發(fā)展起來的，并得到廣泛應(yīng)用的一種新型仿生進化算法。

一、蟻群加密算法原理

人工蟻群加密算法是模仿真實的蟻群行為而提出的。仿生學(xué)家經(jīng)過大量細(xì)致的觀察研究發(fā)現(xiàn)：螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種被稱為外激素的物質(zhì)，并且能夠感知這種物質(zhì)，并以此來指導(dǎo)自己運動方向。因此，蟻群的集體行為就表現(xiàn)出一種信息正反饋現(xiàn)象。

人工蟻群和自然界蟻群的相似之處在于，兩者優(yōu)先選擇的都是含“外激素”濃度較大的路徑；這在兩種情況下，較短的路徑上都能聚集比較多的“外激素”；兩者的工作單元（螞蟻）都是通過在其所經(jīng)過的路徑上留下一定信息的方法進行間接的信息傳遞。有專家對這種機制以形象化的圖示來表示。

設(shè)A是巢穴，E是食物源，HC為一障礙物。由于障礙物存在，螞蟻要想由A到達(dá)E，或者由E返回A，只能由H或C繞過障礙物。各點之間的距離，如上圖所示。設(shè)每個時問單位有30只螞蟻由A到達(dá)B，有30只螞蟻由E到達(dá)D點，螞蟻過后留下的激素物質(zhì)量（以卜我們稱之為信息素）為I，為方便，設(shè)該物質(zhì)停留時間為1。在初始時刻，由于路徑BH’BC，DH，DC上均無信息存在，位于B和E的螞蟻可以隨機選擇路徑。從統(tǒng)計的角度可以認(rèn)為它們以相同的概率選擇BH，BC，DH，DC（如上圖所示）。經(jīng)過一個時間單位后，在路徑BCD上的信息量是路徑BHD上信息量的二倍。當(dāng)ｔ＝1時，將有30只螞蟻由B和D到達(dá)C，有10只螞蟻由B和D到達(dá)H。隨著時間的推移，螞蟻將會以越來越大的概率選擇路徑BCD，最終完全選擇路徑BCD，從而找到由蟻巢到食物源的最短路徑。由此可見，螞蟻個體之間的信息交換是—個正反饋過程。

二、蟻群加密算法的應(yīng)用

蟻群加密算法的理論的應(yīng)用范圍已幾乎遍及到各個領(lǐng)域，并獲得了極大的成功。蟻群加密算法主要用于求解不同的組合優(yōu)化問題。一類應(yīng)用于靜態(tài)組合優(yōu)化問題，另一類用于動態(tài)組合優(yōu)化問題。靜態(tài)問題指一次性給出問題的特征，在解決問題過程中，問題的特征不再改變。動態(tài)問題被定義為一些量的函數(shù)，這些量的值由隱含系統(tǒng)動態(tài)設(shè)置。

1、蟻群加密算法在靜態(tài)組合優(yōu)化中的應(yīng)用

①旅行商問題（簡稱TSP）。TSP問題是組合優(yōu)化中研究最多的NP－h(huán)ard問題之一，該問題就是尋找通過n個城市，各1次且最后回到原出發(fā)城市的最短路徑。

②二次分配問題（簡稱QAP）。QAP問題是指分配n個設(shè)備給n個地點，從而使得分配的代價最小，其中代價是設(shè)備被分配到位置上方式的函數(shù)。QAP是繼TSP之后蟻群加密算法應(yīng)用的第—個問題，實際上，QAP是一般化的TSP。

③車間任務(wù)調(diào)度問題（簡稱JSP）。JSP問題指己知一組M臺機器和一組價任務(wù)，任務(wù)由一組指定的將在這些機器上執(zhí)行的操作序列組成。車間任務(wù)調(diào)度問題就是給機器分配操作和時間間隔，從而使所有操作完成的時間最短。并且規(guī)定兩個工作不能在同一時間在同一臺機器上進行。

④有序排列問題（簡稱SOP）。給定—個有向圖，圖上的弧和節(jié)點都加了權(quán)，服從于節(jié)點間先后次序的約束，SOP指在有向圖上找出一個最小權(quán)值的哈密頓路徑。SOP是NP難題，它以許多工程實際問題為模型，如有著接載和運送乘客約束的單車選路徑問題，生產(chǎn)計劃以及柔性制造系統(tǒng)中的運輸問題等。

2、蟻群加密算法在動態(tài)組合優(yōu)化中的應(yīng)用

在動態(tài)組合優(yōu)化問題中，通訊網(wǎng)絡(luò)應(yīng)用最為廣泛。路由是網(wǎng)絡(luò)控制中最關(guān)鍵的組件之一。它涉及到建立和使用路由表來指導(dǎo)數(shù)據(jù)通信量在網(wǎng)絡(luò)范圍內(nèi)的分配活動。普通路由問題可以理解為是要建立—個路由表使得網(wǎng)絡(luò)性能的一些量度最大化。

①有向連接的網(wǎng)絡(luò)路由：在有向連接的網(wǎng)絡(luò)中，同—個話路的所有數(shù)據(jù)包沿著一條共同的路徑傳輸，這條路徑由一個初步設(shè)置狀態(tài)選出。在國際上，有專家將ACA加密算法用于單對單點和單對多點的有向連接網(wǎng)絡(luò)中路由，通過引入一個動態(tài)規(guī)則機制改善ACA加密算法，他們還將蟻群加密算法用于高速有向連接網(wǎng)絡(luò)系統(tǒng)中，達(dá)到公平分配效果最好的路由。

②無連接網(wǎng)絡(luò)系統(tǒng)路由：在無連接或數(shù)據(jù)包中，同一話路的網(wǎng)絡(luò)系統(tǒng)數(shù)據(jù)包?？梢匝刂煌穆窂絺鬏?，在沿著信道從源節(jié)點到終節(jié)點的每—個中間結(jié)點上，—個具體決策是由局部路由組件做出。

隨著Internet規(guī)模的不斷擴大，在網(wǎng)絡(luò)上導(dǎo)入QOS技術(shù)，以確保實時業(yè)務(wù)的通信質(zhì)量。QOS組播路由的目的是在分布的網(wǎng)絡(luò)中尋找最優(yōu)路徑，要求從源節(jié)點出發(fā)，歷經(jīng)所有的目的節(jié)點，并且在滿足所有的約束條件下，達(dá)到花費最小或達(dá)到特定的服務(wù)水平。

蟻群加密算法除了應(yīng)用于上述兩大類外，還在在很多領(lǐng)域中都有蟻群加密算法的典型應(yīng)用，如車輛路徑問題、機器人領(lǐng)域、電力系統(tǒng)、故障診斷、系統(tǒng)辨識、聚類分析、數(shù)據(jù)挖掘、圖像處理、航跡規(guī)劃、空戰(zhàn)決策、巖土工程、化學(xué)工業(yè)、生命科學(xué)等。

蟻群加密算法是一種新型的模擬進化算法，具有正反饋、并行計算和強魯棒性等許多優(yōu)點。隨著研究的深入，蟻群加密算法這一新興的仿生優(yōu)化算法必將展現(xiàn)出更加廣闊、更加引人注目的發(fā)展前景。

admin

收藏 海報分享