p_center解决方案.doc

《p_center解决方案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、问题：P-Center问题P-Center问题摘要问题：从一个点集合中选择p个点作为中心点，并把其他分配到某个选择的点，使得所有点到其对应的中心点的距离加起来最小。针对问题，分析得出p-center问题实质为选址问题。其研究背景为工厂的选址，属于运筹学中经典问题之一。运用智能算法中模拟退火随机局域搜索算法进行求解最小值。具体步骤为：由于题目中未提供点集合，所以首先通过文献查阅[1]和生活实际得到可靠的二维数据点分布，即表示一个点集合，存储方式为文件存储（data.txt）；其次加载点集合数据，采用模拟退火算法随机局域搜索算法[2]进行

2、处理：1）初始化：中心点个数，温度，温度缩减系数，最大迭代次数。解释：由于P-Center问题是以工厂的选址问题，加上编写的二维数据的分布情况，所以建立工厂的数量为事先已知条件，即；初试温度的设置是影响搜索性能重要因素之一。初始化温度高，则搜索到全局最优值的可能性大，但计算时间大幅度增加；反之，缩短了计算时间，但性能并不优越。所以采用多次实验的方式确定温度；为了保证较大的搜索空间，所以让系数接近于1；经过多次实验，确定迭代次数，此时结果较为理想。2）迭代次，循环第三步到第四步。343）从临域中选择最佳的解，即确定最优值：产生新值；增量

3、；若，则接受作为新解，否者以概率接受作为新解。4）逐渐减少，且，最后跳至第二步。5）得到距离最小值然后通过模拟退火局部搜索算法，得迭代情况为：最后通过模拟退火局部搜索算法，得出分配图为：得出四个粗五角星为各自的中心点，其中颜色相同的属于各自颜色的中心点，即相同颜色距离各自中心点最短。通过Python得出最近距离为：102.401974373问题扩充：针对P-Center问题，还可以通过k-means聚类算法[3]进行解决，得到与最近搜索算法同样的结果。关键词：P-Center选址问题模拟退火随机局域搜索算法K-Means聚类算法目录P

4、-Center问题2摘要21问题重述42数据预处理42.1数据来源42.2数据预处理方法42.3数据选取参考原则4343问题分析43.1问题44问题假设55符号说明56模型的建立与求解56.1解法一56.1.1模拟退火随机局部搜索算法56.1.2算法求解76.2解法二86.2.1K-Means聚类算法86.2.2算法求解87模型的评价98参考文献9附录10附录一模拟退火随机局域搜索算法Python代码10附录二聚类算法Python代码12附录三迭代次数与目标函数关系15附录四结论图20341问题重述选址问题是运筹学中经典的问题之一。经

5、典的选址问题包括连续选址问题、离散选址问题、P-Median问题以及P-Center问题等。该问题属于P-Center问题，从一个点集合中选择p个点作为中心点，并把其他点分配到某个选择的点，使得所有点到其对应中心点的距离加起来最小。2数据预处理注：数据存储形式为：data.txt，可在附件一中查看2.1数据来源（1）文献查阅（2）生活实际2.2数据预处理方法（1）数据选取：去除无效数据以及噪声数据。（2）数据整合：将若干个数据库整合成一个数据存储结构。（3）数据替代：将杂乱数据替代成易处理数据。（4）数据变换：将原始数据转换为适合任务

6、定价的形式。2.3数据选取参考原则（1）统一数据源编码。（2）清除唯一属性。（3）清除重复属性。（4）清除可忽略字段。（5）进一步处理：清除异常数据，去除附带噪声数据，填充空缺值、丢失值。343问题分析3.1问题首先，通过文献查阅和生活实际得到可靠的二维数据点分布，将此二维分布作为数据点集合，然后通过模拟退火最近搜索算法[4]进行迭代优化，最终得到所有点到其中心点的距离。4问题假设1.假设根据数据特征或者政策（例如工厂政策）确定，即已经确定P-Center中的p中心个数。2.假设点集合为二维集合，不包括任何三维或者多维信息。5符号说明

7、符号说明可行解迭代更新后的解概率条件下更新优化目标函数模拟退火温度值中心点个数温度缩减系数最大迭代次数6模型的建立与求解34选址问题目前有多种求解方法，大致分为定性和定量两类：定性的方法主要是结合层次分析法和模糊综合法对各方案进行指标评价，最终得出最优选址；定量的方法主要是松弛算法和启发式算法以及两者的结合。而本题解决的是P-Center问题，即使用启发式算法-智能算法模拟退火随机局部搜索算法[5]进行解决。6.1解法一6.1.1模拟退火随机局部搜索算法模拟退火算法是一种贪心算法，但是其搜索过程引入了随机因素。在迭代更新可行解时，以一

8、定概率来接受一个比当前解要差的解，因此有可能会跳出局部最优解，达到全局最优解，其搜索原理如下图：图1模拟退火随机局部搜索算法示意图假定当前可行解为，迭代更新后的解为，那么对应的“能量差”定义为： 以相应概率接受新值，此概