Chaotic Simulated Annealing by A Neural Network Model with Transient Chaos

Luonan Chen, Kazuyuki Aihara

Abstract

We propose a neural network model with transient chaos, or a transiently chaotic neural network (TCNN) as an approximation method for combinatorial optimization problem, by introducing transiently chaotic dynamics into neural networks. Unlike conventional neural networks only with point attractors, the proposed neural network has richer and more flexible dynamics, so that it can be expected to have higher ability of searching for globally optimal or near-optimal solutions. A significant property of this model is that the chaotic neurodynamics is temporarily generated for searching and self-organizing, and eventually vanishes with autonomous decreasing of a bifurcation parameter corresponding to the "temperature" in usual annealing process. Therefore, the neural network gradually approaches, through the transient chaos, to dynamical structure similar to such conventional models as the Hopfield neural network which converges to a stable equilibrium point. Since the optimization process of the transiently chaotic neural network is similar to simulated annealing, not in a stochastic way but in a deterministically chaotic way, the new method is regarded as chaotic simulated annealing (CSA).

Introduction

Combinatorial optimization problems, such as the Traveling Salesman Problem (TSP), are notoriously difficult to solve due to their NP-hard nature. While traditional neural networks like the Hopfield model offer a fast, parallel approach to these problems, they are frequently hampered by their tendency to settle into local minima—suboptimal solutions that represent stable equilibrium points but fail to reach the global optimum.

To overcome this, researchers traditionally employ Stochastic Simulated Annealing (SSA), which introduces random "thermal" noise to help the system escape local traps. However, SSA is computationally expensive; to guarantee convergence to a global optimum, the cooling schedule must be extremely slow, often requiring more iterations than a brute-force search. This paper introduces Chaotic Simulated Annealing (CSA), a method that replaces stochastic noise with deterministic chaos to achieve a more efficient and reliable global search.

The Transiently Chaotic Neural Network (TCNN)

The foundation of CSA is the Transiently Chaotic Neural Network (TCNN). This model integrates chaotic dynamics into the neural framework through two primary mechanisms:

  1. Negative Self-Feedback: Each neuron is equipped with a self-inhibitory term. When this term is high, the network exhibits chaotic behavior, preventing it from stagnating in any single state and allowing it to explore the state space dynamically.
  2. The Bifurcation Parameter ($z$): Similar to the "temperature" in physical annealing, the variable $z(t)$ controls the strength of the self-feedback. By applying an exponential damping schedule to $z(t)$, the chaos is gradually reduced.

As the "temperature" of the system cools, the network undergoes a series of reversed period-doubling bifurcations. It transitions from high-dimensional chaos to periodic oscillations, and finally to a stable equilibrium point. This autonomous convergence ensures that the network eventually settles into a fixed state, mimicking the stability of a Hopfield network but only after a thorough chaotic search of the solution space.

Deterministic Chaos vs. Stochastic Noise

A key insight of this research is that deterministic chaos is a more effective search tool than random noise. Because chaotic trajectories are dissipative and restricted to a specific "fractal subspace," the search is more focused than a purely random Monte Carlo search. This reduced search space allows the TCNN to identify high-quality solutions with significantly fewer iterations than stochastic methods.

Experimental Results and Benchmarks

The authors validated the CSA method using both theoretical benchmarks and real-world industrial problems.

Traveling Salesman Problem (TSP)

In tests on a 10-city TSP (using the classic Hopfield-Tank data), CSA demonstrated remarkable performance:

  • Success Rate: CSA achieved a 100% global optimization rate under optimal parameters, whereas standard Hopfield networks typically succeed less than 37% of the time.
  • Efficiency: To reach a 100% success rate, CSA required only 398 iterations. In contrast, Stochastic Simulated Annealing required 58,700 iterations to reach a lower success rate of 92%.
  • Scalability: On a 48-city TSP (TSPLIB), the model found solutions within 1.6% of the global optimum in 84% of trials.

Power System Maintenance Scheduling

To test practical efficiency, the model was applied to a large-scale maintenance scheduling problem for a power system. This involved 117 generating units across 40 plants over a one-year horizon, requiring a network of 2,384 neurons. The CSA method solved this complex problem in approximately 26 seconds (on 1990s hardware), producing feasible schedules with consistent reliability margins, proving its viability for high-dimensional, real-world applications.

Conclusion

Chaotic Simulated Annealing represents a significant advancement in neural optimization. By harnessing the power of transient chaos, the TCNN model provides a deterministic alternative to stochastic annealing that is both faster and more reliable. While the authors note that specialized heuristics may still outperform CSA on specific problems like the TSP, the general-purpose nature of CSA and its potential for hardware implementation (via chaotic chips) make it a powerful tool for complex combinatorial optimization.

Summary updated

Abstract

We propose a neural network model with transient chaos, or a transiently chaotic neural network (TCNN) as an approximation method for combinatorial optimization problem, by introducing transiently chaotic dynamics into neural networks. Unlike conventional neural networks only with point attractors, the proposed neural network has richer and more flexible dynamics, so that it can be expected to have higher ability of searching for globally optimal or near-optimal solutions. A significant property of this model is that the chaotic neurodynamics is temporarily generated for searching and self-organizing, and eventually vanishes with autonomous decreasing of a bifurcation parameter corresponding to the "temperature" in usual annealing process. Therefore, the neural network gradually approaches, through the transient chaos, to dynamical structure similar to such conventional models as the Hopfield neural network which converges to a stable equilibrium point. Since the optimization process of the transiently chaotic neural network is similar to simulated annealing, not in a stochastic way but in a deterministically chaotic way, the new method is regarded as chaotic simulated annealing (CSA). Fundamental characteristics of the transiently chaotic neurodynamics are numerically investigated with examples of a single neuron model and the Traveling Salesman Problem (TSP). Moreover, a maintenance scheduling problem for generators in a practical power system is also analysed to verify practical efficiency of this new method.
BibTeX
@inproceedings{chen1995chaotic,
  author = {Luonan Chen and Kazuyuki Aihara},
  title = {{Chaotic Simulated Annealing by A Neural Network Model with Transient Chaos}},
  booktitle = {Neural},
  year = {1995},
  doi = {10.1016/0893-6080(95)00033-v},
}
Figure