Discrete Hopfield network combined with estimation of distribution for unconstrained binary quadratic programming problem

摘要

Unconstrained binary quadratic programming problem (UBQP) consists in maximizing a quadratic 0-1 function. It is a well known NP-hard problem and is a unified model for a variety of combinatorial optimization problems. This paper presents a discrete Hopfield neural network (DHNN) combined with estimation of distribution algorithm (EDA) for the UBQP. The idea of EDA is combined with the DHNN in order to overcome the local minima problem of the network. Once the network is trapped in local minima, the perturbation based on EDA can generate a new starting point for the DHNN for further search, which is in a promising area characterized by a probability model. Thus, the proposed algorithm, named DHNN–EDA, can escape from local minima and further search better results. The DHNN–EDA is tested on a large number of benchmark problems with size up to 7000 variables. Simulation results on the UBQP show that the DHNN–EDA is better than the other improved DHNN algorithms such as multi-start DHNN and DHNN with random flips, and is better than or competitive with metaheuristic algorithms such as simulated annealing, tabu search, scatter search and memetic algorithm.