森林競(jìng)爭(zhēng)算法的并行化及其在線天線自動(dòng)設(shè)計(jì)中的應(yīng)用郭改文

1、森林競(jìng)爭(zhēng)算法的并行化及其在線天線自動(dòng)設(shè)計(jì)中的應(yīng)用 郭改文      摘 要:針對(duì)線天線自動(dòng)設(shè)計(jì)中運(yùn)算時(shí)間過(guò)長(zhǎng)問(wèn)題,提出了一種基于主從模型的并行森林競(jìng)爭(zhēng)算法優(yōu)化模型.主進(jìn)程執(zhí)行森林動(dòng)態(tài)演化的競(jìng)爭(zhēng)模型, 從進(jìn)程并行地執(zhí)行自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)模型并調(diào)用天線數(shù)值計(jì)算程序完成費(fèi)時(shí)的陽(yáng)光適應(yīng)度計(jì)算. 利用該算法設(shè)計(jì)出了一種端射高增益新型樹(shù)結(jié)構(gòu)線天線. 其具有 5 個(gè)枝條, 增益達(dá)到 9. 048 dBi,帶寬為 8. 45%,

2、0;在 元謀 Beowulf 集群 10個(gè)節(jié)點(diǎn)的并行效率達(dá)到了 91%, 從而驗(yàn)證了該算法的合理性和有效性.關(guān)鍵詞:優(yōu)化; 森林競(jìng)爭(zhēng)算法;并行; 天線自動(dòng)設(shè)計(jì); 樹(shù)形線天線中圖分類號(hào):TP202. 7; TP15 文獻(xiàn)標(biāo)志碼: A自上世紀(jì) 80 年代以來(lái), 仿生優(yōu)化算法因克服了傳統(tǒng)的解析優(yōu)化算法對(duì)初始點(diǎn)的選取和目標(biāo)函數(shù)要求過(guò)高的缺點(diǎn)而得到了蓬勃的發(fā)展. 在眾多仿生優(yōu)化算法中主要有以遺傳算法 1為代表的模擬生物進(jìn)化算法

3、和以粒子群優(yōu)化算法 2為代表的群智能優(yōu)化算法, 但它們大都存在著局部搜索能力差、早熟收斂等缺點(diǎn). 鑒于現(xiàn)有優(yōu)化算法的不足, 文獻(xiàn) 3 利用自然樹(shù)生長(zhǎng)、凋落矛盾統(tǒng)一的原理提出自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)算法( TreeGr owth Compet it ion Algorithm, 簡(jiǎn)稱 T GCA) . 該算法的主要特點(diǎn)為搜索方式從簡(jiǎn)單到復(fù)雜、收斂速度快、占用內(nèi)存小等, 已經(jīng)成功運(yùn)用于曲線擬合、超越方程求解 4、天線自動(dòng)

4、設(shè)計(jì)等領(lǐng)域 5.天線是無(wú)線電通訊中的主要組成部分, 天線自動(dòng)設(shè)計(jì)不但節(jié)省設(shè)計(jì)者大量的時(shí)間和精力, 同時(shí)擴(kuò)寬天線設(shè)計(jì)范圍, 提高了設(shè)計(jì)精度, 成為現(xiàn)代天線研究的一個(gè)新熱點(diǎn) 6. 線天線作為一種基本、有效、應(yīng)用廣泛的天線形式, 仍然有著新的技術(shù)要求. 特別是高功率微波系統(tǒng)的輻射天線, 不但要求天線有端射、高增益和高功率容量等性能, 而且要求天線具有低旁瓣和高前后比特性. 文獻(xiàn)7 將 TGCA 應(yīng)用于天線的自動(dòng)設(shè)計(jì), 設(shè)計(jì)出了相同尺寸下比傳統(tǒng)

5、單極子天線高 2 dBi 的新型線天線. 但是在天線優(yōu)化設(shè)計(jì)過(guò)程中, 為找到理想的輸出結(jié)果, 需要多次調(diào)用電磁場(chǎng)數(shù)值計(jì)算程序來(lái)仿真天線的輻射性能. 由于天線結(jié)構(gòu)本身很復(fù)雜, 仿真一次需要很長(zhǎng)時(shí)間, 整個(gè)過(guò)程運(yùn)算時(shí)間不可接受. 為此, 本文首先對(duì) TGCA 進(jìn)行改進(jìn), 改進(jìn)后的算法稱之為森林競(jìng)爭(zhēng)算法, 然后對(duì)其進(jìn)行并行處理, 并將其應(yīng)用于樹(shù)形線天線的自動(dòng)設(shè)計(jì).1 森林競(jìng)爭(zhēng)算法的基本原理森林競(jìng)爭(zhēng)算法的基本思想是: 自然樹(shù)

