Skip Navigation

IEICE Transactions on Information and Systems 2006 E89-D(4):1555-1562; doi:10.1093/ietisy/e89-d.4.1555
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Request Permissions
Google Scholar
Right arrow Articles by NAKANO, T.
Right arrow Articles by NAGAMATU, M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © 2006 The Institute of Electronics, Information and Communication Engineers

Regular Section -- Papers -- Biocybernetics, Neurocomputing

A Continuous Valued Neural Network with a New Evaluation Function of Degree of Unsatisfaction for Solving CSP

Takahiro NAKANO and Masahiro NAGAMATU

The authors are with the Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology, Kitakyushu-shi, 808–0196 Japan. E-mail: nakano-takahiro{at}edu.brain.kyutech.ac.jp, E-mail: nagamatu{at}brain.kyutech.ac.jp

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 wr increases according to the degree of unsatisfaction of clause Cr. 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 hr(x) calculates the degree of unsatisfaction of clause Cr via multiplication. However, this definition of hr(x) has a disadvantage when the number of literals in a clause is large. In the present paper, we propose a new definition of hr(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.

Key Words: neural network, constraint satisfaction problem, Lagrangian method

Manuscript received May 24, 2005. Manuscript revised October 26, 2005.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.