A method to improve the transiently chaotic neural network

doi:10.1016/j.neucom.2004.12.004

Neurocomputing

Volume 67, August 2005, Pages 456-463

https://doi.org/10.1016/j.neucom.2004.12.004 Get rights and content

Abstract

In this article, we propose a method for improving the transiently chaotic neural network (TCNN) by introducing several time-dependent parameters. This method allows the network to have rich chaotic dynamics in its initial stage and to reach a state in which all neurons are stable soon after the last bifurcation. This enables the network to have rich search ability initially and to use less CPU time to reach a stable state. The simulation results on the N-queen problem confirm that this method effectively improves both the solution quality and convergence speed of TCNN.

Introduction

Neural networks have been shown to be powerful tools for solving combinatorial optimization problems, particularly NP-hard problems. The Hopfield neural network [4], [5], one of the well-known models of this type, converges to a stable equilibrium point due to its gradient descent dynamics; however, it causes severe local-minimum problems whenever it is applied to optimization problems. Although many methods have been suggested that attempt to improve them [8], [13], the results have not always been satisfactory. Recently, many artificial neural networks with chaotic dynamics have been investigated [1], [10]; they have much rich and far-from equilibrium dynamics with various coexisting attractors, not only of fixed and periodic points but also of strange attractors, even though its equation is simple. But it is usually difficult to decide how long to maintain chaotic dynamics, or how to harness chaotic behavior so that the network converges to a stable point of equilibrium corresponding to an acceptably near-optimal state [2]. Wishing to reconcile the Hopfield network's convergent dynamics with the principles of chaotic dynamics, Chen and Aihara have proposed a transiently chaotic neural network (TCNN) [2]. However, there are many parameters in TCNN that affect its convergence speed and its solution quality [2], and these therefore need to be chosen carefully. Furthermore, a network with rich dynamics usually requires more steps to stabilize. In this article, we present a method of introducing several time-independent parameters into the original TCNN model. This modified TCNN has relatively rich dynamics initially, and, after bifurcation, converges sooner to a state in which all its neurons are stable.

Section snippets

The transiently chaotic neural network

Chen and Aihara's TCNN model is defined as follows: $v_{i} (t) = \frac{1}{1 + e^{- u_{i} (t) / ε}},$ $u_{i} (t + 1) = k u_{i} (t) + α (\sum_{j = 1, j \neq i}^{n} w_{ij} v_{j} + I_{i}) - z_{i} (t) (v_{i} (t) - I_{0}),$ $z_{i} (t + 1) = (1 - β) z_{i} (t),$ where i is the index of neurons and n is the number of neurons(1⩽i⩽n), v_i the output of neuron i, u_i the internal state for neuron i, w_ij the connection weight from neuron j to neuron i, I_i the input bias of neuron i, α the positive scaling parameter for inputs, k the damping factor of the nerve membrane( $0 ⩽ k ⩽ 1$ ), z_i(t) the self-feedback connection weight or

The method to improve the original model

In order to improve the convergence speed and search ability of the original TCNN, we replace α, β, and ε, constants in the original TCNN model, with three variables (α(t), β(t), and ε(t)). They are updated as follows: $α (t + 1) = (1 + λ) α (t) if α (t) < 0.1 else α (t) = 0.1,$ $β (t + 1) = (1 + φ) β (t) if β (t) < 0.2 else β (t) = 0.2,$ $ε (t + 1) = (1 - η) ε (t) if ε (t) > 0.001 else ε (t) = 0.001,$ where λ, φ and η are small positive constants(selected empirically).

Initially, α(0) and β(0) are set to small values. When α(t) is small, the influence of the

Simulations on the N-queen problem

In order to confirm the effectiveness of the proposed method for TCNN, we tested it on the N-queen problem. This problem involves placing N queens on an N by N chessboard in such a way that no queen is under attack. The N-queen problem has been solved with a variety of artificial neural networks [9], [12], and, more recently, with several chaotic models [6], [7], [11]. In [11], a chaotic neural network with reinforced self-feedback was proposed.

In this article, we use the formulation of the N

Conclusions

