基于改进型贪心算法的单板源源棒排列优化

李 磊 李晓燕 蒋树斌 伍晓利 李宗军

（中国工程物理研究院 核物理与化学研究所 绵阳 621900）

基于改进型贪心算法的单板源源棒排列优化

李 磊 李晓燕 蒋树斌 伍晓利 李宗军

（中国工程物理研究院 核物理与化学研究所 绵阳 621900）

对于单板钴源而言，现有源棒排列优化方法都针对辐射加工，难以满足电子学器件耐辐照考核实验对剂量场均匀性较高的要求。通过建立数学模型，对基于改进型贪心算法进行求解，实现了源棒排列优化。算法采用贪心算法策略，以使参考辐照面剂量率不均匀度最小为约束条件来确定源棒位置；参考经验法来限制求解空间，利用枚举法改善初始条件、放置顺序对排源结果的影响，以增大算法的全局搜索能力。算例结果表明：针对耐辐照考核实验，获得了参考面剂量率不均匀度≤1.02条件下的源棒排列，满足使用要求，排源效果优于经验法，效率提高约100倍；针对辐射加工，排源效果、效率与已有基于贪心算法和模拟植物生长算法的优化方法相当。本文排源方法既能用于耐辐照考核实验又可适用于辐射加工。

单板钴源，源棒优化排列，贪心算法，辐照考核实验

单板强钴源γ辐射场剂量率高、均匀区大，除辐射加工外，还可用于电子学器件/系统耐总剂量辐照考核实验。放射性源棒的排列方式决定了γ剂量场的分布，最佳源棒排列的判定标准通常以参考辐照面（距源架一定距离且平行于源架的平面）上的剂量率不均匀度（=最大值/最小值）为最小[1]。中小规模辐照装置，可能的源棒排列情况多达约1045，获得最佳源棒排列几乎是不可能，实际中常采用适当的方法来获得不均匀度满足一定要求的较优排列，目前主要有人工经验和计算机自动优化排源法。相比较，计算机自动排源法通用性高、源棒排列结果好，正逐步成为辐射加工领域优化排源的重要方法，主要有两种算法：(I) 基于贪心算法的优化排源算法[2]，雷鹏等以参考面上剂量率的不均匀度最小为约束条件，提出下一根源棒的排列取决于使当前参考面上的最小和最大照射量率值在放置源棒后分别变为最大值和最小值的方法，按活度递减的顺序将源棒逐一排列在源架上，获得一个较优的源棒排列；(II) 基于模拟植物生长算法的优化排源算法[3−4]，杨磊等将所有源棒随机置于源架上后，以参考面上均匀布置的参考点群的剂量率值的相对标准误差（或不均匀度）最小为约束条件，利用模拟植物生长算法寻找多个较优源棒排列，排源效果较好、通用性强，并行优化后已具备用于大型辐照装置源棒排列的可行性。

耐辐照考核实验对参考辐照面有较高的要求：(1) 剂量率均匀性足够好，国军标[5−6]规定电子学器件/系统辐照考核用剂量场的不均匀度≤1.10。由于辐照装置附属结构对辐射场的影响，不均匀度实测结果通常大于计算结果，因此应以较小的不均匀度来判定计算机排源方案是否满足要求。经验结果表明，对单板辐照装置，不均匀度计算值取1.02时，实测结果≤1.10；(2) 规格足够大，以满足大尺寸或批量样品的辐照考核。现有算法I和算法II都针对辐射加工应用，给出了不均匀度计算值分别为1.23[2]、1.27−1.31[4]条件下的源棒排列方案，前者全局搜索能力有限，难直接用于本文。后者虽有一定的通用性，但未开展本文应用，同时还需实现并行化的计算机排源过程，对计算机硬件也有特殊要求。

根据耐辐照考核实验的需求，本文建立了单板钴源源棒优化排布模型，改进算法I，设计了基于改进型贪心算法的求解（排源）过程。针对抗辐照考核实验和辐射加工应用，各给出了1个算例。

1 数学模型

1.1 辐照装置与剂量率

单板辐照装置结构如图1所示，线状源棒置于源架上，在参考面上形成目标辐射场。辐射场空间任意点(p)的吸收剂量率按式(1)−(3)计算得到[7]，为与常用重铬酸银剂量计测量结果对比，计算中剂量以水介质计：

式中，Ḋ (p)Air和Ḋ(p)Water分别为p点以空气和水为介质的剂量率；K为p点空气比释动能率；i为源棒序号；E为γ能量；(μen/ρ)Air、(μen/ρ)Water分别为空气和水的质量吸收系数；φ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近似为常数(＜1)，说明利用式(1)−(3)计算空间任意点吸收剂量率是合适的。

1.2 目标函数及约束条件

坐标系如图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)所述方法的优点在于：(1) 通过一次资源调用获得全部源棒位对参考点群剂量率贡献，再利用求和与求积的简单运算即可求得参考点群的剂量率，获得计算速度的大幅提升（与装置规模、参考点数相关，算例I中提升约2 000倍），这使得计算机串行排源过程得以实现；(2) 将参考点的坐标值与剂量率贡献的索引值相映射，使得参考面的形状及大小不仅局限于上述参数限制，可按照实验需要任意可调。目标函数取为参考点群剂量率不均匀度U，见式(5)。约束条件包括：源棒位置的取值范围为全体棒位；单个棒位中最多可放置一根待排源棒；排源结束后，待排源棒都已放入棒位。

2 改进型贪心算法

2.1 贪心算法和源棒排布的特点

贪心算法[2]将源棒依活度大小按递减排序，首先将第一根源棒置于源架边角处，依据使参考面上最小剂量率取最大值和最大剂量率取最小值的原则，依次将单根源棒排列完毕。算法的全局搜索能力有限，仅能够给出一种较优化的排源结果，且不判断结果是否满足使用要求。

人工经验排源结果表明单板钴源辐照装置源棒排布具有以下特点：(1) 对称棒位中放射源活度应尽量接近；(2) 高活度源棒聚集的区域距源架中心较远（如靠近源架边、角处），参考面规格随该距离增大，同时参考面上的剂量率减小。因此，适当限制高活度源在源架上的位置可兼顾对参考面剂量率及其规格的要求。

2.2 改进型贪心算法

考虑单板钴源源棒排布的特点，本文算法包括主要两个过程：(1) 源棒分组后，逐组置入棒位，类似于人工经验排源法和算法I；(2) 利用枚举法增加算法的全局搜索能力，改善放置顺序和初始条件对结果的影响，提高排源质量，类似于算法II。算法主要内容如下：

(1) 源棒按照活度从大到小排列，将活度相近的源棒（相对偏差≤10%为宜）编为一批，排源过程中，同一批中的一组（2N根，N=1,2,…）源棒同时放入位置对称的棒位中，这种设计能大幅缩减解空间状态数；

(2) 按照活度由强到弱的顺序逐组将源棒放入棒位中，参照贪心算法，确定一组源棒的位置，即利用枚举法获得一组待排源棒在所有可能排列条件下参考面点群剂量率不均匀度，以使不均匀度最小为约束条件来确定位置；

(3) 源棒全部置入源架后，为增加算法的全局搜索能力、改善源棒放置顺序对排源结果的影响，利用贪心算法对源棒排列进行优化：求得各组源棒对参考面剂量率不均匀度的贡献（=全部源棒排列时的不均匀度与该组源棒时不均匀度的差值），按贡献从小到大的顺序，不断将一组源棒放入其它空位或与其它源棒对调位置，直到获得局部最优解；

(4) 为增加算法的全局搜索能力、改善初始条件对排源结果的影响，采用枚举法分别将不同活度源棒作为待放置的第一组源棒，并重复(2)和(3)。

计算流程图见图2，各标注号的功能如下：

(1) 输入计算所需的初始数据，如棒位数及位置坐标，源棒数目、编号活度、规格，参考面和参考点群空间位置及规格等；

(2) 利用式(1)−(3)计算得到各棒位中单位活度源棒γ射线在参考点群上产生的剂量率；

(3) 按从大到小排序，将活度接近的源棒编为一批；

(4) 确定第一组待放置的源棒；

(5) 依据使参考点群剂量率不均匀度U最小的原则，确定第一组或下一组（2根或4根）源棒的位置，若棒位仅左右对称，将一组（2根）源棒分别置入对称棒位；若棒位上下、左右对称，则对称放置一组（4根）源棒，次高活度源棒置于最高活度源棒对角方向的棒位中，按顺时针顺序将剩余的两根源棒放入棒位。全部源棒放置完成后，求得参考点群剂量率不均匀度U；

