Solving large scale combinatorial optimisation problems based on a divide and conquer strategy

A Hopfield neural network for a large scale problem optimisation poses difficulties due to the issues of stability and the determination of network parameters. In this paper, we introduce the concept of a divide and conquer algorithm to solve large scale optimisation problems using the Hopfield neural network. This paper also introduces the Grossberg Regularity Detector (GRD) neural network as a partition tool. This neural network based partition tool has the advantages of reducing the complexity of partition selection as well as removing the recursive division process during the divide and conquer operation. A large scale combinatorial optimisation problem (i.e. sequence-dependent set-up time minimisation problem with a large number of parts (N> 100)) is linearly partitioned into smaller sets of sub-problems based on their similarity relations. With a large number of parts (N>100), the problem could not effectively be verified with other methods, such as the heuristic or branch and bound methods. Hence, the effectiveness of the divide and conquer strategy implemented by the GRD neural network in conjunction with a Hopfield neural network was benchmarked against the first-come first-serve method, and the Hopfield neural network based on arbitrary separations. The results showed that the divide and conquer strategy of the GRD neural network was far superior to the other methods.     

A higher order Hopfield network for vector quantisation

A higher order version of the Hopfield neural network is presented which will perform a simple vector quantisation or clustering function. This model requires no penalty terms to impose constraints in the Hopfield energy, in contrast to the usual one where the energy involves only terms quadratic in the state vector. The energy function is shown to have no local minima within the unit hypercube of the state vector so the network only converges to valid final states. Optimisation trials show that the network can consistently find optimal clusterings for small, trial problems and near optimal ones for a large data set consisting of the intensity values from a digitised, grey- level image.     

Liver stereoscopic visualisation by using Hopfield neural nets

Three dimensional visualisation techniques have been used as a powerful tool in surgical and therapeutic applications. Due to large medical data, huge computations are necessary on 3D visualisation, especially for a real-time system. Many existing methods are sequential, which are too slow to be practical in real applications. In our previous work, we showed boundary detection and feature points extraction by using Hopfield networks. In this paper, a new feature points matching method for 3D surfaces using a Hopfield neural network is proposed. Taking advantage of parallel and energy convergence capabilities in the Hopfield networks, this method is faster and more stable for feature points matching. Stereoscopic visualisation is the display result of our system. With stereoscopic visualisation, the 3D liver used in the experiment can leap out of the screen in true 3D stereoscopic depth. This increases a doctor's ability to analyse complex graphics.     

Global exponential stability of Hopfield neural networks

In this article, some sufficient criteria are derived for the global exponential stability of the equilibrium of Hopfield neural networks of the form C_i du_i /dt     

Associative Memory Design via Path Embedding into a Graph

A graph theoretical procedure for storing a set of n-dimensional binary vectors as asymptotically stable equilibrium points of a discrete Hopfield neural network is presented. The method gives an auto-associative memory which stores an arbitrary memory set completely. Spurious memories might occur only in a small neighborhood of the original memory vectors, so cause small errors.     

Hopfield Neural Network Based Stereo Matching Algorithm

In this paper, a neural network based optimization method is described in order to solve the problem of stereo matching for a set of primitives extracted from a stereoscopic pair of images. The neural network used is the 2D Hopfield network. The matching problem amounts to the minimization of an energy function involving specified stereoscopic constraints. This function reaches its minimum when these constraints are satisfied. The network converges to its stable state when the minimum is reached. In the initial step, the primitives to match are extracted from the stereoscopic pair of images. The primitives we use are specific points of interest. The feature extraction technique is the one developed by Moravec, and called the interest operator. Its output comprises mostly corners or feature points with high variance. The Hopfield network is represented as a N _l × N _r matrix of neurons, where N _l is the number of features in the left image and N _r the number of features in the right one. An update of the state of each neuron is done in order to perform the network evolution and then allowing it to settle down into a stable state. In the stable state, each neuron represents a possible match between a left candidate and a right one.     

Neural versus traditional approaches to the location of interacting hub facilities

In this paper we consider the optimal location of interacting hub facilities. Using the well-known quadratic integer programming formulation of the uncapacitated, single allocation, p-hub median problem (USApHMP), we demonstrate a mapping onto a Hopfield neural network which guarantees feasibility of the final solution. We also propose a novel modification to the Hopfield network which enables escape from local minima, thus improving final solution quality. A practical application of the USApHMP—a postal delivery network—is used to demonstrate that the quality of these Hopfield network solutions compares favorably to those obtained using both exact methods and simulated annealing. Well-known data sets from the literature are also tested using the Hopfield network approaches, and provide further evidence that optimal or near-optimal solutions can consistently be obtained. The speed advantages which can be attained when implementing neural networks in hardware make the Hopfield neural network a very attractive potential alternative to the existing solution techniques.     

