李新超 賀前華 李艷雄 朱錚宇

?

基于偏好排序淘汰NSGAII算法的短波網絡多區(qū)域重點覆蓋優(yōu)化方法

李新超 賀前華*李艷雄 朱錚宇

(華南理工大學電子與信息學院 廣州 510640)

在采用偏好NSGAII算法求解多子區(qū)域重點覆蓋的短波網絡頻率優(yōu)化指配時，針對算法中非支配排序耗時較多的問題，該文提出一種偏好排序淘汰的NSGAII算法。在進行非支配排序前，根據解的偏好評價排序結果淘汰一部分偏好評價較差的解，減少參與非支配排序的解的數(shù)量從而減少求解時間，同時降低偏好評價結果較差的個體解被選中進行交叉、變異的概率，提高算法的求解效率和求解效果。在進行的48組數(shù)據測試中，該文算法在其中38組決策解偏好評價結果和求解時間同時最優(yōu)，相同迭代次數(shù)時相比偏好NSGAII算法節(jié)省27%的求解時間。結果表明通過偏好排序淘汰機制的引入，更好利用了偏好信息，使算法用較少的時間求得更好的偏好解。

短波網絡；頻率指配；多目標優(yōu)化；非支配排序；偏好排序淘汰

1 引言

短波通信具有通信距離遠、抗毀能力強、建設成本低等優(yōu)點[1]，在軍事通信、應急救災、海洋漁業(yè)等領域有著不可替代的作用[2]。短波通信頻率是影響其通信質量的關鍵因素之一[3]，但頻率資源日趨緊張。因此針對大區(qū)域應急短波網絡，岸海短波網絡等不對等短波網絡進行頻率優(yōu)化指配具有重要意義[4]。不對等短波網絡常態(tài)下的頻率優(yōu)化已有文獻進行了研究[5]，但應急短波網絡、岸海短波網絡等除在常態(tài)下滿足區(qū)域內機動電臺的隨遇接入需求外，在一個或多個區(qū)域發(fā)生突發(fā)事件時，還需要提高網絡對事發(fā)區(qū)域的可覆蓋臺站個數(shù)從而為區(qū)域內的多個應急機動電臺提供更可靠的通信保障[6]。因此根據事發(fā)區(qū)域的保障需求，在每個電離層變化相對穩(wěn)定的時段內，快速找到可對子區(qū)域進行重點覆蓋，且盡可能保障全網覆蓋最優(yōu)的頻率指配方案則非常重要。目前針對該問題的研究文獻較少，問題可抽象為一個多目標組合優(yōu)化問題。

針對多目標優(yōu)化問題，采用Pareto最優(yōu)求解的相關算法求出一組Pareto最優(yōu)解，由決策者進行選擇是目前的主流方法[7]，但相關算法求得的Pareto解數(shù)目較多，決策者較難選擇，且有許多決策者基本不會考慮的解，對這些解的搜索降低了算法效率。因此將決策者的偏好需求加入到Pareto求解過程的偏好多目標算法成為研究熱點[8]，按照偏好信息的不同主要有：參考點，參考方向[8]等簡單的偏好信息，其求解效果一般但對解的Pareto分布的普適性較好；角度偏好、雷達搜索[9]、光束搜索[10]等結合Pareto解分布情況增加了約束的偏好信息，在一些情況下更為有效，但參數(shù)設置復雜；g-dominance[11], r-dominance[12]等通過偏好信息改變Pareto解的支配關系的偏好算法，實驗表明該類偏好算法在通常情況下更為有效[12]，但對于一些近似水平或垂直分布的Pareto前端，容易造成解的丟失，影響求解性能[13]。各種偏好算法各有優(yōu)缺點，需要結合問題特點進行選取[10]。