6、生長(zhǎng)的動(dòng)力來(lái)源于獲得充足的陽(yáng)光進(jìn)行光合作用, 樹(shù)木內(nèi)部的枝條向光競(jìng)爭(zhēng)地生長(zhǎng), 稱為局部競(jìng)爭(zhēng);同時(shí), 樹(shù)與樹(shù)之間進(jìn)行生存資源的爭(zhēng)奪, 也稱為全局競(jìng)爭(zhēng). 局部競(jìng)爭(zhēng)由自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)模型實(shí)現(xiàn), 全局競(jìng)爭(zhēng)由森林動(dòng)態(tài)演化競(jìng)爭(zhēng)模型實(shí)現(xiàn).樹(shù)的生長(zhǎng)過(guò)程非常復(fù)雜, 本文僅考慮枝條的生長(zhǎng)和凋落. 自然樹(shù)生長(zhǎng)的競(jìng)爭(zhēng)模型可描述為:種子從發(fā)芽開(kāi)始, 生長(zhǎng)主干、產(chǎn)生分枝、向光競(jìng)爭(zhēng)的生長(zhǎng)、有條件的凋落, 到再產(chǎn)生分枝、再向光競(jìng)爭(zhēng)的生長(zhǎng)、 、反復(fù)迭代, 直至生長(zhǎng)年數(shù)或陽(yáng)光適應(yīng)度達(dá)到事先設(shè)定的閾值. 

7、在樹(shù)的生長(zhǎng)過(guò)程中樹(shù)枝的生長(zhǎng)與凋落由陽(yáng)光適應(yīng)度、5 結(jié) 論本文提出了森林競(jìng)爭(zhēng)算法并對(duì)其并行化設(shè)計(jì), 然后將其應(yīng)用于天線的自動(dòng)設(shè)計(jì). 設(shè)計(jì)出了增益9. 048 dB, 帶寬 8. 45% , 具有 5 個(gè)枝條的端射樹(shù)形線天線, 在 元謀 Beowulf 集群中的 10 個(gè)節(jié)點(diǎn)上的并行效率達(dá)到了 91% , 從而驗(yàn)證了算法的有效性.參 考 文 獻(xiàn)

8、0;1 H olland J H. Adaptat ion in n at ure and art ificial syst em  M  . Ann Arbor: The U niver sit y of Mi chigan Press, 1975. 2 Kenned

9、y J , Eb erhart R C. Parti cle swarm opt imizati on  C . T he IEEE Int ern at ional Con feren ce on Neural Net works , Pis cataway, 199

10、5. 3 Guo G W, H uang K M. C om pet it ion algorit hm of sim ulati ng nat ural t ree growt h an d it s appl icat ion in curve 

11、fit t ing J  . Journal of Com-put at ional and Th eoret ical Nanoscience, 2007, 4( 7/ 8) : 1301- 1304. 4 郭改文, 黃卡瑪. 森林競(jìng)爭(zhēng)算法及在超越方程求解中的應(yīng)用 J . 四川大學(xué)學(xué)報(bào): 工程版,

12、 2008, 40( 6) : 127- 132. 5 陳 星, 黃卡瑪, 趙 翔. NEC 和非堵塞式主從并行遺傳算法應(yīng)用于天線自動(dòng)設(shè)計(jì)的研究 J . 電子學(xué)報(bào), 2004, 32(8) : 1380- 1392. 6 Lu B, Zhang J J, H uan g K

13、60;M. C om pet it ive algorit hm of simulat ing nat ural t ree growt h and it s ap pl icati on in ant enn a d esign J  . Progr ess

14、in El ect romagneti cs Research L et t ers, 2009, 12: 41- 48. 7 郭改文. 自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)算法及其在樹(shù)形線天線自動(dòng)設(shè)計(jì)中的應(yīng)用研究 D . 成都: 四川大學(xué), 2008. 8 張金屯. 數(shù)量生態(tài)學(xué) M . 北京: 科學(xué)出版社, 2006. 

15、;9 都志輝. 高性能計(jì)算并行編程技術(shù) M PI 并行程序設(shè)計(jì) M . 北京: 清華大學(xué)出版社, 2001: 99- 124.( 下轉(zhuǎn)第 頁(yè))第 2 期 郭改文等: 森林競(jìng)爭(zhēng)算法的并行化及其在線天線自動(dòng)設(shè)計(jì)中的應(yīng)用1511704. 1. 2 采用同軸線饋電方式 同軸線的特性阻抗為 50, 具體要求如下: 內(nèi)導(dǎo)體半徑為 1. 55

