MTPSO algorithm for solving planar graph coloring problem

被引：29

作者：

Hsu, Ling-Yuan ^{[1
]}

Horng, Shi-Jinn ^{[1
,2
]}

Fan, Pingzhi ^{[2
]}

Khan, Muhammad Khurram ^{[3
]}

Wang, Yuh-Rau ^{[4
]}

Run, Ray-Shine ^{[5
]}

Lai, Jui-Lin ^{[5
]}

Chen, Rong-Jian ^{[5
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Comp Sci & Informat Engn, Taipei 106, Taiwan

[2] SW Jiaotong Univ, Inst Mobile Commun, Chengdu 610031, Sichuan, Peoples R China

[3] King Saud Univ, Ctr Excellence Informat Assurance, Riyadh 11451, Saudi Arabia

[4] St Johns Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

[5] Natl United Univ, Dept Elect Engn, Miaoli 36003, Taiwan

来源：

EXPERT SYSTEMS WITH APPLICATIONS | 2011年 / 38卷 / 05期

关键词：

Planar graph coloring; Four-color problem; Modified turbulent particle swarm; optimization; Walking one; PSO;

D O I：

10.1016/j.eswa.2010.10.084

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we proposed a modified turbulent particle swarm optimization (named MTPSO) model for solving planar graph coloring problem based on particle swarm optimization. The proposed model is consisting of the walking one strategy, assessment strategy and turbulent strategy. The proposed MTPSO model can solve the planar graph coloring problem using four-colors more efficiently and accurately. Compared to the results shown in Cui et al. (2008), not only the experimental results of the proposed model can get smaller average iterations but can get higher correction coloring rate when the number of nodes is greater than 30. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：5525 / 5531

页数：7

共 26 条

[21] TAIFEX and KOSPI 200 forecasting based on two-factors high-order fuzzy time series and particle swarm optimization [J].

Park, Jin-Il ;

Lee, Dae-Jong ;

Song, Chang-Kyu ;

Chun, Myung-Geun .

EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (02) :959-967

[22]

SALARI E, 2005, 2005 ICSC C COMP INT

[23]

SANGHYUCK A, 2003, P 2003 JOINT C 4 INT, V3, P1849

[24] A modified particle swarm optimizer [J].

Shi, YH ;

Eberhart, R .

1998 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION - PROCEEDINGS, 1998, :69-73

[25] The graph coloring problem:: A neuronal network approach [J].

Talavan, Pedro M. ;

Yanez, Javier .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (01) :100-111

[26] The robust coloring problem [J].

Yáñez, J ;

Ramírez, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 148 (03) :546-558

← 1 2 3 →