最適化問題の物性理論的解法に関する解析及び数値的研究

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

最適化問題に対して統計物理学の手法を用いて解析を行った。最適化問題はコストファンクションの最小値を与えられた拘束条件の下で探す問題であり、NP完全問題は厳密な解を求めることが難しいとされている。本研究においては筆者がこれまでに開発した実空間繰り込み群による解法についての考察をさらに進め、シミュレーテッドアニーリング法との組み合わせにより精度を改善する方法論の性質について調べた。また巡回セールスマン問題をSA法で解く場合の経路長の温度変化を統計力学の枠組みを用いて、あるところまで解析的に求めることに成功した。経路長を分配関数の微分という形であらわし、分配関数については平均の経路長を適当なガウス型関数で表して、単純な表式で表すこととした。最終結果は1つの積分系となり、これをSA法の数値シミュレーションと比較したところほとんど一致する結果を得た。この解析を通して、ランダムに結んだ場合が高温極限に、最適解が温度ゼロの経路長として表され、ディスオーダーステート(ランダムに結んだ場合)と最適解、および実空間繰り込み群で求めた解の近似度などを見通し良く整理することに成功した。