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

本课题的主要目的是研究Hopfield神经网络模型对一类组合问题的处理能力，主要研究成果如下：1.集合规划问题可以定义为Hopfield神经网络模型可处理的问题的一般形式。集合规划问题是一类具有线性约束条件的0-1规划问题，目标函数为二次型极小化。2.一些NP完全问题，如最大独立集问题和背包问题，可以转化为集合规划问题。因此我们针对这些问题编写了翻译程序，并对我们的模拟器的能力进行了考察。对于这些问题，结果比现有的启发式方法稍差。这些算法都是在对原问题进行大量研究的基础上产生的，而我们的方法只需要将原问题的程序转化为集合问题就可以了。因此，我们的通用模拟器被认为是有用的，在实践中。3.玻尔兹曼机是一个神经网络模型的概率行为。利用玻尔兹曼机实现了开关盒的布线问题，该布线问题在超大规模集成电路芯片自动设计系统中具有重要意义。我们的路由器在小型交换机中很有用。

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.