劉小明，李暉，熊慕舟

中國地質(zhì)大學（武漢）計算機學院，武漢 430074

并行演化算法在MEMS繼電器參數(shù)優(yōu)化中的應用

劉小明，李暉，熊慕舟

中國地質(zhì)大學（武漢）計算機學院，武漢 430074

使用演化算法求解MEMS繼電器參數(shù)優(yōu)化主要瓶頸在于算法運行時間過長，而算法運行時間過長主要由于電磁仿真軟件進行建模和分析需要耗費大量的計算時間。針對該問題，采用主從并行模式，對演化算法個體適應值計算階段并行化處理。在充分考慮計算機資源的使用效率與負載均衡等因素下，使服務器盡量少地參與任務計算及減少與客戶機的通信以增強并行模式的分布能力，并且增加了客戶端掉線處理，任務重分配等操作以增強并行模式的容錯能力。經(jīng)過測試，該并行演化算法在MEMS微波繼電器參數(shù)優(yōu)化上加速比接近線速，具有良好的并行效率且容錯性較高。

并行計算；演化算法；微機電系統(tǒng)（MEMS）微波繼電器

1 引言

微波繼電器[1]是一種廣泛應用于航空航天、衛(wèi)星通信和國防軍事等領域的電子元件，其優(yōu)化設計研究具有十分重要的理論研究價值和社會應用價值。在微波繼電器設計過程中，涉及到眾多優(yōu)化參數(shù)和優(yōu)化目標，以及復雜多變的約束條件，難以運用傳統(tǒng)的數(shù)值計算方法進行求解；而演化計算具有適宜高度并行及自組織、自適應和自學習等特征，其算子操作不受優(yōu)化問題搜索空間限制條件（如可微、連續(xù)、單峰等）的約束，也不需要其他的諸如導數(shù)之類的輔助信息；因此，演化計算是微波繼電器參數(shù)設計自動優(yōu)化的有效解決途徑。

在MEMS微波繼電器[2]參數(shù)優(yōu)化設計過程中，涉及到駐波比、插入損耗和隔離度三個指標，屬于多目標優(yōu)化問題[3]。一般的多目標演化算法要獲得好的Pareto最優(yōu)解，需要數(shù)萬次的適應值函數(shù)評價；而電磁仿真軟件[4]（本文采用Ansoft HFSS和CST電磁仿真軟件）進行建模和分析需要耗費大量的計算時間，采用典型多目標演化算法[5]進行優(yōu)化，其時間開銷是無法忍受的（設定演化算法種群200個個體，演化代數(shù)為100代，則算法約需運行時間30 d），也加重了優(yōu)化難度。

為此，本文使用了基于主從式的并行模型對演化算法并行化，該模型在充分考慮演化算法并行化的通用及計算機資源的使用效率與負載均衡等因素下，對演化算法適應值計算過程并行處理，對局域網(wǎng)內(nèi)連接的多臺機器按照主從方式進行通信，由服務器將種群個體分發(fā)給客戶機進行個體評價，最后回收個體，達到減少算法運行時間的目的。實驗證明本文的并行演化算法并行效率高（接近線性加速比），能夠在較短的時間內(nèi)獲取較優(yōu)的解。

2 并行演化算法與微波繼電器

2.1 并行演化算法

一般說來，科學研究與工程實踐中許多優(yōu)化問題大都是多目標優(yōu)化問題。解決多目標優(yōu)化問題的演化算法就被稱為多目標演化算法[6]。

演化算法作為一種基于生物界自然選擇和遺傳原理的高效搜索技術，一般來說，可以在合理的計算時間內(nèi)發(fā)現(xiàn)問題的滿意最優(yōu)解，但是隨著問題規(guī)模和復雜程度的不斷提高，串行演化算法（Sequential EA，SEA）的搜索過程將會成倍地延長。因此，很多專家一直致力于提高演化算法的搜索速度，其中一個重要的研究方向就是并行演化算法[7]（Parallel EA，PEA）。

1981年Grefenstette[8]是第一個考察并行計算在遺傳算法中的應用，同樣Grosso[9]在同時期也嘗試介紹并行通過使用空間多種群模型來實現(xiàn)演化算法的并行。此后，并行演化算法繼續(xù)被Cohoon，Rudolph，Tanese，Pettey，Leuze和Gorges-Schleuter，Manderick等人研究，他們?yōu)椴⑿醒莼惴ǖ陌l(fā)展作出了卓越的貢獻。Rudolph第一個提出了演化問題的分布模型，Pettey和Leuze[10]提出了組粒度模型思想。Gorges-Schleuter，Manderick以及Spiessen[11]提出了細粒度模型思想。

隨著高性能計算機，集群計算機的發(fā)展，并行演化算法也越來越受到重視，并行演化算法因在實際工程中的出色表現(xiàn)也使更多的科學家投入到其中的研究。

2.2 演化算法與MEMS微波繼電器

目前繼電器的設計，首先是根據(jù)仿真實驗的方法設計出模型，主要是由微電子設計工程師來完成，依靠個人的專業(yè)素養(yǎng)及日常積累的設計經(jīng)驗；然后結合繼電器性能的需要，由具有工程經(jīng)驗的專業(yè)人士，進行測試，從而對繼電器的結構參數(shù)進行調(diào)整。然而，由于微波開關（繼電器）在結構和機理上的高度復雜性，導致各類型的微波開關設計過程都至少包含電磁學、機械力學、熱力學、材料科學多門學科，是一個跨學科的、難度高、周期長、計算量大的復雜設計過程[12]。因此，如果手動進行分析建模和計算，那將會大大延長設計和開發(fā)周期，因此，一般使用電磁仿真軟件進行建模和計算。目前被廣泛使用的兩款電磁仿真軟件包括CST和Ansoft HFSS，被用于演化計算在衛(wèi)星天線等工程問題設計中，已經(jīng)有了成功的應用[13]。對于同樣屬于結構形狀設計的微波繼電器，采用演化算法進行設計并優(yōu)化具有很強的操作性和可行性。

微波繼電器模型如圖1所示。

圖1 微波繼電器模型

3 算法設計與應用

3.1 并行分析

D.E.Goldberg提出的基本演化算法模型[14]，為演化算法的編寫提供了依據(jù)。對于基本演化算法，其具體的并行性表現(xiàn)在以下方面[15]。

（1）個體適應值評價并行性

每次進行演化計算的時候，都會用到個體適應值函數(shù)對種群個體的適應度進行計算，所以個體適應值的評價函數(shù)計算在演化算法的計算中占用的計算時間比較大?？梢钥紤]對適應值進行并行化研究，讓并行機計算個體適應值，可以提高整個演化算法的效率。

（2）基于種群不同組的并行性

演化算法中，一個大的種群可以劃分為多個子種群，每個子種群可以進行單獨的演化計算，可以在適當?shù)臅r間或間隔里進行信息交換。所以多個子種群也可以并行地運行到不同的并行機上。

（3）子代種群產(chǎn)生的并行性

從父代到子代的產(chǎn)生分別要進行選擇、交叉和變異等演化計算，這三個操作可以是獨立進行的，可以單獨地并行操作。

針對MEMS微波繼電器參數(shù)優(yōu)化中出現(xiàn)的問題進行分析：（1）選擇演化算法求解MEMS繼電器優(yōu)化設計的主要瓶頸在于時間上的消耗。（2）主要的時間消耗來源于個體適應值計算，對于每個個體而言，建立繼電器模型需要的電磁仿真軟件計算一次是相當費時的，使用Ansoft HFSS電磁仿真軟件在快速掃頻狀態(tài)下接近2 min，而在離散掃頻狀態(tài)下則需要20 min才能進行一次完整的評價。（3）對于演化算法這種需要評價成千上萬個個體的算法而言，如此長的時間開銷是難以忍受的。故根據(jù)實際情況，本文主要采取第一種并行方法，即使用主從式并行模型對演化算法適應值計算部分并行化，該并行模型在計算復雜問題，計算量大時，可以有很好的效率[7]。演化算法流程及并行模型見圖2。

3.2 并行MEMS繼電器參數(shù)優(yōu)化流程

主從式并行模型，分為服務器端與客戶端，服務器端主要負責任務分發(fā)與回收、負載均衡、客戶端異常處理等操作?？蛻舳酥饕撠焸€體適應值計算。具體流程如圖3所示。

圖2 并行處理及模型

服務器端：

（1）接收客戶端IP。接收從客戶端發(fā)送的TCP/IP連接請求，并為其編號。

（2）發(fā)送任務。根據(jù)客戶端IP與其編號，發(fā)送并行運行參數(shù)，HFSS或CST調(diào)用腳本給客戶端。

（3）發(fā)送種群個體。將種群發(fā)送到各個客戶端。

（4）等待客戶端返回結果。

又如德宗時，宋若昭姐妹五人均才貌雙全，曾多次受到皇帝的賞赍，而若昭之文章高潔，常以曹大家自比，德宗激賞其志節(jié)，稱其為女學士，授予尚宮之職，掌六宮文學，著有《宋若昭詩文》。女性因為才華卓著而進入男性主導的政治領域以展現(xiàn)其政治才華，這即是追求男性認同的表現(xiàn)。另一方面，唐代下層社會又有許多女道士、妓女從事文學創(chuàng)作的現(xiàn)象，她們多與文人名士相交往，詩文往來，在一定程度上拓寬了女性的生存空間，也是女性詩人文人化傾向的表現(xiàn)。女道士李冶及名妓薛濤皆與中唐詩壇名家多有往來唱和，李冶，字季蘭，著有《李季蘭集》一卷。

（5）接收結果文件。根據(jù)客戶端編號，接收從客戶端發(fā)送的適應值計算結果文件。若返回的文件數(shù)目小于客戶端數(shù)目，轉(zhuǎn)步驟（6），若等于客戶端數(shù)目，轉(zhuǎn)步驟（7）。

（6）心跳檢測。判斷客戶端是否掉線，若有客戶端掉線則刪除掉線客戶端信息，則進入掉線處理，完成任務后轉(zhuǎn)步驟（7）。

（7）更新種群。根據(jù)返回的種群個體適應值結果，篩選個體，并更新種群。

（8）停機條件。判斷種群代數(shù)是否完成或是否找出滿足要求的種群個體。若運行種群代數(shù)滿足或已找出最優(yōu)解算法結束。

客戶端：

（1）發(fā)送本機IP。與服務器建立TCP/IP連接，并將本機IP發(fā)送給客戶端。

（2）接收任務。接收從服務器端發(fā)送的腳本文件和并行運行參數(shù)。

（3）接收種群個體。接收從服務器端發(fā)送的種群個體。

種群個體適應值計算。使用HFSS或CST計算客戶端分配任務的種群個體適應值。

（5）停機條件。接收從服務器端發(fā)送的停機信號，否則轉(zhuǎn)步驟（2）。

3.3 關鍵技術

（1）心跳檢測

在算法運行過程中，有時會出現(xiàn)客戶機遭受一些人為或意外的因素使得客戶機與服務器連接失敗的情況，此時，需要服務器作出相應的處理。心跳檢測就是用來檢測客戶機與服務器的連接情況。本文中，心跳檢測是由客戶端定時向服務器端發(fā)送消息，當服務器在一定時間內(nèi)沒有收到該客戶端消息時認定與該客戶端失去連接。

圖3 并行MEMS繼電器參數(shù)優(yōu)化流程

表1 并行串行機器運行時間對比s

（2）任務重分配與并行分布能力

并行計算過程中，主機與從機的通信及額外計算都影響著并行分布能力。本文為增強算法的分布能力，從以下幾方面進行了考慮：①減少主機和從機之間的聯(lián)系；②減少主機的計算量，使更多的計算量由從機承擔。

在服務器檢測到客戶機掉線時，需要對掉線的客戶機所計算的個體重新計算。對于該情況，本文使用以下兩個準則：（1）在一定時間內(nèi)等待該客戶機重新連接，若重新連接上服務器機器，則由服務器機器將任務重新發(fā)送給該客戶機，客戶機繼續(xù)計算。（2）若超出一定時間，則服務器機器不再管理該客戶機，該客戶機所分配的計算任務由服務器機器完成。

4.3 并行演化算法運行時間測試

4 測試與分析

4.1 并行性能評估參數(shù)

通常并行算法主要由加速比與并行效率來評估[16]，對于規(guī)模為n的問題：

（1）加速比Sp(n)：Sp(n)=Ts/Tp(n)，其中Ts為求解問題的最快串行算法在最壞情形下所需的運行時間，Tp(n)為求解同一問題的并行算法在最壞情形下的運行時間。加速比Sp(n)反映了算法的并行性對運行時間的改進程度。若Sp(n)=p(n)，p(n)為處理器數(shù)，則并行達到線性加速；若Sp(n)＞p(n)，則為超線性加速。

（2）并行效率Ep：Ep(n)=Sp(n)/p(n)，該參數(shù)反映了并行算法中處理器的利用程度，Ep(n)=1為線性加速。

4.2 參數(shù)設置

算法：MOEA/D算法[17]；演化代數(shù)：10代；種群大?。?00。并行機器數(shù)：16臺客戶機，一臺服務器機。操作系統(tǒng)：Windows XP或者Windows 7。服務器機：CPU：Dual-Core E5400@2.70 GHz，內(nèi)存：3 GB?？蛻魴C：CPU：Dual-Core E5300@2.6 GHz，內(nèi)存2 GB。電磁仿真軟件：Ansoft HFSS 10。

由4.2節(jié)給出的參數(shù)設置進行測試，表1給出了在不同機器數(shù)目下，并行演化算法在運行過程中每代的時間大小，且給出了總時間及算法的加速比與并行效率。

圖4給出了算法每代運行時間的曲線圖。

圖4 不同機器數(shù)目下算法運行時間

圖5給出了并行分析過程中不同數(shù)目客戶端機器情況下的并行加速比及并行效率。

圖5 加速比與并行效率曲線

測試結果：測試了串行（1臺機器）和2臺、4臺、8臺、16臺客戶機并行，由測試結果時間表和并行性能分析圖可以看出算法的并行性能良好，在使用多臺并行機測試時算法的并行效率（平均）Ep=0.89，接近線性加速比。

4.4 并行測試結果分析

（1）在MEMS繼電器仿真優(yōu)化平臺優(yōu)化MEMS繼電器測試中，由于種群中的個體在適應值評估過程中有的會不滿足Ansoft Hfss軟件評估，故需要重新將該個體隨機產(chǎn)生，并調(diào)用Ansoft Hfss重新評估該個體，當不滿足Ansoft Hfss評估條件的個體很多時會導致整個種群的評估時間過長，此外，由于測試機器硬件的不統(tǒng)一，所以每代種群的測試時間具有不確定性。所以在本次測試中的2臺機器測試并行效率大于1，為超線性加速比。

（2）從算法每代運行時間圖（圖4）中可以看出多機并行時間曲線的浮動誤差較小，當并行機器大于等于4臺時，算法時間曲線接近于直線，表明并行算法穩(wěn)定性良好。

（3）從算法加速比與算法并行效率曲線上（圖5）分析可得出結論：并行算法性能優(yōu)良。

5 結束語

在很多實際工程中，使用演化算法進行參數(shù)優(yōu)化通常會帶來昂貴的評價或?qū)嶒?，需要消耗大量的時間等，伴隨著計算機性能的提升機及多核多機計算機的普及，并行計算也越來越多地應用于各種計算。本文的并行演化算法在MEMS微波繼電器參數(shù)優(yōu)化過程中性能良好，可為其他類似的工程應用提供一些思路，不足的是，若演化算法適應值計算的時間較少則本文的并行演化算法將不適用。

[1]李閆，譚旭，史彩紅，等.射頻、微波電磁繼電器簡介[J].機電元件，2011（3）.

[2]尤政，李慧娟，張高飛.MEMS微繼電器及其關鍵問題研究現(xiàn)狀[J].壓電與聲光，2006（3）.

