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

關(guān)鍵字：蟻群算法；知識(shí)路由；混合信息素；自適應(yīng)調(diào)整；仿真

中圖法分類(lèi)號(hào)： TP391 文獻(xiàn)標(biāo)識(shí)碼： 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)代信息技術(shù)的發(fā)展，網(wǎng)絡(luò)中的信息資源也越加豐富，如何在其中依據(jù)用戶(hù)需求快速而準(zhǔn)確地找到目標(biāo)信息資源，即已成為目前亟待解決的研究問(wèn)題。

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

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

1 語(yǔ)義Web與知識(shí)路由的概念

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

2 蟻群算法描述

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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ū)動(dòng)的知曉?xún)?nèi)容和上下文的知識(shí)路由研究[J].計(jì)算機(jī)工程與應(yīng)用，2006，（22）：150-154.

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