A Continuous Valued Neural Network with a New Evaluation Function of Degree of Unsatisfaction for Solving CSP(Biocybernetics, Neurocomputing)

スポンサーリンク

概要

• 論文の詳細を見る

• We have proposed a neural network called the Lagrange programming neural network with polarized high-order connections (LPPH) for solving the satisfiability problem (SAT) of propositional calculus. The LPPH has gradient descent dynamics for variables and gradient ascent dynamics for Lagrange multipliers, which represent the weights of the clauses of the SAT. Each weight w_r increases according to the degree of unsatisfaction of clause C_r. This causes changes in the energy landscape of the Lagrangian function, on which the values of the variables change in the gradient descent direction. It was proved that the LPPH is not trapped by any point that is not a solution of the SAT. Experimental results showed that the LPPH can find solutions faster than existing methods. In the LPPH dynamics, a function h_r(x) calculates the degree of unsatisfaction of clause C_r via multiplication. However, this definition of h_r(x) has a disadvantage when the number of literals in a clause is large. In the present paper, we propose a new definition of h_r(x) in order to overcome this disadvantage using the "min" operator. In addition, we extend the LPPH to solve the constraint satisfaction problem (CSP). Our neural network can update all neurons simultaneously to solve the CSP. In contrast, conventional discrete methods for solving the CSP must update variables sequentially. This is advantageous for VLSI implementation.

• 社団法人電子情報通信学会の論文
• 2006-04-01

著者

• Nakano Takahiro

  Graduate School Of Life Science And Systems Engineering Kyushu Institute Of Technology

• Nakano Takahiro

  Graduate School Of Engineering Mie University

• NAGAMATU Masahiro

  Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology

• Nagamatu Masahiro

  Graduate School Of Life Science And Systems Engineering Kyushu Institute Of Technology

関連論文

• 9P-E-5 Using the Internal Rewards for a Mobile Robot to Survive and Perform a Task Effectively.(Room E International session)
• Controlling the Diversive and Specific Exploration in Solving Disjunctive Linear Constraint Satisfaction Problem(Contribution to 21 Century Intelligent Technologies and Bioinformatics)
• Quantitative Evaluation of Left Ventricular Wall Motion in Patient with Coronary Artery Bypass Grafting Using Magnetic Resonance Tagging Technique
• A Continuous Valued Neural Network with a New Evaluation Function of Degree of Unsatisfaction for Solving CSP(Biocybernetics, Neurocomputing)
• Lagrange Neural Network for Solving Constraint Satisfaction Problem
• Parallel Execution of Neural Networks for Solving Satisfiability Problem
• Simple but Efficient Method for Parallel Execution of State Space Search
• Lagrangian Method for Solving Software-MCU Assignment Problem in Car Electronic System Design

スポンサーリンク