基于改進型貪心算法的單板源源棒排列優(yōu)化

李 磊 李曉燕 蔣樹斌 伍曉利 李宗軍

（中國工程物理研究院 核物理與化學研究所 綿陽 621900）

基于改進型貪心算法的單板源源棒排列優(yōu)化

李 磊 李曉燕 蔣樹斌 伍曉利 李宗軍

（中國工程物理研究院 核物理與化學研究所 綿陽 621900）

對于單板鈷源而言，現(xiàn)有源棒排列優(yōu)化方法都針對輻射加工，難以滿足電子學器件耐輻照考核實驗對劑量場均勻性較高的要求。通過建立數(shù)學模型，對基于改進型貪心算法進行求解，實現(xiàn)了源棒排列優(yōu)化。算法采用貪心算法策略，以使參考輻照面劑量率不均勻度最小為約束條件來確定源棒位置；參考經(jīng)驗法來限制求解空間，利用枚舉法改善初始條件、放置順序對排源結果的影響，以增大算法的全局搜索能力。算例結果表明：針對耐輻照考核實驗，獲得了參考面劑量率不均勻度≤1.02條件下的源棒排列，滿足使用要求，排源效果優(yōu)于經(jīng)驗法，效率提高約100倍；針對輻射加工，排源效果、效率與已有基于貪心算法和模擬植物生長算法的優(yōu)化方法相當。本文排源方法既能用于耐輻照考核實驗又可適用于輻射加工。

單板鈷源，源棒優(yōu)化排列，貪心算法，輻照考核實驗

單板強鈷源γ輻射場劑量率高、均勻區(qū)大，除輻射加工外，還可用于電子學器件/系統(tǒng)耐總劑量輻照考核實驗。放射性源棒的排列方式?jīng)Q定了γ劑量場的分布，最佳源棒排列的判定標準通常以參考輻照面（距源架一定距離且平行于源架的平面）上的劑量率不均勻度（=最大值/最小值）為最小[1]。中小規(guī)模輻照裝置，可能的源棒排列情況多達約1045，獲得最佳源棒排列幾乎是不可能，實際中常采用適當?shù)姆椒▉慝@得不均勻度滿足一定要求的較優(yōu)排列，目前主要有人工經(jīng)驗和計算機自動優(yōu)化排源法。相比較，計算機自動排源法通用性高、源棒排列結果好，正逐步成為輻射加工領域優(yōu)化排源的重要方法，主要有兩種算法：(I) 基于貪心算法的優(yōu)化排源算法[2]，雷鵬等以參考面上劑量率的不均勻度最小為約束條件，提出下一根源棒的排列取決于使當前參考面上的最小和最大照射量率值在放置源棒后分別變?yōu)樽畲笾岛妥钚≈档姆椒?，按活度遞減的順序將源棒逐一排列在源架上，獲得一個較優(yōu)的源棒排列；(II) 基于模擬植物生長算法的優(yōu)化排源算法[3?4]，楊磊等將所有源棒隨機置于源架上后，以參考面上均勻布置的參考點群的劑量率值的相對標準誤差（或不均勻度）最小為約束條件，利用模擬植物生長算法尋找多個較優(yōu)源棒排列，排源效果較好、通用性強，并行優(yōu)化后已具備用于大型輻照裝置源棒排列的可行性。

耐輻照考核實驗對參考輻照面有較高的要求：(1) 劑量率均勻性足夠好，國軍標[5?6]規(guī)定電子學器件/系統(tǒng)輻照考核用劑量場的不均勻度≤1.10。由于輻照裝置附屬結構對輻射場的影響，不均勻度實測結果通常大于計算結果，因此應以較小的不均勻度來判定計算機排源方案是否滿足要求。經(jīng)驗結果表明，對單板輻照裝置，不均勻度計算值取1.02時，實測結果≤1.10；(2) 規(guī)格足夠大，以滿足大尺寸或批量樣品的輻照考核?，F(xiàn)有算法I和算法II都針對輻射加工應用，給出了不均勻度計算值分別為1.23[2]、1.27?1.31[4]條件下的源棒排列方案，前者全局搜索能力有限，難直接用于本文。后者雖有一定的通用性，但未開展本文應用，同時還需實現(xiàn)并行化的計算機排源過程，對計算機硬件也有特殊要求。

