pcenter解决方案.docx

pcenter解决方案.docx

《pcenter解决方案.docx》由会员分享，可在线阅读，更多相关《pcenter解决方案.docx（36页珍藏版）》请在冰点文库上搜索。

pcenter解决方案

p_center解决方案（总37页）

问题：

P-Center问题

P-Center问题

摘要

问题：

从一个点集合中选择p个点作为中心点，并把其他分配到某个选择的点，使得所有点到其对应的中心点的距离加起来最小。

针对问题，分析得出p-center问题实质为选址问题。

其研究背景为工厂的选址，属于运筹学中经典问题之一。

运用智能算法中模拟退火随机局域搜索算法进行求解最小值。

具体步骤为：

由于题目中未提供点集合，所以首先通过文献查阅[1]和生活实际得到可靠的二维数据点分布，即表示一个点集合，存储方式为文件存储（）；其次加载点集合数据，采用模拟退火算法随机局域搜索算法[2]进行处理：

1）初始化：

中心点个数

，温度

，温度缩减系数

，最大迭代次数

。

解释：

由于P-Center问题是以工厂的选址问题，加上编写的二维数据的分布情况，所以建立工厂的数量为事先已知条件，即

；初试温度的设置是影响搜索性能重要因素之一。

初始化温度高，则搜索到全局最优值的可能性大，但计算时间大幅度增加；反之，缩短了计算时间，但性能并不优越。

所以采用多次实验的方式确定温度

；为了保证较大的搜索空间，所以让系数接近于1；经过多次实验，确定迭代次数

，此时结果较为理想。

2）迭代

次，循环第三步到第四步。

3）从临域中选择最佳的解，即确定最优值：

产生新值

；增量

；若

，则接受

作为新解，否者以概率

接受

作为新解。

4）

逐渐减少，且

，最后跳至第二步。

5）得到距离最小值

然后通过模拟退火局部搜索算法，得迭代情况为：

最后通过模拟退火局部搜索算法，得出分配图为：

得出四个粗五角星为各自的中心点，其中颜色相同的属于各自颜色的中心点，即相同颜色距离各自中心点最短。

通过Python得出最近距离为：

问题扩充：

针对P-Center问题，还可以通过k-means聚类算法[3]进行解决，得到与最近搜索算法同样的结果。

关键词：

P-Center选址问题模拟退火随机局域搜索算法K-Means聚类算法

1问题重述

选址问题是运筹学中经典的问题之一。

经典的选址问题包括连续选址问题、离散选址问题、P-Median问题以及P-Center问题等。

该问题属于P-Center问题，从一个点集合中选择p个点作为中心点，并把其他点分配到某个选择的点，使得所有点到其对应中心点的距离加起来最小。

2数据预处理

注：

数据存储形式为：

，可在附件一中查看

数据来源

（1）文献查阅

（2）生活实际

数据预处理方法

（1）数据选取：

去除无效数据以及噪声数据。

（2）数据整合：

将若干个数据库整合成一个数据存储结构。

（3）数据替代：

将杂乱数据替代成易处理数据。

（4）数据变换：

将原始数据转换为适合任务定价的形式。

数据选取参考原则

（1）统一数据源编码。

（2）清除唯一属性。

（3）清除重复属性。

（4）清除可忽略字段。

（5）进一步处理：

清除异常数据，去除附带噪声数据，填充空缺值、丢失值。

3问题分析

问题

首先，通过文献查阅和生活实际得到可靠的二维数据点分布，将此二维分布作为数据点集合，然后通过模拟退火最近搜索算法[4]进行迭代优化，最终得到所有点到其中心点的距离。

4问题假设

1.假设根据数据特征或者政策（例如工厂政策）确定，即已经确定P-Center中的p中心个数。

2.2.假设点集合为二维集合，不包括任何三维或者多维信息。

5符号说明

可行解

迭代更新后的解

概率条件下更新

优化目标函数

模拟退火温度值

中心点个数

温度缩减系数

最大迭代次数

6模型的建立与求解

选址问题目前有多种求解方法，大致分为定性和定量两类：

定性的方法主要是结合层次分析法和模糊综合法对各方案进行指标评价，最终得出最优选址；定量的方法主要是松弛算法和启发式算法以及两者的结合。

而本题解决的是P-Center问题，即使用启发式算法-智能算法模拟退火随机局部搜索算法[5]进行解决。

解法一

模拟退火随机局部搜索算法

模拟退火算法是一种贪心算法，但是其搜索过程引入了随机因素。

在迭代更新可行解时，以一定概率来接受一个比当前解要差的解，因此有可能会跳出局部最优解，达到全局最优解，其搜索原理如下图：

图1模拟退火随机局部搜索算法示意图

假定当前可行解为

，迭代更新后的解为

，那么对应的“能量差”定义为：

以相应概率接受新值，此概率为：

模拟退火随机局域搜索算法思路为：

图2模拟退火随机局域搜索算法思路图

算法求解

注：

详细Python程序见附录一与附件一

根据算法思想，通过Python得到迭代与目标函数关系为：

图3模拟退火训练曲线图

可以看出经过200次迭代，优化目标函数处于相对稳定状态。

具体的目标函数与迭代次数对应关系见附录，以下为部分对应关系：

图4部分迭代次数与目标函数关系

最终得出点集合分配图为：

图5点集合分配图

得出四个粗五角星为各自的中心点，其中颜色相同的属于各自颜色的中心点，即相同颜色距离各自中心点最短。

通过Python得出最近距离为：

解法二

通过智能算法中的模拟退火随机局域搜索算法可以得出相应的结论，为了检验以及去探索更多的解决方式，使用了聚类算法，以下为模型以及过程。

具体的Python代码见附录二以及附件一。

聚类算法

算法过程如下：

1）从N个点中随机选取p个点作为中心点

2）对剩余的点测量到其每个中心点的距离，并把它归到中心点的类

3）重新计算已经得到的各个类的中心点

4）迭代第二步、第三步直至新的中心点与原中心点相等或者小于指定阈值，算法结束

算法求解

通过Python程序将通过文献查找的点集合数据进行聚类分析，得到与局域搜索算法类似的分配图，如下图所示：

图6聚类分析分配图

此图的解释与模拟退火随机局域搜索算法相同，不再重复解释。

同样可以得出所有点到对应中心点的距离最小为：

。

7模型的评价

模型的优缺点

模型的优点：

（1）通过模拟退火随机局域搜索算法应用十分广泛，可以高效的解决NP完全问题

（2）模拟退火随机搜索算法与K-Means聚类算法相互结合，相互印证，使得数据准确性得以保证。

（3）通过模拟退火算法与K-Means算法得出的点集合分配图可以形象生动的得出二维的数据关系。

模型的缺点：

（1）模拟退火随机局域搜索算法初始化设置必须准确，要经过多次实验才能得到合适的初始化值。

8参考文献

[1]CCEHC:

Anefficientlocalsearchalgorithmforweightedpartialmaximumsatisfiability, ArtificialIntelligence, 2017, 

[2]LocalSearchforMinimumWeightDominatingSetwithTwo-LevelConfigurationCheckingandFrequencyBasedScoringFunction, JournalofArtificialIntelligenceResearch（JAIR）, 2017, 

[3]王守强.多中心点聚类问题的随机算法[D].山东大学,2010.

[4]朱泓丞.设施选址问题的研究与应用[D].中国科学技术大学,2009.

[5]蒋建林,徐进澎,文杰.基于单亲遗传模拟退火算法的顶点p-中心问题[J].系统工程学报,2011,26（03）:

414-420.

附录

注：

具体代码见附件

附录一模拟退火随机局域搜索算法Python代码

importnumpyasnp

importasplt

importmatplotlib

importasDS

importrandom

zandaoguangfont=''）

deff（x）:

"""

目标函数，所有点到中心点的距离和

:

paramx:

list表示中心点的序号

:

paramdataSet:

数据集

:

return:

"""

distances=（dataSet,dataSet[x,:

]）#用于计算两个输入集合的距离

M=（distances,axis=1）#得出附近点到中心点的最小值

returnsum（M）#将最小值累加得到最小距离

deffind_next（x）:

"""

从邻域中选择最佳的解

:

paramx:

:

paramdataSet:

:

return:

最优值

"""

ind=（range（p）,1）

x_new=（x）

tmp=（range[0]）,1）#[0]返回行数

whiletmp[0]inx:

tmp=（range[0]）,1）

x_new[int（ind[0]）]=tmp[0]

iff（x_new）

returnx_new

else:

if（）<（-（f（x_new）-f（x））/T）:

#模拟退火算法核心

returnx_new

else:

returnx

#得到数据

print（"第一步：

加载数据"）

dataSet=[]

fileIn=open（''）

forlinein（）:

lineArr=（）.split（''）

（[float（lineArr[0]）,float（lineArr[-1]）]）

dataSet=（dataSet）

p=4#设定问题的p中心参数的值

T=1000#模拟退火的初始温度

a=#温度减少的系数，为了保证较大的搜索空间，所以非常接近于1

Iter=200#最大迭代次数

#模拟退火

#param:

history记录距离和最优值，方便比较最小值

#param:

