基于改進蟻群算法的構件檢索優化方法

張燦青彭成薛智山滿君豐

（1.湖南工業大學計算機與通信學院株洲412007）（2.智能信息感知及處理技術湖南省重點實驗室株洲412007）

基于改進蟻群算法的構件檢索優化方法

張燦青1，2彭成1薛智山1，2滿君豐1，2

（1.湖南工業大學計算機與通信學院株洲412007）（2.智能信息感知及處理技術湖南省重點實驗室株洲412007）

在基于構件的系統軟件實現過程中，根據用戶需求對構件進行檢索和選擇越來越成為了構件系統的研究重點。利用基于信息素更新的改進基本蟻群算法來優化構件的復用規則，從而提高系統用戶對所需構件選取的準確性和有效性。最后經實驗結果證明，該方法搜索出來的構件復用規則準確率為75.2%，高于基本蟻群算法和模擬退火算法，對構件的檢索和選擇起到了較好的支持。

構件檢索；改進蟻群算法；復用規則

Class NumberTP301.6

1 引言

隨著軟件多需求及復雜度的不斷增長，軟件的開發成本和效率問題顯得越來越重要，而基于構件重復利用的開發模式已經成為軟件工程中的研究重點。所謂構件復用就是重復利用已經開發成熟的程序或已積累的知識經驗來減少在開發過程中具有相似功能或模式的重復工作［1］。構件復用已經在Web Services等一些服務軟件架構中有了成熟的應用。目前，根據構件結構和功能性的不同，已經提出了很多相應的構件檢索方法。例如，基于構件刻面分類的RE-BOOT、NATO分類方法，還有根據多種組合分類方式的青鳥構件庫等都有了實際的應用［2］。隨著人們對構件檢索的理論研究及程序開發，Alnusair團隊在構件的多刻面描述方法的構件檢索中取得了很大的成果。Wang等使用模型樹匹配方法對構件刻面描述進行匹配原則，提出了一種可重復利用的構件刻面描述性的匹配模型［3］。對構件的檢索主要包括兩方面，一是對構件的適用性進行檢索，另一方面是對構件本身結構或功能的理解效率。目前已有的研究工作主要側重對構件使用的檢索效率，使用最多的就是基于刻面分類的構件檢索方法，而對構件自身的理解還比較少。但目前在構件復用過程中對構件的檢索和擇取還具有以下幾個問題：怎么在繁多的已檢索結果中篩選對使用者真正有用的構件；如何借鑒其他復用者的構件經驗來指導當前使用者對構件進行選擇。

本文以提高構件的檢索效率為目標，結合群體智能算法中具有典型應用的基本蟻群算法，從構件的屬性信息和系統業務所需功能中建立搜索列表，利用改進基本蟻群算法對構件的復用規則和功能性特點等進行檢索篩選，使構件復用者能夠在構件檢索結果中選取符合自己需求的構件。

2 相關知識

構件是系統軟件中的重要組成部分，它實現系統業務特殊的功能，且符合統一的接口規范并實現具體接口方法［4］。如何根據系統軟件的需求在構件庫中找到符合自身功能的構件組合是構件復用的關鍵問題，并根據構件描述方式及分類方式選擇適當的構件檢索方法。在構件檢索過程中，構件復用者根據系統軟件業務對所需構件的需求構建索引，然后現有構件庫根據構件的屬性、功能等信息建立查詢語句或視圖，最后根據相關檢索算法檢索出構件組合。一般的構件檢索結構如圖1所示。

圖1 構件檢索結構

3 改進蟻群算法的構件檢索

3.1 算法改進策略

由于基本蟻群算法具有易收斂于局部最優解和收斂速度慢等缺陷［5］，為提高算法搜索的高效性及可靠性，對基本蟻群算法的規則進行改進。

規則1：首先一輪螞蟻搜索路線結束后，比較各路徑中對應的信息素總量的大小，且只對本組中信息素濃度最大（即構件組合的效率值最大）的螞蟻爬行路徑進行信息素的更新。經過測試證明，改進蟻群算法的收斂速度和搜索結果準確率都有明顯提高。

