2 遺傳模擬退火算法
　遺傳退火算法是一種混合的優(yōu)化算法，它將模擬退火算法融入到遺傳算法當(dāng)中[4],。與基于遺傳算法的總體運(yùn)行過程類似,，遺傳模擬退火算法也是一組隨機(jī)產(chǎn)生的初始種群中全局最優(yōu)解的搜尋過程。它首先通過選擇,、交叉,、變異等遺傳操作產(chǎn)生一組新的個(gè)體，然后再獨(dú)立地對(duì)所產(chǎn)生的個(gè)體進(jìn)行模擬退火過程,，并將結(jié)果作為下一代種群中的個(gè)體[4],。反復(fù)迭代地進(jìn)行這個(gè)過程，直到滿足某個(gè)終止條件為止,。利用模擬退火算法的收斂性以避免出現(xiàn)“早熟”的收斂現(xiàn)象,，可以提高算法的優(yōu)化性能。同時(shí),，本文對(duì)變異算子引入了自適應(yīng)變異的思想,，使變異概率能夠自適應(yīng)地變化。
　當(dāng)溫度較高時(shí),，擁有較高的變異率,，隨著降溫過程的繼續(xù)，變異率不斷地縮小以避免破壞優(yōu)秀的基因,。當(dāng)退火進(jìn)行到種群里的各個(gè)基因的適應(yīng)度差距很小時(shí),，重置退火溫度T，使種群的變異率加大,，以豐富種群的多樣性,，加速能夠使算法脫離局部最優(yōu)點(diǎn)，提高了算法的搜索性能,。根據(jù)問題求解的實(shí)際接近程度,，對(duì)每一個(gè)染色體指定一個(gè)適應(yīng)度的值。本文的遺傳退火算法采用保留部分最佳染色體的方法,，以保護(hù)當(dāng)前最優(yōu)染色體,，提高算法的收斂性能。同時(shí),，為了解決由于采取保留最優(yōu)解而使算法收斂于局部最優(yōu)解的問題,，在問題的解適應(yīng)度的值相差較小時(shí)，用提高變異概率的方法來增強(qiáng)種群的多樣性,，使得問題跳出局部最優(yōu)解,。通過多次的上述操作，問題將最終收斂于全局最優(yōu)解,。
2.1 適應(yīng)度函數(shù)的選取
　在本文的適應(yīng)度函數(shù)中,，為了避免“早熟”現(xiàn)象,，即降低適應(yīng)度較高的個(gè)體與其他個(gè)體適應(yīng)度之間的差異，保持了群體具有多樣性,。遺傳模擬退火算法的適應(yīng)度函數(shù)[5]采用啟發(fā)式方法,，將其定義為：

2.3 選擇
　設(shè)計(jì)選擇算子時(shí)采用排序選擇，選擇策略為轉(zhuǎn)盤式選擇,，同時(shí)使用最佳個(gè)體保留策略,，即從當(dāng)前種群中選擇D%的最佳染色體直接復(fù)制到下一代種群中。

