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

• Item type: SIG Technical Reports(1)
• 公開日: 2014-09-18
• タイトル: ハミング距離に基づく遷移確率を用いたPSOによるグラフ色塗り問題の解法
• タイトル / 言語: en
• タイトル: PSO Algorithm with Transition Probability Based on Hamming Distance for Solving Planar Graph Coloring Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻
• 著者所属: 筑波大学システム情報系情報工学域
• 著者所属: 筑波大学システム情報系情報工学域
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba
• 著者名: 青木, 拓也; アランニャ, クラウス; 狩野, 均
• 著者名(英): Takuya, Aoki; Claus, Aranha; Hitoshi, Kanoh
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，Particle Swarm Optimization (PSO) を用いた，グラフ色塗り問題の解法を提案する．PSO は本来，連続値変数の最適化問題に対して提案された多点探索手法である．そのため，離散値変数の最適化問題に直接適応することは難しい．PSO の速度を遷移確率で表現した研究があるが，距離の概念を考慮していない．本手法は探索点 （解候補） 間の距離をハミング距離で表現し，その距離に比例した遷移確率を導入した．ランダムに作成したグラフ色塗り問題を用いて，本手法と GA および従来の遷移確率を用いた PSO との比較実験を行った．その結果，本手法は正解率と探索速度において従来手法よりも優れていることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2014-MPS-100, 号 8, p. 1-6, 発行日 2014-09-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会