ハミング距離に基づく遷移確率を用いたPSOによるグラフ色塗り問題の解法 PSO Algorithm with Transition Probability Based on Hamming Distance for Solving Planar Graph Coloring Problem

この論文にアクセスする

この論文をさがす

著者

    • 青木 拓也 Takuya Aoki
    • 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻 Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba
    • 狩野 均 Hitoshi Kanoh
    • 筑波大学システム情報系情報工学域 Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba

抄録

本論文では,Particle Swarm Optimization (PSO) を用いた,グラフ色塗り問題の解法を提案する.PSO は本来,連続値変数の最適化問題に対して提案された多点探索手法である.そのため,離散値変数の最適化問題に直接適応することは難しい.PSO の速度を遷移確率で表現した研究があるが,距離の概念を考慮していない.本手法は探索点 (解候補) 間の距離をハミング距離で表現し,その距離に比例した遷移確率を導入した.ランダムに作成したグラフ色塗り問題を用いて,本手法と GA および従来の遷移確率を用いた PSO との比較実験を行った.その結果,本手法は正解率と探索速度において従来手法よりも優れていることを確認した.In this paper, we propose a PSO algorithm with transition probability based on hamming distance for solving planar graph coloring problems. The first version of PSO was intended to handle only continuous optimization problems. Then, to apply PSO to discrete problems, the standard arithmetic operators of PSO are required to be redefined over discrete space. Chin et al (2010) introduced transition probability into PSO to settle this problem, but this model does not consider the concept of distance. 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 correction coloring rate and smaller average iterations than a Genetic Algorithm and the conventional PSO.

In this paper, we propose a PSO algorithm with transition probability based on hamming distance for solving planar graph coloring problems. The first version of PSO was intended to handle only continuous optimization problems. Then, to apply PSO to discrete problems, the standard arithmetic operators of PSO are required to be redefined over discrete space. Chin et al (2010) introduced transition probability into PSO to settle this problem, but this model does not consider the concept of distance. 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 correction coloring rate and smaller average iterations than a Genetic Algorithm and the conventional PSO.

収録刊行物

  • 研究報告数理モデル化と問題解決(MPS)

    研究報告数理モデル化と問題解決(MPS) 2014-MPS-100(8), 1-6, 2014-09-18

    一般社団法人情報処理学会

各種コード

  • NII論文ID(NAID)
    110009822924
  • NII書誌ID(NCID)
    AN10505667
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • データ提供元
    NII-ELS  IPSJ 
ページトップへ