2.4 交叉和變異
　交叉采用算術(shù)交叉,，它是指兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因,，從而形成兩個(gè)新的個(gè)體。通過對(duì)父代染色體間區(qū)域進(jìn)行多次交叉操作,，然后利用包含在新個(gè)體集合中的信息進(jìn)行信息最大化的選擇,，對(duì)每一代個(gè)體進(jìn)行基于適應(yīng)度的選擇。
　變異采用離散單點(diǎn)變異,。本文采用替換路徑中的節(jié)點(diǎn)和刪除路徑中多余節(jié)點(diǎn)兩種方法,。替換方法為：(1)尋找路徑仍未達(dá)到目的節(jié)點(diǎn)時(shí)，把路徑的最后一個(gè)節(jié)點(diǎn)替換為可以與其前一個(gè)節(jié)點(diǎn)構(gòu)成鏈路的節(jié)點(diǎn),。(2)在適應(yīng)度值滿足并已達(dá)到目標(biāo)節(jié)點(diǎn)的路徑中,，引入自適應(yīng)的概率變化進(jìn)行替換，替換準(zhǔn)則為尋找既能與其前一節(jié)點(diǎn)又能與其后一節(jié)點(diǎn)構(gòu)成鏈路的節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn),。刪除多余節(jié)點(diǎn)的方法為：對(duì)任選的一條路徑,，隨機(jī)選擇一個(gè)變異節(jié)點(diǎn)，尋找路徑中所選擇變異節(jié)點(diǎn)之后的節(jié)點(diǎn)中是否有能與其構(gòu)成鏈路的節(jié)點(diǎn),，如果有,，則與之相連，將中間的節(jié)點(diǎn)舍棄,。
2.5 終止條件
　本文的遺傳模擬退火算法(GASA)終止條件采用復(fù)合準(zhǔn)則：迭代次數(shù)達(dá)到預(yù)設(shè)要求和種群成熟度滿足一定條件,，且種群的平均適應(yīng)值提高不足1%；或進(jìn)化代數(shù)已達(dá)到預(yù)先設(shè)定的最大值,，停止迭代,。
3 改進(jìn)的遺傳模擬退火算法IGASA
　根據(jù)上述改進(jìn)算法的基本思想，建立一種適用于WSN路徑尋優(yōu)的遺傳退火算法,。
　(1)種群的初始化,。設(shè)定種群大小、初始溫度,、染色體長度,、交叉概率、變異概率,。重置T的次數(shù),、各個(gè)個(gè)體差異度,。隨機(jī)初始化種群，為了改善初始化搜索性能,，為每一個(gè)染色體指定一個(gè)適應(yīng)度的值。
　(2)適應(yīng)度函數(shù)的判斷,。篩選當(dāng)前最好的個(gè)體進(jìn)入下一代種群,。
　(3)進(jìn)行遺傳操作。選擇策略采用輪盤賭算子和最優(yōu)保存策略相結(jié)合,，交叉采用實(shí)數(shù)編碼的算術(shù)交叉,，變異采用離散單點(diǎn)變異。
　(4)模擬退火操作,。新解接受條件采用Metropolis準(zhǔn)則,。
　(5)更新、迭代過程,。根據(jù)已篩選的當(dāng)前最好個(gè)體和遺傳退火操作新生成的染色體,，加速種群的進(jìn)化，生成下一代新種群,。計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度值,，當(dāng)小于給定值時(shí)，重置T,，以增大變異的概率,，更新父代個(gè)體中最優(yōu)個(gè)體和最差個(gè)體，避免陷入局部最優(yōu)解,。
　(6)判斷重置T的次數(shù)是否等于設(shè)定值,，如果等于，轉(zhuǎn)到(7),，否則,，轉(zhuǎn)到(2)。
　(7)如果保留下來的個(gè)體中包含全局最優(yōu)值,，或者計(jì)算的代數(shù)大于限定值,，算法結(jié)束；否則,，轉(zhuǎn)到(2),。
　(8)輸出最佳目標(biāo)函數(shù)值。
　本文提出的IGASA算法偽代碼如下：

　上述代碼中,，P(t)是GA的種群大小,，Tt是初始溫度，noONodes是未知節(jié)點(diǎn)的個(gè)數(shù),，noOAnchors是錨節(jié)點(diǎn)的個(gè)數(shù),，R是節(jié)點(diǎn)的無線射程距離,，L是每個(gè)T值的迭代次數(shù)。
4 仿真結(jié)果
　為了評(píng)價(jià)IGASA算法在WSN路徑選擇上的性能,，本文將此算法與相關(guān)的算法應(yīng)用Matlab仿真進(jìn)行了比較,。仿真中，設(shè)實(shí)驗(yàn)的WSN有500個(gè)節(jié)點(diǎn),，將未知節(jié)點(diǎn)隨機(jī)部署到一個(gè)100×100的規(guī)則正方形區(qū)域內(nèi),，無線射程R設(shè)為10。根據(jù)參考文獻(xiàn)[5]-[6]對(duì)兩種算法的種群適應(yīng)度值和網(wǎng)絡(luò)生命周期進(jìn)行比較,，再通過運(yùn)行時(shí)間的變化,，均能證明應(yīng)用本方法可以實(shí)現(xiàn)對(duì)WSN路徑的優(yōu)化。
　(1)應(yīng)用IGASA算法對(duì)WSN進(jìn)行路徑優(yōu)化仿真,，種群適應(yīng)度均值及最優(yōu)個(gè)體的進(jìn)化如圖1所示,。從多次仿真結(jié)果可以看出，IGASA算法在種群均值變化的同時(shí),，最優(yōu)個(gè)體的適應(yīng)度值均能在較小的范圍浮動(dòng),，全部成功地找到了優(yōu)秀可行路徑，接近最優(yōu)結(jié)果,。

