Research ArticleAPPLIED SCIENCES AND ENGINEERING

Transiently chaotic simulated annealing based on intrinsic nonlinearity of memristors for efficient solution of optimization problems

See allHide authors and affiliations

Science Advances  14 Aug 2020:
Vol. 6, no. 33, eaba9901
DOI: 10.1126/sciadv.aba9901
  • Fig. 1 Illustration of a Hopfield network with transiently chaotic dynamics.

    (A) Schematic of a fully connected Hopfield network. (B) Illustration of the network energy surface. A Hopfield network generally contains energy minima as attractors. (C) Standard neuron of a Hopfield network, which sums internal inputs from other neurons and external bias and then generates the output through an activation function. (D) Possible state evolution of a standard Hopfield network. When the initial state is near a local minimum, the network can be easily trapped (black line). (E) Single neuron of a Hopfield network with self-feedback. The output of neuron i is recurrently connected to itself, scaled by the self-feedback weight wii. (F) Schematic of state evolution of a Hopfield network with transient chaos. When chaos is introduced into the network with constant self-feedback weight, the network may get out of local minima but is hard to converge (blue line). While using the transient chaos, the network may converge toward the global minimum (yellow line).

  • Fig. 2 Mapping a Hopfield network with transient chaos onto a single memristor array.

    (A) Illustration of a Hopfield network with transient chaos mapped on the memristor crossbar. The devices in diagonal positions represent self-feedback weights, and the other devices map the constant parameters in optimization tasks, which stay unchanged once the task is determined. Neuronal inputs are translated into voltage pulses with different widths and applied onto the rows of the array, while the output currents are collected in each column. The function of neuron is implemented in software. (B) Scanning electron microscopy image of the Ta/TaOx/Pt memristor array. The inset illustrates the stacking structure of the device. (C) I-V characteristics of the device repeated for 10 cycles. (D) Long-term potentiation/depression characteristics of the device in response to 200 identical pulses for potentiation (1.4 V, 100 μs) and depression (−1.25 V, 2 μs), respectively. (E) Dynamic behavior of a single chaotic neuron without bias. The neuronal output converges to around 0.65 after chaotic searching. (F) Dynamic behavior of a single chaotic neuron with bias (αIi = 0.005). The neuronal output is attracted to 1 after chaotic searching.

  • Fig. 3 Experimental solution of continuous function optimizations with transiently chaotic networks.

    (A) Operation flowchart of the transiently chaotic network based on Ta/TaOx/Pt memristors. (B) Surface of the sphere function with its minimum at point (0, 0). (C) Experimental solution of the sphere function optimization with the transiently chaotic network based on Ta/TaOx/Pt memristors, showing the evolutions of neuronal outputs and corresponding Hopfield energy. (D) Surface of the Matyas function. (E) Experimental solution of the Matyas function optimization with the transiently chaotic network based on Ta/TaOx/Pt memristors, showing the evolutions of neuronal outputs and corresponding Hopfield energy.

  • Fig. 4 Experimental solution of combinatorial optimization problems with transiently chaotic networks.

    (A) Schematic of the Max-cut problem. The given vertices need to be separated into two different groups while maximizing the edge across. (B) Experimental solution of the Max-cut problem with the transiently chaotic network based on Ta/TaOx/Pt memristors, showing the evolutions of neuronal outputs and corresponding Hopfield energy.

  • Fig. 5 Efficient and simplified annealing based on intrinsic nonlinearity of memristors.

    (A) Simulation result for the evolution of the Hopfield network when solving the 10-city TSP problem. The numbers of row and column represent the city and visiting sequence, respectively. The activated neurons are depicted in yellow. (B) Energy evolution of the transiently chaotic network. (C) Evolution of output for an unactivated neuron x11. (D) Evolution of output for an activated neuron x23. (E) Randomly selected traveling route for the TSP problem in question. (F) Optimized traveling route after solution with transiently chaotic network. (G) Probability of getting global minimum and iteration cycles as a function of β when exponential annealing process is adopted. (H) LTD process of the Ta/TaOx/Pt device in response to identical programming pulses (−1.25 V, 2 μs) repeated for 20 cycles. The line indicates the averaged curve. (I) Comparison of linear, exponential, and LTD annealing processes. Each point corresponds to a randomly generated city graph, showing averaged iteration cycles and the probability of finding global optimum from 1000 simulations, i.e., 100 random initial conditions for 10 randomly generated city graphs. (J) Corresponding statistical analysis on the probability of finding global optimum (blue) and average iteration cycles (green).

Supplementary Materials

  • Supplementary Materials

    Transiently chaotic simulated annealing based on intrinsic nonlinearity of memristors for efficient solution of optimization problems

    Ke Yang, Qingxi Duan, Yanghao Wang, Teng Zhang, Yuchao Yang, Ru Huang

    Download Supplement

    This PDF file includes:

    • Figs. S1 to S7

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article