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

局部搜索算法

组合问题由于其可能的解的数量十分庞大,无法用穷举法求解最优解。

局部搜索算法旨在减少复杂度的情况下寻找最优解,尽管其不一定能够找到全局最优解,但是往往可以找到满意的局部最优解。

爬山法

类似于盲人爬山,无法看到全局的景象,但是有拐杖可以探测临近的区域。

每一次使用拐杖在周围扫一圈,把这一圈上每一个点的高度与自己脚底的高度比较,找到距离脚底最高的那个点所在的方向前进。

重复以上过程。直到扫描周围的一圈,发现都低于自己脚底的高度。

此时位于局部最高点。

核心思想

邻域内找一个最优的结果,接受它,再以此为新的起点,重复这个过程。

领域的概念

上文中对于领域的现实类比案例是容易理解的, 但是在组合优化问题中,领域是指什么呢?

对解 \(S\) 经过一些简单变换后,得到的另一个解称作解 \(S\) 的邻居,解 \(S\) 所有邻居的集合称作解 \(S\) 的邻域。

邻域举例

  • 皇后问题:每行每列有且只有一个皇后,每对角线至多一个皇后。

    \(S=\{S_i\}\) 表示一个可能解,其中 \(S_i\) 表示在第 \(i\) 行,第 \(S_i\) 列有一个皇后。

    如四皇后问题的一个解: \(S=(2, 4, 1, 3)\)

    任意交换两个皇后的位置获得一个解的邻居,则\((2,4,1,3)\)的所有邻居,也就是邻域为:

    \(\{(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)\}\)

  • 旅行商问题

    • 常规交换法

      序列 \(S\) 是对于 \(n\) 个城市的访问顺序,将其中两个城市的访问顺序进行调换,则得到一个邻居 \(S'\).

      常规交换法的路线改变示例图:

    • 逆序交换法

      选取两个城市 \(x_i\)\(x_j\) ,将这两个城市之间的序列进行逆序操作。( \(x_i\)\(x_j\) 是不变的 )

      逆序交换法的路线改变示例图:

局部搜索算法描述

  1. 随机的选择一个初始的可能解 \(x_0\in D\)\(x_b=x_0\)\(P=N(x_b)\)
  2. 如果 \(P\) 不为空,则
  3. Begin
  4. ​ 选择 \(P\) 的一个子集 \(P'\)\(x_n\)\(P'\) 中的最优解
  5. ​ 如果 \(f(x_n)<f(x_b)\),则 \(x_b = x_n\)\(P=N(x_b)\),转2;
  6. ​ 否则 \(P=P-P'\),转2.
  7. End
  8. 输出计算结果
  9. 结束

其中:

  • \(N(x)\)函数用于获取组合 \(x\) 的邻域。

  • 这里的算法比上文的爬山法更具一般性,没有直接在领域中寻找局部最优解,而是在邻域的子集中寻找最优解。

  • \(f(x)\)用于计算并比较组合 \(x\) 的优良性,从而最终可以选出局部最优解。在旅行商问题中可以是路径的长度,在0-1背包中可以是背包中物品的价格。

热门相关:冉冉心动   买妻种田:山野夫君,强势宠!   不科学御兽   未来兽世:买来的媳妇,不生崽   后福