2024-03-28T23:00:26Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002009652023-04-27T10:00:04Z01164:02735:09724:09991
集団の多様性に着目したArtificial Bee Colonyによる3色グラフ色塗り問題の解法jpnhttp://id.nii.ac.jp/1001/00200872/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=200965&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Information Processing Society of Japan筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻筑波大学システム情報系情報工学域筑波大学システム情報系情報工学域西尾, 祐紀アランニャ, クラウス狩野, 均本論文では,Artificial Bee Colony (ABC) を用いた,グラフ色塗り問題の解法を提案する.ABC は本来,連続値を扱う問題に対する手法であるため,組合せ最適化問題や制約充足問題に適用するためには離散変数の扱いが問題となる.従来,Sigmoid 関数を用いた離散化方法や部分解を用いた方法が提案されているが性能は十分といえない.本論文では,ABC の離散化に加え,従来手法では行われていない解同士が離れる動きを実装した.これは,集団の多様性を維持することで探索空間を広く効率的に探索することを狙いとしたものである.比較実験として,グラフ色塗り問題を用いて本手法と従来手法の ABC との比較を行なった.その結果,本手法が成功数と探索速度において,従来手法より優れていることを確認した.AN10505667研究報告数理モデル化と問題解決(MPS)2019-MPS-12612162019-12-042188-88332019-11-29