A HYBRID NEURAL NETWORK MODEL FOR SOLVING OPTIMIZATION PROBLEMS

Abstract

In this paper, we propose a hybrid neural network model for solving optimization problems. We first derive an energy function, which contains the constraints and cost criteria of an optimization problem, and we then use the proposed neural network to find the global minimum (or maximum) of the energy function, which corresponds to a solution of the optimization problem. The proposed neural network contains two subnets: a Constraint network and a Goal network. The Constraint network models the constraints of an optimization problem and computes the gradient (updating) value of each neuron such that the energy function monotonically converges to satisfy all constraints of the problem. The Goal network points out the direction of convergence for finding an optimal value for the cost criteria. These two subnets ensure that our neural network finds feasible as well as optimal (or near-optimal) solutions. We use two well-known optimization problems-the Traveling Salesman Problem and the Hamiltonian Cycle Problem-to demonstrate our method. Our hybrid neural network successfully finds 100 % of the feasible and near-optimal solutions for the Traveling Salesman Problem and also successfully discovers solutions to the Hamiltonian Cycle Problem with connection rates of 40% and 50%.