Dynamic process programming for a robotic manipulator based on hopfield NN monotonous optimization searching

A new approach to programming the optimal dynamic process for an n‐joint rigid robotic manipulator with the use of the monotonous optimization searching ability of a Hopfield NN is presented. By combining robotic dynamics, this paper designs a programmed controller, which satisfies the aforementioned dynamic process. The convergence of the programmed controller is investigated. Simulations and experiments demonstrate the effectiveness of the scheme described. © 2004 Wiley Periodicals, Inc.     

Hopfield神经网络在机组组合问题中的应用

提出利用多层Hopfield神经网络求解机组组合优化问题。通过构造合适的能量函数使得单层Hopfield神经网络可以解决某一时刻的机组出力问题,与之相对应的多层神经网络可以解决任意时间段的机组出力问题。多层Hopfield神经网络的层数由所需求解问题的时间段确定。给出单层及多层神经网络的能量函数及求解算法,能量函数考虑到机组升降功率和出力上下限的约束。通过对已有文献的算例进行计算比对,所得结果和遗传算法基本一致,但Hopfield神经网络通过解微分方程组来确定最优解,计算时间相对较少。     

基于局部进化的Hopfield神经网络的优化计算方法

提出一种基于局部进化的Hopfield神经网络优化计算方法，该方法将遗传算法和Hopfield神经网络结合在一起，克服了Hopfield神经网络易收敛到局部最优值的缺点，以及遗传算法收敛速度慢的缺点。该方法首先由Hopfield神经网络进行状态方程的迭代计算降低网络能量，收敛后的Hopfield神经网络在局部范围内进行遗传算法寻优，以跳出可能的局部最优值陷阱，再由Hopfield神经网络进一步迭代优化。这种局部进化的Hopfield神经网络优化计算方法尤其适合于大规模的优化问题，对图像分割问题和规模较大的200城市旅行商问题的优化计算结果表明，其全局收敛率和收敛速度明显提高。     

Characteristics of the Hopfield associative memory utilizingisomorphism relations

Isomorphism relations are utilized to analyze the Hopfield associative memory. When the number of fundamental memories m=/<3, it is proved that two Hopfield associative memories are isomorphic if they have the same mutual distances between the fundamental memories. The number of stable states and the synchronous convergence time of a Hopfield associative memory are shown to be less than or equal to 2 to the power 2(m-1) and 4 to the power 2(m-1), respectively, where m>/=1.     

基于CS的Hopfield神经网络数字识别应用

介绍了布谷鸟搜索(cuckoo search, CS)和Hopfield神经网络的基本原理,研究了基于Hopfield神经网络的数字识别应用。针对Hopfield网络权值在数字识别时易陷入局部最优,提出将CS引入Hopfield神经网络的解决方法。利用CS对复杂、多峰、非线性极不可微函数的全局搜索能力,使Hopfield网络在较高噪信比的情况下仍保持较高的联想成功率,并进行了仿真。仿真结果表明,该方法识别数字的效果更佳。     

小波Hopfield神经网络及其在优化中的应用

通过把Hopfield神经网络的sigmoid激励函数替换为Morlet小波函数,提出了一种新型的Hopfield神经网络——小波Hopfield神经网络(WHNN)。由于Morlet小波函数具有良好的局部逼近能力和较高的非线性度,因此WHNN在非线性函数寻优上表现出令人满意的较高精确度的效果。一个典型的函数优化例子表明小波Hopfield神经网络比Hopfield神经网络有较高的精确度。     

Theoretical limitations of a Hopfield network for crossbarswitching

It has been reported through simulations that Hopfield networks for crossbar switching almost always achieve the maximum throughput. It has therefore appeared that Hopfield networks of high-speed computation by parallel processing could possibly be used for crossbar switching. However, it has not been determined whether they can always achieve the maximum throughput. In the paper, the capabilities and limitations of a Hopfield network for crossbar switching are considered. The Hopfield network considered in the paper is generated from the most familiar and seemingly the most powerful neural representation of crossbar switching. Based on a theoretical analysis of the network dynamics, we show what switching control the Hopfield network can or cannot produce. Consequently, we are able to show that a Hopfield network cannot always achieve the maximum throughput.     

Convergence of discrete delayed Hopfield neural networks

