WEKO3
アイテム
類似度を用いたArtificial Bee Colonyによるグラフ色塗り問題の解法
https://ipsj.ixsq.nii.ac.jp/records/192812
https://ipsj.ixsq.nii.ac.jp/records/192812aa7fc1e2-8c0a-4fde-a6d4-87493437c35a
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2018 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2018-12-10 | |||||||||||
タイトル | ||||||||||||
タイトル | 類似度を用いたArtificial Bee Colonyによるグラフ色塗り問題の解法 | |||||||||||
言語 | ||||||||||||
言語 | 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 | ||||||||||||
著者名 |
冨樫, 勇哉
× 冨樫, 勇哉
× アランニャ, クラウス
× 狩野, 均
|
|||||||||||
論文抄録 | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | 本稿では,Artificial Bee Colony (ABC) を用いた,グラフ色塗り問題の解法を提案する.ABC は本来,連続値を扱う問題に対する手法であるため,組合せ最適化問題や制約充足問題に適用するためには離散変数の扱いが問題となる.従来,Sigmoid 関数を用いた離散化方法が提案されているが性能は十分といえない.本稿では,ABC の離散化に加え,解候補間の類似度を導入した手法を提案する.類似度を導入することにより,局所探索をしつつ,仮想的に島モデルをつくり探索空間全体を効率よく探索することを狙いとしたものである.比較実験として,グラフ色塗り問題を用いて,本手法と Sigmoid 関数を用いた ABC および遺伝的アルゴリズムとの比較を行った.その結果,本手法が成功数と探索速度において,従来手法より優れていることを確認した. | |||||||||||
書誌レコードID | ||||||||||||
収録物識別子タイプ | NCID | |||||||||||
収録物識別子 | AN10505667 | |||||||||||
書誌情報 |
研究報告数理モデル化と問題解決(MPS) 巻 2018-MPS-121, 号 7, p. 1-6, 発行日 2018-12-10 |
|||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 2188-8833 | |||||||||||
Notice | ||||||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
出版者 | ||||||||||||
言語 | ja | |||||||||||
出版者 | 情報処理学会 |