| 一种求解厌恶型p-中位问题的混合进化算法 |
| |
| 引用本文： | 林耿.一种求解厌恶型p-中位问题的混合进化算法[J].浙江大学学报(理学版),2018,45(1):29. |
| |
| 作者姓名： | 林耿 |
| |
| 作者单位： | 闽江学院 数学系, 福建 福州 350108 |
| |
| 基金项目： | 国家自然科学基金资助项目（11301255）；福建省自然科学基金资助项目（2016J01025）；福建省高校新世纪优秀人才支持计划项目. |
| |
| 摘 要： | 厌恶型p-中位问题是一个NP-困难问题.提出了一种求解厌恶型p-中位问题的混合进化算法.首先，通过贪心随机自适应搜索方法和随机构造方法产生初始种群.然后，利用搜索过程中收集到的全局信息和局部信息构造新解，期间注意提高搜索的多样性，避免早熟.最后，针对厌恶型p-中位问题的特点，构造基于约束交换邻域的局部搜索算法，提高了算法的局部搜索能力.通过求解72个标准测试例子以检验算法的性能，发现该算法在较短时间内得到了高质量解，优于现有算法.
|
| 关 键 词： | 厌恶型p-中位问题 进化算法 分布估计算法 局部搜索 启发式算法 |
| 收稿时间： | 2016-12-05 |
A hybrid evolutionary algorithm for solving the obnoxious p-median problem |
| |
| LIN Geng.A hybrid evolutionary algorithm for solving the obnoxious p-median problem[J].Journal of Zhejiang University(Sciences Edition),2018,45(1):29. |
| |
| Authors: | LIN Geng |
| |
| Affiliation: | Department of Mathematics, Minjiang University, Fuzhou 350108, China |
| |
| Abstract: | The obnoxious p-median problem is known to be NP-hard.A hybrid evolutionary algorithm is proposed to solve the obnoxious p-median problem.Firstly,an initial population is generated by a greedy randomized adaptive search procedure and a random constructive procedure.Then,to diversify the search and avoid the premature convergence,the proposed algorithm uses the global information and the local information gathered during the search to generate new solutions.Finally,according to the characteristics of obnoxious p-median problem,a constrained swap neighborhood based on local search procedure is developed to enhance the exploitation of the algorithm.Seventy two benchmark instances are tested to demonstrate the effectiveness of the algorithm.Experimental results and comparison with the existing algorithms show that the proposed algorithm is able to obtain high quality solutions in significantly less CPU time. |
| |
| Keywords: | obnoxious p-median problem evolutionary algorithm estimation of distribution algorithm local search heuristic algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《浙江大学学报(理学版)》下载全文 |