規則2：為了解決算法過早陷入局部最優解的早熟現象及停滯收斂性問題［6］，設定蟻群算法的最優路徑列表為L，設路徑列表的長度為Y，Y的值可根據某具體問題的規模大小而定。對每輪中螞蟻尋優過程中信息素濃度（即本輪新搜索到信息素濃度所對應的構件組合）最大的爬行路徑進行比較，并按大小順序依次保存Y個最優的（即信息素濃度最大）路徑到L中，其最大的路徑放在L列表的第一個元素位置，并依次類推進行排列。當算法執行完最大循環次數之后，取L列表中的第一個元素與信息素濃度最大的螞蟻路徑進行比較：如果值大小相同，表示本次尋優的值可能收斂于全局最優解，信息素濃度最大的路徑表示的構件組合即為最優構件組合；如果值大小不同，表示算法收斂于局部最優解，信息素濃度最大的路徑應該與L列表中的路徑進行比較后再得到最優結果［7］。按照L列表中路徑從大到小的排列順序搜索當前有效的、構件組合最優的組合列表。

基于基本蟻群算法的以上兩個改進規則，若要保證算法找到全局最優解，至少需要有一只螞蟻在一次路徑尋優過程中選擇了全局最優路徑。但是倘若所有的螞蟻都沒有選擇最優路徑，此時算法的改進規則就無法搜索到最優解。為了避免或減少這種情況出現，可在算法適當的運行時刻判斷算法是否正在或將要收斂于局部最優解，如果此刻的值收斂于局部最優解，則刪除此刻路徑局部最優解的值以提高算法全局選優的概率［8］。

3.2 算法MPDACO全局優化算法

1）設算法最大循環次數為Ncmax，螞蟻個數為m，初始化時間t=0，螞蟻循環變量k=0，禁忌表tabuk(k=1，2，…，m)，循環控制變量Nc=0，路徑表pathk(k=1，2，…，m)，最優構件組合列表L等，將螞蟻放置于構件組合路線中的初始位置節點，設組合路線中每條弧所表示的各QoS信息素濃度值τij(t)為MPDACO局部優化算法中所選擇構件組合表示的信息素濃度值，若對應的信息素濃度值為空，此時令構件弧上的信息素τij(t)=const，其中const為常數，const的取值不可影響算法程序的下一步運行；

2）循環次數Nc=Nc+1，若Nc>Ncmax，則退出循環，跳轉到步驟10）結束；

3）螞蟻數目k=k+1，若k>m，則退出k循環，跳轉到步驟8）；

4）搜索與螞蟻所在節點相連路線的節點位置，再按照狀態轉移概率公式計算出轉移概率的值，選擇從該節點位置發出的下一個節點（即選擇此節點和下一節點確定的構件）；

5）更新禁忌表tabuk，將新選擇的節點添加到禁忌表中；并記下螞蟻調用該構件后取得的各屬性值Q1，Q2，…，Qn，用信息素進行相應的表示。若發現該構件的狀態為無效，則在構件組合路線中將這一構件刪除；

6）如若新選擇的節點正好是構件組合路線的終點，則此螞蟻尋優過程結束，跳轉到步驟7）；否則跳轉到步驟4）；

7）記錄并計算螞蟻此輪構件尋優路徑新添加進來的信息素總和，這里新添加信息素總和指的是各個子構件新增信息素的加和；若此輪所有螞蟻搜索路徑結束，則跳轉到步驟8），否則跳轉到步驟3）；

8）比較本輪中所有螞蟻選擇構件組合的新增信息素總和，然后得到新增信息素總和值最大的構件組合列表并更新信息素規則，再把該新增信息素總和值最大的構件組合與最優構件組合列表中的構件組合進行比較：如果優于組合列表中最差的構件組合，則將該構件組合添加到最優構件組合序列中；如果最優構件組合列表已達到限定數量，則在添加該構件前需先刪除最差的構件組合；

9）清空路徑表pathk、禁忌表tabuk，跳轉步驟2）；

