Chapter 03 : 组合优化¶
组合优化的基本概念¶
组合优化是应用于离散对象的，从有限多个可行解中找出使某个目标函数达到最优的解的优化问题
- 组合优化是离散数学（Discrete Mathematics）与最优化的交叉学科分支
组合优化与连续优化¶
连续优化
连续优化是应用于连续对象的，从无限多个可行解中找出使某个目标函数达到最优的解的优化问题。
相对决策变量为连续变量的连续优化（Continuous Optimization）问题，组合优化问题的最优解缺少好的性质，求解缺少好的工具。
组合优化例子¶
背包问题¶
连续背包问题¶
现有 \(n\) 件物品，物品 \(j\) 的价值为 \(p_j\)，大小为 \(w_j\)。 物品质地均匀，可任意切割。
这是一个可分割背包问题，贪心算法即可解决。(这是一个连续优化的问题)
离散背包问题¶
现有 \(n\) 件物品，物品 \(j\) 的价值为 \(p_j\)，大小为 \(w_j\)。 物品不可切割。
这便是 0-1 背包问题，动态规划可解。（这是一个组合优化的问题）
旅行商问题 - TSP¶
旅行售货商问题（TravelingSalesman Problem， TSP）
- 一推销员想在若干个城市中推销自己的产品。计划从某个城市出发，经过每个城市恰好一次，最后回到出发的城市
- 城市之间距离已知
- 如何选择环游路线，使推销员走的路程最短
可行解（环游）
- 每一条环游路线由 \(n\) 段两个城市之间的旅行路线连接而成，对应于 \(1,2,⋯,n\) 的一个圆周排列
车辆路径问题 - VRP¶
指派问题¶
排序问题¶
算法与计算复杂性¶
P v.s. NP 问题¶
P 和 NP 问题的通俗解释：
- P：有（确定性）多项式时间算法的问题
- NP：有非确定性多项式时间算法的问题
确定性算法是一种特殊的非确定性算法，故 \(P\subseteq NP\)。
所谓 P v.s. NP 问题是指 \(P=NP\) 还是 \(P\subset NP\) ?
- P v.s. NP 问题是数学和计算机科学中的重大未解决难题之一
- 目前多数人相信 \(P\subset NP\)。此时背包问题等，不存在多项式时间内求得最优解的算法
NP-完全性理论¶
NP–完全与 NP–难 的通俗解释：
- NP–C：NP 类中最难的问题
- 若一个 NP–C 问题有多项式时间算法，所有 NP 问题都有多项式时间算法
- NP–hard：不比 NP–C 问题容易的问题
- 在 \(P\not=NP\) 假设下， NP - 难 问题不存在多项式时间最优算法
NP–hard 可以是 NP 问题，也可以不是 NP 问题
在 \(P\not=NP\) 假设下，多数组合优化问题分属 P 问题 和 NP–hard 问题
NP-完全问题举例¶
- 线性规划和素性检验问题都是 P 问题
SAT 问题¶
图同构问题（目前还没完全证明）¶
组合优化的求解¶
组合优化问题通常不能通过穷举所有可能的解加以比较来求解，因为可行解的数目可能是一很大的数，以致于当前或相当长的一段时间内人力或计算机不能承受。
贪心算法¶
贪心算法：在每一次决策时，选择当前可行且最有利的决策
场馆安排问题¶
贪心算法：按结束时间从小到大的顺序排列最优
排序悖论¶
- 右边第二个是所有加工时间-1，第三个是增加一条线。可见，后面两个不如前面的好，这就是贪婪思想的局限性
- 实际上，这个问题是 NP-难问题，没有多项式时间算法
动态规划¶
动态规划是求解多阶段决策优化问题的一种数学方法和算法思想
背包问题¶
麦子收集¶
一个 n 行 m 列的棋盘，在棋盘的部分格子中各放有一颗麦子
- 一机器人从棋盘左上角的格子出发收集麦子。机器人只能从当前所在格子向下或向右移动一格，到达放有麦子的格子后，即能收集该格子中的麦子
- 如何使机器人到达棋盘右下角的格子时，收集的麦子数量尽可能多
动态规划解法如下：
启发式算法¶
启发式算法（Heuristic）是基于某种直观想法、合理假定，或者借助物理、化学、生命科学中的一些原理而设计的算法，体现了在求解的最优性、精确性与求解资源之间的权衡。启发式算法的有效性一般需通过计算机模拟验证。
常见的启发式算法有：
- 遗传算法（Genetic Algorithm）
- 模拟退火算法（Simulated Annealing）
- 禁忌搜索（Tabu Search）
- 蚁群算法（Ant Colony Optimization）
- 粒子群优化算法（Partial Swarm Optimization）
元启发式算法¶
元启发式算法是一种高层次的问题无关的算法框架，它提供了一组指导方针或策略来开发启发式优化算法
近似算法¶
同 ADS，更详细的笔记在 ADS Chapter 11 : Approximation