The discrete delayed Hopfield neural networks is an extension of the discrete Hopfield neural networks. In this paper, the convergence of discrete delayed Hopfield neural networks is mainly studied, and some results on the convergence are obtained by using Lyapunov function. Several new sufficient conditions for the delayed networks converging towards a limit cycle with period at most 2 are proved in parallel updating mode. Also, some conditions for the delayed networks converging towards a limit cycle with 2-period are investigated in parallel updating mode. All results established in this paper extend the previous results on the convergence of both the discrete Hopfield neural networks, and the discrete delayed Hopfield neural networks in parallel updating mode.     

On a Hopfield Net Arising in the Modelling and Control of Over-Saturated Signalized Intersections

We present a neural method – based on the Hopfield net – for the modelling and control of over-saturated signalized intersections. The problem is to look, in real-time, for lights signal setting which minimize a given traffic criterion such as waiting time. The use of the Hopfield model is straightforward justified by its optimization capabilities, especially its fast time computing (by its own dynamic), which is of a great interest in real-time problems like the traffic control one. The original Hopfield algorithm is modified to take into account proper constraints of the traffic problem. This approach is illustrated by numerical examples of traffic conditions generated by a simulator. We extend the method to urban nets of several interconnected intersections.     

Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique

Most scheduling applications have been demonstrated as NP-complete problems. A variety of schemes are introduced in solving those scheduling applications, such as linear programming, neural networks, and fuzzy logic. In this paper, a new approach of first analogising a scheduling problem to a clustering problem and then using a fuzzy Hopfield neural network clustering technique to solve the scheduling problem is proposed. This fuzzy Hopfield neural network algorithm integrates fuzzy c-means clustering strategies into a Hopfield neural network. This investigation utilises this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration and constrained times (execution time and deadline). Each process is regarded as a data sample, and every processor is taken as a cluster. Simulation results illustrate that imposing the fuzzy Hopfield neural network onto the proposed energy function provides an appropriate approach to solving this class of scheduling problem.       

Medical image segmentation using a contextual-constraint-based Hopfield neural cube

Neural-network-based image techniques such as the Hopfield neural networks have been proposed as an alternative approach for image segmentation and have demonstrated benefits over traditional algorithms. However, due to its architecture limitation, image segmentation using traditional Hopfield neural networks results in the same function as thresholding of image histograms. With this technique high-level contextual information cannot be incorporated into the segmentation procedure. As a result, although the traditional Hopfield neural network was capable of segmenting noiseless images, it lacks the capability of noise robustness. In this paper, an innovative Hopfield neural network, called contextual-constraint-based Hopfield neural cube (CCBHNC) is proposed for image segmentation. The CCBHNC uses a three-dimensional architecture with pixel classification implemented on its third dimension. With the three-dimensional architecture, the network is capable of taking into account each pixel's feature and its surrounding contextual information. Besides the network architecture, the CCBHNC also differs from the original Hopfield neural network in that a competitive winner-take-all mechanism is imposed in the evolution of the network. The winner-take-all mechanism adeptly precludes the necessity of determining the values for the weighting factors for the hard constraints in the energy function in maintaining feasible results. The proposed CCBHNC approach for image segmentation has been compared with two existing methods. The simulation results indicate that CCBHNC can produce more continuous, and smoother images in comparison with the other methods.     

Comparison of image recognition efficiency of Bayes,correlation, and modified Hopfield network algorithms

The statistical estimates of the probability of correct recognition of the images, noisy reference by an additive handicap, for Bayes, correlation, and modified Hopfield network algorithms are compared. It is shown that, in the case of complete a priori probability concerning a handicap, the modified Hopfield network algorithm reaches the quality of the Bayes algorithm. At a deviation a priori probability on a handicap, the quality of the Bayes algorithm is worse than that of the modified Hopfield network algorithm. The correlation algorithm is worse than the modified Hopfield network algorithm, in general.     

用改进的差分式Hopfield网络实现线性二次型最优控制

为解决差分式Hopfield网络能量函数的局部极小问题,本文对之改进得到一种具有迭代学习功能的线性差分式Hopfield网络.理论分析表明,该网络具有稳定性,且稳定状态使其能量函数达到唯一极小值.基于线性差分式Hopfield网络稳定性与其能量函数收敛特性的关系,本文将该网络用于求解多变量时变系统的线性二次型最优控制问题.网络的理论设计方法表明,网络的稳态输出就是欲求的最优控制向量.数字仿真取得了与理论分析一致的实验结果.