Optimization of N+1 Queens Problem using Discrete Neural Network

Title:

Optimization of N+1 Queens Problem using Discrete Neural Network

Creator:

Waqas, M. and Bhatti, A. A.

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:5a4c3a36-7cb2-4250-a305-72f085c76a42
uuid:5a4c3a36-7cb2-4250-a305-72f085c76a42
doi:10.14311/NNW.2017.27.016

Subject:

neural networks optimatization problem, Hopfielf-Tank model, NP-Hard problem, N + 1 Queens problem, the proximity rule of initialization, and multiprocessor job scheduling

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Combinatorial optimization problems are extensively solved by using neural networks. Hopfield-Tank model is used to solve Traveling Salesman Problem and many NP-Hard Problems. This paper describes a neural network optimizer/scheduler that optimizes a solution for a highly complicated version of N Queens Problem (NQP), i.e. N+1 non-threatening Queens on a N*N chessboard with an intermediate pawn on it. Both synchronous and asynchronous methods of updating of the neurons have been applied for optimization of N+1 Queens Problem. Computer simulations are used to confirm the results. The proposed neural network is attracted to optimized solution or finds the global minima in 90% of the trials. A new rule of initialization, i.e. the proximity rule of initialization has been proposed. Using the proximity rule of initialization the performance of the system is enhanced and the system converges to an optimal solution in much less time. Many novel applications like multiprocessor job scheduling, resource optimization, of the above mentioned algorithm have been proposed. N Queens Problem has been solved by many techniques but no other algorithm exists to solve N+1 QP in the literature. Consequently, the performance of the network is compared with full space search algorithm.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Source:

Neural network world: international journal on neural and mass-parallel computing and information systems | 2017 Volume:27 | Number:3

Harvested from:

CDK

Metadata only:

false