Development of High Performance Metaheuristics for Combinatorial Optimization Problems and Its Evaluations

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

組合せ最適化問題の代表例である最大クリーク問題(MCP)および2次割当問題(QAP),通信・ネットワーク関連の問題であるノード配置問題(NPP)に対する高性能なメタ戦略アルゴリズムの開発と評価を行った.MCPにおいては,最近開発した強力な局所探索法を反復局所探索法およびMemetic アルゴリズムの枠組みに導入した高性能メタ戦略を開発し,その性能を評価した.その結果,既存アルゴリズムとの比較において高い探索性能を有することを明らかにした.またQAP およびNPP に対しても同様のアプローチが可能であり,高性能な反復局所探索法を開発した.その他,バイオインフォマティクス分野におけるアミノ酸配列のマルチプルアライメントのアルゴリズムとして,クリークを考慮した解構築法を開発した.加えて,関数最適化問題に対するメタ戦略であるParticle Swarm Optimization法やメタ戦略に導入を試みるための学習法の検討などを通して,本研究課題をより洗練化するための模索も同時に行った.以上の研究成果は学術論文誌,国際会議,国内で開催の学会・研究会等で発表した.