Modeling of 3 SAT discrete Hopfield neural network optimization using genetic algorithm optimized K-modes clustering

Abstract

The discrete Hopfield neural network 3-satisfiability (DHNN-3SAT) model represents an innovative application of deep learning techniques to the Boolean SAT problem. Existing research indicated that the DHNN-3SAT model demonstrated significant advantages in handling 3SAT problem instances of varying scales and complexities. Compared to traditional heuristic algorithms, this model converged to local minima more rapidly and exhibited enhanced exploration capabilities within the global search space. However, the model faced several challenges and limitations. As constraints in SAT problems dynamically increased, decreased, or changed, and as problem scales expanded, the model's computational complexity and storage requirements may increase dramatically, leading to reduced performance in handling large-scale SAT problems. To address these challenges, this paper first introduced a method for designing network synaptic weights based on fundamental logical clauses. This method effectively utilized the synaptic weight information from the original SAT problem within the DHNN network, thereby significantly reducing redundant computations. Concrete examples illustrated the design process of network synaptic weights when constraints were added, removed, or updated, offering new approaches for managing the evolving constraints in SAT problems. Subsequently, the paper presented a DHNN-3SAT model optimized by genetic algorithms combined with K-modes clustering. This model employed genetic algorithm-optimized K-modes clustering to effectively cluster the initial space, significantly reducing the search space. This approach minimized the likelihood of redundant searches and reduced the risk of getting trapped in local minima, thus improving search efficiency. Experimental tests on benchmark datasets showed that the proposed model outperformed traditional DHNN-3SAT models, DHNN-3SAT models combined with genetic algorithms, and DHNN-3SAT models combined with imperialist competitive algorithms across four evaluation metrics. This study not only broadened the application of DHNN in solving 3SAT problems but also provided valuable insights and guidance for future research.

Keywords

• discrete hopfield neural network
• 3sat
• genetic algorithm
• k-modes clustering