本文的多子區(qū)域重點覆蓋的頻率優(yōu)化問題，子區(qū)域的覆蓋情況通常未知，但覆蓋要求和覆蓋任務的重要程度通常可知且可能不同，可以將子區(qū)域覆蓋任務重要程度作為偏好參考方向或子區(qū)域的覆蓋要求作為偏好參考點。在目標重要程度不同時采用目標權重參考方向則更為合適[14]。文獻[14]將偏好參考方向和由遺傳算法(Genetic Algorithms, GA)發(fā)展而來的性能優(yōu)異的多目標優(yōu)化算法NSGAII (Non-dominated Sorting Genetic Algorithms II, NSGAII)算法[9]結合，以種子解在偏好參考方向上的權重和作為評價種子解優(yōu)劣的指標，增強Pareto求解沿偏好參考方向的搜索以求得決策者需求的解，因此本文利用子區(qū)域覆蓋任務的重要程度作為偏好參考方向并結合NSGAII算法對多子區(qū)域重點覆蓋的頻率優(yōu)化問題進行求解。

在NSGAII等算法中，采用非支配排序的擁擠距離計算機制可以使Pareto精英解得到保留并分布均勻合理[14]，但該過程也是算法中最耗時的環(huán)節(jié)之一[15]，影響算法的效率。圍繞非支配排序產生了一些改進算法，提高了效率[16]，但提高的幅度也很有限。

本文結合短波網絡多子區(qū)域重點覆蓋的頻率優(yōu)化問題的特點和需求，在采用參考方向的偏好NSGAII算法求解時，針對算法中非支配排序過程耗時及偏好信息利用不足的問題，在算法進行非支配排序前，根據解的偏好評價進行排序，先淘汰一部分決策者不會考慮的偏好評價較差的解，減少參與偏好排序的解的數(shù)量，同時減少偏好評價差的解被選中遺傳的概率，提高算法的求解效果和效率。

2 短波網絡多區(qū)域多重保障問題的數(shù)學模型

2.1 決策變量及約束條件

本文研究的不對等短波網絡由一個短波核心網絡和若干機動電臺構成，核心網絡臺站通過有線互通，短波通信在短波核心網絡臺站和機動電臺之間進行，頻率優(yōu)化指配針對核心網絡臺站實現(xiàn)[5]。短波臺站的有效通信區(qū)域形狀通常不規(guī)則，需要將目標區(qū)域劃分為小的單元格以實現(xiàn)計算[6]。將目標區(qū)域劃分為個格，整個區(qū)域用矩陣表示。重點通信覆蓋的子區(qū)域表示為,為子區(qū)域編號，共個。如果單元格屬于子區(qū)域，則，否則為0,,對應單元格的坐標，,。全網覆蓋可作為一個為全1的子區(qū)域。

由于短波傳輸距離較遠，為避免同頻干擾，一個方案中一個頻率點只能使用一次。若屬于，則，否則。該約束條件表示為

(2)

2.2目標函數(shù)

(5)

(7)

2.3目標函數(shù)的Pareto解定義

由于網絡臺站頻率資源的限制，多個子區(qū)域很難同時達到最優(yōu)覆蓋保障，可能不存在最優(yōu)解，因此需要采用Pareto最優(yōu)相關概念描述解的關系。

(9)

2.4 Pareto解的偏好評價

3 偏好排序淘汰的偏好NSGAII算法

3.1偏好排序種群淘汰機制的引入

3.1.1算法的思路 在 NSGAII等算法中，非支配排序時間復雜度由參與排序解的個數(shù)和目標數(shù)確定，是算法中耗時最多的步驟之一[15]。文獻[16]的研究表明，一些非支配排序改進算法在特殊情況下可使該過程的時間復雜度降為，但通常情況下的復雜度為，仍需要大量的時間。

在偏好NSGAII算法中，僅利用偏好評價作為種子解被選中進行交叉、變異的概率，存在偏好信息利用不足的問題。在迭代解及外部檔案解合并后非支配排序前，更好地利用偏好評價信息，將偏好評價較差的一部分解先淘汰掉，減少參與非支配排序的解的數(shù)量可以減少求解時間，且減少了偏好評價較差的種群解被選中的概率，從而提高算法的求解效果和效率。

