Parallel analog method for optimization by using neural networks

使用神经网络进行优化的并行模拟方法

• 批准号: 05650357
• 负责人: URAHAMA Kiichi
• 金额: $ 1.22万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 1994
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05650357/
• 关键词: Hopfield Nets; Combinatorial Optimization; Lagrangean Method; Analog Circuit; Mixed Integer Programming; Image Restoration; Clustering; Assignment Problem; ニューラルネット; ファジィクラスタリング; パターン認識; 自己組織化マップ; アナログ回路; 図地分離

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.

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

项目成果

K.Urahama amd M.Watanabe: "Nonlinear scale space filtering of images" Trans.IEICE. J77D-II. 1761-1767 (1994)

K.Urahama 和 M.Watanabe：“图像的非线性尺度空间过滤”Trans.IEICE。

K.Urahama: "Analog circuit for solving assignment problems" IEEE Trans.Circuits&Syst.41. 426-429 (1994)

K.Urahama：“解决分配问题的模拟电路” IEEE Trans.Circuits

K. Urahama: "Analog circuit for solving assignment problems" IEEE Trans.Circuits & Syst.41. 426-429 (1994)

K. Urahama：“解决分配问题的模拟电路” IEEE Trans.Circuits

浦浜 喜一: "抵抗ヒューズ回路による図地分離" 電子情報通信学会 論文誌. J76-A. 1383-1384 (1993)

Kiichi Urahama：“使用电阻保险丝电路进行图地分离”电子、信息和通信工程师学会期刊 J76-1384 (1993)。

K.Urahama: "Modified deformable model for bijective topology presearving map" IEICE Trans. Inf.& Syst.E77D. 1186-1188 (1994)

K.Urahama：“双射拓扑预保存图的修改变形模型”IEICE Trans。