求解k中间点问题的新局部搜索算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (4): 36-38.

求解k中间点问题的新局部搜索算法

潘锐¹,朱大铭²,董林光^1,3,董颖^1,3

1.山东省农村信用社联合社计算机网络中心，济南 250001
2.山东大学计算机科学与技术学院，济南 250061
3.山东大学齐鲁软件学院，济南 250061

收稿日期:2007-08-13 修回日期:2007-11-23 出版日期:2008-02-01 发布日期:2008-02-01
通讯作者: 潘锐

New local search algorithm for k-median problem

PAN Rui¹,ZHU Da-ming²,DONG Lin-guang^1,3,DONG Ying^1,3

1.Computer Network Center，Shandong Rural Credit Union，Ji’nan 250001，China
2.School of Computer Science and Technology，Shandong University，Ji’nan 250061，China
3.Qilu Software College，Shandong University，Ji’nan 250061，China

Received:2007-08-13 Revised:2007-11-23 Online:2008-02-01 Published:2008-02-01
Contact: PAN Rui

摘要/Abstract

摘要： 为有效求解大规模k中间点问题，利用适应度距离相关性方法分析，发现该问题局部最优解的适应度与其到全局最优解的距离无太大关系，且多个局部最优解求交所得子集以极大概率包含全局最优解中的元素，进而提出一种基于求交操作的k中间点问题局部搜索算法。实验结果表明该算法在求解质量上与目前已知算法相比有较大改进。

关键词: k-中间点, 组合优化, 局部搜索

Abstract: Aiming at effectively solving the large-scale k-median problem，by using fitness distance correlation method，this paper finds that there is little relation between the fitness of local minimum and the distance of local minimum to global minimum，and that the intersection of local minima contains the members in global minimum with a high probability.Then a intersection-based local search algorithm for k-median problem is proposed.Finally，the experimental results show that the algorithm outperforms the known algorithms in the quality of solutions.

Key words: k-median, combinatorial optimization, local search

潘锐¹,朱大铭²,董林光^1,3,董颖^1,3. 求解k中间点问题的新局部搜索算法[J]. 计算机工程与应用, 2008, 44(4): 36-38.

PAN Rui¹,ZHU Da-ming²,DONG Lin-guang^1,3,DONG Ying^1,3. New local search algorithm for k-median problem[J]. Computer Engineering and Applications, 2008, 44(4): 36-38.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[4]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[5]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[6]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[7]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[8]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[9]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[10]	杨小东，康雁，柳青，孙金文. 求解作业车间调度问题的禁忌分布估计算法[J]. 计算机工程与应用, 2017, 53(7): 147-153.
[11]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[12]	洪剑珂1，张峥华2，许贵平2. 基于加强概率控制策略的SAT局部搜索算法[J]. 计算机工程与应用, 2017, 53(14): 56-60.
[13]	王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.
[14]	伍艳莲1，2，姜海燕1，2，庄嘉祥1，郭小清1，许一骅1. 精英策略个体优势遗传算法研究[J]. 计算机工程与应用, 2016, 52(7): 143-149.
[15]	林耿1，徐梅琴2. 图的最大二等分问题的一种离散填充函数算法[J]. 计算机工程与应用, 2016, 52(5): 27-32.