• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 论文 • 上一篇    下一篇

针对选址问题的一种遗传算法改进探究

邹贵祥,张飞舟   

  1. (北京大学地球与空间科学学院,北京 100871)
  • 收稿日期:2016-09-22 修回日期:2017-01-03 出版日期:2018-04-25 发布日期:2018-04-25

An improved genetic algorithm
for site selection problem

ZOU Guixiang,ZHANG Feizhou   

  1. (School of Earth and Space Science,Peking University,Beijing 100871,China)
  • Received:2016-09-22 Revised:2017-01-03 Online:2018-04-25 Published:2018-04-25

摘要:

选址问题是现代地理信息资源配置的重要研究领域之一,通用性强、鲁棒性高的遗传算法可以较好地解决这类问题。常用方法是使用二进制编码的遗传算法对栅格数据地图进行选址。为克服二进制编码的标准遗传算法在解决选址问题过程中易陷入早熟的缺点,在研究了使用不同算子、引入观测概念这两大类解决标准遗传算法陷入早熟问题的方法后,针对选址问题的特点,选择了引入多样性测度与应用小生境技术对遗传算法进行改进,并深入探究了引入多样性测度与应用小生境技术后,遗传算法解决选址问题的过程中准确性、在线性能函数、离线性能函数的改善;接着提出了进一步改进小生境技术的方法,使得遗传群体中的每一个个体都参与遗传操作,并且避免了两个相同的个体参与交叉操作的情况。最后通过地图选址实验,将改进的小生境遗传算法与多样性测度结合,成功提高了遗传算法的性能。
 

关键词: 选址问题, 遗传算法, 多样性测度, 小生境技术

Abstract:

Site selection problem is one of the most important research fields of modern geographic information resource distribution. Genetic algorithm with strong universality and robustness can solve this problem. A common approach is to use a binarycoded genetic algorithm to locate sites on a grid map. To deal with the early maturity of the standard binarycoded genetic algorithm, this paper studies two methods that use different operators and observation concepts to solve early maturity problem of the standard binarycoded genetic algorithm, chooses to introduce the diversity measure and niche technology to improve the genetic algorithm, further explores the improvement of accuracy, online performance function and offline performance function of genetic algorithm in solving the site selection problem, and proposes a method to improve the niche technique in order to make every individual in the genetic group involved in genetic operation and avoid the situation where two identical individuals are involved in crossover operation. Finally, in the site selection experiment, the improved niche genetic algorithm is combined with the diversity measure to improve the performance of genetic algorithm successfully.
 

Key words: site selection problem, genetic algorithm, diversity measure, niche technique