Presentation | 2005/3/22 Parallel Execution of Neural Networks for Solving Satisfiability Problem Kairong Zhang, Masahiro Nagamatu, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | We have proposed a neural network named Langrage programming neural network with polarized high-order connections (LPPH) for solving the SAT, together with parallel execution of LPPHs to increase efficiency. Experimental results demonstrate a high speedup ratio using this parallel execution of LPPHs. Furthermore, it is easy to realize by hardware. LPPH dynamics has an important parameter named attenuation coefficient which strongly affects LPPH execution speed. For parallel execution of LPPHs, it is important to increase diversity of the set of LPPHs. We have proposed a method in which LPPHs have mutually different attenuation coefficients generated by a probabilistic generating function. Experimental results show the efficiency of this method. We also have proposed a LPPH dynamics with a bias. In this paper, to increase the diversity we propose a parallel execution in which LPPHs have mutually different kinds of biases, e.g., a bias toward 1 (positive bias), a bias toward 0 (negative bias), and a bias toward 0.5 (centripetal bias). For some problems, a positive bias has advantage if percentage of 1s is high in a solution, and negative bias if percentage of 0s is high. However the speed of the dynamics of LPPH does not completely depend on the percentage of 1s or 0s. So it is difficult to decide which bias is better before solving a problem. In this paper, we introduce mixed biases to parallel execution of LPPHs. Experimental results show the efficiency of the method. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Lagrange method / neural network / SAT / parallel execution |
Paper # | NC2004-179 |
Date of Issue |
Conference Information | |
Committee | NC |
---|---|
Conference Date | 2005/3/22(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Neurocomputing (NC) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Parallel Execution of Neural Networks for Solving Satisfiability Problem |
Sub Title (in English) | |
Keyword(1) | Lagrange method |
Keyword(2) | neural network |
Keyword(3) | SAT |
Keyword(4) | parallel execution |
1st Author's Name | Kairong Zhang |
1st Author's Affiliation | Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology() |
2nd Author's Name | Masahiro Nagamatu |
2nd Author's Affiliation | Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology |
Date | 2005/3/22 |
Paper # | NC2004-179 |
Volume (vol) | vol.104 |
Number (no) | 759 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |