λ-branching factorにより解の多様性を維持する蟻コロニー最適化

• 芳賀光瑠

• 加藤昇平

抄録

巡回セールスマン（TSP）のようなNP困難な問題は現実社会で数多く存在し，これらの問題は計算量が莫大なため現在の計算機の処理能力を持ってもすべての組合せを計算することは不可能である．しかし，現実社会では長い時間をかけて最も良い解（最適解）を求める必要は少なく，短時間に最適解に十分近い準最適解の方が必要とされることが多い．そこで，本稿では収束速度を速めながら他の手法と比較し同質またはそれ以上の解を求めることを目的とするASwideを提案する．ASwideとは蟻同士が分泌するフェロモンによりコミュニケーションを行い餌への経路を最適化する一連の行動をモデル化した蟻コロニー最適化のフェロモン分泌式の部分を改良した手法である．その有効性を確認するために，巡回セールスマン問題のベンチマーク問題を用いて，複数の蟻コロニー最適化の類似手法と比較実験を行い，その有効性を確認する．また，解の探索中に局所解に陥ってしまうのを回避するため蟻コロニー最適化の終了判定に多く用いられるλ-branching factorの値により解に多様性を持たせる手法の提案も行う．こちらも上記実験と同様，巡回セールスマン問題のベンチマーク問題を用いた実験により，従来手法よりも解の質と収束速度が向上したことを確認する．

収録刊行物

• 研究報告知能システム（ICS）

  研究報告知能システム（ICS） 2013 (17), 1-8, 2013-03-11

詳細情報

• CRID: 1574231877641133440
• NII論文ID: 110009551532
• NII書誌ID: AA11135936
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles