摘要
组合优化问题广泛存在于国防、交通、工业、生活等各个领域,几十年来,传统运筹优化方法是解决组合优化问题的主要手段,但随着实际应用中问题规模的不断扩大、求解实时性的要求越来越高,传统运筹优化算法面临着很大的计算压力,很难实现组合优化问题的在线求解.近年来随着深度学习技术的迅猛发展,深度强化学习在围棋、机器人等领域的瞩目成果显示了其强大的学习能力与序贯决策能力.鉴于此,近年来涌现出了多个利用深度强化学习方法解决组合优化问题的新方法,具有求解速度快、模型泛化能力强的优势,为组合优化问题的求解提供了一种全新的思路.因此本文总结回顾近些年利用深度强化学习方法解决组合优化问题的相关理论方法与应用研究,对其基本原理、相关方法、应用研究进行总结和综述,并指出未来该方向亟待解决的若干问题.
Combinatorial optimization problems widely exist in various fields such as national defense,transportation,industry and life.For decades,traditional operational research methods are the main means to solve combinatorial optimization problems.However,with the increase of problem size in practical applications and the increasing demands for real-time optimization,traditional methods suffer from great computational burdens,and it is difficult to realize the online solution of combinatorial optimization problems.In recent years,with the rapid development of deep learning technology,the achievements of deep reinforcement learning in AlphaGo,robot and other fields show its strong learning ability and sequential decision-making ability.In view of this,in recent years,a number of new methods using deep reinforcement learning to solve combinatorial optimization problems have emerged,which have the advantages of fast solving speed and strong model generalization ability.It provides a new idea for solving combinatorial optimization problems.Therefore,this paper summarizes and reviews the theoretical methods and application researches of this kind of methods in recent years.
作者
李凯文
张涛
王锐
覃伟健
贺惠晖
黄鸿
LI Kai-Wen;ZHANG Tao;WANG Rui;QIN Wei-Jian;HE Hui-Hui;HUANG Hong(College of System Engineering,National University of De-fense Technology,Changsha 410073;Hunan Key Laboratory of Multi-Energy System Intelligent Interconnection Technology,Changsha 410073)
出处
《自动化学报》
EI
CAS
CSCD
北大核心
2021年第11期2521-2537,共17页
Acta Automatica Sinica
基金
国家自然科学基金面上项目(61773390)
湖湘青年英才计划(2018RS3081)
科技委国防创新特区项目(193-A11-101-03-01)
国防科技大学自主科研计划(ZZKY-ZX-11-04)资助。
关键词
深度强化学习
组合优化问题
深度神经网络
图神经网络
指针网络
Deep reinforcement learning
combinatorial optimization problems
deep neural network
graph neural networks
pointer networks
