局所探索法の普遍的探索特性の描出

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

初年度に得られた知見をふまえ,アニーリング法(SA)を典型とする閾値関数を用いる局所探索法の有限時間における解探索特性が,関数形の詳細,技法の構成によらず,ガラス形成物質のダイナミクスとのアナロジーから統一的に説明されることの検証を,種々の閾値関数,機能構成の系に対して行った.閾値関数を特徴付けるパラメータが最適化に影響力をもつ値を有すること,すなわちベイスン間の遷移ダイナミクスから検知されるガラス転移相当温度を一般的に認め得ることを確認した.さらに,機能構成に注目した既存技法の分類を行うとともに,大域的に単峰な景観構造を有するとみられる巡回セールスマン問題(TSP)のSAによる求解を参照系に採り,一方では機能構成を等しく設計した異種技法への対象拡大にともなう,他方では景観構造の大域的多峰化にともなう,解探索特性の変化の観察を通して,普遍特性の描出に資する観点の明確化を図った.主たる知見として,ランダムなTSPの求解において,メトロポリスアルゴリズム(MA)による局所探索を行う探索空間平滑化法におけるベイスン間遷移ダイナミクスの平滑化パラメータ依存性が,MAにおけるそれの温度依存性と定性的に等しく,これらの探索特性が機能構成から第一義的に説明されること,SAの分割統治機能の説明に用いられた特殊なTSPの1パラメータ化により,景観構造の1つの大域的多峰化が実現され,最適化に要するベイスン間ならびにメタベイスン間の二種類の緩和ダイナミクスと,ガラス研究におけるエネルギー景観上の二種類の緩和描像との間にもアナロジーが認められること,などを得た.これらの知見は,探索の機能構成やガラスとのアナロジーに着目する本研究で採るアプローチの,局所探索法の普遍的探索特性の描出,設計根拠/指針の明確化における有効性を示すものと考える.