深度学习和强化学习在组合优化方面有哪些应用？
- 采用深度学习和强化学习的角度去看待组合优化问题的求解
- 组合优化问题
- 数学优化方法
- 单纯的基于search
- 深度学习和强化学习
- learning to search
- 数学优化方法
一、深度学习和强化学习求解组合优化问题思路简介
- 组合优化问题
- NP-hard问题
- 神经网络
- Hopfield神经网络求解TSP问题
1. 组合优化的序列决策可以由深度学习或强化学习来替代
-
组合优化问题大多数情况下都是涉及到决策顺序（即序列的决策问题）
- TSP问题：决定以什么顺序访问每一个城市
- job shop问题：决定以什么顺序在机器上加工工件
这两者都是在给定了一个候选集合的情况下确定这些集合中元素应该以什么样的顺序排列
该类问题的共性是，从一个序列到一个序列的映射 -
递归神经网络
- 可以完成从一个序列到另一个序列的映射问题
-
强化学习
- 强化学习天生就是做序列决策用的
-
对序列决策问题的理解应该是什么？
- 这个决策不是在一个时间步完成的，而是需要多个时间步来完成
- 对于TSP和派单问题，在不同的时间步中完成的问题是确定的，只需要基于当前已知的集合考虑元素的排列问题即可
- 对于派单问题，在不同的时间步中完成的问题是不确定的，所以我在t时刻的决策还需要考虑该时刻之后的供需的不确定性，是吗？
- 难点：
state、reward
2. 求解组合优化的经典算法可以由强化学习帮助指导算法策略
- 强化学习的帮助指导和启发式规则之间有什么关系？
- learning to search，在优化过程中引入学习的概念，帮助更加有效的搜索最优解
二、专为组合优化求解而诞生的神经网络——Pointer Network介绍
- Pointer Network(Ptr-Net)
- 基于Seq-Seq网络生成的一种新的网络架构
- 解决从一个序列到另一个序列的映射问题
- 针对的序列问题更加特殊
- 输出序列的内容与输入序列的内容完全一致，只是序列的顺序发生了改变
- 这种问题在实际中常见的应用就是组合优化问题
- 建立了神经网络与组合优化问题的联系
三、相关资料汇总
https://zhuanlan.zhihu.com/p/64869694
https://www.zhihu.com/question/43610101/answer/586741755