(12)

式(12)的時間復雜度小于式(11)時，本文算法即可減少求解時間，在,已知時，求得，當,,時，即的情況下，，當接近取值范圍中值時既可以均衡發(fā)揮非支配排序和偏好排序淘汰的作用，此時該步驟相比偏好NSGAII算法節(jié)省33%的時間。當，其他條件相同時，，當時節(jié)省41%的時間。

3.2算法的框架

本文的偏好排序淘汰NSGAII(preference ranking elimination NSGAII, pre-NSGAII)算法求解短波網絡多子區(qū)域重點覆蓋的頻率優(yōu)化指配時，用頻方案的染色體采用整數(shù)編碼，用頻方案對子區(qū)域的覆蓋率為對應個體解的適應度值。采用式(10)計算個體解的偏好評價值，算法框架如圖1。

4 實驗仿真及分析

4.1實驗條件及評價指標

選取以28oN, 104oE為中心的邊長為6×103km的方形區(qū)域作為短波網絡的區(qū)域場景，區(qū)域劃分為邊長20 km的9×104個方格以實現(xiàn)算法的仿真評估。短波核心網絡由36個125 W的固定臺站構成，可用頻率點數(shù)為77[5]。時間背景選取2015年1月。

圖1 pre-NSGAII求解多目標頻率指配的算法框架

采用本文的pre-NSGAII算法，目標偏好加權的單目標p-GA算法、NSGAII算法、目標偏好加權的p-NSGAII[14], g-NSGAII[15]，針對以上兩種情形以1 h為時段進行24 h的覆蓋優(yōu)化求解。

從各組算法求得的最優(yōu)決策解的偏好評價值、Pareto前沿解的分布情況、求解時間3個方面對各組算法進行評價。對NSGAII算法從最終Pareto集中按照式(10)挑選一個偏好評價最優(yōu)解作為決策解。對于本文的問題，每個時段真正的Pareto前沿解的分布是未知的，因此將描述兩個Pareto集的測度[18]進行擴展，通過多個Pareto集在最終的Pareto前沿解集的占優(yōu)比例進行Pareto解集分布廣度評價，其子集占優(yōu)越多測度越大，說明算法求得的Pareto前端分布廣度越好。

4.2實驗及結果分析

4.2.1兩個目標的實驗結果 兩個目標24個時段的覆蓋優(yōu)化結果分為兩類情況，在短波通信條件較差的時段如2~6點，13~15點，所有算法求得的解均未達到期望覆蓋。在通信條件較好的時段如1點，7~12點，18~24點，部分算法求解達到期望覆蓋而提前終止，其Pareto前端是一個解。

表1 5組算法兩個目標3個指標的最優(yōu)次數(shù)統(tǒng)計

圖3(a)中4時段的Pareto分布表明，在覆蓋較差的時段，單目標p-GA算法求解效果不如多目標相關算法，NSGAII算法Pareto前端的分布域較廣，但對偏好解的求解不如3種偏好多目標算法。3種偏好算法中，本文的pre-NSGAII算法，通過偏好淘汰，利用了更多的偏好信息，效果最好。結合表2的最優(yōu)決策解評價值及求解時間可以看出，本文算法求解效果和時間均優(yōu)于其他算法，在同樣迭代次數(shù)下，相比p-NSGAII算法節(jié)約了27%的時間。

在覆蓋較好的10時段，除p-GA外所有算法都達到了期望覆蓋，從圖3(b)難以區(qū)分算法性能，但結合表2的求解時間可以看出本文算法求解時間最短，效率最高。圖3 為兩個時段的最優(yōu)決策解的覆蓋效果，從圖4(a)與圖4(b)可以看出，的時段實現(xiàn)了全網區(qū)域2個覆蓋，子區(qū)域覆蓋效果也優(yōu)于時段。

