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 条

[1] A graph coloring heuristic using partial solutions and a reactive tabu scheme [J].

Bloechliger, Ivo ;

Zufferey, Nicolas .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (03) :960-975

[2] An ant-based algorithm for coloring graphs [J].

Bui, Thang N. ;

Nguyen, ThanhVu H. ;

Patel, Chirag M. ;

Phan, Kim-Anh T. .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (02) :190-200

[3] REGISTER ALLOCATION VIA COLORING [J].

CHAITIN, GJ ;

AUSLANDER, MA ;

CHANDRA, AK ;

COCKE, J ;

HOPKINS, ME ;

MARKSTEIN, PW .

COMPUTER LANGUAGES, 1981, 6 (01) :47-57

[4] THE PRIORITY-BASED COLORING APPROACH TO REGISTER ALLOCATION [J].

CHOW, FC ;

HENNESSY, JL .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1990, 12 (04) :501-536

[5] 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

[6] AN INTRODUCTION TO TIMETABLING [J].

DEWERRA, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 19 (02) :151-162

[7] An improved ant colony optimisation heuristic for graph colouring [J].

Dowsland, Kathryn A. ;

Thompson, Jonathan M. .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (03) :313-324

[8]

Eberhart R., 1995, MHS 95, P39, DOI [DOI 10.1109/MHS.1995.494215, 10.1109/MHS.1995.494215]

[9]

EBERHART RC, 1998, COMP GENETIC ALGORIT, V1447

[10] Comparison among five evolutionary-based optimization algorithms [J].

Elbeltagi, E ;

Hegazy, T ;

Grierson, D .

ADVANCED ENGINEERING INFORMATICS, 2005, 19 (01) :43-53

← 1 2 3 →