例子:
k-median问题:在备选工厂集里面选定k个工厂,使得需求点到离它最近工厂的加权距离总和最小.
近似方法分为两种:近似算法(Approximate Algorithms)和启发式算法(Heuristic Algorithms).近似算法通常有质量保证的解.然而启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略,之后用这种策略来在可行时间内寻找一个相对比较好的解,但对解的质量没有保证.
工厂选址问题已经形成了多种求解方法,大致可以分为定性和定量两类方法.
启发式搜索在状态空间中对每一个要搜索的位置按照某种方式进行评估,得到最优的位置,再从这个位置进行搜索直到达到目标.常用的启发式算法包括:禁忌搜索/遗传算法/进化算法/模拟退火算法/蚁群算法/人工神经网络等等.
Note: Metric问题:指距离函数上是对称的且满足三角形不等式.
禁忌搜索在局部搜索(基于领域搜索)算法中加入了禁忌周期,使得搜索领域里的解分成了两种类型:禁忌的解和非禁忌的解,这样帮助了搜索过程”跳坑”,扩大了搜索领域,避免了局部最优,增强了解的疏散性.
思路: (1)给定一个禁忌表(Tabu List)H=null,并选定一个初始解X_now. (2)如果满足停止规则,则停止计算,输出结果;否则,在X_now的领域中选出满足不受禁忌的候选集N(X_now).在N(X_now)中选择一个评价值最佳的解X_next,X_now:=X_next;更新历史记录H, 重复步骤(2).