組合せ最適化問題に対するメタ戦略の総合的評価とハイブリッド型戦略の構築

点击翻译按钮获取中文摘要

近年、計算困難な問題である組合せ最適化問題に対してGenetic Algorithm、Simulated Annealing、Tabu Searchなどに代表されるメタヒューリスティックにより有効な手法が種々提案されている。しかし、これらの手法の各問題に対する優劣は明確ではなく、各応用分野で利用するための総合的な評価分析と効果的な手法の検討が望まれている。そこで、グラフ分割問題、巡回セールスマン問題など試金石とされている代表的な組合せ最適化問題をターゲットとしメタヒューリスティックアルゴリズムの性能を分析する。まず、以上の問題に対して標準的なGenetic Algorithm、Simulated Annealing、Tabu Searchおよびアントシステムアルゴリズム等を構成する。以上の各算法について数値実験を行い、各問題に対する特性と、アルゴリズムの優劣を判定する。それによると、グラフの多分割問題ではSimulated AnnealingがTabu Searchをやや上回り、Genetic Algorithmにおいてはこの問題に対してはLocal Searchにも及ばない劣勢な解を求めるのにとどまった。最後に、実験によって得られた各アルゴリズムの特性より、より有効な戦略を結合したハイブリッド型のアルゴリズムを提案する。巡回セールスマン問題ではアントシステムアルゴリズムのフェロモン強化とTabuのハイブリッドによる改良型が有効な結果をもたらし、新たなメタヒューリスティックアルゴリズムの展開が期待される。また、並列計算パラダイムをメタヒューリスティックアルゴリズムに組み込んだ並列Tabu Searchアルゴリズムの構築を行い、その結果、従来のアルゴリズムに対して大幅な改善が示され、新たなメタヒューリスティックの計算パラダイムへの基盤となるものと考える。