[3]顏雪松，曾文聰，王漢寧，等.正交演化算法在繼電器體積優(yōu)化設計中的應用[J].計算機工程與應用，2011，47（18）：215-217.

[4]肖唐杰.航天電磁繼電器綜合仿真與開發(fā)軟件系統(tǒng)的研究[D].哈爾濱：哈爾濱工業(yè)大學，2009.

[5]鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2007.

[6]Deb K.Multi-objective optimization using evolutionary algorithms[M].[S.l.]：Wiley，2001.

[7]Alba E，Tomassini M.Parallelism and evolutionary algorithms[J].IEEE Trans on Evol Comput，2002，6（5）.

[8]Grefenstette J J.Parallel adaptive algorithms for function optimization，Tech.Rep.CS-81-19[R].Vanderbilt Univ，Nashville，TN，1981.

[9]Grosso P B.Computer simulation of genetic adaptation：parallel subcomponent interaction in a multilocus model[D]. Univ Michigan，Ann Arbor，1985.

[10]Pettey C C，Leuze M R.A theoretical investigation of a parallel genetic algorithm[C]//Schaffer J D.Proc 3rd Int Conf Genetic Algorithms，1989：398-405.

[11]Gorges-Schleuter M.ASPARAGOS：an asynchronous parallel genetic optimization strategy[C]//Schaffer J D.Proc 3rd Int Conf Genetic Algorithms，1989：422-427.

[12]付世.磁致雙穩(wěn)態(tài)MEMS電磁微繼電器的研制[D].上海：上海交通大學，2008.

[13]Cai Zhenhua，Zeng Sanyou，Yang Yang，et al.Automated antenna design using normalized steady state genetic algorithm[C]//Proceedings of NASA/ESA 2008 Conference on Adaptive Hardware and System.Netherlands：IEEE，2008：125-132.

[14]Goldberg D E.Genetic algorithms in search，optimizaion& machine learning[M].[S.l.]：Addison-Wesley，1989.

[15]陳國良.并行算法實踐[M].北京：高等教育出版社，2004.

[16]陳國良，孫廣中，徐云，等.并行算法研究方法學[J].計算機學報，2008（9）.

[17]Zhang Q，Li H.MOEA/D：a multi-objective evolutionary algorithm based on decomposition[J].IEEE Trans on Evol Comput，2007，11.

LIU Xiaoming,LI Hui,XIONG Muzhou

School of Computer Science,China University of Geosciences,Wuhan 430074,China

Time-consuming by using evolutionary algorithm to optimize MEMS microwave relay parameters is the manly problem.To solve this problem,this paper presents a master-slave parallel model to parallel the fitness calculation during the evolutionary algorithm.Considering the efficiency of the use of computer resources and load balancing,and other factors, the parallel model allows the server as little as possible to participate in mission computing and to reduce the communication between clients to enhance the distribution capacity.Besides,the model can complete the client exception handling,task redistribution to enhance the model’s fault-tolerant capability.By comparing the testing result,it proves the parallel evolutionary algorithm for MEMS microwave relay parameters optimization has a good performance.

parallel computing;evolutionary algorithm;Micro-Electro-Mechanical System（MEMS）microwave relay

A

TP302.1

10.3778/j.issn.1002-8331.1211-0300

LIU Xiaoming,LI Hui,XIONG Muzhou.Parallel evolutionary algorithm for MEMS relay parameters optimization.Computer Engineering and Applications,2014,50（6）：200-204.

國家自然科學基金（No.61103145）；中央高?；究蒲袠I(yè)務費專項資金資助項目（No.CUG100314，No.CUG120409）。

劉小明，通訊作者，男，碩士研究生；李暉（1967—），女，教授，主要研究方向為智能計算及智能信息處理；熊慕舟，男，碩士生導師。E-mail：asfion.lxm@gmail.com

2012-11-26

2013-01-15

1002-8331（2014）06-0200-05

CNKI網(wǎng)絡優(yōu)先出版：2013-02-28，http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.003.html