best_x记录当前距离和最小值

x=（range[0]）,p）#随机产生初始解

best_x=x

history=[]

foriinrange（Iter）:

print（'第%d次迭代：

目标函数=%s'%（i,f（x）））

x=find_next（x）

T*=a

iff（x）

best_x=x

（f（best_x））

print（'距离和最小为%s'%f（best_x））

#模拟退火局部搜索训练曲线图

#resul:

t得出模拟退火的迭代次数与目标函数值的关系

（0）

（range（1,Iter+1）,history,'r-'）

（'迭代次数',fontproperties=zandaoguangfont）

（'目标函数值',fontproperties=zandaoguangfont）

（'模拟退火训练曲线图',fontproperties=zandaoguangfont）

#数据分配图

#用红蓝黄绿等颜色代表p中心中的p类

#其中经过搜索后的p个中心点用markersize=10的五边形表示

#相同颜色的点相比较与相同颜色的加粗markersize=10的五边形，即相同颜色以相同颜色的加粗五边形为中心，此时距离最近。

（1）

distances=（dataSet,dataSet[best_x,:

]）

sorted_dist=（distances,axis=1）

color=['r.','b.','y.','g.']

color0=['rp','bp','yp','gp']

foriinrange（p）:

ind=sorted_dist[:

0]==i

（dataSet[ind,0],dataSet[ind,1],color[i]）

（dataSet[best_x[i],0],dataSet[best_x[i],1],color0[i],markersize=10）

（'分配图',fontproperties=zandaoguangfont）

（）

附录二聚类算法Python代码

fromnumpyimport*

importasplt

importKMeans

##得到数据...

print（"第一步：

加载数据..."）

dataSet=[]

fileIn=open（""）

forlinein（）:

temp=[]

lineArr=（）.split（'\t'）

（float（lineArr[0]））

（float（lineArr[1]））

（temp）

（）

##进行聚类...

print（"第二步：

进行聚类..."）

dataSet=mat（dataSet）

#设置为4个中心点

k=4

#调用KMeans文件中定义的kmeans方法。

centroids,clusterAssment=（dataSet,k）

##第三步：

显示结果...

#数据分配图

#用不同种颜色代表p中心中的p类

#其中经过搜索后的p个中心点用markersize=10的五边形表示

#相同颜色的点相比较与相同颜色的加粗markersize=10的五边形，即相同颜色以相同颜色的加粗五边形为中心，此时距离最近。

print（"第三步：

显示结果..."）

（dataSet,k,centroids,clusterAssment）

#################################################

#kmeans:

k-meanscluster

#Author:

ZanDaoguang

#Date:

2018/03/09

#HomePage:

#Email

#################################################

fromnumpyimport*

importtime

importasplt

#calculateEuclideandistance

defeuclDistance（vector1,vector2）:

returnsqrt（sum（power（vector2-vector1,2）））#求这两个矩阵的距离，vector1、2均为矩阵

#initcentroidswithrandomsamples

#在样本集中随机选取k个样本点作为初始质心

definitCentroids（dataSet,k）:

numSamples,dim=#矩阵的行数、列数

centroids=zeros（（k,dim））#感觉要不要你都可以

foriinrange（k）:

index=int（0,numSamples））#随机产生一个浮点数，然后将其转化为int型

centroids[i,:

]=dataSet[index,:

]

returncentroids

#k-meanscluster

#dataSet为一个矩阵

#k为将dataSet矩阵中的样本分成k个类

defkmeans（dataSet,k）:

numSamples=[0]#读取矩阵dataSet的第一维度的长度,即获得有多少个样本数据

#firstcolumnstoreswhichclusterthissamplebelongsto,

#secondcolumnstorestheerrorbetweenthissampleanditscentroid

clusterAssment=mat（zeros（（numSamples,2）））#得到一个N*2的零矩阵

clusterChanged=True

##step1:

initcentroids

centroids=initCentroids（dataSet,k）#在样本集中随机选取k个样本点作为初始质心

whileclusterChanged:

clusterChanged=False

##foreachsample

foriinrange（numSamples）:

#range

minDist=

minIndex=0

##foreachcentroid

##step2:

findthecentroidwhoisclosest

#计算每个样本点与质点之间的距离，将其归内到距离最小的那一簇

forjinrange（k）:

distance=euclDistance（centroids[j,:

],dataSet[i,:

]）

ifdistance

minDist=distance

minIndex=j

##step3:

updateitscluster

#k个簇里面与第i个样本距离最小的的标号和距离保存在clusterAssment中

#若所有的样本不在变化，则退出while循环

ifclusterAssment[i,0]!

=minIndex:

clusterChanged=True

