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

• 学术探讨 • 上一篇    下一篇

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

潘 锐1,朱大铭2,董林光1,3,董 颖1,3   

  1. 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 Rui1,ZHU Da-ming2,DONG Lin-guang1,3,DONG Ying1,3   

  1. 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

摘要: 为有效求解大规模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