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

doi:10.3778/j.issn.1002-8331.2009.20.011

计算机工程与应用 ›› 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，韩云⁴

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-shun^1，2，3，XIA Bin ^1，2，PAN Cong ^1，2，3，LV Zhi-qiang ^1，3，HAN Yun ⁴

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

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

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

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

陈红顺^1，2，3，夏斌^1，2，潘聪^1，2，3，吕志强^1，3，韩云⁴. 粒子群优化算法求解地图四色问题
[J]. 计算机工程与应用, 2009, 45(20): 39-41.

CHEN Hong-shun^1，2，3，XIA Bin ^1，2，PAN Cong ^1，2，3，LV Zhi-qiang ^1，3，HAN Yun ⁴. Particle Swarm Optimization algorithm for solving four-coloring map problem[J]. Computer Engineering and Applications, 2009, 45(20): 39-41.

[1]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[2]	陈万芬，王宇嘉，林炜星. 异构集成代理辅助多目标粒子群优化算法[J]. 计算机工程与应用, 2021, 57(23): 71-80.
[3]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[4]	廖玮霖，程杉，尚冬冬，魏昭彬. 多策略融合的粒子群优化算法[J]. 计算机工程与应用, 2021, 57(1): 69-76.
[5]	张鑫1，邹德旋1，肖鹏1，喻秋2. 自适应简化粒子群优化算法及其应用[J]. 计算机工程与应用, 2019, 55(8): 250-263.
[6]	郑朝鑫1，2，董晨1，3，贺国荣1，3，陈荣忠1，3，熊子奇1，3. 基于改进粒子群算法的动态3D实时建模技术[J]. 计算机工程与应用, 2019, 55(5): 65-71.
[7]	马炫，刘栋，胡家鑫. 求解必经点k条最优路径问题的粒子群优化算法[J]. 计算机工程与应用, 2019, 55(20): 89-94.
[8]	郭世伟，孟昱煜，陈绍立. 改进的PSOGM算法在动态关联规则挖掘中的应用[J]. 计算机工程与应用, 2018, 54(8): 160-165.
[9]	胡震，邹德旋，张旭. R-dPSO算法及其在ATO控制策略中的应用[J]. 计算机工程与应用, 2018, 54(24): 212-220.
[10]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[11]	何明慧1，徐怡1，2，王冉1，胡善忠1. 改进的粒子群算法优化神经网络及应用[J]. 计算机工程与应用, 2018, 54(19): 107-113.
[12]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[13]	常红伟1，夏克文1，2，白建川1，2，牛文佳1，武盼盼1. 采用云量子PSO的属性约简方法[J]. 计算机工程与应用, 2018, 54(10): 99-104.
[14]	杨小东，康雁，柳青，孙金文. 求解作业车间调度问题的禁忌分布估计算法[J]. 计算机工程与应用, 2017, 53(7): 147-153.
[15]	南敬昌，田娜. 基于改进粒子群算法的模糊小波神经网络建模[J]. 计算机工程与应用, 2017, 53(3): 120-123.

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

Particle Swarm Optimization algorithm for solving four-coloring map problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics