巡回セールスマン問題における解の分岐

ISHII Shin, SATO Masaaki

アナログホップフィールドモデルおよびボルツマンマシンの平均場近似モデルにおいてはアニーリングする際にエネルギー関数の対称性に応じた解の分岐が起きる。本報告では、巡回セールスマン問題を課題として、この分岐現象について述べる。巡回セールスマン問題は巡回対称性と反転対称性という二種の対称性を持ち、これらが分岐の構造に影響を与える。次に、これら分岐の構造によって、平均場アニーリングのアルゴリズムとしての性質が分かることを示す。結果として、平均場アニーリングは一般に「準」最適解を求めるアルゴリズムであり、非決定論的性質を有する。最後にこれらの性質を踏まえて、修正アルゴリズムを提案する。
In the analog Hopfield network and the mean field theory (MFT) of the Boltzmann machine, bifurcations of solutions occur during the course of the annealing procedure. In this report, we investigate the bifurcation processes of MFT solutions when MFT is applied to traveling salesman problems (TSPs). A TSP has two types of symmetries, i.e., cyclic and reverse. These symmetries affect the bifurcation structure. Next, some features of the MFT annealing procedure, which are dependent on the bifurcation processes, are shown. The MFT annealing has "non-deterministic" and "non-optimal" properties, which implies some procedural limitations. To overcome these, we also propose a couple of modified algorithms.

巡回セールスマン問題における解の分岐

Bibliographic Information

Search this article

Description

Journal

References(7)*help

Keywords

Details 詳細情報について

Export

Report a problem