⑥ 调整源棒位置，求得各组源棒对剂量不均匀度的贡献，按照贡献从小到大的顺序，将一组源棒置于其它空位或与其它组源棒对调位置，若某种源棒排布条件下参考点群剂量率不均匀度U1＜U，则保存源棒排布；

⑦ 重复⑥，直到通过调整源棒位置不能继续减小U（即连续两轮调整所得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，每层有左右两区，区间距11 cm，棒位的编号分别为1−180。

表1 源棒编号及活度Table 1 Activity distribution of source bars.

经验结果表明，参考辐照面距离源架35 cm、规格约120 cm×80 cm。对参考面宽、高方向分别进行120、80等分。编写MATLAB程序脚本实现计算机自动排源过程。硬件环境：CPU i5；内存 4G。软件环境：Windows7，MATLAB 2010b。

表2是经验法和本文方法所得源棒的位置，图3给出了参考辐照面上的剂量率分布情况。

表2 经验法和本文方法给出的排源方案Table 2 Source pencil deployment obtained by empirical method and this work.

由图3和分析可知：(1) 经验法所得参考面剂量率不均匀度为1.022，本文方法为1.010，较经验法好。辐照站有10余年的运行经验，经验法结果已经较好，本文方法的优化效果不显著；(2) 本文方法参考面的边界更平整。表3给出了经验法和本文方法的耗时对比，由表3可知：(1) 本文方法能够显著降低排源耗时，效率提升约100倍；(2) 本文方法耗时主要用于计算单位活度源棒对各参考点剂量率的贡献，耗时正比于参考点数量，可根据需要，通过稀疏等分参考面来减少参考点，提高效率。

上述算例结果表明本文方法排源结果满足抗辐照考核实验的需要，结果较经验法更优，且能够大幅度提高排源效率，节省人力耗费。

图3 参考面(z=35 cm, o-xy)等剂量率线(不均匀度为1.02) (a) 经验法，(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

现有排源算法都针对辐照加工应用，作为对比，表4给出了文献[2,4]算例本文算法的源棒排布方案，结果表明本文方法参考辐照面剂量率不均匀度为1.21稍好于算法I (1.23[2])和算法II (1.27[4])。本文算法耗时(约20 s)稍多于算法II (14.5 s[4])，除算法自身的差异外，耗时差异还与计算机软硬件配置有关，可通过使用运行效率更高的脚本和并行化提高本文算法的速度。

算例结果说明利用本文排源方法也适用于辐射加工应用，排源效果、排源耗时与现有算法I、II相当。

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

4 结语

采用建立数学模型、设计基于改进型贪心算法求解的方法实现了单板钴源源棒排列优化。算例结果表明：针对耐辐照考核实验，能够获得参考面剂量率不均匀度≤1.02条件下的源棒排列，满足实验要求，排源效率较经验法高；针对辐射加工应用，排源效果、排源效率与现有算法I（基于贪心算法）、II（基于模拟植物生长算法）相当。

优化排源方法的特点在于：目标函数与约束条件相互独立，使得算法对目标函数和约束条件的更换不敏感，可根据需求选定排源标准、调整参考面的形状及大小；借鉴经验排源结果，大幅减小解空间的状态数，提高排源效率；采用枚举法来改进算法的全局搜索能力，该结构易于实现并行化，以满足大型辐照装置优化排源工作的需求；算法结构简单，易于实现。

现有的优化排源方法都针对辐射加工，对剂量场不均匀度要求较高(≤1.02)的应用而言，也需要有一种稳健、有效和快速的方法来替代人工经验排源，从计算结果来看，本文方法可以满足这种需求，能够节省人力物力。但贪心算法本身是局部搜索算法，文中的改进措施，尚不能完全弥补该缺陷，排源方法的适用性和可靠性还需细致讨论和验证，以期给出通用、高速的计算程序。源棒排列优化可归结为多极值组合优化问题，若能建立适当的数学模型，可使用全局搜索能力较好的算法。

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 杨磊, 刘义保, 刘玉娟. 基于模拟植物生长算法的钴源源棒的排列优化[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]. 辐射研究与辐射工艺学报, 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联合基金(No.U1530129)资助

李磊，男，1986年出生，2011年于四川大学获理学硕士学位，助理研究员，从事耐辐射加固及辐照工艺研究，E-mail: skyhappier@163.com

2015-05-29，

2015-07-28