連続型大域的最適化に対するメタヒューリスティクス

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

連続変数をもつ非凸関数の大域的最適化は非常に困難な問題であり,これまで様々な手法が提案されているが未だ実用上十分といえる段階には達していない.本研究は単体法やパターン探索法などの直接探索法を基礎にアニーリング法(焼きなまし法),遺伝的アルゴリズム,タブー探索法などのメタヒューリスティクスを構築するという,これまであまり考えられていないアイデアを用いることにより,連続型最適化問題に対する実用的な大域的最適化手法の開発を試みるものである.本年度は3年間にわたる研究期間の最終年度であり,これまでに得られた成果をさらに発展させ,いくつかの新たな研究成果を得ることができた.まず,組合せ最適化においてよく知られたメタヒューリスティクスであるタブー探索法を,連続的最適化のための古典的手法であるNelder-Mead法と新たに我々が開発した適応的パターン探索法という直接探索法を組み合わせた新しいアルゴリズムを開発した.この方法ではタブー領域に加えて準タブー領域という概念を導入することにより,性能の向上を図っている.この研究成果はEuropean Journal of Operational Researchに掲載される予定である.さらに,制約条件をもつ最適化問題を取り扱うために,非線形計画法において近年注目されているフィルター法の考え方を取り入れたアニーリング法のアルゴリズムを構築し,計算実験により,このアルゴリズムが制約付き大域的最適化問題に対して優れた性能を有することを明らかにした.