ハミング距離に基づく遷移確率を用いたPSOによるグラフ色塗り問題の解法

• 青木 拓也

  筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻

• アランニャ クラウス

  筑波大学システム情報系情報工学域

• 狩野 均

  筑波大学システム情報系情報工学域

書誌事項

タイトル別名

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

抄録

本論文では,Particle Swarm Optimization (PSO) を用いた,グラフ色塗り問題の解法を提案する.PSO は本来,連続値変数の最適化問題に対して提案された多点探索手法である.そのため,離散値変数の最適化問題に直接適応することは難しい.PSO の速度を遷移確率で表現した研究があるが,距離の概念を考慮していない.本手法は探索点 (解候補) 間の距離をハミング距離で表現し,その距離に比例した遷移確率を導入した.ランダムに作成したグラフ色塗り問題を用いて,本手法と GA および従来の遷移確率を用いた PSO との比較実験を行った.その結果,本手法は正解率と探索速度において従来手法よりも優れていることを確認した.

収録刊行物

• 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告

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

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

詳細情報

• CRID: 1570854177882377984
• NII論文ID: 110009822924
• NII書誌ID: AN10505667
• ISSN: 09196072
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles