PSO Algorithm with Transition Probability Based on Hamming Distance for Graph Coloring Problem

被引：7

作者：

Aoki, Takuya ^{[1
]}

Aranha, Claus ^{[2
]}

Kanoh, Hitoshi ^{[2
]}

机构：

[1] Univ Tsukuba, Grad Sch Syst & Informat Engn, Dept Comp Sci, Tsukuba, Ibaraki 305, Japan

[2] Univ Tsukuba, Fac Engn Informat & Syst, Div Informat Engn, Tsukuba, Ibaraki 305, Japan

来源：

2015 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC 2015): BIG DATA ANALYTICS FOR HUMAN-CENTRIC SYSTEMS | 2015年

关键词：

Particle Swarm Optimization; Graph Coloring Probrem; Hamming distance; discrete PSO; OPTIMIZATION;

D O I：

10.1109/SMC.2015.341

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we propose a PSO algorithm with transition probability based on Hamming distance for solving planar graph coloring problems. PSO was originally intended to handle only continuous optimization problems. To apply PSO to discrete problems, the standard arithmetic operators of PSO need to be redefined over discrete space. In this work, we propose a new algorithm that uses transition probability based on Hamming distance into PSO. The experimental results show that the new algorithm can get higher success rate and smaller average iterations than a Genetic Algorithm and the conventional PSO.

引用

页码：1956 / 1961

页数：6

共 14 条

[1]

[Anonymous], 5 INT S INT MAN SYST

[2] A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems [J].

Chen, Wei-Neng ;

Zhang, Jun ;

Chung, Henry S. H. ;

Zhong, Wen-Liang ;

Wu, Wei-Gang ;

Shi, Yu-hui .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (02) :278-300

[3] Modified PSO algorithm for solving planar graph coloring problem [J].

Cui, Guangzhao ;

Qin, Limin ;

Liu, Sha ;

Wang, Yanfeng ;

Zhang, Xuncai ;

Cao, Xianghong .

PROGRESS IN NATURAL SCIENCE-MATERIALS INTERNATIONAL, 2008, 18 (03) :353-357

[4]

Deep Kusum, 2008, 2008 1st International Conference on Emerging Trends in Engineering and Technology (ICETET), P355, DOI 10.1109/ICETET.2008.163

[5]

Hembecker F, 2007, LECT NOTES COMPUT SC, V4431, P358

[6] THE HARDEST CONSTRAINT PROBLEMS - A DOUBLE-PHASE TRANSITION [J].

HOGG, T ;

WILLIAMS, CP .

ARTIFICIAL INTELLIGENCE, 1994, 69 (1-2) :359-377

[7] MTPSO algorithm for solving planar graph coloring problem [J].

Hsu, Ling-Yuan ;

Horng, Shi-Jinn ;

Fan, Pingzhi ;

Khan, Muhammad Khurram ;

Wang, Yuh-Rau ;

Run, Ray-Shine ;

Lai, Jui-Lin ;

Chen, Rong-Jian .

EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (05) :5525-5531

[8]

Kanoh H, 2013, LECT NOTES COMPUT SC, V7824, P256, DOI 10.1007/978-3-642-37213-1_27

[9]

Kennedy J., 1995, 1995 IEEE International Conference on Neural Networks Proceedings (Cat. No.95CH35828), P1942, DOI 10.1109/ICNN.1995.488968

[10]

Kennedy J, 1997, IEEE SYS MAN CYBERN, P4104, DOI 10.1109/ICSMC.1997.637339

← 1 2 →