Solving Satisfiability Problem by Parallel Execution of Neural Networks with Biases

We have proposed a neural network named LPPH (Lagrange programming neural network with polarized high-order connections) for solving the SAT (SATisfiability problem of propositional calculus), together with parallel execution of LPPHs to increase efficiency. Experimental results demonstrate a high speedup ratio of this parallel execution. LPPH dynamics has an important parameter named attenuation coefficient which strongly affects LPPH execution speed. We have proposed a method in which LPPHs have different attenuation coefficients generated by a probabilistic generating function. Experimental results show the efficiency of this method. In this paper, to increase the diversity we propose a parallel execution in which LPPHs have mutually different kinds of biases, e.g., positive bias, negative bias, and centripetal bias. Experimental results show the efficiency of this method.

Authors and Affiliations

1. Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology, Kitakyushu, Japan, 2-4, Hibikino, Wakamatsu, Kitakyushu, 808-0196, Japan

   Kairong Zhang & Masahiro Nagamatu

Editors and Affiliations

1. Department of Informatics, Nicolaus Copernicus University, Toruń, Poland

   Włodzisław Duch

2. Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01–447, Warsaw, Poland

   Janusz Kacprzyk

3. Adaptive Informatics Research Centre, Helsinki University of Technology, P.O. Box 5400, 02015, HUT, Finland

   Erkki Oja

4. Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland

   Sławomir Zadrożny

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics