计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (20): 39-41.DOI: 10.3778/j.issn.1002-8331.2009.20.011

• 研究、探讨 • 上一篇    下一篇

粒子群优化算法求解地图四色问题

陈红顺1,2,3,夏 斌1,2,潘 聪1,2,3,吕志强1,3,韩 云4   

  1. 1.中国科学院 广州地球化学研究所,广州 510640
    2.中国科学院 地理信息产业发展中心,北京 100101
    3.中国科学院 研究生院,北京 100049
    4.南方数码科技有限公司,广州 510665
  • 收稿日期:2008-04-21 修回日期:2008-07-22 出版日期:2009-07-11 发布日期:2009-07-11
  • 通讯作者: 陈红顺

Particle Swarm Optimization algorithm for solving four-coloring map problem

CHEN Hong-shun1,2,3,XIA Bin 1,2,PAN Cong 1,2,3,LV Zhi-qiang 1,3,HAN Yun 4   

  1. 1.Guangzhou Institute of Geochemistry,Chinese Academy of Sciences,Guangzhou 510640,China
    2.Center for GIS Industry Development,Chinese Academy of Sciences,Beijing 100101,China
    3.Graduate University of Chinese Academy of Sciences,Beijing 100049,China
    4.South Digital Technology Co.Ltd(South Surveying & Mapping),Guangzhou 510665,China
  • Received:2008-04-21 Revised:2008-07-22 Online:2009-07-11 Published:2009-07-11
  • Contact: CHEN Hong-shun1

摘要: 针对地图四色问题,重新定义了粒子群优化算法中粒子的位置、速度及其运算规则,并融入了遗传算法的变异思想,在传统粒子群优化算法的基础上增加了变异算子。将改进后的粒子群优化算法在湖南省地图上进行仿真实验,结果表明改进后的算法在全局寻优能力方面有较大的提高,求解速度和稳定性方面也都取得了较为满意的效果。

关键词: 四色问题, 粒子群优化算法, 贪心算法, 组合优化

Abstract: Particle’s position,velocity and their operation rules in Particle Swarm Optimization(PSO) are redefined based on the characteristic of four-coloring map problem.A mutation operator is designed according to the mutation thought in Genetic Algorithm(GA).The improved algorithm is tested by coloring Hunan Province Administrative Map,and the results show that it is good at the ability of finding optimal value,the speed and the stability.

Key words: four-coloring problem, Particle Swarm Optimization(PSO), greedy algorithm, combinatorial optimization