부산대학교 도서관

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.