p-center解决方案

1问题：P-Center问题P-Center问题摘要问题：从一个点集合中选择p个点作为中心点，并把其他分配到某个选择的点，使得所有点到其对应的中心点的距离加起来最小。针对问题，分析得出p-center问题实质为选址问题。其研究背景为工厂的选址，属于运筹学中经典问题之一。运用智能算法中模拟退火随机局域搜索算法进行求解最小值。具体步骤为：由于题目中未提供点集合，所以首先通过文献查阅[1]和生活实际得到可靠的二维数据点分布，即表示一个点集合，存储方式为文件存储（data.txt）；其次加载点集合数据，采用模拟退火算法随机局域搜索算法[2]进行处理：1）初始化：中心点个数4p，温度1000T，温度缩减系数0.999a，最大迭代次数200Iter。解释：由于P-Center问题是以工厂的选址问题，加上编写的二维数据的分布情况，所以建立工厂的数量为事先已知条件，即4p；初试温度的设置是影响搜索性能重要因素之一。初始化温度高，则搜索到全局最优值的可能性大，但计算时间大幅度增加；反之，缩短了计算时间，但性能并不优越。所以采用多次实验的方式确定温度1000T；为了保证较大的搜索空间，所以让系数接近于1；经过多次实验，确定迭代次数200Iter，此时结果较为理想。2）迭代200Iter次，循环第三步到第四步。3）从临域中选择最佳的解，即确定最优值：产生新值_xnewxx；增量(_)()ffxnewfx；若0f，则接受_xnew作为新解，否者以概率exp(/())fkT接受_xnew作为新解。4）T逐渐减少，且minTT，最后跳至第二步。5）得到距离最小值然后通过模拟退火局部搜索算法，得迭代情况为：2最后通过模拟退火局部搜索算法，得出分配图为：得出四个粗五角星为各自的中心点，其中颜色相同的属于各自颜色的中心点，即相同颜色距离各自中心点最短。通过Python得出最近距离为：102.401974373问题扩充：针对P-Center问题，还可以通过k-means聚类算法[3]进行解决，得到与最近搜索算法同样的结果。关键词：P-Center选址问题模拟退火随机局域搜索算法K-Means聚类算法目录P-Center问题............................................................................................................................1摘要............................................................................................................................................11问题重述.................................................................................................................................42数据预处理.............................................................................................................................42.1数据来源......................................................................................................................42.2数据预处理方法..........................................................................................................42.3数据选取参考原则......................................................................................................43问题分析.................................................................................................................................43.1问题..............................................................................................................................44问题假设................................................................................................................................55符号说明................................................................................................................................56模型的建立与求解................................................................................................................56.1解法一..........................................................................................................................56.1.1模拟退火随机局部搜索算法...........................................................................56.1.2算法求解...........................................................................................................76.2解法二..........................................................................................................................86.2.1K-Means聚类算法............................................................................................86.2.2算法求解...........................................................................................................87模型的评价.............................................................................................................................98参考文献................................................................................................................................93附录..........................................................................................................................................10附录一模拟退火随机局域搜索算法Python代码......................................................10附录二聚类算法Python代码......................................................................................12附录三迭代次数与目标函数关系................................................................................15附录四结论图................................................................................................................2041问题重述选址问题是运筹学中经典的问题之一。经典的选址问题包括连续选址问题、离散选址问题、P-Median问题以及P-Center问题等。该问题属于P-Center问题，从一个点集合中选择p个点作为中心点，并把其他点分配到某个选择的点，使得所有点到其对应中心点的距离加起来最小。2数据预处理注：数据存储形式为：data.txt，可在附件一中查看2.1数据来源（1）文献查阅（2）生活实际2.2数据预处理方法（1）数据选取：去除无效数据以及噪声数据。（2）数据整合：将若干个数据库整合成一个数据存储结构。（3）数据替代：将杂乱数据替代成易处理数据。（4）数据变换：将原始数据转换为适合任务定价的形式。2.3数据选取参考原则（1）统一数据源编码。（2）清除唯一属性。（3）清除重复属性。（4）清除可忽略字段。（5）进一步处理：清除异常数据，去除附带噪声数据，填充空缺值、丢失值。3问题分析3.1问题首先，通过文献查阅和生活实际得到可靠的二维数据点分布，将此二维分布作为数据点集合，然后通过模拟退火最近搜索算法[4]进行迭代优化，最终得到所有点到其中心点的距离。54问题假设1.假设根据数据特征或者政策（例如工厂政策）确定，即已经确定P-Center中的p中心个数。2.假设点集合为二维集合，不包括任何三维或者多维信息。5符号说明符号说明x可行解_xnew迭代更新后的解()pf概率条件下更新()fx优化目标函数T模拟退火温度值p中心点个数a温度缩减系数Iter最大迭代次数6模型的建立与求解选址问题目前有多种求解方法，大致分为定性和定量两类：定性的方法主要是结合层次分析法和模糊综合法对各方案进行指标评价，最终得出最优选址；定量的方法主要是松弛算法和启发式算法以及两者的结合。而本题解决的是P-Center问题，即使用启发式算法-智能算法模拟退火随机局部搜索算法[5]进行解决。6.1解法一6.1.1模拟退火随机局部搜索算法模拟退火算法是一种贪心算法，但是其搜索过程引入了随机因素。在迭代更新可行解时，以一定概率来接受一个比当前解要差的解，因此有可能会跳出局部最优解，达到全局最优解，其搜索原理如下图：6图1模拟退火随机局部搜索算法示意图假定当前可行解为x，迭代更新后的解为_xnew，那么对应的“能量差”定义为：(_)()ffxnewfx以相应概率接受新值，此概率为：exp()最小值优化问题()exp()最大值优化问题fkTpffkT