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

1 介绍

例子:

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

2 方法

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

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

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

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

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

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

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

3.1.1 贪心算法(Greedy Algorithm)

3.1.2 局部搜索(Local Search)

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)

3.2.4 禁忌搜索(Tabu Search)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

利用摇滚乐队学习TensorFlow,Word2Vec模型和TSNE算法

学习“TensorFlow方式”来构建神经网络似乎是开始机器学习的一大障碍。在本教程中,我们将一步一步地介绍使用Kaggle的Pitchfork数据构建Band...

18820
来自专栏机器学习养成记

小案例(七):口碑分析(python)

案件回顾 商业街口碑分析 顾客在网络上会发表对商品或商店的留言信息 对留言进行分析,可以对商业街进行口碑分析 在论坛中整理了300条留言,并进行分词处理,整理...

40470
来自专栏AI启蒙研究院

从“猜画小歌”背后的AI原理,教大家如何得高分

谷歌在2017年5月发布的文章《ANeural Representation of Sketch Drawings》中,详细介绍了如何对这类简笔画进行建模,以及...

13310
来自专栏PPV课数据科学社区

【学习】SPSS聚类分析全过程

案例数据源: 有20种12盎司啤酒成分和价格的数据,变量包括啤酒名称、热量、钠含量、酒精含量、价格。数据来自《SPSS for Windows 统计分析》dat...

38260
来自专栏数据小魔方

R语言可视化——数据地图离散百分比填充(环渤海)

今天跟大家分享如何以百分比形式填充离散分段数据地图。 案例用环渤海三省二市的地理数据。 library(ggplot2) library(maptools) l...

33640
来自专栏Petrichor的专栏

论文阅读: YOLOv2

本文获得了CVPR 2017 Best Paper Honorable Mention:

38540
来自专栏数据派THU

从零开始用Python实现k近邻算法(附代码、数据集)

68080
来自专栏AI2ML人工智能to机器学习

非均衡数据处理--如何评价?

在分类问题中, 常见的数据预处理包括: 数据缺失(Missing), 奇值处理(Outlier), 数据变换(Transformation), 特征选择(Fea...

9210
来自专栏大数据文摘

机器学习算法一览(附python和R代码)

260140
来自专栏杨熹的专栏

机器学习-多元线性回归

A. 用途: 可以用来预测,由多种因素影响的结果。 B. 建立公式: ? C. 求解方法: 方法1. Gradient Descent: ? ...

36150

扫码关注云+社区

领取腾讯云代金券