優化蟻群算法在網絡知識路由系統中的應用

摘要： 研究網絡知識路由問題，提高網絡資源搜索質量。針對傳統方法在網絡資源搜索過程中，存在搜索時間長，得不到最優解，導致搜索速度慢，效率低的問題。為了提高網絡資源搜索效率，提出一種基于改進蟻群的路徑搜索算法，在混合信息素更新策略，自適應揮發因子等方面進行改進，并設置了先行螞蟻和后行螞蟻。該方法有效地避免了蟻群搜索陷入局部最優，加快了收斂，提高了搜索效率。仿真結果表明，改進方法縮短了搜索時間，網絡資源搜索效率明顯提高，證明是一種有效的優化方法，能夠在最短時間找到資源搜索的最優解，是解決網絡資源搜索優化問題的有效算法。

關鍵字：蟻群算法；知識路由；混合信息素；自適應調整；仿真

中圖法分類號： TP391 文獻標識碼： A

Application of ant colony optimization algorithm to knowledge routing system

WEI Xing

（ Department of Scientific Research，Guilin University of Aerospace Technology，Guilin Guangxi 541004，China）

ABSTRACT：Knowledge routing system are studied to improve the quality of network resources. In the course of the search network resources， the traditional method takes a long time and could not get the global optimal solution， resulting in slow search speed and low efficiency problems. In order to improve search efficiency of network resources， the paper puts forward a path search algorithm based on improved ant colony optimization， focusing on improving hybrid pheromone update strategy， adaptive volatile factor， etc， meanwhile setting the first ants and after ants. The improved ant colony could effectively avoid falling into local optimum， speed up the convergence and increase the search efficiency. Simulation results show that the improved method which is an effective optimization method， could shorten the search time and improve the search efficiency of network resources， and find the optimal solution in the shortest time. Therefore it could be proved that the proposed algorithm is an optimization solution algorithm in the problem of network resources.

KEYWORDS：ACO； knowledge routing； hybrid pheromone； adaptive adjustment； simulation

0 引言

隨著現代信息技術的發展，網絡中的信息資源也越加豐富，如何在其中依據用戶需求快速而準確地找到目標信息資源，即已成為目前亟待解決的研究問題。

蟻群算法是一種群智能算法，具體是由意大利學者DORIGO[1-2]等人通過研究自然界中蟻群尋找食物過程中發現路徑的過程而形成的一種進化算法。目前，蟻群算法主要用于解決常見的復雜組合優化問題，比如：TSP問題（Traveling Salesman Problem）、路徑規劃問題（Vehicle Routing Problem）等。算法表現出了多樣性、正反饋和具有強大全局搜索能力等特點，但是，蟻群算法也同樣存在這計算開銷數值偏高、而且容易陷入局部最優等不足。

基于此，為提高蟻群算法的效率和搜索能力，本文設計提出一種基于改進蟻群的路徑搜索算法，該算法在混合信息素更新策略，自適應揮發因子等方面研究生成改進，并設置了先行螞蟻和后行螞蟻，運用于網絡知識路由問題中，有效地避免了蟻群搜索陷入局部最優， 加快了收斂速度。同時也提高了搜索效率。仿真實驗驗證了改進算法的有效性和優越性。

1 語義Web與知識路由的概念

語義Web由Berners-Lee于2001年首次公布推出[3]，其基本思想是提供基于機器可處理的語義元數據，并進行自動化的信息訪問，協助人們在Web上發現知識、處理事務。而知識路由[4]的形成則來自語義Web，重點是協同運用依據用戶的請求，網絡信息相關性及語義信息，通過搜索準確快速地發現用戶需要的目標知識。

2 蟻群算法描述

蟻群算法是在離散狀態下，將算法中的解抽象成初始狀態到目標狀態的轉移序列，其最優解就是轉移序列中的最優值。蟻群中的每只螞蟻可利用其路徑上的信息素強度執行狀態轉移，一次搜索結束后，將即時更新信息素強度，由此群體就完成一次搜索；然后不斷循環，螞蟻間也將繼續展開交流和協作，最后，得到強度最大的路徑就是最優轉移序列，即算法最優解。

蟻群算法的數學模型如下[5]：

首先，設螞蟻數量為m，螞蟻個體k在運動時的移動方向取決于各路徑上的信息量濃度； 為螞蟻k已走過的所有城市集合，且可以隨著螞蟻運動而動態調整；城市i和城市j之間的距離為 ； t 時刻ij路徑上的信息素濃度為 ； 為信息啟發式因子，反映了路徑上的信息重要性，其值越大，螞蟻間的協作性越強； 為期望啟發式因子； 為螞蟻k所經過的集合。算法開始時，m只螞蟻被隨機地放置在平面中，各路徑上的初始信息素濃度是一致的。那么在t時刻，螞蟻k從城市i轉移到城市j的概率 為：

為了避免螞蟻運動過程中在路上殘留過多的信息素而使啟發信息被淹沒，當每只螞蟻遍歷完成后，需要對殘留信息進行信息素更新處理。由于更新策略不同，DORIGO為此提出了“蟻周模型”（Ant-Cycle）、“蟻量模型”（Ant-Quantity）及“蟻密模型”（Ant-Density）等3種模型。具體實現可分做如下描述：

5 結束語

本文針對網絡知識路由系統中資源搜索存在的問題， 對基本蟻群算法開展了研究改進，提出了混合信息素更新策略，自適應揮發因子等改進方法，設置了先行螞蟻和后行螞蟻，有效地改善了基本算法存在收斂速度慢等缺陷。仿真實驗說明本文的改進算法能快速、有效、準確地搜索到網絡資源，是一種性能上更加優越的實用算法。

參考文獻：

[1] DORIGO M， VITTORIO M， ALBERTO C. The ant system： Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems， Man， and Cybernetics-Part B， 1996， 26（1）： 1-13.

[2] DORIGO M， GAMBARDELLA L M. Ant colony system： A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.

[3]Berners-Lee T， Connolly D， Swick R R. Web Architecture： Describing and Exchanging Data[EB/OL].[1999-06-07]. http：//www.w3.org/1999/04/WebData.html.

[4] 李英杰，王莉，余雪麗. 本體驅動的知曉內容和上下文的知識路由研究[J].計算機工程與應用，2006，（22）：150-154.

[5] 魏星，李志遠，陳艷. 基于蟻群和魚群的混合優化光網絡動態RWA算法[J].光通信技術，2015，3（3）：47-49.