（1沈陽工業大學 a.運籌與控制研究所，b.信息科學與工程學院，遼寧沈陽 110870）

 

摘  要：分析了全終端網絡成本優化問題中的尋優效果和尋優速度問題，結合了泰國學者Kanyapat Watcharasitthiwat在解決網絡優化問題的建模思想，利用成本最小化模型實施優化。根據該優化模型的特點，給出了改進蟻群算法(I-ACA)，并利用該優化算法解決了全終端網絡成本優化問題。仿真驗證結果表明，該優化算法不僅有效，且與文獻[5]中的優化方法相比具有尋優效果佳、尋優速度快的特點。尤其針對計算大型復雜全終端網絡優化問題具有較好的實用價值。

關鍵詞：全終端；網絡；可靠度；優化模型；改進蟻群算法

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

 

Research Institute of Operation and Control, Shenyang University of Technology

 Shenyang 110870, China

Abstract: Analyzing optimization results and the optimization speed in the problem of all-terminal network reliability optimization design. Reference to the optimization modeling idea used by Kanyapat Watcharasitthiwat, a cost minimization model will be used in the optimization problem, According to the characteristics of the optimization model， proposing an improvement ant colony algorithm (I-ACA) solves the solutions. The simulation results show that the algorithm is more effective than the one in literature[5], for it can get a better solution and speed rapidly. The algorithm is suitable for the problem of complex all-terminal network optimization.

Key words: all-terminal；network； reliability；optimization model；improvement ant colony algorithm；

 

 

參考文獻 (References)：

[1] Dengiz B, Altiparmak F and smith A.E.,“Efficient optimization of all-terminal Reliability Reliable networks using an evolutionary approach”, IEEE transactions on Reliability 1997,41(1):18-26.

[2] Jan, Rong-Hong., Hwang, Fung-Jen. and Chen, Sheng-Tzong., Topology optimization of a communication network subject to a reliability constraint. IEEE Trans Reliab. 1993；42（1）： 63-70.

[3] 劉艷秋,宮照廣，辛雪婷.基于全終端可靠度的網絡整體退火GA設計[J].沈陽工業大學學報.2007,29(2):165-167.

(liu Yan-qiu, Gong Zhao-guang,Xin Xue-ting. Overall annealing GA design of networks based on all-terminal reliability[J]. Journal of Naval University of Engineering, 2007, 29(2):165-167.)

[4] 劉艷秋,劉君，張穎.遺傳算法在計算機網絡可靠度優化計算中的應用[J].沈陽工業大學學報,2006,13(1):102─106.

(Liu Yian-qiu, Liu Jun, Zhang Ying.Genetic algorithm based reliability optimization for communication network design[J] Journal of Naval University of Engineering, 2001,13(6):102─106.)

[5]Kanyapat Watcharasitthiwat, Paramote Wardkein.“Reliability optimization of topology communication network design using an improved ant colony optimization ”, Computer and Electrical Engineering. 2009,35(2009):730-747.

[6]王朝瑞.圖論[M].北京:北京理工大學出版社,2001.

(WANG Chao-rui. Graph Theory [M].Beijing:Beijing University of Science and Technology Press,2001)

[7] Politof Th, Satyanarayana A.A linear time algorithm to Compute the reliability of planar cube free networks. IEEE. trans Reliability,1990,39(12):557～563.

[8]Konak A , Smith A E. An improved general upper

bound for all2terminal network reliability [ EB/ OL ] .[2005 - 12 - 15 ] . www. pitt . edu/ aesmith/ postscript/bound. pdf .

[9]段海濱.蟻群算法原理及其應用[M].北京:科學出版社, 2005.

    (Duan Hai-bing.Ant Conlony Algorithms:Theroy and Application [M].Beijing: Science Press,2005)

[10]高尚,楊靜宇,吳小俊,等.可靠性優化的蟻群算法[J].計算機應用與軟件,2004, 21 12: 94-96.

(Gao Shang,,Yang Jing-yu,Wu Xiao-jun. Ant Colony for Optimization of System Reliability [J]. Computer Applications and Software, 2004, 21 12: 94-96.)