組合せ最適化問題の解空間における上位構造に基づくメタヒューリステイクスの基礎検討

摘要

優れたメタヒューリステイクスの構築には，適切な集中 化・多様化の実現が重要となる。集中化とは短期的な解の 改善を目標として解空間の局所的な探索を行う戦略であり， 多様化とは長期的な解の改善を目標として解空間の大域的 な探索を行う戦略である。本研究では，長期的方針を有す る集中化・多様化の実現を目的とし，従来の探索点間の移 動戦略ではなく，局所的最適解が持つ引込み領域間の移動 戟略を提案する。この移動戦略は解空間における新たな大 域的構造（上位構造）の導入とその活用を与える。最後に ベンチマーク問題を用いて提案手法の性能を検証する。%Metaheuristics is a new paradigm that aims to obtain an approximate solution within a feasible computation time. To design the effective metaheuristics, strategies of intensification and diversification are essential. This paper proposes an algorithm that has long term policy for realizing intensification and diversification based on higher level structure in solution space. In order to verify the performance, the proposed algorithm is applied to some traveling salesman problems which are typical combinatorial optimization problems.