Neural networks for the N-Queens Problem : a review

• Autorzy: Mańdziuk J.
• Języki publikacji: EN

Abstrakty

EN

Neural networks can be successfully applied to solving certain types of combinatorial optimization problems. In this paper several neural approaches to solving constrained optimization problems are presented and their properties discussed. The main goal of the paper is to present various improvements to the wellknown Hopfield models which are intensively used in combinatorial optimization domain. These improvements include deterministic modifications (binary Hopfield model with negative self-feedback connections and Maximum Neural Network model), stochastic modifications (Gaussian Machine), chaotic Hopfield-based models (Chaotic Neural Network and Transiently Chaotic Neural Network), hybrid approaches (Dual-mode Dynamic Neural Network and Harmony Theory approach) and finally modifications motivated by digital implementation feasibility (Strictly Digital Neural Network). All these models are compared based on a commonly used benchmark prohlem - the N-Queens Problem (NQP). Numerical results indicate that each of modified Hopfield models can be effectively used to solving the NQP. Coonvergence to solutions rate of these methods is very high - usually close to 100%. Experimental time requirements are generally low - polynomial in most casos. Some discussion of non-neural, heuristic approaches to solving the NQP is also presented in the paper.

Słowa kluczowe

EN

combinatorial optimization; Hopfield network; N-Queens Problem; neural networks

PL

optymalizacja kombinatoryczna; problem n-hetmanów; sieć Hopfielda; sieć neuronowa

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2002
• Tom: Vol. 31, no 2
• Strony: 217--248
• Opis fizyczny: Bibliogr. 49 poz.,Rys., wykr.,

Twórcy

autor

Mańdziuk J.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Plac Politechniki 1, 00-661 Warsaw, Poland,