基于改進遺傳算法的射電望遠鏡主動面布線優(yōu)化

申正，黃劍輝，葉騫

(上海交通大學 機械與動力工程學院，上海，200240)

射電望遠鏡通過精確的主動面形來接收天體的射電波，對主動面形的精度要求非常高。目前，一些大型射電望遠鏡采用了基于促動器的主動面技術，如美國的GBT 100 m、意大利的NOTO 34 m、上海的65 m射電望遠鏡等，來實時補償由于重力、溫度和風壓等外界因素引起的主動面變形[1?3]。上海的65 m射電望遠鏡的主動面系統(tǒng)共有1 104臺促動器，1 008塊面板，每塊面板由4臺促動器調整，促動器通過總線進行通訊。保證促動器的工作可靠性是主動面能實時調整的前提，因此，合理地布置總線以及每條總線上的促動器數目就顯得尤為重要。通過主動面系統(tǒng)布線來提高促動器的可靠性，目前對該問題的研究較少。許多學者利用智能算法解決生活中的布線問題，如 ANAND等[4?5]利用模擬退火、蟻群算法等算法在大規(guī)模集成電路設計中提高芯片電路的集成化，簡化加工工藝。在天然氣管道布置中，利用遺傳算法、蟻群算法等智能算法來解決各種管網形狀的布線問題[6?8]，提高管路的可靠性。本文作者針對上海65 m射電望遠鏡，采用改進的遺傳算法對其主動面系統(tǒng)的布線問題進行優(yōu)化。

1 數學模型

1.1 布線問題的實質

根據射電望遠鏡結構的對稱性，取其中的1個15°分區(qū)作為研究目標，其他分區(qū)的布線方式與此相同。將整個射電望遠鏡主動面板劃分成24個區(qū)，每個區(qū)共46個節(jié)點。射電望遠鏡在1個15°分區(qū)的促動器節(jié)點分布平面圖如圖1所示。

為了簡化布線，在不影響布線結果的前提下，將曲面布線問題轉化成平面布線問題，轉化后的促動器分布如圖2所示。根據射電望遠鏡在實際中的使用情況和優(yōu)化目標，對布線有如下要求：

1)每條總線從控制箱出發(fā)，最后再回到控制箱；

2)每條總線上的促動器盡可能少；

3)所有總線的總長度盡可能??；

4)每條總線沿著輻射梁布置，不同總線只在輻射梁上相交，在圖2中，只能沿豎直或水平方向布置。

布線優(yōu)化是一種多組尋優(yōu)的最佳路徑規(guī)劃問題，屬于一類多旅行商問題(MTSP)[9]。對于MTSP問題的求解，目前常用的算法有粒子群算法、蟻群算法、人工蜂群算法、遺傳算法等[10?13]。對于多目標的MTSP問題，朱云飛等[14]給出一種多目標混合遺傳算法，RONI等[15]也給出一種多目標遺傳算法，并測試了算法的可靠性，對布線優(yōu)化有較大指導意義。

圖1 15°分區(qū)促動器實際分布Fig. 1 Actual distribution of actuators in a 15° partition

圖2 15°分區(qū)促動器節(jié)點坐標Fig. 2 Nodes coordinates of actuators in a 15° partition

1.2 MTSP的轉化

將MTSP可以轉化成TSP，這樣就可方便地定義性能指標[9]。轉化的方法是：將多余的M?1個旅行商(共M個旅行商)看成是虛擬節(jié)點，并依附在其他節(jié)點上，TSP路線到達這些虛擬節(jié)點時自動轉向原點，則對應TSP的解即是原MTSP的解。此時，布線總長需額外考慮虛擬節(jié)點到原點的長度，屬于非線性問題，如圖3所示。

圖3 6點MTSP問題轉化成6點TSP非線性問題Fig. 3 MTSP-6 to TSP-6 nonlinear transformation

1.3 布線問題的數學模型

從布線角度來看，線路的可靠性主要取決于節(jié)點數量，單根總線節(jié)點數越多則可靠性越低；線路壓降主要取決于線路長度，總線越長則損失的電壓越大。因此，整個主動面系統(tǒng)布線問題的優(yōu)化目標是：滿足可靠性要求下使得線路壓降最小。相應的MTSP遺傳算法的目標函數是：考慮分組數，在節(jié)點數存在最大限制的條件下，尋求使得總長度最小的路線，用數學模型表示：

式中：k為布線分組數，與K有關；K是與可靠性有關的最大節(jié)點限制數；li為第i個虛擬節(jié)點到原點的距離；為第Pi?1個虛擬節(jié)點到Pi個虛擬節(jié)點之間的路徑S的長度；Ni為被虛擬節(jié)點分割后的各段節(jié)點數量；N為總節(jié)點數。

在計算總線長度時，由于要求總線沿輻射梁布置，無跨接，所以，在設計算法時，總線長度不再是一般意義上的歐氏距離，而應該是相應坐標差的絕對值之和。假設A點和B點坐標分別為A(x1，y1)和B(x2，y2)，則AB兩點之間的線長L為

為簡便起見，可以將上述帶約束的最優(yōu)化問題轉化為無約束問題。引入布線可靠性權重因子a和線路總壓降權重因子b，則布線性能指標可以認為是線路總長度和單根總線最大節(jié)點數的線性組合。對這2個指標歸一化處理。線路總長度歸一化系數選擇為最大輻射線長，即按輻射狀分成45組，每組只包含起點和1個節(jié)點；最大節(jié)點數歸一化系數選擇為除去起點的線路節(jié)點數，此處為 45。歸一化之后的優(yōu)化目標函數為

式中：′為考慮每條總線只有1個節(jié)點時，第i條總線的長度；N為總節(jié)點數。

綜上，通過改變a和b，算法在迭代過程中將同時對線路總長度、最大節(jié)點數、分組數這3個參數進行全局優(yōu)化，最終得到布線最優(yōu)的方案。

2 遺傳算法設計

2.1 個體編解碼方式

本文采用十進制的編碼方式，現(xiàn)假設共有7個城市(1為起點，不參與排序)，其中一條染色體編碼如下(斜體陰影數字表示虛擬節(jié)點，下同)：

此時，染色體共有7位，前面6位是去除起點后的任意排序，代表路徑。最后一位(帶字符邊框的表示分組數，下同)代表布線分組數為3，即對應2個虛擬節(jié)點4和7。則3組線路分別是：

為了方便地處理變組數的情況，可以將染色體拆分成2個部分。

1)路徑向量，長度為1×(N?1)的向量。

2)虛擬節(jié)點向量，長度為 1×(N?1)的向量，前(N?2)位代表虛擬節(jié)點，不足補0，第N位是分組數標志，取值范圍[1，(N?1)]。

在設計算法時將路徑向量和虛擬節(jié)點向量存儲在一個矩陣里。存儲形式如下：

2.2 適應度函數

根據布線優(yōu)化的數學模型可知，適應度是總線長度和最大節(jié)點數的函數，定義為

式(5)中的所有變量均可由路徑向量和虛擬節(jié)點計算得出。

2.3 遺傳操作算子

在傳統(tǒng)遺傳算法中，上一代通過選擇、交叉、變異等操作得到下一代。由于適應性差的個體也參與交叉變異，所以，算法的收斂速度會較慢。若先將種群分成若干個小組，在小組內進行遺傳變異，每次迭代后即重新隨機分組，則在避免算法早熟的同時可以提高收斂速度。因此，本文先對種群進行均勻分組，組內個體進行適應度計算，只保留最好個體，之后該個體通過不同方向的變異產生新個體，每次迭代后再進行新的隨機分組以避免早熟。對本文所研究的布線優(yōu)化問題，個體的差異由以下3個方面決定：MTSP轉化成 TSP后的路徑向量、虛擬節(jié)點的數量(布線分組數)、虛擬節(jié)點的位置?，F(xiàn)假設有8個城市，種群隨機分組，每組有12個個體，其染色體編碼均是隨機產生，經過適應度計算后，選出組內最好個體(如表1所示)。然后將該個體復制11個，并控制這11個個體按照以下方向進行變異。

2.3.1 對路徑向量變異

算法隨機產生2個斷點(加粗斜體數字)，假設為第2位和第6位。對復制個體1~3號進行路徑變異操作。

表1 最好個體Table 1 The best individual

1)交換操作。

交換第2位和第6位上的基因，得到1號子代個體的路徑向量如下：

2)反轉操作。

將第2位和第6位中間的基因段反轉排列，得到2號子代個體的路徑向量如下：

3)移位操作。

將第2位和第6位中間的基因段進行循環(huán)移位操作，即整個基因片段環(huán)形右移1位，基因片段最后一位變成第1位，變異后的3號子代個體的路徑向量如下：

2.3.2 對虛擬節(jié)點向量變異

4號子代個體生成方式為：路徑向量不變(仍為最好個體路徑向量)，分組數不變，在原序列的基礎上隨機產生新的虛擬節(jié)點，產生新的虛擬節(jié)點向量如下：

5號子代個體生成方式為：路徑向量不變，分組數隨機產生，且根據分組數重新隨機配置虛擬節(jié)點位置，產生新的虛擬節(jié)點向量如下：

2.3.3 組合變異

子代個體6~8號由最好個體的變異路徑向量和子代個體4號的虛擬節(jié)點向量組合產生；子代9~11號由最好個體的變異路徑向量和子代個體5號的虛擬節(jié)點向量組合產生。

算法中每個分組都進行相同的遺傳變異操作，最終產生新一代種群。在下一次迭代時種群將會重新隨機分組，以保證種群的多樣性。整個遺傳變異過程如流程圖4所示。

圖4 遺傳算法計算流程圖Fig. 4 Flow chart of genetic algorithm

3 優(yōu)化結果及討論

假定總線長和可靠性同等重要，考慮到較N大很多(約 10倍)，所以，設定可靠性權重因子a=10和線路總壓降權重因子b=1。然后，利用遺傳算法進行優(yōu)化，得到優(yōu)化結果(見圖5)，相應的適應度收斂曲線如圖6所示。在實際應用時，可以根據總線長和可靠性的不同要求調整權重因子，得到相應的優(yōu)化結果。

為了測試算法的穩(wěn)定性，在相同的條件下多次運行，得到的優(yōu)化結果如表2所示。采用傳統(tǒng)遺傳算法對同樣的問題進行求解，優(yōu)化結果如表3所示。測試中用到的主要參數如表4所示。

從表2和表3可以看出，考慮總線長和可靠性同等重要時，最優(yōu)方案是最短線長為64的2組布線(排布方式不唯一)。在10次測試中，總線長有8次都收斂于64，說明算法穩(wěn)定性很高。與傳統(tǒng)遺傳算法相比，該程序的平均運行時間為 2 min，而傳統(tǒng)遺傳算法平均運行時間大于5 h，計算效率有明顯提高；此外，傳統(tǒng)遺傳算法很不穩(wěn)定，容易出現(xiàn)丟點的現(xiàn)象，最優(yōu)的總線長為71。

圖5 布線優(yōu)化分組結果Fig. 5 Optimized grouping results of wiring

圖6 適應度變化曲線Fig. 6 Changing curve of fitness

表2 分組遺傳算法測試結果Table 2 Test results of group-based GA

表3 傳統(tǒng)遺傳算法測試結果Table 3 Test results of general GA

表4 2種算法主要參數Table 4 Main parameters of two algorithms

傳統(tǒng)遺傳算法出現(xiàn)運行時間長、不穩(wěn)定的情況是由于適應性差的個體在算法中參與了交叉變異，減慢了算法向最優(yōu)解收斂的速度，同時容易使算法早熟。從結果可以看出：減少適應性差的個體的參與度，并提高變異概率會提高算法的性能。

通過對比可以看出：在穩(wěn)定性、計算效率和優(yōu)化結果方面，本文基于分組優(yōu)化的遺傳算法比傳統(tǒng)遺傳算法有很大的提升，證明了該算法的正確性和有效性。

4 結論

1)提出了一種改進的遺傳算法，該算法利用分組優(yōu)化的思想和針對組內最好個體的變異方式，有效地提高了遺傳算法的收斂速度和算法穩(wěn)定性。

2)改進的遺傳算法可以對射電望遠鏡主動面系統(tǒng)的布線問題進行優(yōu)化，得到最小壓降和最大可靠性的布線方案，使主動面系統(tǒng)能更好地實時補償射電望遠鏡的表面變形，進而提高射電望遠鏡的觀測性能。

