改進(jìn)蟻群算法在全終端網(wǎng)絡(luò)可靠性優(yōu)化問(wèn)題上的應(yīng)用

杜嬌嬌

摘要：本文著重解決全終端網(wǎng)絡(luò)成本優(yōu)化問(wèn)題，以達(dá)到最佳的尋優(yōu)效果和尋優(yōu)速度，基于泰國(guó)學(xué)者KanyapatWatcharasitthiwat在解決網(wǎng)絡(luò)優(yōu)化問(wèn)題的建模思想，提出了可靠性最優(yōu)的優(yōu)化模型，利用改進(jìn)蟻群算法（I-ACA）解決了全終端網(wǎng)絡(luò)可靠性優(yōu)化問(wèn)題。進(jìn)行了仿真驗(yàn)證，結(jié)果表明改進(jìn)蟻群算法不僅有效，且與傳統(tǒng)蟻群算法相比具有尋優(yōu)效果佳、尋優(yōu)速度明顯加快的特點(diǎn)，特別針對(duì)優(yōu)化大型復(fù)雜全終端網(wǎng)絡(luò)優(yōu)化問(wèn)題具有較大的意義。

關(guān)鍵詞：全終端 網(wǎng)絡(luò) 可靠度 蟻群算法 仿真驗(yàn)證

近年來(lái)通訊網(wǎng)絡(luò)技術(shù)發(fā)展飛速。計(jì)算機(jī)網(wǎng)絡(luò)的可靠性已成為眾多學(xué)者研究的焦點(diǎn)。“網(wǎng)絡(luò)可靠性研究主要有兩個(gè)核心問(wèn)題：網(wǎng)絡(luò)的可靠度計(jì)算問(wèn)題和網(wǎng)絡(luò)可靠性優(yōu)化問(wèn)題。目前國(guó)內(nèi)外學(xué)者在網(wǎng)絡(luò)可靠性優(yōu)化方面已經(jīng)取得了一系列成果”。本文主要研究的是全終端網(wǎng)絡(luò)優(yōu)化的計(jì)算問(wèn)題。即在一定的成本約束下，以極大地提高網(wǎng)絡(luò)可靠度為目標(biāo)，對(duì)通信主干網(wǎng)進(jìn)行一定的優(yōu)化。早期解決全終端可靠性優(yōu)化問(wèn)題的方法多適用于中小規(guī)模的網(wǎng)絡(luò)，對(duì)于大規(guī)模的網(wǎng)絡(luò)往往采用智能優(yōu)化方法。但是這些算法存在計(jì)算時(shí)間長(zhǎng)，容易陷入局部最優(yōu)等弊端。針對(duì)以上算法的不足。結(jié)合全終端網(wǎng)絡(luò)的構(gòu)成特點(diǎn)，提出了自適應(yīng)蟻群算法，并用實(shí)例對(duì)算法實(shí)現(xiàn)了執(zhí)行過(guò)程。

—、蟻群算法

“蟻群算法是通過(guò)受到真實(shí)蟻群的集體行為啟發(fā)的一種基于群體的模擬進(jìn)化算法，”它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制。

蟻群算法在尋優(yōu)方面具有良好性質(zhì)，在很多復(fù)雜困難的組合優(yōu)化問(wèn)題得到了廣泛的應(yīng)用。但是蟻群算法也存在一定的缺點(diǎn)，存在收斂速度慢、計(jì)算時(shí)間長(zhǎng)、容易陷入局部最優(yōu)等一些問(wèn)題。針對(duì)以上的缺點(diǎn)，本文采用自適應(yīng)蟻群算法對(duì)計(jì)算模型進(jìn)行優(yōu)化。

（一）改進(jìn)蟻群算法優(yōu)化問(wèn)題的策略

傳統(tǒng)蟻群算法存在停滯現(xiàn)象，為了避免這一缺點(diǎn)，改進(jìn)蟻群算法采用了隨機(jī)性選擇和確定性選擇相結(jié)合的選擇策略。并且采用自適應(yīng)更新原則計(jì)算轉(zhuǎn)移概率，改進(jìn)后的蟻群算法在尋優(yōu)速度和尋優(yōu)效果上有了明顯的改善。

根據(jù)自適應(yīng)蟻群算法的原理且結(jié)合優(yōu)化模型的特點(diǎn)，解決該類可靠性優(yōu)化問(wèn)題的策略為：

l。把優(yōu)化問(wèn)題轉(zhuǎn)化成矩陣的形式。

2.螞蟻只在該矩陣列上移動(dòng)。

3.螞蟻在移動(dòng)前先隨機(jī)判斷，根據(jù)判斷結(jié)果選擇移動(dòng)方式。

4.“約定螞蟻每走一步即生成一組解，然后求對(duì)應(yīng)的目標(biāo)函數(shù)的值與約束函數(shù)，對(duì)于滿足約束條件的點(diǎn)，把其作為一次迭代的結(jié)果，螞蟻轉(zhuǎn)移至該點(diǎn)；否則螞蟻保持不動(dòng)。”

5.重復(fù)上述步驟直到終止條件。

（二）目標(biāo)函數(shù)的確立

針對(duì)全終端網(wǎng)絡(luò)的特點(diǎn)確立目標(biāo)函數(shù)為：

其中，R_U（X）為基于可靠度上界來(lái)評(píng)估網(wǎng)絡(luò)可靠度的計(jì)算公式。

（三）實(shí)現(xiàn)改進(jìn)蟻群算法的步驟

初始化：設(shè)定實(shí)驗(yàn)次數(shù)，將矩陣初始化相同的數(shù)值，給出揮發(fā)系數(shù)和信息量的強(qiáng)度的值。

第一步：將螞蟻放置在初始位置上。

第二步：每只螞蟻在移動(dòng)前先進(jìn)行隨機(jī)判定，根據(jù)判定結(jié)果確定螞蟻是否移動(dòng)。

第三步：計(jì)算目標(biāo)函數(shù)差，根據(jù)目標(biāo)差判斷螞蟻是否移動(dòng)。

第四步：按照更新方程修改信息量，并且增加循環(huán)次數(shù)。

第五步：如果循環(huán)次數(shù)大于規(guī)定次數(shù)，程序結(jié)束。否則回到第二步。

二、實(shí)例仿真

選取簡(jiǎn)單和相對(duì)復(fù)雜的兩個(gè)計(jì)算機(jī)主干網(wǎng)進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中。對(duì)算法進(jìn)行35次測(cè)驗(yàn)，由仿真驗(yàn)證結(jié)果可知，改進(jìn)蟻群算法在尋優(yōu)結(jié)果上明顯優(yōu)于原始的蟻群算法，同時(shí)在計(jì)算時(shí)間上明顯優(yōu)異于傳統(tǒng)蟻群算法。

三、結(jié)論

本文運(yùn)用改進(jìn)蟻群算法優(yōu)化了全終端網(wǎng)絡(luò)可靠性問(wèn)題，結(jié)果表明改進(jìn)后的蟻群算法在尋優(yōu)速度和尋優(yōu)結(jié)果上都優(yōu)于傳統(tǒng)的蟻群算法。仿真結(jié)果驗(yàn)證了改進(jìn)蟻群算法具有可參考價(jià)值。