We have presented a method to improve the original TCNN for combinatorial optimization problems. This method allows a TCNN to maintain rich dynamics and converge in fewer steps after the last bifurcation to a state in which all its neurons are stable. Simulations on the N-queen problem show that the proposed model is superior to the original model and another chaotic neural network because of its optimal convergence rate and average update steps. For other combinatorial optimization problems,

Acknowledgements

We wish to thank Prof. R. Newcomb and our anonymous reviewers for their valuable suggestions.

Xinshun Xu received a B.S. degree from Shandong Normal University, Shandong, China and an M.S. degree from Shandong University, Shandong, China in 1998 and 2002, respectively. From 1998 to 2000, he was an Engineer in Shandong Provincial Education Department, Shandong, China. Now he is working toward the Ph.D. degree at Toyama University, Toyama, Japan. His main research interests are neural networks, machine learning, pattern recognition, image processing, and optimization problems.

References (13)

K. Aihara et al.
Chaotic neural networks
Phys. Lett. A
(1990)
L. Chen et al.
Chaotic simulated annealing by a neural network model with transient chaos
Neural Networks
(1995)
L. Chen et al.
Chaos and asymptotical stability in discrete-time neural networks
Physica D
(1997)
T. Kwok et al.
Experimental analysis of chaotic neural network models for combinatorial optimization under a unifying framework
Neural Networks
(2000)
M. Ohta
Chaotic neural networks with reinforced self-feedbacks and its application to N-queen problem
Math. Comput. Simulation
(2002)
J.J. Hopfield et al.
Neural computation of decisions in optimization problems
Biol. Cybern.
(1985)

There are more references available in the full text version of this article.

Cited by (16)