10）將信息素最大的構件組合與最優構件組合列表L中的構件組合進行比較，得到最優的構件組合。

構件組合優化過程，有時需要根據構件的多個QoS值整體計算出最優的構件組合，利用MPDACO算法來計算得到τij(t)。設路徑(i，j)表示的構件為s，且構件s共包含n個QoS屬性值Q1，Q2，…，Qn，對應的轉換函數為Q1(s)，Q2(s)，…，Qn(s)，各權值分別為w1，w2，…，wn，則構件s第r個QoS屬性對應的信息素pheromoner的計算公式為：

從而τij(t)的計算公式如下：

進一步計算得到狀態轉移概率的計算公式為

圖2 MPDACO算法性能測試圖（構件數=100）

如果有接連多只螞蟻的爬行路線相同，則表明該算法趨向于收斂；否則，當路徑y點在完成信息素濃度的更新之后，需要繼續進行下一輪的尋優搜索。在改進蟻群算法的規則中，將其中符合要求的添加進來，不符合的則刪除。當一輪搜索完成之后，被添加進來的路徑將從原路徑列表中去除，并且繼續下一輪的路徑搜索，直到滿足構件組合列表的數量小于給定值為止。

4 實驗及分析

實驗環境：服務器處理器為Inter Xeon CPU E5620，雙處理器，主頻均為2.4 GHz，內存為32 GB，操作系統為Windows 7專業版，編譯器為Matlab2010。使用的構件庫部分數據列表如表1所示。

本文使用基于信息素更新規則的改進蟻群算法對構件檢索的方法，并將評估標準分為極好、好、良好、較差四類。最后通過實驗驗證提出的基于信息素更新規則的改進蟻群算法對構件復用性能起到一定的優化作用。

表1 構件庫采集數據

算法中參數的設定也是個關鍵問題，參數或大或小均不能全面驗證自身的有效性。經多次實驗測試，本算法中參數設為如下時較為合適：螞蟻數量設為600，信息素揮發常用系數為0.20。各算法對實驗分別進行多次操作驗證，得到一個較為穩定的值。在不同支持度閾值條件下，模擬退火算法、基本蟻群算法和改進蟻群算法搜索出來的規則數各平均值如圖3所示。

圖3 搜索規則數的比較

隨著支持度閾值的增加，搜索出來的信息素規則數逐漸減少。在支持度閾值不變的情況下，基于信息素更新規則的改進蟻群算法比基本蟻群算法搜索出的規則數更多。改進蟻群算法雖比模擬退火算法搜索出來的規則數少，但模擬退火算法也有較明顯的缺陷，其算法運行時間過長，且搜索出來的規則質量不高。三種算法搜索出來的復用規則經數據驗證，各算法的準確率平均值分別如圖4所示。

實驗結果顯示，使用基本蟻群算法和模擬退火算法的平均準確率分別為71.8%和68.1%，而基于信息素更新規則的改進蟻群算法的準確率則高達75.2%，可知基于信息素更新規則的改進蟻群算法檢索性能有一定的提升。

圖4 不同算法的準確率比較

5 結語

本文依照算法搜索機制，將基于信息素更新規則的改進基本蟻群算法應用到系統構件檢索的優化問題中，并通過實驗驗證該改進算法的有效性和可靠性，從而提高了構件組合的檢索性能。同時相比較于模擬退火算法68.1%的準確率和基本蟻群算法71.8%的準確率，基于信息素更新規則的改進蟻群算法的構件檢索性能有所提高，其準確率達到了75.2%。但仍存在一些不足：由于構件的可復用性會受到多種因素的影響［10］，所以對于檢索出來的構件組合要想滿足各種業務需求是比較困難的。

［1］廖軍，譚浩，劉錦德.基于Pi-演算的Web服務組合的描述和驗證［J］.計算機學報，2005，28（4）：635-643.

LIAO Jun，TAN Hao，LIU Jinde.Describing and Verifying Web Service Using Pi-Calculus［J］.Chinese Journal of Computers，2005，28（4）：635-643.

