如何用随机方法求解组合优化问题（一）
什么是组合优化问题
定义
-
优化问题
设 \(x\) 是决策变量，\(D\) 是 \(x\) 的定义域，\(f(x)\) 是指标函数，\(g(x)\) 是约束条件。则优化问题可以表示为求解满足 \(g(x)\) 的 \(f(x)\) 最小值问题。即：
\[\min_{x\in D}(f(x)|g(x)) \] -
组合优化问题
如果在定义域 \(D\) 上，满足约束条件 \(g(x)\) 的解的总数是有限的，则优化问题成为组合优化问题。
常见的组合优化问题
-
旅行商问题（TSP）
一个商人去n个城市卖货，从所在城市出发，每个城市去一次且仅去一次，并最后回到出发城市。问如何安排才能
使得商人走的路径最短。 -
0-1背包问题
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
组合优化问题的实际意义
以旅行商问题为例：
- 交通运输
- 飞机航班的安排
- 快递员送快递
- 校车的行驶路线
- 印刷电路板打孔
组合优化问题的难点
旅行商问题可能的行走路线为 \(n!\) 个
复杂度是阶乘级别的，这意味着使用穷举法遍历所有决策计算最优解的思路是不可行的。
求解思路
引入随机因素求解满意解
-
最优解与满意解
大多数时候组合优化问题求最优解是十分困难的（复杂度很高）。如果退一步，只求相对较优的“满意解”，大多数时候可以满足“满意解符合实际问题的需求”且“复杂度大大降低”。
-
引入随机因素
满意解往往是局部最优解，在设计算法的时候可以引入随机因素，考虑数学期望，并在理论上认为其可以收敛于较优的局部最优解。