1问题：P-Center问题P-Center问题摘要问题：从一个点集合中选择p个点作为中心点，并把其他分配到某个选择的点，使得所有点到其对应的中心点的距离加起来最小。针对问题，分析得出p-center问题实质为选址问题。其研究背景为工厂的选址，属于运筹学中经典问题之一。运用智能算法中模拟退火随机局域搜索算法进行求解最小值。具体步骤为：由于题目中未提供点集合，所以首先通过文献查阅[1]和生活实际得到可靠的二维数据点分布，即表示一个点集合，存储方式为文件存储（data.txt）；其次加载点集合数据，采用模拟退火算法随机局域搜索算法[2]进行处理：1）初始化：中心点个数，温度，温度缩减系数，最大迭代次数。解释：由于P-Center问题是以工厂的选址问题，加上编写的二维数据的分布情况，所以建立工厂的数量为事先已知条件，即；初试温度的设置是影响搜索性能重要因素之一。初始化温度高，则搜索到全局最优值的可能性大，但计算时间大幅度增加；反之，缩短了计算时间，但性能并不优越。所以采用多次实验的方式确定温度；为了保证较大的搜索空间，所以让系数接近于1；经过多次实验，确定迭代次数，此时结果较为理想。2）迭代次，循环第三步到第四步。3）从临域中选择最佳的解，即确定最优值：产生新值；增量；若，则接受作为新解，否者以概率接受作为新解。4）逐渐减少，且，最后跳至第二步。5）得到距离最小值然后通过模拟退火局部搜索算法，得迭代情况为：2最后通过模拟退火局部搜索算法，得出分配图为：得出四个粗五角星为各自的中心点，其中颜色相同的属于各自颜色的中心点，即相同颜色距离各自中心点最短。通过Python得出最近距离为：102.401974373问题扩充：针对P-Center问题，还可以通过k-means聚类算法[3]进行解决，得到与最近搜索算法同样的结果。关键词：P-Center选址问题模拟退火随机局域搜索算法K-Means聚类算法目录P-Center问题...........................................................................................................................2摘要..........................................................................................................................................21问题重述...............................................................................................................................42数据预处理...........................................................................................................................42.1数据来源....................................................................................................................42.2数据预处理方法.........................................................................................................42.3数据选取参考原则.....................................................................................................43问题分析...............................................................................................................................43.1问题............................................................................................................................44问题假设...............................................................................................................................55符号说明...............................................................................................................................56模型的建立与求解................................................................................................................56.1解法一........................................................................................................................56.1.1模拟退火随机局部搜索算法...................................................................