16、 mm, 外導(dǎo)體半徑為 6 mm, 內(nèi)外導(dǎo)體之間填充介質(zhì)材料. 因此, 樹(shù)形線天線的枝條半徑也為 1. 55 mm. 同軸外導(dǎo)體接半徑為 61 mm的金屬反射板.4. 1. 3 天線輻射模式為端射 具有盡可能大的增益和帶寬, 且最多有 5 根枝條.利用上述的線天線自動(dòng)設(shè)計(jì)軟件包設(shè)計(jì)該天線, 定義陽(yáng)光適應(yīng)度如下:= exp( - | 1- 

17、( . ( 90- Angle) . . Gain+. S11widt h) | ) , ( 3)其中, Gain 為天線增益, Angle 為最大輻射方向偏離主干的角度( 簡(jiǎn)稱為偏離角), S11widt h 為天線的絕對(duì)帶寬, 為偏離角加權(quán)因子, 為增益加權(quán)因子, 為帶寬加權(quán)因子. 加權(quán)因子的取值反映了設(shè)計(jì)者對(duì)不同設(shè)計(jì)目標(biāo)的側(cè)重,&#

18、160;具體取值大小根據(jù)設(shè)計(jì)要求和經(jīng)驗(yàn). 本文中 = 0. 65, = 0. 1, = 0. 35.4. 2 設(shè)計(jì)結(jié)果表 1 自動(dòng)設(shè)計(jì)的樹(shù)形線天線的枝條坐標(biāo)編號(hào) 起點(diǎn)坐標(biāo)(x, y, z) 終點(diǎn)坐標(biāo)(x, y, z)1 ( 0. 00, 0. 00, 0. 00) ( 0. 00, 0.&

19、#160;00, 17. 26)2 ( 0. 00, 0. 00, 2. 62) ( - 2. 03, - 4. 51, 16. 39)3 ( 0. 00, 0. 00, 12. 37) ( - 1. 36, 9. 68, 45. 69)4 ( -&

20、#160;1. 22, - 2. 71, 10. 89) ( - 2. 29, 28. 79, 9. 94)5 ( 0. 00, 0. 00, 6. 24) ( - 15. 20, - 18. 85, 13. 86)該系統(tǒng)在 元謀 Beowulf 集群系統(tǒng)使用 

21、;10個(gè)節(jié)點(diǎn)進(jìn)行天線自動(dòng)設(shè)計(jì), 運(yùn)行 13 小時(shí)輸出了端射高增益樹(shù)形線天線設(shè)計(jì)結(jié)果:增益 Gain= 9. 048dBi, 絕對(duì)帶寬 210 MH z, 相對(duì)帶寬為. 該天線的樹(shù)形輻射單元有 5 個(gè)枝條, 其坐標(biāo)如表 1 所示. 最優(yōu)化樹(shù)形線天線的仿真結(jié)構(gòu)如圖 3 所示. 天線的反射系數(shù)在 1. 5 2. 8 GHz 內(nèi)隨頻率的

22、變化曲線如圖 4所示, 高增益樹(shù)形線天線在 2. 45 GHz 端射模式的二維方向圖如圖 5所示. 輻射模式展示了天線典型的端射模式.4. 3 并行計(jì)算結(jié)果的討論本文的并行森林競(jìng)爭(zhēng)算法在 元謀 Beowulf集群中的 10 個(gè)節(jié)點(diǎn)上運(yùn)行總時(shí)間為 13 h, 在一個(gè)節(jié)點(diǎn)上的運(yùn)行時(shí)間為 118. 5 h, 并行效率達(dá)到了 91% , 從而驗(yàn)證了本文并行森林競(jìng)爭(zhēng)算

23、法的有效性.為了進(jìn)一步驗(yàn)證本文算法的有效性, 用并行標(biāo)準(zhǔn)遺傳算法 GA 作優(yōu)化算法設(shè)計(jì)樹(shù)形線天線, 結(jié)果花費(fèi)了 倍于上述優(yōu)化結(jié)果的時(shí)間, 但最終沒(méi)有找到符合端射要求的樹(shù)形線天線 這說(shuō)明并行森林競(jìng)爭(zhēng)算法是合理的和有效的 分析其主要原因 本文利用并行森林競(jìng)爭(zhēng)算法優(yōu)化樹(shù)形線天線的結(jié)構(gòu), 種群中的個(gè)體從簡(jiǎn)單到復(fù)雜, 收斂速度快;同時(shí), 引入森林動(dòng)態(tài)競(jìng)爭(zhēng)因子, 使種群動(dòng)態(tài)更新, 群體更具普遍性和廣泛性150 河南師范大學(xué)學(xué)報(bào)( 自然科學(xué)版)

24、60;2011 年10 . :.營(yíng)養(yǎng)因子、遮擋因子共同決定.在自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)的過(guò)程中, 如果考慮環(huán)境競(jìng)爭(zhēng)因子引起種群規(guī)模的變化, 從而引起種群動(dòng)態(tài)的更新,則森林動(dòng)態(tài)演化的競(jìng)爭(zhēng)模型可以描述如下:設(shè)森林只有一個(gè)種群, 其最大進(jìn)化代數(shù)為 Gmax, 將最大進(jìn)化代數(shù)分成 H 個(gè) M 代, 即 Gmax= H*M, 則種群里的個(gè)體每經(jīng)過(guò) M 代的向光競(jìng)爭(zhēng)生長(zhǎng), 就通過(guò)種群增長(zhǎng)與環(huán)境間的動(dòng)力學(xué)特征方程 8N&

