Actor-critic框架下的二次指派问题求解方法OA北大核心CSTPCD

二次指派问题(QAP)属于NP-hard组合优化问题,在现实生活中有着广泛应用。目前相对成熟的启发式算法通常以问题为导向来设计定制化算法,缺乏迁移泛化能力。为提供一个统一的QAP求解策略,将QAP问题的流量矩阵及距离矩阵抽象成两个无向完全图并构造相应的关联图,从而将设施和地点的指派任务转化为关联图上的节点选择任务,基于actor-critic框架,提出一种全新的求解算法ACQAP。首先,利用多头注意力机制构造策略网络,处理来自图卷积神经网络的节点表征向量;然后,通过actor-critic算法预测每个节点被作为最优节点输出的概率;最后,依据该概率在可行时间内输出满足目标奖励函数的动作决策序列。该算法摆脱人工设计,且适用于不同规模的输入,更加灵活可靠。实验结果表明,在QAPLIB实例上,本算法在精度媲美传统启发式算法的前提下,迁移泛化能力更强;同时相对于NGM等基于学习的算法,求解的指派费用与最优解之间的偏差最小,且在大部分实例中,偏差均小于20%。