| 运筹帷幄之中，决胜千里之外 |
组合优化(CO)是数学优化的子领域, 其常常因为相关问题具有”NP-hard”复杂度而闻名. 比如说很经典的旅行商人问题, 背包问题等等. 这些问题中, 使用穷举搜索或枚举法是不可行的(因为无法承受的时间复杂度), 而在现实生活中, 很多真实的应用都可以映射到这些问题中, 比如在几十个城市或者几百个网点的物流中缩减成本, 又或者是在装箱时保证装载尽量多的货物等等.
而这门对资源配置进行高效管理, 解决复杂问题中最优解的学科, 有一个响亮的名字: 运筹学(Operations Research). 该专栏旨在记录, 并分享学习OR的过程, 尽量从初学者的角度分析, 与各位学子共勉
传统算法求解组合优化
CO问题并不是一个新概念, 早在二战期间就有团队研究了. 因此一些数学算法当然可以对CO进行求解, 比如精确算法, 近似算法, 启发式算法 (如贪心算法, 局部搜索), 元启发式算法 (如遗传算法, 模拟退火, 蚁群算等等). 但这些算法往往具有局限性, 比如:
- 精确算法在大规模场景中的计算代价过高 (以至于无法实现)
- 近似算法仅在时间复杂度为更高阶多项式的时候能保证解的质量
- 启发式算法可以保持计算时间与解的质量之间 “微妙” 的平衡, 但无法提供理论保证 (说白了就是太随机了, 偏向玄学调参)
在传统运筹学中, 要求解一个复杂问题, 通常分这两个步骤:
- 对该问题进行数学建模, 制定目标函数, 约束条件等
- 设计算法, 比如上面提到的遗传算法等
但正如上文所说, 对于大规模的复杂问题, 这一过程会存在一些问题, 比如:
- 很难建立精确的数学模型, 通常需要对问题进行简化, 降维等操作
- 基本没法处理大规模问题, 会出现”组合爆炸”现象, 也就是时间和空间复杂度指数级增长 (随着问题规模变大)
- 只能处理静态问题, 无法根据时间变化, 也就是说每次输入发生变化, 都需要重新计算, 效率较低
因此, 面对枯燥的传统求解过程, 各路学者自然而然地, 提出了一个问题:
我们可以部署机器学习, 来成功地学习如何求解组合优化问题吗?
机器学习和组合优化的文献综述
话不多说, 先请出三篇综述佳作:
- Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon
- Reinforcement Learning for Combinatorial Optimization: A Survey
- Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
推荐阅读顺序1, 2, 3.
这三篇文章的功效有:
- 如果通读这3篇综述性质的文章, 就可以通晓机器学习和组合优化问题的前世今生
- 如果熟知每个章节的工作原理/代码实现, 就算是毕了业