　(2)應(yīng)用IGASA算法和GA算法的路由路徑在網(wǎng)絡(luò)中運(yùn)行,，通過對(duì)如圖2所示的網(wǎng)絡(luò)生命周期的比較可以看出，隨著源節(jié)點(diǎn)個(gè)數(shù)的增加,，基于IGASA的網(wǎng)絡(luò)生命周期一直大于基于GA的網(wǎng)絡(luò)生命周期,，從而有效均衡了網(wǎng)絡(luò)能耗。

　將IGASA與基于GA的WSN路徑優(yōu)化進(jìn)行比較,，運(yùn)行結(jié)果如表1所示,，目標(biāo)為通過降低搜索時(shí)間以使能耗減小。各參數(shù)如下：交叉率為0.38,，變異率為0.2,，種群大小為20，保存最優(yōu)解占4%,，對(duì)每種情況均運(yùn)行20次,。
本文引入GASA解決WSN的路徑優(yōu)化問題，采用循環(huán)策略改進(jìn)了WSN的遺傳路徑優(yōu)化算法,，并將改進(jìn)后的IGASA算法應(yīng)用于WSN路徑優(yōu)化上,。IGASA在確保遺傳算法有效性的前提下，增強(qiáng)了收斂效率,，防止了“早熟”現(xiàn)象的發(fā)生,。相對(duì)于標(biāo)準(zhǔn)模擬退火算法以及最優(yōu)保存遺傳算法，該算法提高了算法的收斂效率又不失算法的收斂速度，具有相對(duì)的優(yōu)越性,。仿真結(jié)果表明,，該方法取得了良好的定位效果，實(shí)現(xiàn)了最佳路徑尋優(yōu)的目的,，可以滿足實(shí)際運(yùn)行需要,。下一步將繼續(xù)對(duì)模擬退火和選擇部分進(jìn)行改進(jìn)，以獲得更好的效果,。

參考文獻(xiàn)
[1] 周洪偉,，原錦輝，張來順.遺傳算法“早熟”現(xiàn)象的改進(jìn)策略[J].計(jì)算機(jī)工程,，2007，33(19)：201-203.
[2] 劉泉,，梁小宇.一種基于被動(dòng)分簇算法的能源有效WSN模型[J].計(jì)算機(jī)工程與應(yīng)用,，2007，43(16)：142-145.
[3] 李陶深,，李朔,，陳松喬，等.基于遺傳算法的網(wǎng)絡(luò)選播路由算法的研究[J].小型微型計(jì)算機(jī)系統(tǒng),，2005,，26(1)：50-55.
[4] 曹恒智，余先川.單親遺傳模擬退火及在組合優(yōu)化問題中的應(yīng)用[J].北京郵電大學(xué)學(xué)報(bào),，2008,，31(3)：38-41.
[5] 雷霖，李偉峰,，王厚軍.基于遺傳算法的無線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J].電子科技大學(xué)學(xué)報(bào),，2009，38(2)：227-230.
[6] TAM V,， CHENG K Y,， LUI K S. Using micro-genetic algorithms to improve localization in wireless sensor networks[J]. Journal of Communications， Academy,， 2006(7)：47-52.