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

Abstract

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.