4.2.2 3個目標的實驗結果 3個目標情形下的實驗類似兩個目標，由于通信條件、資源的限制，子區(qū)域重點覆蓋任務要求的增加，與兩個目標相比，24個時段中，未達到期望覆蓋的時段增加為15個，為1~8點，11~17點時段。達到覆蓋期望而提前終止的時段減少為9個，為9~10點，18~24點時段。根據上述情況兩類(未達到覆蓋期望的15個時段)、(達到覆蓋期望的9個時段) 各組算法,,的統(tǒng)計如表3所示。

圖4兩個目標較差、較優(yōu)時段的最優(yōu)覆蓋

表2 5組算法兩個目標較差、較優(yōu)時段的求解情況

表3 5組算法3個目標問題3個指標的勝出次數(shù)統(tǒng)計

從表3的統(tǒng)計可以看出，算法性能的比較結果與兩個目標情況基本一致，在類的15個時段中，本文算法的,分別為12和15。在類的9個時段中，本文算法的為8，均優(yōu)于其他算法。

綜合兩個目標和3個目標各24個時段共48組測試數(shù)據的求解情況，本文算法在38組上偏好評價值和求解時間均最優(yōu)，表明本文的pre-NSGAII算法通過偏好排序淘汰機制提高了算法偏好求解的效果和效率。

4.2.3淘汰剩余率取值實驗分析 偏好淘汰率是影響偏好排序淘汰和非支配排序機制的發(fā)揮作用的關鍵參數(shù)之一，為此選取上述的和時段，分別取1.00, 1.25, 1.50, 1.75, 2.00, 2.25, 2.50(僅3個目標)進行偏好淘汰率取值實驗，并與p-NSGAII進行比較，各取值分別運行5次所求得的最優(yōu)覆蓋的偏好評價值及求解時間平均如圖7所示。

表4 5組算法3個優(yōu)化目標時較差、較優(yōu)時段的求解情況

圖5 5組算法求得的3個目標較差、較優(yōu)時段的Pareto解分布

圖6 3個目標兩個子區(qū)域較差、較優(yōu)時段的最優(yōu)覆蓋

5 結束語

對子區(qū)域重點覆蓋保障的短波網絡頻率優(yōu)化指配這一多目標優(yōu)化問題，在采用偏好NSGAII算法求解時，針對算法求解中的非支配排序這一步驟耗時較多的問題，提出了偏好排序淘汰的偏好NSGAII算法。該算法在種群解和外部檔案解合并后進行非支配排序前根據偏好評價信息進行排序淘汰，淘汰一部分偏好評價較差的解，減少參與非支配排序的解的數(shù)量，同時減少后續(xù)對偏好評價差的解區(qū)域的搜索。在兩個目標和3個目標共48組測試數(shù)據中，本文算法相比p-GA, NSGAII, p-NSGAII, g-NSGAII算法在38組上的決策解偏好評價結果和求解時間同時最優(yōu)，表明通過偏好排序淘汰機制的引入，本文算法可以在節(jié)省求解時間的同時取得較好的求解效果。但在Pareto前沿解集的分布廣度上，本文算法表現(xiàn)一般，說明算法在偏好方向上穿透能力增強的同時，解集的分布廣度受到了影響。將該偏好排序淘汰機制引入其他采用非支配排序的偏好多目標算法是下一步研究的方向。

圖7 淘汰剩余率取值實驗情況

[1] 王俊江, 柳文, 焦培南. 基于返回散射探測和干擾監(jiān)測的短波通信實時選頻系統(tǒng)[J]. 電子學報, 2012, 40(4): 729-733. doi: 10.3969/j.issn.0372-2112.2012.04.017.

WANG Junjiang, LIU Wen, and JIAO Peinan. Real-time frequency selection system in HF communication based on backscatter sounding and interference monitoring[J]., 2012, 40(4): 729-733. doi: 10.3969/j.issn. 0372-2112.2012.04.017.