25、#160;= r NK- NK( 1)計(jì)算種群的變化量 N. 其中, K 為環(huán)境負(fù)荷量;N 為種群的大小;r 為種群的增長(zhǎng)率. 然后由( 2)式調(diào)整種群的規(guī)模:NM+ 1= NM+ N , ( 2)其中, NM為M 代內(nèi)的種群的個(gè)體數(shù)量. 當(dāng) N> 0 時(shí), 產(chǎn)生 N 個(gè)種子, 以增大種群的規(guī)模; 當(dāng)&

26、#160;N< 0時(shí), 刪除適應(yīng)度最小的 N 棵樹(shù), 以減少種群的規(guī)模.2 森林競(jìng)爭(zhēng)算法的并行設(shè)計(jì)本文將森林競(jìng)爭(zhēng)算法的并行運(yùn)算設(shè)計(jì)為主從控制模型. 其基本思想是在并行系統(tǒng)的一個(gè)處理器上執(zhí)行主進(jìn)程, 其它處理器上執(zhí)行從進(jìn)程. 主進(jìn)程的種群里保存了當(dāng)前最佳陽(yáng)光適應(yīng)度的個(gè)樹(shù)體. 主進(jìn)程執(zhí)行森林動(dòng)態(tài)演化的競(jìng)爭(zhēng)模型, 并控制和協(xié)調(diào)整個(gè)并行計(jì)算過(guò)程. 從進(jìn)程并行地執(zhí)行自然樹(shù)生長(zhǎng)競(jìng)爭(zhēng)模型生成樹(shù)體結(jié)構(gòu), 完成費(fèi)時(shí)的 陽(yáng)光適應(yīng)度計(jì)算 , 并以

27、60;M 個(gè)年代間隔與主進(jìn)程進(jìn)行通信. 而主進(jìn)程參與通信的時(shí)間間隔是不固定的, 它必須經(jīng)常地檢測(cè)是否有某個(gè)從進(jìn)程要與它通信, 一旦有, 則開(kāi)始通信, 然后再做其它工作.該方案采用了 MPI 消息函數(shù) 9實(shí)現(xiàn)主從進(jìn)程間的通信. 對(duì)自動(dòng)設(shè)計(jì)的天線, 由于尺寸的差異, 天線數(shù)值計(jì)算耗時(shí)難以準(zhǔn)確預(yù)計(jì). 由于天線數(shù)值計(jì)算的耗時(shí)正比于天線尺寸, 為了實(shí)現(xiàn)計(jì)算任務(wù)的平衡分配, 該方案按天線尺寸從大到小 快速排序 , 從而使大計(jì)算量

28、的任務(wù)優(yōu)先分配且最大限度地讓從進(jìn)程滿負(fù)荷工作. 設(shè)為樹(shù)體當(dāng)前的陽(yáng)光適應(yīng)度, E 為最佳陽(yáng)光適應(yīng)度, 則從進(jìn)程流程如圖 1所示, 主進(jìn)程流程如圖 2所示.3 樹(shù)形線天線自動(dòng)設(shè)計(jì)的基本原理樹(shù)形線天線自動(dòng)設(shè)計(jì)的基本原理是將樹(shù)形線天線的設(shè)計(jì)轉(zhuǎn)化為森林競(jìng)爭(zhēng)算法搜索尋優(yōu)過(guò)程, 即, 轉(zhuǎn)化為一個(gè)目標(biāo)函數(shù)及其約束變量, 然后將其定義為一個(gè)陽(yáng)光適應(yīng)度函數(shù). 用陽(yáng)光適應(yīng)度函數(shù)值的大小來(lái)定量樹(shù)形線天線性能的優(yōu)劣, 并引導(dǎo)樹(shù)形線天線向陽(yáng)光適應(yīng)度增大的方向生長(zhǎng).將上述并行化的森林競(jìng)爭(zhēng)算法用來(lái)

29、設(shè)計(jì)樹(shù)形線天線, 開(kāi)發(fā)樹(shù)形線天線自動(dòng)設(shè)計(jì)軟件包. 本文主從進(jìn)程使用C+ + 作為編程語(yǔ)言, Visual St udio2005 作為編譯環(huán)境.從進(jìn)程中的天線建模由 Visual basic6. 0 編程實(shí)現(xiàn), 并調(diào)用天線的數(shù)值計(jì)算程序仿真天線的輻射性能. 本文的天線數(shù)值計(jì)算方法采用時(shí)域有限差分法 FDTD.4 樹(shù)形線天線自動(dòng)設(shè)計(jì)的應(yīng)用舉例為驗(yàn)證并行算法的正確性和有效性, 利用這個(gè)系統(tǒng),設(shè)計(jì)一種端射、高增益、寬帶新型樹(shù)形線天線

30、, 并在相同的硬件平臺(tái)上與串行算法進(jìn)行比較, 得出并行效率樹(shù)形線天線的具體設(shè)計(jì)要求天線的中心工作頻率為 5 G z 因此, 波長(zhǎng)= , 樹(shù)最大高度= 6 , 樹(shù)最大半徑= 3 5第 2 期 郭改文等: 森林競(jìng)爭(zhēng)算法的并行化及其在線天線自動(dòng)設(shè)計(jì)中的應(yīng)用149.4. 14. 1. 1 2. 4 H 122 mm 1 mm&

31、#160;0. mm.于是人類便把一切都交給了科學(xué), 包括人的主觀性和能動(dòng)性. 科學(xué)主義放棄了對(duì)科學(xué)的自省, 致使人類只知向外用力, 卻遭到自然的無(wú)情報(bào)復(fù);而向內(nèi)溯求的不足, 又導(dǎo)致了人類對(duì)自身文化主體地位的喪失. 基因芯片選材技術(shù)研究反映在體育領(lǐng)域的正是人類物質(zhì)文化的過(guò)度追求和精神文化的嚴(yán)重缺失. 基因芯片選材技術(shù)的征服性不僅在于其改變了競(jìng)技體育的內(nèi)容和形式, 更在于其剝奪了人對(duì)體育精神文化的追求, 并將人處于科技的統(tǒng)治之下. 科學(xué)主義只有放棄征服一切的野心, 轉(zhuǎn)而內(nèi)心自我

32、的反思, 認(rèn)識(shí)人類對(duì)體育精神的內(nèi)在需求, 將自由與快樂(lè)還贈(zèng)予體育, 科學(xué)的人文精神便得以展現(xiàn).參 考 文 獻(xiàn) 1 許之屏. 基因芯片技術(shù)及其在運(yùn)動(dòng)員科學(xué)選材研究中的應(yīng)用和展望 J . 北京體育大學(xué)學(xué)報(bào), 2004, 27( 6) : 781- 787. 2 桂起權(quán), 傅 靜, 任曉明. 生物科學(xué)的哲學(xué) M . 成都: 

33、四川教育出版社, 2003: 98- 99. 3 李 斌, 毛 磊. 你還是你嗎? 人類基因組報(bào)告 M  . 北京: 新華出版社, 2000: 160. 4 申建勇, 傅 靜. 現(xiàn)代生物技術(shù)的發(fā)展對(duì)競(jìng)技體育帶來(lái)的倫理道德問(wèn)題研究 J . 河南師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2000, 28( 4) :

34、 97- 101. 5 E 舒爾曼. 科技時(shí)代與人類未來(lái) M . 李小兵, 謝京生, 張峰譯. 北京: 東方出版社, 1996: 320. 6 孟建偉. 創(chuàng)新文化與科學(xué)觀的轉(zhuǎn)變 J . 中國(guó)人民大學(xué)學(xué)報(bào), 2005( 4): 17- 23. 7 申建勇. 基因芯片技術(shù)應(yīng)用于運(yùn)動(dòng)員選材的倫理思考 J  . 北京體育大學(xué)學(xué)報(bào), 2010, 33( 5) : 66- 68.Scientism of Genetic Chip Technology in Athlete SelectionSH EN