根據(jù)耐輻照考核實驗的需求，本文建立了單板鈷源源棒優(yōu)化排布模型，改進算法I，設計了基于改進型貪心算法的求解（排源）過程。針對抗輻照考核實驗和輻射加工應用，各給出了1個算例。

1 數(shù)學模型

1.1 輻照裝置與劑量率

單板輻照裝置結構如圖1所示，線狀源棒置于源架上，在參考面上形成目標輻射場。輻射場空間任意點(p)的吸收劑量率按式(1)?(3)計算得到[7]，為與常用重鉻酸銀劑量計測量結果對比，計算中劑量以水介質計：

式中，? (p)Air和?(p)Water分別為p點以空氣和水為介質的劑量率；K為p點空氣比釋動能率；i為源棒序號；E為γ能量；(μen/ρ)Air、(μen/ρ)Water分別為空氣和水的質量吸收系數(shù)；φi為i號源棒在p點的γ注量率；Ai為i號源棒的活度；θ是p點源棒端點所成線段的夾角；d是p點到源棒的距離；L為源棒長度；C為校準因子（=測量值/計算值），表征附屬結構（導源管、護源罩）對γ的散射和吸收過程，以及式(1)換算不同介質中劑量率誤差等因素的綜合影響。

圖1 單板源結構 (a) 源棒，(b) 源架，(c) 參考面Fig.1 Schematics of single-plate irradiation facility. (a) Source pencil, (b) Source plaque, (c) Reference plane

前期研究結果表明[7]，對于特定的裝置，C近似為常數(shù)(＜1)，說明利用式(1)?(3)計算空間任意點吸收劑量率是合適的。

1.2 目標函數(shù)及約束條件

坐標系如圖1所示，原點取在源架的中心。參考面與源架面平行，對寬、高方向分別進行M、N等分，其交點即是在參考面內均勻分布的參考點群，其中任一參考點的坐標為(xi, yi, zi)。源架上第m(或p)行、n(或q)號棒位中單位活度源棒在第i行、j列參考點產生的劑量率?mnij由式(1)?(3)計算得到。對?mnij與源棒活度Amn的乘積求和，即可得到參考點的劑量率?ij，將參考點群的劑量率寫為點陣形式，見式(4)。

文獻[2?4]所述排源過程，需頻繁調用計算機資源(CPU、內存)計算式(1)?(3)來求得參考點群的劑量率，式(4)所述方法的優(yōu)點在于：(1) 通過一次資源調用獲得全部源棒位對參考點群劑量率貢獻，再利用求和與求積的簡單運算即可求得參考點群的劑量率，獲得計算速度的大幅提升（與裝置規(guī)模、參考點數(shù)相關，算例I中提升約2 000倍），這使得計算機串行排源過程得以實現(xiàn)；(2) 將參考點的坐標值與劑量率貢獻的索引值相映射，使得參考面的形狀及大小不僅局限于上述參數(shù)限制，可按照實驗需要任意可調。目標函數(shù)取為參考點群劑量率不均勻度U，見式(5)。約束條件包括：源棒位置的取值范圍為全體棒位；單個棒位中最多可放置一根待排源棒；排源結束后，待排源棒都已放入棒位。

2 改進型貪心算法

2.1 貪心算法和源棒排布的特點

貪心算法[2]將源棒依活度大小按遞減排序，首先將第一根源棒置于源架邊角處，依據(jù)使參考面上最小劑量率取最大值和最大劑量率取最小值的原則，依次將單根源棒排列完畢。算法的全局搜索能力有限，僅能夠給出一種較優(yōu)化的排源結果，且不判斷結果是否滿足使用要求。

人工經(jīng)驗排源結果表明單板鈷源輻照裝置源棒排布具有以下特點：(1) 對稱棒位中放射源活度應盡量接近；(2) 高活度源棒聚集的區(qū)域距源架中心較遠（如靠近源架邊、角處），參考面規(guī)格隨該距離增大，同時參考面上的劑量率減小。因此，適當限制高活度源在源架上的位置可兼顧對參考面劑量率及其規(guī)格的要求。

2.2 改進型貪心算法

考慮單板鈷源源棒排布的特點，本文算法包括主要兩個過程：(1) 源棒分組后，逐組置入棒位，類似于人工經(jīng)驗排源法和算法I；(2) 利用枚舉法增加算法的全局搜索能力，改善放置順序和初始條件對結果的影響，提高排源質量，類似于算法II。算法主要內容如下：

(1) 源棒按照活度從大到小排列，將活度相近的源棒（相對偏差≤10%為宜）編為一批，排源過程中，同一批中的一組（2N根，N=1,2,…）源棒同時放入位置對稱的棒位中，這種設計能大幅縮減解空間狀態(tài)數(shù)；

(2) 按照活度由強到弱的順序逐組將源棒放入棒位中，參照貪心算法，確定一組源棒的位置，即利用枚舉法獲得一組待排源棒在所有可能排列條件下參考面點群劑量率不均勻度，以使不均勻度最小為約束條件來確定位置；

(3) 源棒全部置入源架后，為增加算法的全局搜索能力、改善源棒放置順序對排源結果的影響，利用貪心算法對源棒排列進行優(yōu)化：求得各組源棒對參考面劑量率不均勻度的貢獻（=全部源棒排列時的不均勻度與該組源棒時不均勻度的差值），按貢獻從小到大的順序，不斷將一組源棒放入其它空位或與其它源棒對調位置，直到獲得局部最優(yōu)解；

(4) 為增加算法的全局搜索能力、改善初始條件對排源結果的影響，采用枚舉法分別將不同活度源棒作為待放置的第一組源棒，并重復(2)和(3)。

計算流程圖見圖2，各標注號的功能如下：

(1) 輸入計算所需的初始數(shù)據(jù)，如棒位數(shù)及位置坐標，源棒數(shù)目、編號活度、規(guī)格，參考面和參考點群空間位置及規(guī)格等；

(2) 利用式(1)?(3)計算得到各棒位中單位活度源棒γ射線在參考點群上產生的劑量率；

(3) 按從大到小排序，將活度接近的源棒編為一批；

(4) 確定第一組待放置的源棒；

(5) 依據(jù)使參考點群劑量率不均勻度U最小的原則，確定第一組或下一組（2根或4根）源棒的位置，若棒位僅左右對稱，將一組（2根）源棒分別置入對稱棒位；若棒位上下、左右對稱，則對稱放置一組（4根）源棒，次高活度源棒置于最高活度源棒對角方向的棒位中，按順時針順序將剩余的兩根源棒放入棒位。全部源棒放置完成后，求得參考點群劑量率不均勻度U；

⑥ 調整源棒位置，求得各組源棒對劑量不均勻度的貢獻，按照貢獻從小到大的順序，將一組源棒置于其它空位或與其它組源棒對調位置，若某種源棒排布條件下參考點群劑量率不均勻度U1＜U，則保存源棒排布；

⑦ 重復⑥，直到通過調整源棒位置不能繼續(xù)減小U（即連續(xù)兩輪調整所得U相等，表明獲得局部最優(yōu)解）；

⑧ 重復④?⑦，利用枚舉法以不同活度源棒為第一組源棒進行新一輪排列，遍歷完成后，輸出U最小時的源棒排列，作為解。

圖2 排源流程Fig.2 Flow diagram of deployment of source pencils.

3 算例分析和討論

3.1 算例I

算例針對耐輻照考核應用，輻照裝置如圖1所示，裝源量8.4 PBq，50根源棒（活度見表1）分三層垂直排布在源架上，源棒的編號分別為S1?S50。源架寬160 cm、高210 cm，分上中下三層，層間距11 cm，每層60個棒位，棒位間隔3.5 cm，每層有左右兩區(qū)，區(qū)間距11 cm，棒位的編號分別為1?180。

表1 源棒編號及活度Table 1 Activity distribution of source bars.

經(jīng)驗結果表明，參考輻照面距離源架35 cm、規(guī)格約120 cm×80 cm。對參考面寬、高方向分別進行120、80等分。編寫MATLAB程序腳本實現(xiàn)計算機自動排源過程。硬件環(huán)境：CPU i5；內存 4G。軟件環(huán)境：Windows7，MATLAB 2010b。

表2是經(jīng)驗法和本文方法所得源棒的位置，圖3給出了參考輻照面上的劑量率分布情況。

表2 經(jīng)驗法和本文方法給出的排源方案Table 2 Source pencil deployment obtained by empirical method and this work.

由圖3和分析可知：(1) 經(jīng)驗法所得參考面劑量率不均勻度為1.022，本文方法為1.010，較經(jīng)驗法好。輻照站有10余年的運行經(jīng)驗，經(jīng)驗法結果已經(jīng)較好，本文方法的優(yōu)化效果不顯著；(2) 本文方法參考面的邊界更平整。表3給出了經(jīng)驗法和本文方法的耗時對比，由表3可知：(1) 本文方法能夠顯著降低排源耗時，效率提升約100倍；(2) 本文方法耗時主要用于計算單位活度源棒對各參考點劑量率的貢獻，耗時正比于參考點數(shù)量，可根據(jù)需要，通過稀疏等分參考面來減少參考點，提高效率。

上述算例結果表明本文方法排源結果滿足抗輻照考核實驗的需要，結果較經(jīng)驗法更優(yōu)，且能夠大幅度提高排源效率，節(jié)省人力耗費。

圖3 參考面(z=35 cm, o-xy)等劑量率線(不均勻度為1.02) (a) 經(jīng)驗法，(b) 本文方法Fig.3 Isodose curve of reference plane (uniformity is 1.02) obtained by empirical method (a) and this work (b).

表3 不同排源法的耗時對比Table 3 Time consumption of different methods.

3.2 算例II

現(xiàn)有排源算法都針對輻照加工應用，作為對比，表4給出了文獻[2,4]算例本文算法的源棒排布方案，結果表明本文方法參考輻照面劑量率不均勻度為1.21稍好于算法I (1.23[2])和算法II (1.27[4])。本文算法耗時(約20 s)稍多于算法II (14.5 s[4])，除算法自身的差異外，耗時差異還與計算機軟硬件配置有關，可通過使用運行效率更高的腳本和并行化提高本文算法的速度。

算例結果說明利用本文排源方法也適用于輻射加工應用，排源效果、排源耗時與現(xiàn)有算法I、II相當。

表4 對比算例排列結果Table 4 Source pencil deployment of simple for contrasting with other method.

4 結語

采用建立數(shù)學模型、設計基于改進型貪心算法求解的方法實現(xiàn)了單板鈷源源棒排列優(yōu)化。算例結果表明：針對耐輻照考核實驗，能夠獲得參考面劑量率不均勻度≤1.02條件下的源棒排列，滿足實驗要求，排源效率較經(jīng)驗法高；針對輻射加工應用，排源效果、排源效率與現(xiàn)有算法I（基于貪心算法）、II（基于模擬植物生長算法）相當。

優(yōu)化排源方法的特點在于：目標函數(shù)與約束條件相互獨立，使得算法對目標函數(shù)和約束條件的更換不敏感，可根據(jù)需求選定排源標準、調整參考面的形狀及大??；借鑒經(jīng)驗排源結果，大幅減小解空間的狀態(tài)數(shù)，提高排源效率；采用枚舉法來改進算法的全局搜索能力，該結構易于實現(xiàn)并行化，以滿足大型輻照裝置優(yōu)化排源工作的需求；算法結構簡單，易于實現(xiàn)。

現(xiàn)有的優(yōu)化排源方法都針對輻射加工，對劑量場不均勻度要求較高(≤1.02)的應用而言，也需要有一種穩(wěn)健、有效和快速的方法來替代人工經(jīng)驗排源，從計算結果來看，本文方法可以滿足這種需求，能夠節(jié)省人力物力。但貪心算法本身是局部搜索算法，文中的改進措施，尚不能完全彌補該缺陷，排源方法的適用性和可靠性還需細致討論和驗證，以期給出通用、高速的計算程序。源棒排列優(yōu)化可歸結為多極值組合優(yōu)化問題，若能建立適當?shù)臄?shù)學模型，可使用全局搜索能力較好的算法。

1 單賢芻, 關遲, 徐力平, 等. 強60Co源輻照裝置的最佳源棒排列設計及其輻射場的分布[J]. 原子能科學與技術, 1990, 24(5): 39?45

SHAN Xianchu, GUAN Chi, XU Liping, et al. Optimum designing of bars arrangement and distribution of radiation field for a strong60Co irradiator[J]. Atomic Energy Science and Technology, 1990, 24(5): 39?45

2 雷鵬, 祝清俊, 鄧鵬, 等. 輻照裝置源棒排列與參考面不均勻度的關系[J]．核農學報, 2007, 21(4): 387?389. DOI: 10.3969/j.issn.1000-8551.2007.04.016

LEI Peng, ZHU Qingjun, DENG Peng, et al. Relation of source pencil arrangement and uniformity of standard plane at irradiation facility[J]. Journal of Nuclear Agricultural Science, 2007, 21(4): 387?389. DOI: 10.3969/j.issn.1000-8551.2007.04.016

3 楊磊, 劉義保, 劉玉娟. 基于模擬植物生長算法的鈷源源棒的排列優(yōu)化[J]. 核技術, 2009, 32(12): 915?921

YANG Lei, LIU Yibao, LIU Yujuan. Optimization of source pencil deployment based on plant growth simulation algorithm[J]. Nuclear Techniques, 2009, 32(12): 915?921

4 楊磊, 王玲, 龔學余. 基于CUDA的大型γ輻照裝置通用并行排源算法[J]. 原子能科學與技術, 2013, 47(2): 303?311. DOI: 10.7538/yzk.2013.47.02.0303

YANG Lei, WANG Ling, GONG Xueyu. General-purpose parallel algorithm based on CUDA for source pencils’deployment of large γ irradiator[J]. Atomic Energy Science and Technology, 2013, 47(2): 303?311. DOI: 10.7538/yzk.2013.47.02.0303

5 GJB 548B-2005, 微電子器件試驗方法和程序[S] GJB 548B-2005, Test methods and procedures for microelectronic device[S]

6 GJB 5422-2005, 軍用電子元器件γ射線累積劑量效應測量方法[S]

GJB 5422-2005, Testing method of military electronic devices for γ-ray total dose radiation[S]

7 曾凡松, 伍曉利, 李曉燕, 等.60Co單板源劑量場分布經(jīng)驗計算公式的建立[J]. 輻射研究與輻射工藝學報, 2012, 30(4): 198?201

ZENG Fansong, WU Xiaoli, LI Xiaoyan, et al. The construction of empirical formula to calculate the dose field distribution of the single-plate60Co source[J]. Journal of Radiation Research and Radiation Processing, 2012, 30(4): 198?201

CLC TL929, TB114.1

Optimization of source pencil deployment of single-plate irradiation facility based on improved greedy algorithm

LI Lei LI Xiaoyan JIANG Shubin WU XiaoLi LI Zongjun
(Institute of Nuclear Physics and Chemistry, Chinese Academy of Engineering Physics, Mianyang 621900, China)

Background: Concerning radiation hardness assurance testing of microelectronic devices, there is rigorous requirement for the dose rate uniformity of irradiation field. With existing methods, the source rods of single-plate irradiation facility cannot be configured properly in the source plaque, which consequently form the prospected irradiation field. Purpose: This study aims to construct a new method to realize the optimal deployment of source rods and meet the requirements of radiation hardness assurance testing. Methods: The new method was realized by constructing mathematical model and designing improved greedy algorithm. The algorithm mainly contained three aspects. First of all, there was the thought of existing greedy algorithm, which is to determine position of source rods with the objective function defined by uniformity of dose rate at the reference points. In addition, the position of source rods was constricted according to empirical method. Finally, the global searching ability was improved by using enumeration technique. Results: For radiation hardness assurance testing, this method was able to construct irradiation field with dose rate uniformity no more than 1.02, and it was better and 100 times faster than the empirical method. As for irradiation process, the dose rate uniformity and efficiency obtained by this new method is similar to the existing methods such as greedy algorithm and plant growth simulation algorithm. Conclusion: This new method is effective for both the radiation hardness assurance testing and the irradiation process applications.

Single-rack cobalt source, Optimization of source pencil deployment, Greedy algorithm, Radiation hardness assurance testing

TL929，TB114.1

10.11889/j.0253-3219.2015.hjs.38.100204

委員會—中國工程物理研究院NSAF聯(lián)合基金(No.U1530129)資助

李磊，男，1986年出生，2011年于四川大學獲理學碩士學位，助理研究員，從事耐輻射加固及輻照工藝研究，E-mail: skyhappier@163.com

2015-05-29，

2015-07-28