優(yōu)化蟻群算法在網(wǎng)絡知識路由系統(tǒng)中的應用

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

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

中圖法分類號： 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 引言

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

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

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

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

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

2 蟻群算法描述

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

蟻群算法的數(shù)學模型如下[5]：

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

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

5 結束語

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

參考文獻：

[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] 李英杰，王莉，余雪麗. 本體驅(qū)動的知曉內(nèi)容和上下文的知識路由研究[J].計算機工程與應用，2006，（22）：150-154.

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