Parallel analog method for optimization by using neural networks

Hopfield网络也存在一些不足，如计算时间随着问题规模的增长而增长，经常输出非法解，并且对其性能没有理论保证。本研究的目的是针对Hopfield方法在求解组合优化问题时遇到的困难给出一些解决方法。为了提高算法的速度，首先提出了一种基于混合整数规划的算法。其次，提出了只求合法解的拉格朗日方法。对于最常见的NP-hard组合优化问题之一的最大割问题，给出了该拉格朗日方法的一个理论保证。设计了一种新的确定性退火技术，以提高所开发的方法对极难问题的性能。所设计的新方法适用于许多组合优化问题，如分配问题、布局问题、数据聚类问题。拓扑保持映射和图像恢复。一些数值实验表明，本研究开发的求解方法具有良好的性能。

Some deficiencies have been observed for the Hopfield networks, e.g.growth of its computational time with problem size, its often outputs of illegal solutions and no theoretical guarantee for its performance. The aim of this research is to give some solutions for these difficulties of the Hopfield method for solving combinatorial optimization problems. A method based on a mixed integer programming is first developed for speeding up of the algorithm. Next a Lagrangean method is proposed for obtaining only legal solutions. A theoretical guarantee is derived for this Lagrangean method for the maximum cut problem which is one of the most popular NP-hard combinatorial optimization problems. A novel deterministic annealing technique is devised for raising up the performance of the developed method for extremely hard problems. The devised new method is applied to many combinatorial optimization problems, e.g.assignment problems, placement problems, data clustering.topology preserving mappings and image restoration. Some numerical experiments have revealed a promising performance of the solution method developed in this research.