Design and analysis of a novel chaotic diagonal recurrent neural network
2015, Communications in Nonlinear Science and Numerical Simulation
Citation Excerpt :
In order to make the network stable quickly, several chaotic control methods have been proposed for CNN. Xu et al. [19] adopted a chaos control by introducing several time-dependent parameters for the original transiently chaotic neural network model. A chaos parameter control was designed in [20], in which the changes of the chaos parameters depend on the value of system partial energy and the differential value of the partial energy.
A chaotic neural network model with logistic mapping is proposed to improve the performance of the conventional diagonal recurrent neural network. The network shows rich dynamic behaviors that contribute to escaping from a local minimum to reach the global minimum easily. Then, a simple parameter modulated chaos controller is adopted to enhance convergence speed of the network. Furthermore, an adaptive learning algorithm with the robust adaptive dead zone vector is designed to improve the generalization performance of the network, and weights convergence for the network with the adaptive dead zone vectors is proved in the sense of Lyapunov functions. Finally, the numerical simulation is carried out to demonstrate the correctness of the theory.
Multiperiodicity analysis and numerical simulation of discrete-time transiently chaotic non-autonomous neural networks with time-varying delays
2010, Communications in Nonlinear Science and Numerical Simulation
Citation Excerpt :
For such interesting phenomenon, we can refer to our computer simulations. For transiently chaotic neural networks, many previous works [10–12] mainly focus on their chaotic structure and bifurcations which would be useful for chaos synchronization such as complete synchronization, lag synchronization [36–38]. However, multiperiodicity and convergence analysis of transiently chaotic neural networks are never reported and have some interesting attractive structure (see Figs. 1 and 3) and chaotic unstable regions (see Figs. 2 and 4) which would have an insight into chaotic synchronization.
In this paper, we investigate multiperiodicity analysis of discrete-time transiently chaotic neural networks, i.e., the coexistence and exponential stability of multiple periodic sequence solutions. By using analytic property of activation functions and Schauder’s fixed point theorem, we attain the coexistence of $2^{N}$ periodic sequence solutions. Meanwhile, some new and simple criteria are derived for the networks to converge exponentially toward $2^{N}$ periodic sequence solutions. Our results are new and complement existing ones in the literature. Finally, computer numerical simulations are performed to illustrate multiperiodicity of discrete-time transiently chaotic neural networks.
Optimal matching by the transiently chaotic neural network
2009, Applied Soft Computing Journal
Dynamic programming matching (DPM) is a technique that finds an optimal match between two sequences of feature vectors allowing for stretched and compressed sections of the sequence. The purpose of this study is to formulate the matching problem as an optimization task and carry out this optimization problem by means of a chaotic neural network. The proposed method uses TCNN, a Hopfield neural network with decaying self-feedback, to find the best-matching (i.e., the lowest global distance) path between an input and a template. Experimental results show a very good performance for the proposed algorithm in pattern recognition tasks.
Minimizing interference in satellite communications using transiently chaotic neural networks
2009, Computers and Mathematics with Applications
Citation Excerpt :
Numerical experiments on the traveling salesman problem (TSP) and the maintenance scheduling problem showed that the TCNN has high efficiency for converging to globally optimal solutions. The TCNN, which is also known as chaotic simulated annealing [10], is not problem-specific but a powerful general method for addressing combinatorial optimization problems (COPs) [23–25]. With autonomous decreases of the self-feedback connection, TCNNs are more effective in solving COPs compared to the HNN.
The frequency assignment problem (FAP) in satellite communications is solved with transiently chaotic neural networks (TCNN). The objective of this optimization problem is to minimize cochannel interference between two satellite systems by rearranging the frequency assignments. For an $N$ -carrier– $M$ -segment FAP problem, we construct a TCNN consisting of $N \times M$ neurons. The performance of the TCNN is demonstrated through solving a set of benchmark problems, where the TCNN finds comparative if not better solutions as compared to the existing algorithms.
A TCNN filter algorithm to maximum clique problem
2009, Neurocomputing
Citation Excerpt :
Hasegawa et al. have proposed an automatic parameter tuning method [8]. Xu et al. have proposed a method of introducing several time-independent parameters into TCNN model [9]. Although these methods give some guide to determine parameter values, the difficulty of parameter tuning is still hard and novel methods are still required to support the determination of parameter values.
In this paper, coefficient sensitiveness of transiently chaotic neural network (TCNN) for maximum clique problem (MCP) is analyzed. By introducing a new definition of adaptivity into TCNN and utilizing a neuron filter, the domain of coefficient selection is enlarged to search globally optimal solution and near-optimal solution on MCP. Based on our analysis on the characteristic of TCNN, we propose a TCNN filter algorithm to shrink the network scale and improve solution quality. The algorithm effectively relaxes the coefficient sensitiveness and improves network ability to solve MCP. Simulations have been performed to verify the validity of our algorithm.
A novel hysteretic chaotic neural network and its applications
2007, Neurocomputing
A model of single neuron with chaotic and hysteretic characteristics is proposed. Neural network coupled by such neurons exhibits complex dynamic behaviors. The network is also studied from the viewpoint of optimization. Chaos and hysteresis phenomena make the network have the characteristic of escaping from a local minimum of the energy function, so it can find a global minimum more easily as compared with others. The experimental results show that it has a higher average success rate of obtaining a global optimization solution.

View all citing articles on Scopus

Zheng Tang received a B.S. degree from Zhejiang University, Zhejiang, China in 1982 and an M.S. degree and a D.E. degree from Tsinghua University, Beijing, China in 1984 and 1988, respectively. From 1988 to 1989 he was an Instructor in the Institute of Microelectronics at Tsinghua University. From 1990 to 1999, he was an Associate Professor in the Department of Electrical and Electronic Engineering, Miyazaki University, Miyazaki, Japan. In 2000, he joined Toyama University, Toyama, Japan, where he is currently a Professor in the Department of Intellectual Information Systems. His current research interests include intellectual information technology, neural networks, and optimizations.

Jiahai Wang received a B.S. degree from Gannan Teachers College, Jiangxi, China and an M.S. degree from Shandong University, Shandong, China in 1999 and 2001, respectively. Now he is working toward the Ph.D. degree at Toyama University, Toyama, Japan. His main research interests include neural networks, meta-heuristic algorithms, evolutionary computation, hybrid soft computing algorithms and their applications to various real-world combinatorial optimization problems.

View full text

LetterA method to improve the transiently chaotic neural network

Abstract

Introduction

Section snippets

The transiently chaotic neural network

The method to improve the original model

Simulations on the N-queen problem

Conclusions

Acknowledgements

Phys. Lett. A

Neural Networks

Physica D

Neural Networks

Math. Comput. Simulation

Neural computation of decisions in optimization problems

Biol. Cybern.

Letter
A method to improve the transiently chaotic neural network