On Problem Solving Ability of Hopfield Neural Network Model for Combinatorial Problems

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

Main goal of this project is to investigate the ability of Hopfield neural network model for a certain kind of combinatorial problems.Research results are as follows:1.A set programming problem can be defined as a general form of problems that is treatable with Hopfield neural network model. The set programming problem is one of 0-1 programming problems with linear constraints and quadratic objective function to be minimized. We implement a general purpose simulator for set programming problems.2.Some NP-complete problems,e.g.maximum independent set problem and knapsack problem, can be reformulated as set programming problems. Therefore we make translating programs for these problems,and investigate the ability of our simulator. Results are a little worse than existent heuristic methods for these problems. Those heuristics are produced with great effort of research on original problems,however,our approach needs only an effort to make translating programs from original problems to set programming problems. Thus our general purpose simulator is considered to be useful in practice.3.Boltzmann machine is a neural network model with probabilistic behavior. By using Boltzmann machine,we implement a router of switchbox,whose routing problem is important in an automated design system of VLSI chips. Our router is useful in small size switchboxes.