基于深度强化学习的魔方还原与组合优化开题报告

1. 研究目的与意义（文献综述包含参考文献）

文 献 综 述摘要：深度强化学习结合了深度学习强大的感知能力与强化学习优秀的决策能力，在不同领域均体现出巨大的潜力，使之成为当前机器学习领域研究一大研究热点.本文首先阐述了深度强化学习在不同领域中的应用.其次讲解了现有魔方相关还原算法基础，包括Thislethwaite算法， Kociemba's Two-Phase算法和Iterative Deepening A*算法.随后对基于深度强化学习的自学迭代算法的基本原理和方法进行了描述.最后简要介绍了自学迭代算法与蒙特卡洛树搜索相结合形成的Deep Cube魔方还原算法，并将其与目前其他魔方还原算法在还原步数和成功率两个方面进行了比较.关键词：深度学习强化学习深度强化学习组合优化魔方Abstract: Combined with strong perception ability of deep learning and excellent decision-making ability of reinforcement learning, deep reinforcement learning (DRL) shows great potential in many fields, making it a research hotspot in the field of machine learning. Firstly, this paper illustrates the application of DRL in different fields. Secondly, introduces the basic algorithms related to Rubik's cube restoration, including Thislethwaite algorithm, Kociemba's Two-Phase algorithm and Korf iterative Deepening A* algorithm. Then introduces an algorithm based on DRL called Autodidactic Iteration (ADI) and its basic principle and method. Finally, briefly introduces the Deep Cube algorithm formed by the combination of Autodidactic Iteration and Monte Carlo tree search, and compares it with other cube restoration algorithms in terms of steps and success rate.Keywords: deep learning; reinforcement learning; deep reinforcement learning; combinatorial optimization; Rubik's cube1 引言随着人工智能学科的发展，深度学习（Deep Learning, DL）作为人工智能的一大研究热点已经在诸如计算机视觉[1][2]、语音识别[3][4]、自然语言处理[5][6]、自动驾驶[7][8]等诸多领域获得了巨大成功，甚至在某些方面具有了超过了人类的能力.与着重对事物进行感知的深度学习所不同，强化学习（Reinforcement Learning, RL）作为人工智能领域另一热点，着眼于通过智能体与环境进行交互，学习能够获得最大化累计回报的策略.在协同控制[9]、游戏[10][11]、机器人控制[12][13]等领域强化学习获得了突出的成就.谷歌Deep Mind[14]团队创新性将深度学习与强化学习相结合，创立了兼具感知和决策能力的深度强化学习算法.该算法工作流程图如图1所示.算法自面世以来，以Alpha Go为代表的深度强化学习算法取得了令人举世瞩目的成就，并被视为人工智能领域发展的一个里程碑. 图 1 DRL工作流程图3阶魔方是一个经典的3维组合问题，魔方具有很大的状态空间，有 个可能的不同状态，但只有一个目标状态，面对如此大的状态空间和单一的目标状态，如果从随机状态开始使用传统DRL算法，如A3C算法[15]可能会导致魔方永远无法解出，从而智能体将不会获得正的奖励信号，因此这一类问题给机器学习带来了全新的挑战.2 深度强化学习的应用深度强化学习是将深度学习与强化学习相结合的算法，当前深度强化学习正处于快速发展的时期，每年都有很多针对不同应用场景的新算法被提出，而这也极大地推动了整个人工智能领域的发展.2.1 棋类博弈2016年，谷歌DeepMind 团队将深度强化学习应用到状态空间和动作空间都非常大，且策略更复杂的围棋上，开发的AlphaGo 基于深度神经网络，同时采用蒙特卡洛树搜索算法（Monte Carlo Tree Search, MCTS) ，这一结合深度学习和强化学习的训练方式，让Alpha Go获得了高于人类水平的围棋技艺，于2016年击败顶尖棋手李世石，2017年击败世界冠军柯洁．2.2 自动驾驶车辆的驾驶过程是一个根据路况进行惯序决策的过程，而这一决策过程具有马尔可夫性，因此可以通过深度强化学习算法对环境进行学习．Kendall[16]等人将深度强化学习应用到自动驾驶中，智能体首先接收道路图像作为输入，通过神经网络提取图像特征得到当前状态，在此基础上学习转向和加减速等动作策略，从而实现自动驾驶．3魔方还原算法基础3.1 Thislethwaite算法魔方原始的还原算法是通过依次还原魔方块来减少乱序块的排列数，直到完成所有块的还原.Thistlethwaite算法[17]则与原始解法完全不同.魔方块的排列状态均和魔方群元素是相对应的，Thistlethwaite方法的指导思想就是将魔方所处的群降到更小的子群，最后到单位子群，即魔方的还原状态.所以魔方直到还原的最后几步看起来都是乱的，但实际上状态数已经随所处群的减小而同步减小了.3.2 Kociemba's Two-Phase算法普通三阶魔方具有 个可能的不同状态，为了处理如此巨大的状态空间，Kociemba's Two-Phase算法[18]将魔方还原的过程分为两个阶段依次处理，这样一来魔方还原问题就被分解为两个子阶段，这也是该算法名称的由来.该算法的第一阶段并不只局限于找到最优解法，而是从少到多找到求解步数不同的解法，同时在第二阶段尝试不同的解法，这样一来虽然第一阶段可能不是最优解，但综合两个阶段会得到总步数更少的解法.3.3 Iterative Deepening A*Iterative Deepening A*(IDA*)算法[19][20]是基于迭代加深的A*算法.迭代加深是一种常用的方法，在开始的时候给出估计值，然后通过迭代使它越来越精确.一旦当结果不发生大的变化或者提升幅度很小时，就可以认为当前已经得到了一个非常好的结果，即使让它更精确，结果也不会有较大幅度改善.4 自学迭代算法2016 年Alpha Go 击败顶尖棋手李世石引起了人们的广泛关注．对于状态空间和动作空间都非常大，且策略更复杂的围棋，传统的强化学习算法难以简单求解，为此Deep Mind团队在Alpha Go 的算法中引入了两个相对独立的卷积神经网络，分别为策略网络和值函数网络，而这一融合强化学习和监督学习的训练方式正是自学迭代算法（Autodidactic Iteration, ADI）[21]的灵感来源.与传统的魔方求解算法不同，自学迭代算法在大量不同的魔方数据集上训练神经网络，进而获得求解策略.在强化学习算法的指导下，神经网络的训练过程不需要智能体具有任何先验知识.这是其与Thislethwaite算法，Kociemba'sTwo-Phase算法和 IDA*的最大不同.三阶魔方的状态有 种，但只有一个还原成功的状态能获得正的奖励信号.正因如此，魔方和围棋之类具有巨大状态空间的游戏不能简单使用传统强化学习算法进行求解.面对这种稀疏回报的情况，Forest Agostinelli[21]等人受策略迭代的启发，提出了名为自学迭代的深度强化学习算法.自学迭代是一个有监督的迭代学习过程，它用来训练具有参数θ的深层神经网络 ，该神经网络以状态s为输入，以价值策略对(v, p)为输出.每一次自学迭代都从目标状态 开始，把魔方随机转动k次，生成k个魔方样本序列，循环这个过程 次，总共得到 个魔方数据样本，标记为 .对每一个样本 ，分别执行全部12个动作，如此对每一个样本 生成12个子样本.对当前神经网络输入 得到输出 和 ，随后将 作为 的标签 ，将 作为 的另一标签 .用样本 和 训练神经网络 ，重复这个过程即为自学迭代.5 Deep Cube5.1 Deep Cube算法介绍仅仅生成了一个深度神经网络，算法还不具备求解魔方的全部功能，在异步蒙特卡洛树搜索（MCTS）的使用下，两者组成了Deep Cube[22]算法，之前训练好的 网络对搜索进行优化，神经网络输出价值策略对(v, p)中策略p可以减小树的广度，价值v可以降低树的深度.每执行一步MCTS，都要沿着树进行探索.如果当前节点是叶节点，通过对状态执行所有12种动作对其进行延伸，并检查结果状态是否为目标状态，当扩展状态为目标状态时，搜索完成，随后将叶节点状态传递给模型，输出值和策略，存储以备用.如果当前节点不是叶节点，那么我们就能够知道该节点的可到达状态，并从网络获得值和策略输出.5.2 Deep Cube算法与其他算法对比基于深度强化学习的Deep Cube算法在不使用任何先验知识的情况下学习效果令人满意.Forest Agostinelli[21]等人使用640个随机打乱了1000次的魔方对Deep Cube和Kociemba's Two-Phase算法进行了测试，并设置1小时的求解时间限制，实验结果表明Deep Cube和Kociemba's Two-Phase算法还原魔方成功率均为100%. 但基于群论的Kociemba算法求解速度更快，解算时间的中值低于一秒，但其求解并不总是最短.Deep Cube算法虽然花费了更多的时间，解算时间的中值约为10分钟，但其中55％的魔方会得到比Kociemba步骤更少的解法.由于IDA*算法求解一个魔方的时间就高达6天，因此Forest Agostinelli[21]等人使用100个随机打乱了15次的魔方对Deep Cube,Kociemba's Two-Phase和IDA*算法进行测试，实验结果表明三种算法均能在1小时内还原全部魔方，其中Deep Cube和IDA*算法解算步骤中值均为13步，并且在Deep Cube算法下有74％的魔方以最优步骤解出了魔方.6小节本文首先介绍了深度强化学习在不同领域中的应用，可以看到在控制、娱乐、机器人、出行等各个方面深度强化学习均表现出广阔的研究前景和对该领域巨大的推动力.随后对基于深度强化学习的魔方还原与组合优化研究课题从基础算法，如Thislethwaite算法，Kociemba's Two-Phase算法和IDA*算法进行了简要介绍.进而结合深度强化学习介绍了ADI算法和由ADI算法与MCTS相结合形成的Deep Cube算法进行了阐述.最后根据Forest Agostinelli等人的实验研究结果对Deep Cube,Kociemba's Two-Phase和IDA*算法在还原步数和成功率两方面进行了对比.相信随着对深度强化学习研究的深入，相关的研究成果势必会对人们的生活产生更加深远的影响，为人类的发展和社会的进步作出更大的贡献.参考文献[1]. 李庆忠，白文秀，牛炯.基于改进CycleGAN的水下图像颜色校正与增强[J/OL].自动化学报:1-11[2022-01-19]. DOI: 10.16383/j.aas.c200510.[2]. 丁文谦，余鹏飞，李海燕，陆鑫伟.基于Xception网络的弱监督细粒度图像分类[J/OL].计算机工程与应用:1-10[2022-01-19].[3]. 陈佳豪，白炳松，王冬华，严迪群，王让定.面向语音识别系统的对抗样本攻击及防御综述[J/OL].小型微型计算机系统:1-11[2022-01-19].[4]. 孙韩玉，黄丽霞，张雪英，李娟.基于双通道卷积门控循环网络的语音情感识别[J/OL].计算机工程与应用:1-10[2022-01-19].[5]. 夏鸿斌，肖奕飞，刘渊.融合自注意力机制的长文本生成对抗网络模型[J/OL].计算机科学与探索:1-10[2022-01-19].[6]. 王颖洁，朱久祺，汪祖民，白凤波，弓箭.自然语言处理在情感分析领域应用综述[J/OL].计算机应用:1-12[2022-01-19].[7]. 杜中强，唐林波，韩煜祺.面向嵌入式平台的车道线检测方法[J/OL].红外与激光工程:1-10[2022-01-19].[8]. 李彦辰，张小俊，张明路，沈亮屹.基于改进Efficientdet的自动驾驶场景目标检测[J/OL].计算机工程与应用:1-11[2022-01-19].[9]. 周宏宇，王小刚，单永志，赵亚丽，崔乃刚.基于改进粒子群算法的飞行器协同轨迹规划[J/OL].自动化学报:1-8[2022-01-19]. DOI: 10.16383/j.aas.c190865.[10]. Silver D, Hubert T, Schrittwieser J, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play[J]. Science, 362.[11]. Mcaleer S, Agostinelli F, Shmakov A, et al. Solving the Rubik's Cube Without Human Knowledge[J]. 2018.[12]. 宋锐，李凤鸣，权威，李贻斌.多约束条件下机器人柔性装配技能自学习[J/OL].控制与决策:1-10[2022-01-19]. DOI: 10.13195/j.kzyjc.2020.0925.[13]. 韩建福，杜昌平，郑耀.不确定性下扑翼飞行器的自适应滑模控制[J/OL].控制工程:1-8[2022-01-19]. DOI: 10.14107/j.cnki.kzgc.20200464.[14]. D Silver, Huang A, Maddison C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature.[15]. Mnih V, Adri Puigdomnech Badia, Mirza M, et al. Asynchronous Methods for Deep Reinforcement Learning[J]. 2016.[16]. Kendall A, Hawke J, D Janz, et al. Learning to Drive in a Day[J]. 2018.[17]. Misra A. Solving Rubik's Cube using Genetic Algorithm. [18]. Herbert Kociemba. Two-phase algorithm details. http://kociemba.org/math/imptwophase.htm[19]. Korf R E. Iterative-Deepening-A*: An Optimal Admissible Tree Search[J]. Artificial Intelligence, 1985.[20]. Korf R E. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. AAAI Press, 1997.[21]. Mcaleer S, Agostinelli F, Shmakov A, et al. Solving the Rubik's Cube Without Human Knowledge[J]. 2018.[22]. Agostinelli F, Mcaleer S, Shmakov A, et al. Solving the Rubik's cube with deep reinforcement learning and search[J]. Nature Machine Intelligence, 2019, 1(8):356-363.

2. 研究的基本内容、问题解决措施及方案

1．研究的问题本课题主要研究的是深度强化学习应用于魔方的还原与组合优化。

三阶魔方是经典的组合优化问题，由于其状态空间巨大，目标状态唯一的特点，当前大多数的还原算法均基于人类知识，即群论和代数抽象来对其进行求解。

当前深度学习与强化学习正处于蓬勃发展的时期，两者相结合产生的深度强化学习更是大展身手，2016年alpha go与李世石的人机大战给人们留下了深刻印象，因此本课题希望以如alpha go之类的深度强化学习算法为启发，解决传统深度强化学习在大状态空间，稀疏回报，如魔方这一类问题中的应用。