On the performance of the LP-guided Hopfield network-genetic algorithm

This paper proposes a linear programming (LP)-guided Hopfield-genetic algorithm for a class of combinatorial optimization problems which admit a 0–1 integer linear programming. The algorithm modifies the updating order of the binary Hopfield network in order to obtain better performance of the complete hybrid approach. We theoretically analyze several different updating orders proposed. We also include in the paper a novel proposal to guide the Hopfield network using the crossover and mutation operators of the genetic algorithm. Experimental evidences that show the good performance of the proposed approach in two different combinatorial optimization problems are also included in the paper.     

基于CHNN聚类算法的款式部件生成模型

对智能化服装款式设计系统中的款式部件的自动获取功能进行了研究.采用基于连续Hopfield神经网络(CHNN)的聚类算法提出了一个款式部件的风格生成模型.提取表现部件造型特征的特征要素构造一个空间点集,利用CHNN网络对该点集进行聚类,分析部件类别与款式设计风格之间的关系,建立基于款式风格设计的部件搭配规则.并将该模型应用于款式的衣片部件上,实现了衣片部件的聚类.实验结果表明,该模型设计合理,分类清晰,具有可扩展性.     

Complexity of reachability problems for finite discrete dynamical systems

Sequential Dynamical Systems (SDSs) are a special type of finite discrete dynamical systems that can be used to model simulation systems. We focus on the computational complexity of testing several phase space properties of SDSs. Our main result is a sharp delineation between classes of SDSs whose behavior is easy to predict and those whose behavior is hard to predict. Specifically, we show the following.

1.

Several state reachability problems for SDSs are PSPACE-complete, even when restricted to SDSs whose underlying graphs are of bounded bandwidth (and hence of bounded pathwidth and treewidth), and the function associated with each node is symmetric. Moreover, this result holds even when the underlying graph is d-regular for some constant d and all the nodes compute the same symmetric Boolean function. An immediate corollary of this result is a PSPACE-hard lower bound on the complexity of reachability problems for regular generalized 1D-Cellular Automata and undirected systolic networks with Boolean totalistic local transition functions.

2.

In contrast, the above reachability problems are solvable in polynomial time for SDSs when the Boolean function associated with each node is symmetric and monotone.

The PSPACE-completeness results follow as corollaries of simulation results which show for several classes of SDSs, how one class of SDSs can be efficiently simulated by another (more restricted) class of SDSs. We also prove several structural properties concerning the phase space of an SDS. SDSs are closely related to Cellular Automata (CA), concurrent transition systems, discrete Hopfield networks and systolic networks. This observation in conjunction with our lower bounds for SDSs, yields new PSPACE-hard lower bounds on the complexity of state reachability problems for these models, extending some of the earlier results in [K. Culik II, J. Karhumäki, On totalistic systolic networks, Inform. Process. Lett. 26 (5) (1988) 231-236; P. Floréen, E. Goles, G. Weisbuch, Transient length in sequential iterations of threshold functions, Discrete Appl. Math. 6 (1983) 95-98; P. Floréen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994. Also appears in: I. Parberry (Ed.), Comp. and Learning Complexity of Neural Networks: Advanced Topics, 1999; D. Harel, O. Kupferman, M.Y. Vardi, On the complexity of verifying concurrent transition systems, Inform. and Comput. 173 (2002) 143-161; S.K. Shukla, H.B. Hunt III, D.J. Rosenkrantz, R.E. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP, 1996, pp. 466-477; A. Rabinovich, Complexity of equivalence problems for concurrent systems of finite agents, Inform. and Comput. 127 (2) (1997) 164-185].     

用改进的竞争Hopfieid神经网络求解多边形近似问题

多边形近似是提取曲线特征点和简化曲线描述的一种重要方法。提出一种改进的Hopfield神经网络多边形近似算法,该算法利用选择拐点策略减少了搜索空间,重新定义了神经网络的能量函数,使其更能反映优化目标;引入合并拆分搜索策略,有效帮助神经网络脱离局部最小值。实验结果表明,提出的改进算法是有效的,比其它算法如关键点检测法、竞争Hopfield神经网络、混沌Hopfield神经网络、遗传算法等具有更优的性能。     

Optimization with the Hopfield network based on correlated noises: Experimental approach

