Equilibria of Iterative Softmax and Critical Temperatures for Intermittent Search in Self-Organizing Neural Networks

Optimization dynamics using self-organizing neural networks (SONN) driven by softmax weight renormalization has been shown to be capable of intermittent search for high-quality solutions in assignment optimization problems. However, the search is sensitive to temperature setting in the softmax renormalization step. The powerful search occurs only at the critical temperature that depends on the problem size. So far the critical temperatures have been determined only by tedious trial-and-error numerical simulations. We offer a rigorous analysis of the search performed by SONN and derive analytical approximations to the critical temperatures. We demonstrate on a set of N-queens problems for a wide range of problem sizes N that the analytically determined critical temperatures predict the optimal working temperatures for SONN intermittent search very well.