带平衡约束矩形布局优化问题的深度强化学习算法  

Deep reinforcement learning algorithm for rectangle layout optimization with equilibrium constraint

作　　者：徐义春[1] 万书振[1] 董方敏[1] Xu Yichun;Wan Shuzhen;Dong Fangmin(College of Computer&Information Technology,China Three Gorges University,Yichang Hubei 443002,China)

机构地区：[1]三峡大学计算机与信息学院,湖北宜昌443002

出　　处：《计算机应用研究》2022年第1期146-150,共5页Application Research of Computers

基　　金：国家自然科学基金—新疆联合基金资助项目(U1703261)。

摘　　要：带平衡约束的矩形布局问题源于卫星舱设备布局设计,属于组合优化问题。深度强化学习利用奖赏机制,通过数据训练实现高性能决策优化。针对布局优化问题,提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序,再利用定位机制给出布局结果,算法的时间复杂度是O(n^(3));IDAR算法在DAR的基础上引入迭代机制,算法时间复杂度是O(n^(4)),但能给出更好的结果。测试表明DAR算法具有较好的学习能力,用小型布局问题进行求解训练所获得的模型,能有效应用在大型问题上。在两个大规模典型算例的对照实验中,提出算法分别超出和接近目前最优解,具有时间和质量上的优势。The rectangle layout optimization problem with balance constraints is derived from the layout design of satellite module equipment.It belongs to combinatorial optimization problem.Deep reinforcement learning uses reward mechanism to realize high-performance decision optimization through data training.This paper proposed a new deep reinforcement learning algorithm DAR and its extension IDAR.The DAR algorithm output the optimized location sequence with a pointer network,and then used the positioning mechanism to give the layout results.The training of pointer network was realized by deep reinforcement learning.The time complexity of the DAR algorithm was O(n^(3)).The IDAR algorithm was an iteration version of DAR,which had better results but with a time complexity of O(n^(4)).The test results show that DAR algorithm has good lear-ning ability,and the model obtained by small layout problems can be effectively applied to large-scale problems.The results on two typical large-scaled instances show that the proposed algorithms have achieved or approached to the current best results,so that they have advantages both in time and solution quality.

关 键 词：布局优化问题 指针网络 强化学习 深度学习 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]