如何用随机方法求解组合优化问题(一)

什么是组合优化问题

定义

  • 优化问题

    \(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!\)

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

求解思路

引入随机因素求解满意解

  • 最优解与满意解

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

  • 引入随机因素

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

热门相关:倾心之恋:总裁的妻子   今天也没变成玩偶呢   今天也没变成玩偶呢   今天也没变成玩偶呢   不科学御兽