This paper presents two simple optimization techniques based on combining the Langevin Equation with the Hopfield Model. Proposed models – referred as stochastic model (SM) and pulsed noise model (PNM) – can be regarded as straightforward stochastic extensions of the Hopfield optimization network. Both models follow the idea of stochastic neural network (Levy and Adams, IEEE Conference on Neural Networks, vol. III, San Diego, USA, 1987, pp. 681–689) and diffusion machine (Wong, Algorithmica 6 (1991) 466–478). They differ form the referred approaches by the nature of noises and the way of their injection. Optimization with stochastic model, unlike in the previous works, in which δ-correlated Gaussian noises were considered, is based on Gaussian noises with positive autocorrelation times. This is a reasonable assumption from a hardware implementation point of view. In the other model – pulsed noise model, Gaussian noises are injected to the system only at certain time instances, as opposed to continuously maintained δ-correlated noises used in the previous related works. In both models (SM and PNM) intensities of injected noises are independent of neurons’ potentials. Moreover, instead of impractically long inverse logarithmic cooling schedules, the linear cooling is tested. With the above strong simplifications neither SM nor PNM is expected to rigorously maintain thermal equilibrium (TE). However, numerical tests based on the canonical Gibbs–Boltzmann distribution show, that differences between rigorous and estimated values of TE parameters are relatively low (within a few percent). In this sense both models are said to perform quasithermal equilibrium. Optimization performance and quasithermal equilibrium properties of both models are presented based on the travelling salesman problem (TSP).     

进化策略求解Hopfield神经网络

提出了一种进化策略求解ＨＯｐｆｉｅｌｄ神经网络的方法。该进化策略分三个阶段,即第一阶段只在较小区间上求出局部优化解;然后,在此基础上,由第二阶段求出较大区间上的局部优化解;最后由第三阶段求出全局优化解。同时采用Ｈｏｐｆｉｅｌｄ神经网络动态方程指导第一阶段的局部进化策略的进化方向,因而大大加快了优化搜索速度。在分阶段的进化策略中,其第一阶段只需搜索较小区间、第二和第三阶段的搜索则建立在其前一阶段的基     

利用多种特征和Hopfield神经网络的有遮挡的目标识别

该文提出了一种新的识别有遮挡目标的方法,即将目标模型和含有目标的遮挡图象的轮廊在某一尺度上张角的极值、极值点（亦称显著点）之间距离、相对位置等信息集成在一起,作为描述目标模型（遮挡图象）的一组特征,且这组特征在平移、旋转和均匀尺度变换下保持不变。其轮廓上点ｐ处的张角可用余弦定理很方便地求出,而张角的极值点则对应于轮廊急剧变化的地方。同时将特征匹配定义为模型特征与遮挡图象特征之间的对应,若这种对应被映射到Ｈｏｐｆｉｅｌｄ神经网络上,则该网络即可用于完成全局特征匹配。该文提出了的方法已在ＰⅡ个人计算机上用Ｍａｔｌａｂ５．２编程实现,并给出了应用实例。实验结果表明,该方法能有效地从含有遮挡目标的景物图象中识别出目标,且实现起来非常方便。     

Associative Memories in Infinite Dimensional Spaces

A generalization of the Little–Hopfield neural network model for associative memories is presented that considers the case of a continuum of processing units. The state space corresponds to an infinite dimensional euclidean space. A dynamics is proposed that minimizes an energy functional that is a natural extension of the discrete case. The case in which the synaptic weight operator is defined through the autocorrelation rule (Hebb rule) with orthogonal memories is analyzed. We also consider the case of memories that are not orthogonal. Finally, we discuss the generalization of the non deterministic, finite temperature dynamics.     

RNN和Hopfield两网络中的优化解法的对比研究

基于一种动态随机神经网络(DRNN)求解典型NP优化问题TSP的改进算法，在理论上对DRNN与连续的Hopfiled网络(CHNN)进行了对比研究，指出虽然两种网络均以能量函数表达TSP的最优路径，并通过训练反馈网络求得路径解，但由于两者所用激活函数和收敛条件不同，使得DRNN网络能够接受能量函数的小波动，从而跳出局部最小值达到全局最优；此外，DRNN与CHNN相比网络训练对参数变化不敏感，参数设置简单。最后，通过仿真实验对随机坐标十城市使用两种网络对比路径寻优能力，进一步验证理论分析的结论。揭示RNN网络和CHNN网络在求解TSP时各自的优缺点。     

MC-CDMA系统的神经鱼群算法检测器

为使人工鱼群算法在最短的时间内取得多用户检测问题的最优解,在MC-CDMA系统基础上设计一种神经网络人工鱼群算法。人工鱼的3种神经网络行为使神经网络人工鱼群算法在解决多用户检测该类组合优化问题时,减少搜索的随机性和任意性,加快原鱼群算法的收敛速度。仿真结果证明,该算法能够快速收敛,且其抗多址干扰能力和抗远近效应能力优于已有应用智能算法的多用户检测器。