2層確率場モデルを用いた組合せ最適化問題の解法 : 平均場近似

概要

論文の詳細を見る
巡回セールスマン問題などの組合せ最適化問題をシミュレーテッドアニーリング法を用いて解く際には,最小にしたいコストを表す項と,解に対する制約条件を表す項からなるエネルギー関数を定義するのが一般的である.この際,制約条件項の重み係数の値を適切に設定するのが重要であり,この目的のために,2層確率場モデルを用いた解法が既に提案されている.しかしながら,2値ニューロン系に対して,直接,シミュレーテッドアニーリング法を適用するよりは,平均場近似を行って得られるアナログニューロン系に対して決定論的アニーリングを行う方が,処理の高速化として点からは望ましい.この場合にもエネルギー関数中の重み係数の値を適切に設定することは重要である.本論文では,既に提案した2層確率場モデルを用いた重み係数の自動調節方法を,決定論的アニーリング法による最適解探索に適用できるように工夫した.更に,今回は,SIMD型の並列計算機であるコネクションマシン(CM-2)を用いて,都市数64の比較的大規模な問題を取り扱った.
社団法人電子情報通信学会の論文
1993-09-25