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

来源：计算机应用研究杂志2022年第1期北京时间：

作者：徐义春,万书振,董方敏,

单位：三峡大学计算机与信息学院,湖北宜昌443002；

摘要：带平衡约束的矩形布局问题源于卫星舱设备布局设计，属于组合优化问题。深度强化学习利用奖赏机制，通过数据训练实现高性能决策优化。针对布局优化问题，提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序，再利用定位机制给出布局结果，算法的时间复杂度是O(n3)；IDAR算法在DAR的基础上引入迭代机制，算法时间复杂度是O(n4)，但能给出更好的结果。测试表明DAR算法具有较好的学习能力，用小型布局问题进行求解训练所获得的模型，能有效应用在大型问题上。在两个大规模典型算例的对照实验中，提出算法分别超出和接近目前最优解，具有时间和质量上的优势。

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

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