[2] BAYNAT B, PROUVEZ R, KHALIFE H,. Modélisation d’un mécanisme de prise de ligne dans les réseaux de communication HF[J]., 2015, 28(8): 42-46.

[3] 景淵, 李栓紅, 楊峰, 等. 短波IP網絡中速率自適應與SR- ARQ性能分析[J]. 系統(tǒng)工程與電子技術, 2013, 35(1): 184-190. doi: 10.3969/j.issn.1001-506X.2013.01.31.

JING Yuan , LI Shuanhong, YANG Feng,. Performance analysis of rate adaptation and SR-ARQ in high frequency IP network[J].&, 2013, 35(1): 184-190. doi: 10.3969/j.issn.1001-506X.2013.01.31.

[4] 朱振飛, 劉毅敏, 吳永宏, 等. 短波網動態(tài)頻率管理系統(tǒng)的狀態(tài)查詢設計[J]. 電波科學學報, 2013, 28(3): 65-69. doi: 10.13443/j.cjors.2013.03.016.

ZHU Zhenfei, LIU Yimin, WU Yonghong,. A method of link status inquiry for HF network dynamic frequency management[J]., 2013, 28(3): 65-69. doi: 10.13443/j.cjors.2013.03.016.

[5] 李新超, 賀前華, 李艷雄, 等. 基于互信息擴散蟻群算法的短波頻率優(yōu)化指配[J]. 華中科技大學學報(自然科學版), 2016, 44(4): 6-11. doi: 10.13245/j.hust.160402.

LI Xinchao, HE Qianhua, LI Yanxiong,. HF frequency assignment based on ant colony algorithm utilizing mutual information pheromone diffusion[J].(), 2016, 44(4): 6-11. doi: 10.13245/j.hust.160402.

[6] 楊青彬, 余毅敏, 郭馬坤, 等. 大區(qū)域網絡化應急短波通信中的頻率管理方法[J]. 電訊技術, 2013(4): 470-475. doi: 10 .3969/j.issn.1001-893x.2013.04.019.

YANG Qingbin, YU Yimin, GUO Makun,. Frequency management methods for large regional network of emergency HF communication[J]., 2013(4): 470-475. doi: 10.3969/j.issn.1001-893x. 2013.04.019.

[7] 公茂果, 焦李成, 楊咚咚, 等. 進化多目標優(yōu)化算法研究[J]. 軟件學報, 2009, 20(2): 271-289. doi: 10.3724/SP.J.1001. 2009.03483.

GONG Maoguo, JIAO Licheng, YANG Dongdong,. Research on evolutionary multi-objective optimization algorithms[J]., 2009, 20(2): 271-289. doi: 10.3724/SP.J.1001.2009.03483.

[8] KHARE V, YAO X, and DEB K. Performance Scaling of Multi-objective Evolutionary Algorithms[M]. Evolutionary Multi-Criterion Optimization, Springer Berlin Heidelberg, 2015: 376-390.

[9] HU Jianjie, YU Guo, ZHENG Jinhua,. A preference-based multi-objective evolutionary algorithm using preference selection radius[J]., 2016: 1-27. doi: 10.1007/s00500-016-2099-9.

[10] 鞏敦衛(wèi), 王更星, 孫曉燕. 高維多目標優(yōu)化問題融入決策者偏好的集合進化優(yōu)化方法[J]. 電子學報, 2014, 42(5): 933-939. doi: 10.3969/j.issn.0372-2112.2014.05.015.

GONG Dunwei, WANG Gengxing, and SUN Xiaoyan. Set-based evolutionary optimization algorithms integrating decision-maker's preferences for many-objective optimization problems[J]., 2014, 42(5): 933-939. doi: 10.3969 /j.issn.0372-2112.2014.05.015.

