什么是组合优化问题

定义

• 优化问题

  设 \(x\) 是决策变量，\(D\) 是 \(x\) 的定义域，\(f(x)\) 是指标函数，\(g(x)\) 是约束条件。则优化问题可以表示为求解满足 \(g(x)\) 的 \(f(x)\) 最小值问题。即：

  \[\min_{x\in D}(f(x)|g(x)) \]

• 组合优化问题

  如果在定义域 \(D\) 上，满足约束条件 \(g(x)\) 的解的总数是有限的，则优化问题成为组合优化问题。

常见的组合优化问题

1. 旅行商问题（TSP）

   一个商人去n个城市卖货，从所在城市出发，每个城市去一次且仅去一次，并最后回到出发城市。问如何安排才能
   使得商人走的路径最短。

   

2. 0-1背包问题

   给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

   

组合优化问题的实际意义

以旅行商问题为例：

• 交通运输
• 飞机航班的安排
• 快递员送快递
• 校车的行驶路线
• 印刷电路板打孔

组合优化问题的难点

旅行商问题可能的行走路线为 \(n!\) 个

复杂度是阶乘级别的，这意味着使用穷举法遍历所有决策计算最优解的思路是不可行的。

求解思路

引入随机因素求解满意解

• 最优解与满意解

  大多数时候组合优化问题求最优解是十分困难的（复杂度很高）。如果退一步，只求相对较优的“满意解”，大多数时候可以满足“满意解符合实际问题的需求”且“复杂度大大降低”。

• 引入随机因素

  满意解往往是局部最优解，在设计算法的时候可以引入随机因素，考虑数学期望，并在理论上认为其可以收敛于较优的局部最优解。