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.