2 遺傳模擬退火算法
　遺傳退火算法是一種混合的優(yōu)化算法，它將模擬退火算法融入到遺傳算法當(dāng)中[4]。與基于遺傳算法的總體運(yùn)行過程類似，遺傳模擬退火算法也是一組隨機(jī)產(chǎn)生的初始種群中全局最優(yōu)解的搜尋過程。它首先通過選擇、交叉、變異等遺傳操作產(chǎn)生一組新的個(gè)體，然后再獨(dú)立地對所產(chǎn)生的個(gè)體進(jìn)行模擬退火過程，并將結(jié)果作為下一代種群中的個(gè)體[4]。反復(fù)迭代地進(jìn)行這個(gè)過程，直到滿足某個(gè)終止條件為止。利用模擬退火算法的收斂性以避免出現(xiàn)“早熟”的收斂現(xiàn)象，可以提高算法的優(yōu)化性能。同時(shí)，本文對變異算子引入了自適應(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í)際接近程度，對每一個(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è)相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。通過對父代染色體間區(qū)域進(jìn)行多次交叉操作，然后利用包含在新個(gè)體集合中的信息進(jìn)行信息最大化的選擇，對每一代個(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)的方法為：對任選的一條路徑，隨機(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é)果
　為了評價(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]對兩種算法的種群適應(yīng)度值和網(wǎng)絡(luò)生命周期進(jìn)行比較，再通過運(yùn)行時(shí)間的變化，均能證明應(yīng)用本方法可以實(shí)現(xiàn)對WSN路徑的優(yōu)化。
　(1)應(yīng)用IGASA算法對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)行，通過對如圖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%，對每種情況均運(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ā)生。相對于標(biāo)準(zhǔn)模擬退火算法以及最優(yōu)保存遺傳算法，該算法提高了算法的收斂效率又不失算法的收斂速度，具有相對的優(yōu)越性。仿真結(jié)果表明，該方法取得了良好的定位效果，實(shí)現(xiàn)了最佳路徑尋優(yōu)的目的，可以滿足實(shí)際運(yùn)行需要。下一步將繼續(xù)對模擬退火和選擇部分進(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.