A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model
The Boolean satisfiability problem, a renowned NP-complete challenge in computer science, has recently garnered interest in the Discrete Hopfield Neural Network - Satisfiability model. This model adeptly integrates logical rules into Hopfield networks, excelling in locating global minima for traditi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157824000168 |
| _version_ | 1797322418774081536 |
|---|---|
| author | Caicai Feng Saratha Sathasivam |
| author_facet | Caicai Feng Saratha Sathasivam |
| author_sort | Caicai Feng |
| collection | DOAJ |
| description | The Boolean satisfiability problem, a renowned NP-complete challenge in computer science, has recently garnered interest in the Discrete Hopfield Neural Network - Satisfiability model. This model adeptly integrates logical rules into Hopfield networks, excelling in locating global minima for traditional SAT problems. However, it faces efficiency challenges when dealing with SAT problems characterized by dynamic evolution constraints due to its static network architecture. During dynamic evolution iterations, there is a significant exponential increase in the computational costs due to redundant and repetitive computations.In order to address this challenge, this paper introduces a dynamic evolution variant of the Discrete Hopfield Neural Network - Satisfiability model. In extensive simulation experiments, we progressively augmented the number of constraint clauses from 1 to 1500, seeking global minima for CNF problems. The proposed model exhibited congruent performance with the traditional model, achieving a Global Minimum Ratio of 1 and a Hamming distance of 0. Crucially, the proposed model minimized CPU utilization and neared zero error metrics, while the traditional model experienced exponential CPU and error metric escalation. These outcomes affirm the proposed model's robust global search capabilities and high precision, aligning with the traditional model. Furthermore, owing to this model's incorporation of not only temporal constraint increment operator but also innovative real-time learning techniques and clever integration methods, along with the establishment of a novel real-time decision mechanism, the proposed model effectively addresses the issues of redundancy and repeated calculations inherent in traditional models. This results in a stable and significantly improved computational speed. Additionally, this model's dynamic evolution network architecture is specifically designed to accommodate arbitrary and efficient extensions of dynamic constraints, while also featuring a built-in preprocessing function to filter out duplicate variables. In the future, as a dynamic evolution processor, this model exhibits immense potential for solving large-scale SAT problems with dynamic evolution constraints and holds broad application prospects in emerging fields such as automated reasoning, intelligent recommendation systems, and machine learning. |
| first_indexed | 2024-03-08T05:14:02Z |
| format | Article |
| id | doaj.art-4e448c2986be4fe09a25c3d24e946614 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2024-03-08T05:14:02Z |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-4e448c2986be4fe09a25c3d24e9466142024-02-07T04:43:51ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782024-01-01361101927A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability modelCaicai Feng0Saratha Sathasivam1College of General Education, Guangdong University of Science and Technology, Guangdong, China; School of Mathematical Sciences, Universiti Sains Malaysia (USM), Penang 11800, MalaysiaSchool of Mathematical Sciences, Universiti Sains Malaysia (USM), Penang 11800, Malaysia; Corresponding author.The Boolean satisfiability problem, a renowned NP-complete challenge in computer science, has recently garnered interest in the Discrete Hopfield Neural Network - Satisfiability model. This model adeptly integrates logical rules into Hopfield networks, excelling in locating global minima for traditional SAT problems. However, it faces efficiency challenges when dealing with SAT problems characterized by dynamic evolution constraints due to its static network architecture. During dynamic evolution iterations, there is a significant exponential increase in the computational costs due to redundant and repetitive computations.In order to address this challenge, this paper introduces a dynamic evolution variant of the Discrete Hopfield Neural Network - Satisfiability model. In extensive simulation experiments, we progressively augmented the number of constraint clauses from 1 to 1500, seeking global minima for CNF problems. The proposed model exhibited congruent performance with the traditional model, achieving a Global Minimum Ratio of 1 and a Hamming distance of 0. Crucially, the proposed model minimized CPU utilization and neared zero error metrics, while the traditional model experienced exponential CPU and error metric escalation. These outcomes affirm the proposed model's robust global search capabilities and high precision, aligning with the traditional model. Furthermore, owing to this model's incorporation of not only temporal constraint increment operator but also innovative real-time learning techniques and clever integration methods, along with the establishment of a novel real-time decision mechanism, the proposed model effectively addresses the issues of redundancy and repeated calculations inherent in traditional models. This results in a stable and significantly improved computational speed. Additionally, this model's dynamic evolution network architecture is specifically designed to accommodate arbitrary and efficient extensions of dynamic constraints, while also featuring a built-in preprocessing function to filter out duplicate variables. In the future, as a dynamic evolution processor, this model exhibits immense potential for solving large-scale SAT problems with dynamic evolution constraints and holds broad application prospects in emerging fields such as automated reasoning, intelligent recommendation systems, and machine learning.http://www.sciencedirect.com/science/article/pii/S1319157824000168Discrete Hopfield neural networkSatisfiability problemLogic programmingDynamic constraintConstrained SAT |
| spellingShingle | Caicai Feng Saratha Sathasivam A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model Journal of King Saud University: Computer and Information Sciences Discrete Hopfield neural network Satisfiability problem Logic programming Dynamic constraint Constrained SAT |
| title | A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model |
| title_full | A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model |
| title_fullStr | A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model |
| title_full_unstemmed | A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model |
| title_short | A novel processor for dynamic evolution of constrained SAT problems: The dynamic evolution variant of the discrete Hopfield neural network satisfiability model |
| title_sort | novel processor for dynamic evolution of constrained sat problems the dynamic evolution variant of the discrete hopfield neural network satisfiability model |
| topic | Discrete Hopfield neural network Satisfiability problem Logic programming Dynamic constraint Constrained SAT |
| url | http://www.sciencedirect.com/science/article/pii/S1319157824000168 |
| work_keys_str_mv | AT caicaifeng anovelprocessorfordynamicevolutionofconstrainedsatproblemsthedynamicevolutionvariantofthediscretehopfieldneuralnetworksatisfiabilitymodel AT sarathasathasivam anovelprocessorfordynamicevolutionofconstrainedsatproblemsthedynamicevolutionvariantofthediscretehopfieldneuralnetworksatisfiabilitymodel AT caicaifeng novelprocessorfordynamicevolutionofconstrainedsatproblemsthedynamicevolutionvariantofthediscretehopfieldneuralnetworksatisfiabilitymodel AT sarathasathasivam novelprocessorfordynamicevolutionofconstrainedsatproblemsthedynamicevolutionvariantofthediscretehopfieldneuralnetworksatisfiabilitymodel |