巡回置換に基づくアナログニューラルネットワークによる二次割当問題の解法
矢野 真吾
大規模な組み合わせ最適化問題を近似的に解く、メタヒューリスティック法は重要な手法である。これまでに、ボルツマンマシンのような確率的なニューラルネットワークを用いた手法がメタヒューリスティックとして提案されてきた。しかし、確率的なニューラルネットを用いた手法は非常に多くの計算時間が必要になるため、平均場近似法と呼ばれる手法が用いられる。しかし、この近似のためにこの手法は決定論的になるため、アルゴリズムは無数にある局所最適解から抜け出すのが困難になる。この問題を避けるため、次々と局所最適解を探索し続ける非平衡なダイナミクスが重要になる。これまでに、置換操作を基本操作とするアルゴリズムがいくつか提案されてきた。置換操作は可能な解から可能なその他の解へと変換を行うため、非平衡なダイナミクスが導入される。本発表では、巡回置換を探索の基本操作とする手法を提案する。また、本手法を2次割り当て問題（QAP)に適用して、計算機シミュレーションによりその有効性を示す。