[11] MOLINA J, SANTANA L V, HERNANDEZ-DIAZ A G,. g-dominance: Reference point based dominance for multiobjective metaheuristics[J]., 2009, 197(2): 685-692. doi: 10.1016/j.ejor.2008.07.015.

[12] LIU Ruochen, SONG Xiaolin, FANG Lingfen,. An r-dominance-based preference multi-objective optimization for many-objective optimization[J]., 2016: 1-22. doi: 10.1007/s00500-016-2098-x.

[13] WANG S, ALI S, YUE T,. UPMOA: An improved search algorithm to support user-preference multi-objective optimization[C]. IEEE 26th International Symposium on Software Reliability Engineering, Gaithersbury, MD, USA, 2015: 393-404. doi: 10.1109/ISSRE.2015.7381833.

[14] DEB Kalyanmoy, and KUMAR Abhishek. Interactive evolutionary multi-objective optimization and decision- making using reference direction method[C]. Genetic and Evolutionary Computation Conference, GECCO 2007, Proceedings, London, 2007: 788-802. doi: 10.1145/1276958. 1277116.

[15] 曾三友, 李暉, 丁立新, 等. 基于排序的非劣集合快速求解算法[J]. 計算機研究與發(fā)展, 2004, 41(9): 1565-1571.

ZENG Sangou LI Hui, DING Lixin,. A fast algorithm for finding non-dominated set based on sorting[J]., 2004, 41(9): 1565-1571.

[16] ZHANG X, TIAN Y, CHENG R,. An efficient approach to non-dominated sorting for evolutionary multi-objective optimization[J]., 2015, 19(2): 201-213. doi: 10.1109/TEVC. 2014.2308305.

[17] YAN Z, ZHANG L, RAHMAN T,. Prediction of the HF ionospheric channel stability based on the modified ITS model[J]., 2013, 61(6): 3321-3333. doi: 10.1109/TAP.2013.2249571.

[18] ZITZLER E and THIELE L. Multi-objective evolutionary algorithms: A comparative case study and the strength pareto approach[J]., 1999, 3(4): 257-271. doi: 10.1109/4235.797969.

Multi-areas Outstanding Covering Optimization Method of HF NetworkBased on Preference Ranking Elimination NSGAII Algorithm

LI Xinchao HE Qianhua LI Yanxiong ZHU Zhengyu

(,,510640,)

This paper proposes a preference ranking elimination NSGAII algorithm to deal with the time-consuming issue of the preference NSGAII algorithm in optimizing HF network frequency assignment in multi-areas outstanding coverage. The proposed algorithm sorts and eliminates solutions according to their preference evaluation priori to the non-dominate sorting. By eliminating solutions with low ranking, the number of solutions participates in non-dominate sorting is reduced. The calculation time and the probability of selecting low ranking individuals for crossover or mutation are both decreased. The proposed algorithm simultaneously achieves the best performance and least calculation time in 38 of 48 sets experiments. Constrained with the same iteration number, the proposed algorithm saves 27% of computation time against the preference NSGAII algorithm. Experimental results show that by adopting preference evaluation sorting, the proposed algorithm takes less time and obtains a better solution.

High Frequency (HF) network; Frequency assignment; Multi-objective optimization; Non-dominate sorting; Preference ranking elimination

TN92

A

1009-5896(2017)08-1779-09

10.11999/JEIT161172

2016-11-02；

改回日期：2017-03-01；

2017-04-25

賀前華 eeqhhe@scut.edu.cn

國家自然科學基金(61571192)，廣東省公益研究(2015A 010103003)

The National Natural Science Foundation of China (61571192), The Public Welfare Research Project of Guangdong Province (2015A010103003)

李新超： 男，1980年生，博士生，研究方向為短波通信及智能優(yōu)化.

賀前華： 男，1965年生，教授，主要研究方向為音視頻信號處理.

李艷雄： 男，1980年生，副教授，主要研究方向為音視頻信號處理.

朱錚宇： 男，1984年生，博士生，研究方向為音視頻信號處理.