[1]PRESTAGE R M, CONSTANTILEES K T, HUNTER T R, et al.The green bank telescope[J]. Proceedings of the IEEE, 2009,97(8): 1382?1390.

[2]趙衛(wèi), 葉騫, 馮正進. 射電望遠鏡主動反射面控制技術簡析[J]. 現(xiàn)代雷達, 2011, 33(5): 85?90.ZHAO Wei, YE Qian, FENG Zhengjin. Analysis of control technology for active reflector of radio telescope[J]. Modern Radar, 2011, 33(5): 85?90.

[3]杜彪, 伍洋, 張一凡, 等. 大口徑反射面天線技術綜述[J]. 無線電通信技術, 2016(1): 1?8.DU Biao, WU Yang, ZHANG Yifan, et al. Survey of large aperture reflector antenna technology[J]. Radio Communications Technology, 2016(1): 1?8.

[4]ANAND S, SARAVANASANKAR S, SUBBARAJ P. A multiobjective optimization tool for very large scale integrated nonslicing floorplanning[J]. International Journal of Circuit Theory & Applications, 2013, 41(9): 904?923.

[5]CHEN Guotong, GUO Wenzhong, CHEN Yuzhong. A PSO-based intelligent decision algorithm for VLSI floorplanning[J]. Soft Computing, 2010, 14(12): 1329?1337.

[6]蔣永明. 基于蟻群算法的天然氣長輸管線優(yōu)化設計研究[D].哈爾濱: 哈爾濱工業(yè)大學市政環(huán)境工程學院, 2007: 31?38.JIANG Yongming. The research about optimization design of natural gas pipeline based on ant colony algorithms[D]. Harbin:Harbin Institute of Technology. School of Municipal and Environmental Engineering, 2007: 31?38.

[7]呂木英. 基于遺傳算法的城市燃氣管網最優(yōu)化布局研究[D].武漢: 武漢理工大學能源與動力工程學院, 2009: 28?36.Lü Muying. Study on optimization of urban gas distribution network based on genetic algorithm[D]. Wuhan: Wuhan University of Technology. School of Energy and Power Engineering, 2009: 28?36.

[8]劉奇. 天然氣管道調度優(yōu)化研究[D]. 南充: 西南石油大學石油與天然氣工程學院, 2014: 35?39.LIU Qi. Study on the optimization of natural gas pipeline scheduling[D]. Nanchong: Southwest Petroleum University.College of Petroleum Engineering, 2014: 35?39.

[9]俞慶生, 林冬梅, 王東. 多旅行商問題研究綜述[J]. 價值工程,2012, 31(2): 166?168.YU Qingsheng, LIN Dongmei, WANG Dong. An overview of multiple traveling salesman problem[J]. Value Engineering,2012, 31(2): 166?168.

[10]CARTER A E, RAGSDALE C T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J]. European Journal of Operational Research, 2006,175(1): 246?257.

[11]PAN Junjie, WANG Dingwei. An ant colony optimization algorithm for multiple travelling salesman problem[C]//International Conference on Innovative Computing, Information and Control. Los Alamitos: IEEE Computer Society, 2006:01446.

[12]ZHANG Z, CHEN Y, CHENG H, et al. MTSP based solution for minimum mobile node number problem in sweep converge of wireless sensor network[C]//International Conference on Computer Science and Network Technology. Piscataway: IEEE,2011: 1827?1830.

[13]VENKATESH P, SINGH A, VENKATESH P, et al. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing, 2015, 26: 74?89.

[14]朱云飛, 蔡自興, 袁琦釗, 等. 求解多目標旅行商問題的混合

遺傳算法[J]. 計算機工程與應用, 2011, 47(7): 52?56.

ZHU Yunfei, CAI Zixing, YUAN Qizhao, et al. Hybrld genetic algorithm for multiple-objective TSP[J]. Computer Engineering and Applications, 2011, 47(7): 52?56.

[15]RONI M A, RAHMAN S. Using Genetic Algorithms to minimize the distance and balance the routes for the multiple Traveling Salesman Problem[J]. Evolutionary Computation,2015, 41(6): 3171?3178.