［2］Guo Su-Chang，Huang Hong-Zhong，WANG Zhong-Lai，et al.Grid service reliability modeling and optimal task scheduling considering fault recovery.IEEE Transactions on Reliability，2011，60（1）：263-274.

［3］Alnusair A，Zhao Tian.Component search and reuse：an ontology based approach［C］//Proc of IEEE Internationa Conference on Information Reuse and Integration，2010：258-261.

［4］Xu Jiangle，Xiao Zhitao，Zhao Jinghua.An improved intelligent ant colony optimization based on genetic algorithm［J］.Microelectronics&Computer，2011，28（8）：47-50.

［5］Yuan Donghui，Liu Dayou，Shen Shiqun.Improved AC-GA based data association method for multi-target tracking［J］.Journal on Communications，2011，32（6）：17-22.

［6］姚全珠，馮歡，田琳.基于云端的構件庫檢索模型［J］.計算機應用，2016，36（S1）：262-264.

YAO Quanzhu，FENG Huan，TIAN Lin.Retrieval model based on cloud component library［J］.Journal of Computer Applications，2016，36（S1）：262-264.

［7］劉海亮，屈華敏，武方方，等.基于領域構件的余度管理軟件平臺研究與實現［J］.微電子學與計算機，2015，32（12）：100-104. LIU Hailiang，QU Huamin，WU Fangfang，et al.Research and Implementation of Domain Components Based Software Development Platform of Redundancy Management［J］.Microelectronics&Computer，2015，32（12）：100-104.

［8］張雷，陳立潮，潘理虎，等.構件的標識表示與檢索方法研究［J］.小型微型計算機系統，2013，34（5）：1076-1079.

ZHANG Lei，CHEN Lichao，PAN Lihu，et al.Study on Tags Representation of Components and Tags Based Components Retrieval［J］.Journal of Chinese Computer Systems，2013，34（5）：1076-1079.

［9］夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務組合優化［J］.計算機學報，2012，35（2）：2270-2281.

XIA Yamei，CHENG Bo，CHEN Junliang，et al.Optimizing Services Composition Based on Improved Ant Colony Algorithm［J］.Chinese Journal of Computers，2012，35（2）：2270-2281.

［10］童浩，孫航，李晶，等.基于改進蟻群算法的構件檢索方法［J］.計算機應用研究，2015，32（7）：2057-2059.

TONG Hao，SUN Hang，LI Jing，et al.Method based on improved ant colony algorithm for component retrieving［J］.Application Research of Computers，2015，32（7）：2057-2059.

Component Search Optimization Method Based on Improved Ant Colony Algorithm

ZHANG Canqing1，2PENG Cheng1XUE Zhishan1，2MAN Junfeng1，2
（1.College of Computer and Communication，Hunan University of Technology，Zhuzhou412007）（2.Key Laboratory of Intelligent Information Perception and Processing Technology（Hunan Province），Zhuzhou412007）

In the process of component based software implementation，it is more and more important to search and select components according to the needs of users.Based on pheromone update，the improved basic ant colony algorithm is used to optimize the component reuse rules，which can improve the accuracy and efficiency of the system users.Finally，the experimental results show that the proposed method is 75.2%，higher than the basic ant colony algorithm and simulated annealing algorithm，which has better support for the retrieval and selection of components.

component retrieval，improved ant colony algorithm，multiplexing rule

TP301.6

10.3969/j.issn.1672-9722.2017.06.010

2016年12月20日，

2017年1月20日

國家自然科學基金項目（編號：61350011，61379058，41362015）；湖南省自然科學基金項目（編號：14JJ2115，12JJ2036）；湖南省教育廳重點項目（編號：16A059）；湖南省教育廳優秀青年項目（編號：16B071）資助。

張燦青，女，碩士研究生，研究方向：網絡化軟件。彭成，男，博士，講師，研究方向：可信軟件、軟件工程。薛智山，男，碩士研究生，研究方向：網絡化軟件。滿君豐，男，教授，碩士生導師，研究方向：網絡化軟件。