clusterAssment[i,:

]=minIndex,minDist**2#两个**表示的是minDist的平方

##step4:

updatecentroids

forjinrange（k）:

#clusterAssment[:

0].A==j是找出矩阵clusterAssment中第一列元素中等于j的行的下标，返回的是一个以array的列表，第一个array为等于j的下标

pointsInCluster=dataSet[nonzero（clusterAssment[:

0].A==j）[0]]#将dataSet矩阵中相对应的样本提取出来

centroids[j,:

]=mean（pointsInCluster,axis=0）#计算标注为j的所有样本的平均值

print（'聚类完成！

'）

returncentroids,clusterAssment

#showyourclusteronlyavailablewith2-Ddata

#centroids为k个类别，其中保存着每个类别的质心

#clusterAssment为样本的标记，第一列为此样本的类别号，第二列为到此类别质心的距离

defshowCluster（dataSet,k,centroids,clusterAssment）:

numSamples,dim=

ifdim!

=2:

print（"Sorry!

Icannotdrawbecausethedimensionofyourdataisnot2!

"）

return1

mark=['or','ob','og','ok','^r','+r','sr','dr','

ifk>len（mark）:

print（"对不起，您输入的k太大了，请联系管理员山东科技大学昝道广"）

return1

#drawallsamples

foriinrange（numSamples）:

markIndex=int（clusterAssment[i,0]）#为样本指定颜色

（dataSet[i,0],dataSet[i,1],mark[markIndex]）

mark=['Dr','Db','Dg','Dk','^b','+b','sb','db','

#drawthecentroids

foriinrange（k）:

（centroids[i,0],centroids[i,1],mark[i],markersize=10）

（'Distributiondiagram'）

（）

附录三迭代次数与目标函数关系

第0次迭代：

目标函数=

第1次迭代：

目标函数=

第2次迭代：

目标函数=

第3次迭代：

目标函数=

第4次迭代：

目标函数=

第5次迭代：

目标函数=

第6次迭代：

目标函数=

第7次迭代：

目标函数=

第8次迭代：

目标函数=235.

第9次迭代：

目标函数=

第10次迭代：

目标函数=

第11次迭代：

目标函数=

第12次迭代：

目标函数=

第13次迭代：

目标函数=

第14次迭代：

目标函数=

第15次迭代：

目标函数=

第16次迭代：

目标函数=

第17次迭代：

目标函数=

第18次迭代：

目标函数=

第19次迭代：

目标函数=

第20次迭代：

目标函数=

第21次迭代：

目标函数=

第22次迭代：

目标函数=

第23次迭代：

目标函数=

第24次迭代：

目标函数=

第25次迭代：

目标函数=

第26次迭代：

目标函数=

第27次迭代：

目标函数=

第28次迭代：

目标函数=

第29次迭代：

目标函数=

第30次迭代：

目标函数=

第31次迭代：

目标函数=

第32次迭代：

目标函数=

第33次迭代：

目标函数=

第34次迭代：

目标函数=

第35次迭代：

目标函数=

第36次迭代：

目标函数=

第37次迭代：

目标函数=

第38次迭代：

目标函数=

第39次迭代：

目标函数=

第40次迭代：

目标函数=

第41次迭代：

目标函数=

第42次迭代：

目标函数=

第43次迭代：

目标函数=

第44次迭代：

目标函数=

第45次迭代：

目标函数=

第46次迭代：

目标函数=204.

第47次迭代：

目标函数=

第48次迭代：

目标函数=178.

第49次迭代：

目标函数=

第50次迭代：

目标函数=

第51次迭代：

目标函数=

第52次迭代：

目标函数=

第53次迭代：

目标函数=

第54次迭代：

目标函数=

第55次迭代：

目标函数=

第56次迭代：

目标函数=

第57次迭代：

目标函数=

第58次迭代：

目标函数=

第59次迭代：

目标函数=186.

第60次迭代：

目标函数=

第61次迭代：

目标函数=

第62次迭代：

目标函数=

第63次迭代：

目标函数=

第64次迭代：

目标函数=

第65次迭代：

目标函数=

第66次迭代：

目标函数=

第67次迭代：

目标函数=

第68次迭代：

目标函数=

第69次迭代：

目标函数=

第70次迭代：

目标函数=

第71次迭代：

目标函数=187.

第72次迭代：

目标函数=

第73次迭代：

目标函数=

第74次迭代：

目标函数=

第75次迭代：

目标函数=

第76次迭代：

目标函数=

第77次迭代：

目标函数=

第78次迭代：

目标函数=

第79次迭代：

目标函数=

第80次迭代：

目标函数=

第81次迭代：

目标