A solution for combinational optimization problems using a two-layer random field model-mean-field approximation

✍ Scribed by Harukazu Igarashi

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 765 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690250806

✦ Synopsis

Abstract

In the solution of the combinational optimization problem such as the traveling salesman problem, the usual approach is to define the energy function, which consists of the term representing the cost to be minimized and the terms representing the constraint for the solution. It is important at this stage to define adequately the weight coefficients for the constraint terms. For this purpose, a solution method based on the two‐layer random field model has already been proposed.

However, it is desirable from the viewpoint of the processing speed to apply the deterministic annealing to the analog neuron system obtained by the mean‐ield approximation, rather than to apply directly the simulated annealing to the binary neuron system. In his case, it is important also to define adequately the weight coefficients in the energy function.

This paper considers the already proposed method which automatically adjusts the weight coefficients using the two‐layer random field model. An elaboration is presented which applies the method to the search of the optimal solution by the deterministic nnealing. In this study, the connection machine CM‐2), which is a SIMD‐type parallel computer, is used to handle the relatively large‐scale problem composed of 64 cities.