A noisy self-organizing neural network with bifurcation dynamics for combinatorial optimization

The self-organizing neural network (SONN) for solving general "0-1" combinatorial optimization problems (COPs) is studied in this paper, with the aim of overcoming existing limitations in convergence and solution quality. This is achieved by incorporating two main features: an efficient weight normalization process exhibiting bifurcation dynamics, and neurons with additive noise. The SONN is studied both theoretically and experimentally by using the N-queen problem as an example to demonstrate and explain the dependence of optimization performance on annealing schedules and other system parameters. An equilibrium model of the SONN with neuronal weight normalization is derived, which explains observed bands of high feasibility in the normalization parameter space in terms of bifurcation dynamics of the normalization process, and provides insights into the roles of different parameters in the optimization process. Under certain conditions, this dynamical systems view of the SONN reveals cascades of period-doubling bifurcations to chaos occurring in multidimensional space with the annealing temperature as the bifurcation parameter. A strange attractor in the two-dimensional (2-D) case is also presented. Furthermore, by adding random noise to the cost potentials of the network nodes, it is demonstrated that unwanted oscillations between symmetrical and "greedy" nodes can be sufficiently reduced, resulting in higher solution quality and feasibility.