Duncan's Blog

NP-Hard问题(重点关注k-median问题)

Veröffentlicht am | in

1 介绍

例子:

k-median问题:在备选工厂集里面选定k个工厂,使得需求点到离它最近工厂的加权距离总和最小.

2 方法

近似方法分为两种:近似算法(Approximate Algorithms)和启发式算法(Heuristic Algorithms).近似算法通常有质量保证的解.然而启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略,之后用这种策略来在可行时间内寻找一个相对比较好的解,但对解的质量没有保证.

工厂选址问题已经形成了多种求解方法,大致可以分为定性和定量两类方法.

  • 定性的方法主要是结合层次分析法和模糊综合法对各方案进行指标评价,找出最优选址.
  • 定量的常用方法包括松弛算法和启发式式算法以及两者的结合.

启发式搜索在状态空间中对每一个要搜索的位置按照某种方式进行评估,得到最优的位置,再从这个位置进行搜索直到达到目标.常用的启发式算法包括:禁忌搜索/遗传算法/进化算法/模拟退火算法/蚁群算法/人工神经网络等等.

Note:
Metric问题:指距离函数上是对称的且满足三角形不等式.

3 求解NP-Hard问题常用方法

3.1 近似算法(Approximate Algorithms,含近似比)

3.1.1 贪心算法(Greedy Algorithm)

3.2 启发式算法(Heuristic Algorithms,不能保证解的质量)

3.2.1 遗传算法(Genetic Algorithm)

  • 交叉:对非公共部分进行单点交叉,若交叉过后,子代对于父代有改进,则用子代替换父代.
  • 变异:基于种群中所有个体的概率,通过轮盘赌选择一个个体i进行变异:对个体i进行局部搜索,若有改进则取代种群中的最差个体.

3.2.2 模拟退火算法(SA算法)

  • step1:贪心或随机构造初始解
  • step2:设置一个退火温度参数T,假设当前解X,他的邻居解X’与其目标函数差值为f(X)-f(X’),如果邻居解比其差,则需要以概率T来接受邻居解

3.2.3 蚁群算法(Ant Colony Optimization,ACO)

禁忌搜索在局部搜索(基于领域搜索)算法中加入了禁忌周期,使得搜索领域里的解分成了两种类型:禁忌的解和非禁忌的解,这样帮助了搜索过程”跳坑”,扩大了搜索领域,避免了局部最优,增强了解的疏散性.

思路:
（1）给定一个禁忌表（Tabu List）H=null,并选定一个初始解X_now.
（2）如果满足停止规则，则停止计算，输出结果；否则，在X_now的领域中选出满足不受禁忌的候选集N(X_now).在N(X_now)中选择一个评价值最佳的解X_next，X_now:=X_next;更新历史记录H, 重复步骤（2）.

分享