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

劉小明，李暉，熊慕舟

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

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

劉小明，李暉，熊慕舟

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

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

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

1 引言

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

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

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

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

2.1 并行演化算法

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

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

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

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

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

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

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

圖1 微波繼電器模型

3 算法設(shè)計(jì)與應(yīng)用

3.1 并行分析

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

（1）個(gè)體適應(yīng)值評價(jià)并行性

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

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

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

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

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

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

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

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

圖2 并行處理及模型

服務(wù)器端：

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

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

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

（4）等待客戶端返回結(jié)果。

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

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

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

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

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

客戶端：

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

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

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

種群個(gè)體適應(yīng)值計(jì)算。使用HFSS或CST計(jì)算客戶端分配任務(wù)的種群個(gè)體適應(yīng)值。

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

3.3 關(guān)鍵技術(shù)

（1）心跳檢測

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

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

表1 并行串行機(jī)器運(yùn)行時(shí)間對比s

（2）任務(wù)重分配與并行分布能力

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

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

4.3 并行演化算法運(yùn)行時(shí)間測試

4 測試與分析

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

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

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

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

4.2 參數(shù)設(shè)置

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

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

圖4給出了算法每代運(yùn)行時(shí)間的曲線圖。

圖4 不同機(jī)器數(shù)目下算法運(yùn)行時(shí)間

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

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

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

4.4 并行測試結(jié)果分析

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

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

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

5 結(jié)束語

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

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

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

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

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

[5]鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，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].上海：上海交通大學(xué)，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]陳國良.并行算法實(shí)踐[M].北京：高等教育出版社，2004.

[16]陳國良，孫廣中，徐云，等.并行算法研究方法學(xué)[J].計(jì)算機(jī)學(xué)報(bào)，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.

國家自然科學(xué)基金（No.61103145）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（No.CUG100314，No.CUG120409）。

劉小明，通訊作者，男，碩士研究生；李暉（1967—），女，教授，主要研究方向?yàn)橹悄苡?jì)算及智能信息處理；熊慕舟，男，碩士生導(dǎo)師。E-mail：asfion.lxm@gmail.com

2012-11-26

2013-01-15

1002-8331（2014）06-0200-05

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