Solving Satisfiability problem by parallel execution of neural network
|
Accession number;05A0661026
|
| Title;Solving Satisfiability problem by parallel execution of neural network |
| Author;
ZHANG KAIRONG
(Graduate School of Life Sci. and Systems Engineering, Kyushu Inst. Technol., JPN)
NAGAMATSU MASAHIRO
(Graduate School of Life Sci. and Systems Engineering, Kyushu Inst. Technol., JPN)
|
Journal Title;Proceedings of the Annual Conference on JSAI (CD-ROM)
|
Journal Code:X0580B
|
ISSN:
|
|
VOL.19th;NO.;PAGE.1A1-02(2005)
|
| Figure&Table&Reference;FIG.3, REF.3 |
| Pub. Country;Japan |
| Language;Japanese |
| Abstract;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. (author abst.) |
|
|
|
Related Articles;
|
|
