2-SAT discrete Hopfield neural networks optimization via Crow search and fuzzy dynamical clustering approach

1.   Introduction

The SAT problem is a classic NP-complete problem in computer science ^[1]. The fundamental objective of the SAT problem is to determine whether a given Boolean logic expression has a set of Boolean variable assignments that make the expression true (satisfiable). This problem holds significant importance in both theoretical computer science and practical applications, such as logic programming, circuit design, and artificial intelligence. Various methods exist to solve the SAT problem, including traditional exhaustive search methods, branch and bound, learning and backtracking techniques, specialized SAT solvers, and neural computational approaches. Among these, the application of discrete Hopfield Neural Networks (DHNN) for solving the SAT problem has garnered widespread attention as an emerging research direction.

Discrete Hopfield Neural Networks (DHNN) are a classical self-feedback neural network model ^[2]. DHNN acquires the weight matrix of the objective function using Hebbian learning and dynamically updates to a stable state based on the principle of energy minimization, which corresponds to potential solutions of the objective function. Due to its unique energy minimization characteristics, DHNN is often used as a tool for solving combinatorial optimization problems. The SAT problem is essentially a combinatorial optimization problem. In recent years, with breakthroughs in neural symbolic learning on neural networks and the discovery of the Wan Abdullah learning method, researchers have found a suitable way to embed the SAT problem as an objective function in discrete Hopfield networks and obtain solutions to the SAT problem.

In 1992, Wan Abdullah introduced a novel DHNN learning method that successfully embedded special logic programming as symbolic rules into discrete Hopfield neural networks ^[3]. This method, equivalent to traditional Hebbian learning, was formally named the Wan Abdullah learning method (WA method) in 2011 ^[4]. In WA method, logic rules of the SAT problem are learned in Conjunctive Normal Form (CNF) and stored in the form of an optimal weight matrix. Neurons in the neural network store the truth values of atomic propositions, and different combinations of neuron states express different logical clauses. A cost function corresponding to the CNF is constructed using logic inconsistency theory, and the optimal weight matrix representing the CNF is learned by comparing the cost function with the energy function. WA method embeds logic rules into DHNN, effectively storing the SAT problem as an objective function in DHNN. Building upon this, an Exhaustive search algorithm ^[5] is applied to retrieve the global minimum of the SAT problem. Starting with an initial assignment in the assignment space, neurons calculate local fields based on the optimal weight matrix and update to the state of minimum energy following the principle of energy minimization. This minimum energy state of the network corresponds to the global minimum of the SAT problem, which is also a consistent interpretation to the CNF ^[6]. This makes all clauses of the CNF true, rendering the CNF satisfied with its cost function of 0. The size of the assignment space is ${2}^{N}$, where $N$ represents the number of variables in the CNF.

In 2014, Sathasivam et al. successfully embedded high-order Horn SAT into DHNN ^[6]. Different logic rules typically represent constraints or conditions of different types of real-world scenarios related to SAT. Motivated by this, researchers have continued to develop DHNN models with different types of logic rules for SAT problems, successfully obtaining the desired solutions. In 2017, Kasihmuddin et al. proposed DHNN for 2-SAT problems ^[5], and subsequently, Mansor et al. introduced DHNN for 3-SAT problems with higher-order logic rules ^[7]. Considering that not all combinatorial problems are inherently satisfiable, DHNN models based on maximum K-SAT logic rules were proposed in 2018 ^[8]. In 2020, Sathasivam proposed the DHNN-RAN-2-SAT model incorporating first and second-order logic rules ^[9]. In 2023, DHNN with 3-SAT fuzzy logic was introduced by Azizan and Sathasivam ^[10]. These DHNN-based models for SAT, collectively referred to as DHNN-SAT models or DHNN-SAT-WA models, have been applied to solve various constraint optimization problems ^{[11,12,13,14,15]}, owing to the diversity of logic rules they encompass. However, as researchers have delved deeper into DHNN-SAT models, they have discovered that due to the inherent limitations of discrete Hopfield neural networks, the computational efficiency of DHNN-SAT models is not optimal for large-scale problems, and they tend to get trapped in local minima. To mitigate these issues, scholars have attempted to incorporate heuristic elements to enhance the accuracy of DHNN-SAT models in the optimization process ^{[16,17,18,19,20]}. Currently, these studies have shown promising results in achieving high global minimum value ratios, representing accuracy, in models with fewer neurons ^[21].

However, the DHNN-SAT model, as a hybrid network integrating discrete Hopfield neural networks and SAT problem rules, faces challenges not only due to the limitations of discrete Hopfield neural networks but also due to the logical complexity of SAT rules. As the logical complexity of SAT rules increases, interference between neurons and the redundancy of neurons also increase, leading to a drastic decrease in model computational accuracy and speed. Therefore, addressing how to enhance the solving capability, and improve the accuracy, and speed of DHNN-SAT models under the influence of both model size and logical complexity is an urgent task. Presently, the literature on this topic is notably scarce. In 2011, Sathasivam discussed the use of fuzzy logic to solve logic programs with lower logical complexity ^[22]. In this work, each clause of the CNF contained a positive literal, guaranteeing the existence of at least one satisfying solution. This article focuses on binary satisfiability problems (2-SAT) with more complex logical relations. In 2-SAT, each clause is composed of exactly two literals (Boolean variables or their negations), and the entire Boolean formula represents the conjunction (AND operation) of these clauses. 2-SAT, as a fundamental subset of Boolean satisfiability problems, holds profound significance in the fields of computational theory and algorithm design. Due to its simpler problem representation ^[23,24], it has gained favor among researchers in various domains ^{[25,26,27,28]}. In traditional DHNN-2SAT models, as the model size and logical complexity increase, numerous interferences and redundancies occur among neurons, leading to a rapid decrease in the number of global minima and more frequent oscillations. Moreover, the final convergence state of the model increasingly depends on its initial configuration, limiting the solution of the model to specific problems. As logical complexity continues to increase and enters the realm of hard-to-solve areas, 2-SAT problems shift from having many satisfying solutions to being hard to satisfy, resulting in poor solution accuracy and speed for the model.

On one hand, considering that, during the application of the traditional Exhaustive search algorithm to retrieve global minima, as the number of neurons and logical complexity increase, interference and redundancy affect the logical inconsistency of each CNF of initial assignments in the assignment space. The degree of logical inconsistency determines whether the CNF can successfully converge to satisfying solutions. Fortunately, the cost function benefits from its unique structure, which enables it to quantify the degree of initial assignment inconsistency of CNFs. Inspired by this, this paper employs fuzzy clustering techniques to cluster initial assignments in the assignment space, filtering out potential satisfying solutions. Compared to the Exhaustive search algorithm, this significantly reduces the search space, improving retrieval speed. On the other hand, considering that, in the context of CNFs, only global minima correspond to useful consistent explanations. Fuzzy clustering is essentially a local search technique and highly sensitive to the choice of cluster centers. To ensure that the model maintains excellent global optimization capability in hard-to-solve areas with a large number of neurons and high logical complexity, it is crucial to introduce a global optimization algorithm to guide the selection of optimal initial cluster centers for fuzzy clustering. Therefore, this paper selects the novel Crow Search Algorithm (CSA) to guide fuzzy clustering in the context of global optimization, proposing the DHNN-2SAT model with Crow search algorithm-guided fuzzy clustering (DHNN-2SAT-CSAFC model). To comprehensively assess the performance of the proposed DHNN-2SAT-CSAFC model, this paper incorporates another renowned global optimization algorithm, the Genetic Algorithm. This integration results in the creation of the DHNN-2SAT-GAFC model. In order to establish a robust benchmark for comparison, the traditional DHNN-2SAT-WA model, which employs the Exhaustive search algorithm, is included alongside the DHNN-2SAT-CSAFC model as a control group.

The remainder of this paper is organized as follows: Section 2 provides the foundational knowledge, including an introduction to DHNN models, the Wan Abdullah method, fuzzy C-means clustering, and the Crow search algorithm. In Section 3, the implementation and workflow of the DHNN-2SAT-CSAFC model, guided by the Crow search algorithm, are described in detail. In Section 4, a series of simulation experiments are conducted to solve target 2-SAT problems of different scales and logical complexities. The results are analyzed and compared among the proposed DHNN-2SAT-CSAFC model and two reference models: the traditional Exhaustive search algorithm-based DHNN-2SAT-WA model and the Genetic Algorithm-guided fuzzy clustering-based DHNN-2SAT-GAFC model, using five evaluation metrics. Finally, in Section 5, this work is summarized.

2.   Preliminary knowledge

2.1.   The discrete Hopfield neural network

The Discrete Hopfield Neural Network (DHNN) is a recursive neural network renowned for its proficient associative memory functions. A key distinguishing feature of DHNN is the use of an energy function to gauge the stability of the network state. DHNN constitutes a monolayer network comprising N neurons, designated as $\{{x}_{1}, {x}_{2}, \cdots, {x}_{N}\}$. The state of each neuron is bipolar, conventionally denoted as ${S}_{i}\in \{-\mathrm{1, 1}\}$. Neurons engage in bidirectional communication, transmitting their outputs to other neurons via synaptic connections while concurrently receiving input from other neurons, as shown in Figure 1. Synaptic weight ${W}_{ij}$ between neurons ${x}_{i}$ and ${x}_{j}$ undergo learning via the Hebbian rule.

The synaptic weights are strictly symmetric. Each neuron maintains full connectivity without self-feedback, leading to ${W}_{jj} = {W}_{ii} = 0$.

The input of neuron ${x}_{i}$ at time $t$ is referred to as the "local field, " denoted as

where ${S}_{i}$ is the state of unit ${x}_{i}; {W}_{ij}$ is the synaptic weight from ${x}_{j}$ to ${x}_{i}$; and ${W}_{i}$ is the predefined threshold for ${x}_{i}$.

The activated neurons adhere to the well-known McCulloch-Pitts Updating Rule and update their states according to the formula (3) based on the local field's magnitude. influenced by minimal energy excitation, the network converges to a stable state. In this context, the activation function is typically chosen to be a binary sign function, consistent with the Discrete Hopfield Neural Network.

The Lyapunov energy function is expressed as follows,

Because the output variation $\Delta {H}_{P}$ can only be 0 or negative values, energy can only decrease or remain constant with each update during the network's dynamic evolution.

For each stable state, its Lyapunov energy $H$ is computed, and it is determined whether this stable state is the global minimum based on whether the energy reaches the minimum energy. If the conditions specified in Eq (5) are met, then the stable state is considered a global minimum. Otherwise, it is deemed a local minimum.

Here, ${H}_{P}^{min}$ represents the Lyapunov minimum energy, and $\sigma$ represents the user-defined tolerance value.

2.2.   Wan Abdullah method

The Wan-Abdullah (WA) method leverages principles from logical programming theory to construct a cost function, providing a unique perspective on developing a novel learning approach for DHNN by uncovering logical relationships among neurons. Recognized as one of the earliest learning methods based on logical inconsistency for extracting synaptic weights ^[3], the WA method has been empirically demonstrated to be equivalent to Hebbian learning ^[4].

In the Wan Abdullah method, the rationality and effectiveness of representing various logical rules for the SAT problem in the form of Conjunctive Normal Form (CNF) clauses within the framework of neural symbol integration have been explicitly demonstrated in ^[29]. Consequently, various logical rules for the SAT problem are expressed in CNF and corresponding cost functions are constructed.

By comparing these cost functions with energy functions, optimal connection weights representing the logical rules are learned. Finally, these optimal weights are stored in the Discrete Hopfield Neural Network in the form of the best weight matrix.

The subsequent section elucidates the precise principles and sequential procedures entailed in acquiring synaptic weights via the utilization of the WA method.

Step 1. For the given 2SAT formula below, associate the Boolean variables ${S}_{\alpha }$ and ${S}_{\beta }$ with the binary neurons ${x}_{\alpha }$ and ${x}_{\beta }$ of the Hopfield neural network.

Step 2. Apply De Morgan's law for negation of $P$,

Step 3. Construct the cost function ${E}_{p}$ for $\neg P$, where $\frac{1}{2}\left({1-S}_{X}\right)$ and $\frac{1}{2}\left({1+S}_{X}\right)$ represent the logical values of neurons $X$ ($X$ occurs) and $\neg X$ ($X$ does not occur) within $\neg P$. Here, if $X$ is true, then ${S}_{X}$ equals 1, and if $X$ is false, then ${S}_{X}$ equals -1. Utilize multiplication to denote conjunction connectors and addiction to represent disjunction connectors. Therefore, the cost function for Eq (6) is as follows:

It is worth noting that in this specific construction method, the cost function ${\mathrm{E}}_{\mathrm{p}}$ exhibits a notable feature: its value is directly correlated with the quantity of inconsistent clauses.

Step 4. Seek a consistent interpretation for $P$, which involves finding the combination of minimum values for $\neg P$'s inconsistencies. The minimum value of ${E}_{p}$ corresponds to the "most consistent" selection for S. Through a comparative analysis of cost function (8) and energy function (5), the specific synaptic weight values can be determined, as outlined in Table 1. The flowchart for the Wan Abdullah method can be found in Figure 2.

2.3.   Fuzzy C-means clustering method

The Fuzzy C-Means (FCM) clustering algorithm, initially introduced by Dunn ^[30] and subsequently advanced by Bezdek ^[31], stands as a significant cornerstone within the realm of fuzzy clustering methodologies. Fuzzy C-Means (FCM) leverages the principles of fuzzy mathematics to express the probability of each sample belonging to different clusters as values ranging from 0 to 1. This enables each sample to be associated with multiple distinct classes. The clustering process involves the minimization of an objective function.

Let $X = \{{x}_{1}, {x}_{2}, \cdots, {x}_{n}\}$ be the data set and $X$ have to be partitioned into C clusters based on the features of the data set. Using distance as the metric for similarity evaluation, the membership degree of sample ${x}_{j}$ to class ${X}^{i}$ is defined as

${\mu }_{ji}\in \left[\mathrm{0, 1}\right]$ also needs to satisfy equations (10) and (11).

m is the fuzzification parameter. It is used to dominate the influence of membership grade and therefore the centroids and reduces the noise sensitivity in the computation of the centroids.

The objective function of FCM is as follows

The centroids are updated according to the following formula

Following the update of all centroids, it is imperative to recompute the fresh membership values. This iterative procedure persists until consecutive iterations converge to identical centroid positions or until the saturation of the objective function is attained. In culmination, guided by the computed membership values across all classes for each individual sample, the assignment of samples to their appropriate categories is achieved, thereby automating the process of sample data classification. Figure 3 depicts the flowchart for the fuzzy C-means clustering method.

2.4.   Crow search algorithm

The Crow search algorithm (CSA) is a metaheuristic optimization algorithm inspired by the intelligent behavior of Crows. It was introduced by Alireza Askarzadeh in 2016 ^[32] and achieves a balance between local and global search by controlling two key parameters: flight length and perception probability. Unlike many other well-known heuristic algorithms, CSA requires fewer parameter adjustments and is relatively easy to implement. Consequently, it has found widespread applications in diverse optimization problem domains, including power systems ^[33], healthcare ^[34], image processing ^[35], and chemical engineering ^[36], among others.

In this optimization scheme, each Crow serves as a representative of a potential solution to the problem under consideration. The assessment of these solutions hinges on their fitness, a measure dictated by the objective function. Assuming there are $n$ Crows, each with its food stash hidden in an undisclosed location, we operate within a predetermined limit of maximum iterations, denoted as ${T}_{max}$. Within the $t$-th iteration, the positions of Crow $k$ and its best-remembered location are ${x}_{t}^{k}$ and ${mem}_{t}^{k}$, respectively. Crow $k$ then embarks on a random pursuit of Crow $j$, in hopes of unveiling the hiding place of Crow $j$ 's sustenance. Two distinct scenarios unfold in this endeavor:

(a)   Crow $j$ remains oblivious to the fact that Crow $k$ is tracking it, thereby leading Crow $k$ to the spot where food is concealed.

(b)   Crow $j$, discerning Crow $k$ 's tracking intent, endeavors to safeguard the location of its

sustenance by misleading Crow $k$, luring it to an alternate random spot within the search space.

Using $AP$ to represent the perception probability of Crow $j$ being tracked. The position update equation for Crow $k$ manifests as follows:

Here, ${r}_{k}\in \left(\mathrm{0, 1}\right)$ signifies the random probability associated with Crow $k$, while $fl$ represents the flight length. An excessively modest flight length may entrap us within a local minimum, whereas an extended flight length may unveil a global minimum.

We subsequently compute the fitness value ${f(x}_{t+1}^{k})$ pertaining to the novel position. If the fitness value of this newfound location surpasses that of the previously remembered position, update the memory of Crow $k$.

The iteration terminates when the termination criterion is met, and the global optimal solution is output. Figure 4 illustrates the flowchart of the Crow search algorithm.

3.   Development of the DHNN-2SAT model integrated with the Crow search-guided fuzzy clustering hybrid optimization algorithm

3.1.   Designing the Crow search algorithm-guided fuzzy clustering hybrid optimization algorithm for enhancing the DHNN-2SAT model

The conventional DHNN-2SAT-WA model utilizes an exhaustive search algorithm in the retrieval phase, tasked with updating, ensuring convergence, and evaluating each random initial assignment within the assignment space of size '${2}^{N}$'. Its goal is to search for consistent interpretations satisfying 2-SAT clauses. However, as the network's size and logical complexity increase, interference and redundancy between neurons intensify, leading to a rapid contraction of the solution space. More and more random initial assignments experience a staggering increase in their corresponding cost functions due to the growing number of inconsistent clauses. These initial assignments tend to exhibit significant oscillations during subsequent updates, making the model susceptible to local minima, prolonged convergence cycles, or even convergence failure.

Addressing these challenges posed by the traditional DHNN-2SAT-WA model, this paper introduces a novel solution: Crow Search-guided Fuzzy Clustering-based Hybrid Optimization DHNN-2SAT model, abbreviated as DHNN-2SAT-CSAFC. In the DHNN-2SAT-CSAFC model, the initial assignments within the assignment space are subjected to fuzzy clustering based on the cost function, as its size directly relates to the number of inconsistent clauses. This process identifies potential solutions, significantly reducing the search space and improving retrieval efficiency.

However, fuzzy clustering inherently represents a local search technique and is highly sensitive to cluster center selection. Concurrently, the 2-SAT problem mandates stringent quality criteria for solutions. In the context of CNF, only the global minimum corresponds to consistent interpretations. Therefore, incorporating the Crow Search method, one of the latest global optimization metaheuristics, to guide fuzzy clustering for optimal initial cluster center selection can substantially enhance global optimization capabilities. CSA has been proven to have a significant advantage in various optimization domains, particularly when integrated with FCM. References ^{[37,38,39,40,41,42,43]} highlight CSA's effectiveness in a variety of optimization fields, especially its integration with FCM ^[44,45,46].

3.2.   Workflow of the DHNN-2SAT-CSAFC model

The DHNN-2SAT-CSAFC model represents an innovative amalgamation of the DHNN-2SAT framework with the Crow Search Fuzzy Clustering Hybrid Optimization Algorithm. Its primary objective is convergent to a set of Boolean variable assignments that adhere to the CNF formula associated with the 2SAT problem. During the model's initialization phase, a fundamental mapping is established: each neuron within the Hopfield network is linked to a specific Boolean variable within the CNF. In practice, neurons serve as repositories for preserving the truth values of atomic variables, while synaptic weights serve as a representation of the intricate relationships that exist between variables and clauses.

Subsequent to initialization, the operational workflow of this model unfolds through two pivotal phases: the learning phase and the retrieval phase. During the learning phase, the acquisition of synaptic weight matrices is orchestrated through the utilization of the WA learning methodology. As the model progresses to the retrieval phase, activated neurons undertake iterative updates, adjusting their local fields and states in alignment with predefined update rules. This iterative process continues until the network converges to a stable equilibrium, during which the dynamic energy function undergoes a consistent monotonic descent.

Ultimately, the pivotal role of the energy function is in determining whether this stabilized equilibrium corresponds to the global minimum of the 2SAT problem. The identification of the global minimum signifies a coherent interpretation of the CNF. The specific implementation steps of the DHNN-2SAT-CSAFC model are outlined as follows:

Step 1. Model initialization.

For a given 2SAT problem, translate into the corresponding CNF formula, denoted as $P$. Let $P$ contain $n$ Boolean variables and $m$ clauses. The initialization of various parameters within the optimization algorithm is also carried out.

Step 2. Neuron assignment.

Each Boolean variable is uniquely assigned a Hopfield neuron, with neurons used to store the truth values of individual atoms. Consequently, the Hopfield network is configured with $n$ neurons $\{{x}_{1}, {x}_{2}, \cdots, {x}_{n}\}$, and their corresponding states at time $t$ are denoted as $\left\{{S}_{1}\right(t), {S}_{2}(t), \cdots, {S}_{n}(t\left)\right\}$.

Step 3. Learning phase.

During this phase, the model acquires synaptic weights using the WA method. The cost function ${E}_{P}$ for the negation of $\neg P$ is derived, followed by the computation of synaptic weights through a comparison between the cost function ${E}_{P}$ and the energy function $H$.

Step 4. Retrieval phase.

A batch of $M$ random initial assignments $\{{P}_{1}, {P}_{2}, \cdots, {P}_{M}\}$ is generated during this phase, where ${P}_{i} = {P}_{i}\left(S\left(t\right)\right) = {P}_{i}\left({S}_{1}\left(t\right), {S}_{2}\left(t\right), \cdots, {S}_{n}\left(t\right)\right), 1\le i\le M$. These assignments may or may not constitute consistent interpretations of the CNF formula. The cost function ${E}_{P} = \{{E}_{{P}_{1}}, {E}_{{P}_{2}}, \cdots, {E}_{{P}_{M}}\}$ for these initial assignments is computed based on Eq (7).

Step 5. Fuzzy clustering with Crow search guidance.

Leveraging the cost function, a fuzzy clustering algorithm guided by Crow search is employed to cluster $\{{P}_{1}, {P}_{2}, \cdots, {P}_{M}\}$. Pre-select a subset of random initial assignments with favorable cost functions, denoted as ${A}_{k} = {A}_{k}\left(S\left(t\right)\right) = {A}_{k}\left({S}_{1}\left(t\right), {S}_{2}\left(t\right), \cdots, {S}_{n}\left(t\right)\right), k\in Z, t = 0$. Initially, the Crow search algorithm minimizes an objective function ${J}_{m}$ identical to that of the fuzzy clustering algorithm, resulting in optimal centroid solutions ${V}_{best} = \{{v}_{1}, {v}_{2}, \cdots, {v}_{C}\}$. Subsequently, fuzzy clustering is carried out. Importantly, the minimization process of the objective function is guided by CSA, rather than an iterative steepest descent process.

Step 6. Local field calculation.

For each ${A}_{\_k}\left(S\left(t\right)\right) = {A}_{\_k}({S}_{1}\left(t\right), {S}_{2}\left(t\right), \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\cdots, {S}_{n}\left(t\right)), k = 0, t = 0$, calculates its local field ${A}_{\_k}\left(h\left(t\right)\right) = {A}_{\_k}\left({h}_{1}\right(t), {h}_{2}(t), \mathrm{ }\cdots,$ ${h}_{n}\left(t\right))$.

Step 7. State updating and stability determination.

Each neuron state within ${A}_{\_k}\left({S}_{1}\left(t\right), {S}_{2}\left(t\right), \cdots, {S}_{n}\left(t\right)\right)$ is updated according to the McCulloch-Pitts Updating Rule, with ${S}_{i}(t+1) = sign\left({h}_{i}\right(t\left)\right) = \left\{\begin{array}{c}1, {h}_{i}\left(t\right)\ge 0\\ -1, {h}_{i}\left(t\right) < 0\end{array}\right.$, until a stable state is reached. If, after five consecutive runs, the neuron states remain consistent (i.e., ${A}_{\_k}\left(S\right(t\left)\right) = {A}_{\_k}\left(S\right(t-1\left)\right)$ = ${A}_{\_k}\left(S\right(t-2\left)\right)$ = ${A}_{\_k}\left(S\right(t-3\left)\right)$ = ${A}_{\_k}\left(S\right(t-4\left)\right)$), the final state ${A}_{\_k}\left(S\right(t\left)\right)$ is defined as the stable state.

Step 8. Global minimum energy assessment

The stability state's energy ${H}_{{A}_{\_k}}$ is assessed using the Lyapunov energy criteria. If the following condition (5) is met $\left|{{H}_{{A}_{\_k}}-H}_{P}^{min}\right| < \mathrm{\sigma }$. Where ${H}_{P}^{min}$ represents the global minimum energy, and $\mathrm{\sigma }$ is the tolerance value predetermined by the user, then the stability state ${A}_{\_k}\left(S\right(t\left)\right)$ is recognized as the global minimum and is stored. Otherwise, if it does not meet this condition, it is considered a local minimum, and $k = k+1$, leading to a repeat of Step 6.

Step 9. Calculation of metrics

This final step involves calculating metrics such as the global minima ratio, Hamming distance, CPU time, retrieval rate of stable state, and retrieval rate of global minima. Figure 5 presents the flowchart of the DHNN-2SAT-CSAFC model.

4.   Experiments on simulated datasets

4.1.   Introduction to the experiments

To accurately assess the performance of the proposed DHNN-2SAT-CSAFC model and enhance the robustness of experimental results, this experiment encompasses two control group models: the traditional DHNN-2SAT-WA model, which employs the exhaustive search algorithm, and another model, DHNN-2SAT-GAFC, guided by genetic algorithms for fuzzy clustering-based hybrid optimization.

Considering the high precision requirements for SAT problem solutions and the significant impact of the chosen optimization algorithm on the success rate and efficiency of consistent interpretations' search, it was crucial to examine whether the selection of CSA as the global optimization algorithm to guide fuzzy clustering, was a prudent choice. Despite several studies ^{[47,48,49,50,51]} suggesting that CSA requires relatively few parameter adjustments compared to other metaheuristic algorithms such as Particle Swarm Optimization (PSO), Shark Algorithm (SA), Genetic Algorithm (GA), Weed Algorithm (WA), Grey Wolf Optimizer (GWO), Sine Cosine Algorithm (SCA), Bat Algorithm (BA), Firefly Algorithm (FA), Moth Flame Optimization (MFO), Whale Optimization Algorithm (WOA), Invasive Weed Optimization (IWO), and Electromagnetic Mechanism-based Algorithm (EM), which have demonstrated superior performance in specific application domains. However, adhering to rigorous scientific research principles, this experiment additionally introduces another control group model, DHNN-2SAT-GAFC, guided by genetic algorithms for fuzzy clustering-based hybrid optimization. In this DHNN-2SAT-GAFC model, another classic global optimization algorithm, Genetic Algorithm, was chosen to guide the fuzzy clustering process. Genetic Algorithm (GA), initially proposed by John Holland in 1975 ^[52], serves as an early heuristic algorithm embedded within the Fuzzy Clustering method (GAFC), and it has found wide applications across domains such as transportation and classification problems ^{[53,54,55,56]}.

In this simulation experiment for solving the 2-SAT problem, we utilized MATLAB R2021b, running on a laptop equipped with the Windows 11 operating system, an AMD Ryzen R7-5800H processor, and 16GB of RAM. During the experiment, we optimized the relevant parameters, as detailed in Tables 2–4, through iterative adjustments based on trial and error. The logical complexity of a propositional formula is measured by the ratio of the number of clauses to the number of Boolean variables, known as the constraint rate coefficient or constraint density. The number of neurons ranged from 10 to 100 in increments of 10, while the constraint ratio coefficient varied from 0.1 to 2.0 in steps of 0.1. To mitigate statistical errors, we conducted 100 trials with different neuron combinations for each level of logical complexity, with each combination undergoing 250*NN experiments. Simulated datasets were employed to evaluate the performance of the DHNN-2SAT-WA, DHNN-2SAT-GAFC, and DHNN-2SAT-CSAFC models using five performance evaluation metrics: global minima ratio, Hamming distance, CPU time, retrieval rate of stable states, and retrieval rate of global minima.

4.2.   Results and discussion

4.2.1.   Global minima ratio

The Global Minima Ratio (GMR) is a metric defined as the ratio of global minima count to the total number of solutions ^[57]. For example, if the GMR value equals 0.9605, it signifies that out of 10,000 simulated results, 9,605 correspond to global minima, while the remaining 395 represent local minima solutions. GMR is a dependable measure of algorithm efficiency, with a value near 1 indicating model robustness ^[58].

Figures 6 and 7 illustrate the GMR results concerning diverse logical complexities and varying numbers of neurons. At lower logical complexities, all three models benefit from the robust global search capability of the discrete Hopfield neural network model with SAT. Every neuron converges toward the global optimal solution, yielding a GMR of 1.

However, as the constraint ratio coefficient escalates from 0.1 to 2.0 while maintaining a constant number of neurons, logical complexity surges. Different logical clauses start to interfere with each other due to sharing the same atomic elements ^[4]. Coupled with a significant amount of logical redundancy, this leads to a rapid reduction in the solution space, making it increasingly challenging for models to retrieve satisfying solutions. Consequently, the GMR also declines swiftly. Notably, even in such scenarios, the DHNN-2SAT-CSAFC and DHNN-2SAT-GAFC models, incorporating optimization methods, consistently demonstrate significantly higher GMR values than the conventional DHNN-2SAT-WA model.

According to Table 5, as the number of neurons increases from 10 to 100, the average GMR for the HNN-2SAT-CSAFC model is 1.173 times that of the HNN-2SAT-WA model and 1.053 times that of the HNN-2SAT-GAFC model. This can be attributed to the Crow search algorithm-guided fuzzy clustering, which preselects initial assignments with strong logical consistency, effectively directing the reduction of network energy.

4.2.2.   Hamming distance

Hamming distance serves as a metric to gauge the precision of model solutions by quantifying the disparity in bits between stable states and global minimum values. A Hamming distance nearing zero signifies a more precise convergence of stable states toward the global minimum.

Figures 8 and 9 illustrate that at lower constraint ratio coefficients, all three models, with varying numbers of neurons, exhibit Hamming distances that are essentially zero. When the number of neurons remains constant and the constraint ratio coefficient gradually increases to 2.0, the network's memory capacity diminishes, leading to a reduced solution space. Although the Hamming distance gradually increases under these conditions, it still maintains a relatively low level.

With the number of neurons expanding from 10 to 100, even though an increase in redundant and duplicated variables may introduce some interference to the weights, the connections among neurons become more intricate and closely interconnected. As a result, the models' learning capabilities not only remain unimpaired but also encourage a further convergence of final states toward the global minimum Hamming distance. Table 6 reveals that the average Hamming distance for the DHNN-2SAT-CSAFC model is 0.668 times that of the DHNN-2SAT-WA model and 0.898 times that of the DHNN-2SAT-GAFC model. This indicates that all three models perform exceptionally well in terms of precision when solving the 2-SAT problem. Notably, the HNN-2SAT-CSAFC model excels in conducting more precise global searches.

4.2.3.   CPU time

CPU time refers to the average time required for each model to achieve a global minimum value. Smaller average CPU times indicate higher computational efficiency for the models.

Figures 10 and 11 provide insights that when the number of neurons is relatively low, neither the DHNN-2SAT-CSAFC model nor the DHNN-2SAT-GAFC model exhibits a notable advantage. This is because utilizing the Crow search algorithm or Genetic Algorithm to guide the optimal centroids consumes time.

However, with an increase in the number of neurons and constraint rate coefficient, due to the fully connected nature of DHNN where each neuron is connected to every other neuron, the computational cost grows exponentially. The traditional HNN-2SAT-WA model, which employs the Exhaustive search algorithm, needs to retrieve randomly generated initial assignments from the assignment space within a given time threshold, incurring significant time costs. In contrast, the HNN-2SAT-CSAFC and HNN-2SAT-GAFC models benefit from the integration of different optimization algorithms, implementing directed filtering of random assignments within the assignment space, significantly reducing the search space and thus greatly decreasing computational time.

Furthermore, as shown in Table 7, when the number of neurons increases from 10 to 100, the computational speed of the HNN-2SAT-CSAFC model is 0.131 times that of the HNN-2SAT-WA model and 0.414 times that of the HNN-2SAT-GAFC model. Moreover, as the constraint ratio coefficient increases, the speed advantage of HNN-2SAT-CSAFC exhibits a noticeable linear growth trend. This indicates that within the same given time frame, the number of consistent interpretations obtained using the proposed HNN-2SAT-CSAFC model is 7.6334 times and 2.415 times that of the other two control models, respectively. Clearly, Crow Search-guided fuzzy clustering, due to its fewer parameters and simpler implementation, is more effective in reducing the computational complexity of the 2-SAT problem and accelerating global search compared to the other two models.

4.2.4.   Retrieval rate of stable state and retrieval rate of global minimum

With the increase in network capacity and logical complexity, the solution space contracts, making it increasingly difficult for models to discover the global minimum within specified timeframes. Especially when network capacity and logical complexity reach a certain threshold, the 2-SAT problem enters the region of difficulty in solving, where extensive search efforts during the retrieval phase often end in vain. At this point, the focus of model improvement is to maximize the success rate of locating the global minimum and even local minima within each retrieval task. To assess the success rate of model retrieval efforts, we introduce two novel evaluation criteria: the retrieval rate of stable states and the retrieval rate of the global minimum. Specifically, the retrieval rate of stable states is defined as the ratio of the number of stable states to the total number of retrievals, while the retrieval rate of the global minimum is defined as the ratio of the number of global minima to the total number of retrievals.

Figures 12 to 15 illustrate that both the DHNN-2SAT-CSAFC model and the DHNN-2SAT-GAFC model effectively leverage optimization algorithms to identify potential solutions, substantially enhancing the model's success rate. Data presented in Tables 8 and 9 indicate that as the number of neurons increases from 10 to 100, the retrieval rate of stable states and the retrieval rate of the global minimum for the DHNN-2SAT-CSAFC model are 2.423 and 2.726 times that of the DHNN-2SAT-WA model, respectively, and 1.105 and 1.157 times that of the DHNN-2SAT-GAFC model. When the search region enters the challenging zone, the retrieval rates of stable states and the retrieval rates of the global minimum experience a sharp decline, almost approaching zero. In such circumstances, the DHNN-2SAT-CSAFC model effectively boosts the retrieval rate of stable states and the retrieval rate of the global minimum to approximately four times that of the traditional model.

5.   Experiments on real-world datasets

In Chapter 4, we exhaustively demonstrated the significant advantages of the HNN-2SAT-CSAFC model over traditional HNN-2SAT-WA and HNN-2SAT-GAFC models in solving 2-SAT problems of varying logical complexities and model scales through the application on simulated datasets. The experimental results on the simulated datasets not only validated the effectiveness of the HNN-2SAT-CSAFC model but also laid a solid foundation for further research. However, to comprehensively evaluate the HNN-2SAT-CSAFC model's capability in addressing real-world application issues, we believe it is necessary to conduct further tests on real-world datasets. Chapter 5 aims to bridge this research gap by applying the HNN-2SAT-CSAFC model and traditional HNN-2SAT-WA model to specific 2-SAT problem instances, exploring their performance in solving practical problems.

5.1.   Experimental design for 2-SAT instances

Due to the absence of a renowned dataset exclusively containing 2-SAT problems, we utilized the JNH dataset from the DIMACS benchmark instances available on SATLIB (https://www. cs. ubc.ca/ ~hoos/SATLIB/benchm.html). This dataset comprises 16 satisfiable instances and 34 unsatisfiable instances, provided by John Hooker, generated through a hard generator, presenting random problems with certain challenging characteristics, such as the absence of single-literal clauses and hard density. To construct a representative set of 2-SAT instances, we selected 16 problem instances ($jnhi-2SAT, 1\le i\le 16$) that contain only clauses with two literals from these 16 satisfiable instances ($jnhi, 1\le i\le 16$). This ensured that our experimental dataset maintained a clear 2-SAT structure, consistent with real-world application problems, where each clause contains precisely two literals.

In the subsequent experiments, the traditional HNN-2SAT-WA model and the HNN-2SAT-CSAFC model proposed in this paper were applied to solve these 16 2-SAT instances. During the retrieval phase, the HNN-2SAT-WA model directly searches among 10,000 different combinations of neuron initial assignments, whereas the HNN-2SAT-CSAFC model employs Crow-guided fuzzy clustering to preprocess these 10,000 combinations of neuron initial assignments, picking out a subset of potential solutions for retrieval. This significantly narrows the actual search space and reduces computational efforts. To minimize statistical errors, each combination of neurons will undergo 100 repeated experiments to calculate an average value. Specific parameters are detailed in Tables 10 and 11. We will comprehensively document the performance of the HNN-2SAT-CSAFC model and the HNN-2SAT-WA model in solving these 16 2-SAT instances across the following five performance metrics: Global minima ratio, Hamming distance, CPU time, retrieval rate of stable states, and retrieval rate of global minima, as shown in Table 12. Through this experiment, we will objectively assess the performance advantage of the HNN-2SAT-CSAFC model over the traditional HNN-2SAT-WA model in solving practical application problems, thereby providing valuable insights for future research and applications.

5.2.   Results and discussion

As depicted in Figures 16 to 20, the DHNN-2SAT-CSAFC model outperforms the DHNN-2SAT-WA model across all five metrics. Notably, a significant advantage of the DHNN-2SAT-CSAFC model is observed in terms of CPU time. CPU time is a crucial factor in measuring algorithm efficiency, as it directly reflects the average time required by the model to obtain a satisfactory solution for a 2SAT instance. Given the early stages of the HNN-SAT model as an emerging SAT processor and the current context of precious computing resources, reducing the CPU time needed for algorithm operation not only saves valuable computing resources but also enhances the feasibility and appeal of the algorithm in practical applications. Therefore, we decided to conduct a more in-depth statistical analysis on the CPU time metric.

As shown in Tables 13 and 14, with the significance level set at 0.05, the p-values of the Jarque-Bera test for the DHNN-2SAT-WA model and the DHNN-2SAT-CSAFC model are 0.0406 and 0.0401, respectively, both of which are less than 0.05. Thus, the CPU times for both models do not follow a normal distribution. Further analysis using the Wilcoxon signed-rank test reveals a significant difference in the median CPU times between the two models. This indicates that the DHNN-SAT-Dy-Ev model proposed in this paper has a significant improvement over the traditional DHNN-2SAT-WA model in terms of CPU time, highlighting its enhanced performance and potential for practical application.

6.   Conclusions

The HNN-SAT model, developed in recent years as a prototype of emerging SAT solvers, focuses on a crucial research direction: improving the model to achieve faster solving speeds and higher precision in addressing SAT problems. The previous studies predominantly focused on the impact of model scale. This study comprehensively investigates both the scale of the model and its logical complexity, along with their impacts on HNN-2SAT. With the model scale and logical complexity gradually increasing, HNN-2SAT evolves from having multiple satisfiable solutions to becoming challenging to solve, or even unsolvable.

Grounded on the discovery that "the cost function can serve as a quantification tool for the degree of inconsistency in logical rules, " this establishes a basis for fuzzy clustering. The proposed HNN-2SAT-CSAFC model integrates the advantages of CSA and fuzzy clustering, effectively mitigating this issue. Compared to the traditional HNN-2SAT-WA and another heuristic-integrated model, HNN-2SAT-GAFC, the HNN-2SAT-CSAFC model features fewer parameters, simpler implementation, and leverages a Crow search-guided fuzzy clustering hybrid optimization method for batch processing of search objects. This approach pre-selects potential solutions, narrows the search space, and significantly enhances computational speed. Additionally, two new evaluation criteria are defined, namely the retrieval rate of stable state and retrieval rate of global minima, effectively assessing the model's success rate.

In Chapter 4, we employ a simulation dataset of 2 SAT problems to experiment with our solution model. Within the simulated environment for solving a series of 2SAT problems with gradually increasing model scale and logical complexity, we meticulously observe the differing patterns exhibited by the HNN-2SAT-WA, HNN-2SAT-GAFC, and HNN-2SAT-CSAFC solution models across five metrics: global minima ratio, Hamming distance, CPU time, retrieval rate of stable state, and retrieval rate of global minima. The experimental results on the simulation dataset not only validate the effectiveness of the HNN-2SAT-CSAFC model but also lay a solid foundation for further research.

In this simulation experiment, as the constraint rate coefficient increased from 0.1 to 2.0 and the number of neurons grew from 10 to 100, the HNN-2SAT-CSAFC model consistently achieved the best performance in terms of global minima ratio, Hamming distance, CPU time, retrieval rate of stable state, and retrieval rate of global minima. Compared to the HNN-2SAT-WA and HNN-2SAT-GAFC models, the HNN-2SAT-CSAFC model exhibited superior results, with an average GMR being 1.173 times and 1.053 times higher, an average Hamming distance being 0.668 times and 0.898 times lower, an average CPU time being 0.131 times and 0.414 times less, a number of consistent interpretations obtained within the same time frame being 7.6334 times and 2.415 times greater, a stable state retrieval rate being 2.423 times and 1.105 times higher, and a global minimum retrieval rate being 2.726 times and 1.157 times greater, respectively. This signifies that the HNN-2SAT-CSAFC model not only enhances the quality of solutions in terms of accuracy and precision but also increases the quantity of solutions retrieved, even in regions where finding solutions is challenging. Notably, the HNN-2SAT-CSAFC model demonstrates a notable improvement in computational efficiency. Furthermore, the model's advantages across five evaluation metrics are expected to exhibit a linear growth trend with increasing network size and logical complexity. Evidently, the HNN-2SAT-CSAFC model is better suited for handling large-scale, highly logically complex 2-SAT problems.

In Chapter 5, the application of the solving models to 2SAT problem instances from real datasets was explored, demonstrating the superior capability of the proposed HNN-2SAT-CSAFC model over traditional models in addressing practical application issues. This is the first time in the field where the DHNN-SAT model has been applied to solve real dataset instances. Experimental results indicate that the HNN-2SAT-CSAFC model outperforms the DHNN-2SAT-WA model across five evaluation metrics. Notably, it exhibits statistically significant improvements in CPU time. This signifies that the DHNN-2SAT-CSAFC model is more efficient in solving practical SAT problems.

Although there is room for improvement in the scale and speed of solving compared to other SAT-solving tools, the HNN-2SAT-CSAFC model offers advantages such as parallel computing, ease of integration with other logical rules, and the absence of preprocessing for duplicates and redundancies. Looking ahead, with continued exploration and refinement, this model holds great potential to evolve into an outstanding SAT-solving tool.

Use of AI tools declaration

The authors declare that no Artificial Intelligence (AI) tools were utilized in the drafting of this article.

Acknowledgments

The authors are deeply thankful to the editor and the reviewers for their valuable suggestions to improve the quality of this manuscript. The authors extend their appreciation for the financial support from the Mathematical Modeling and Intelligent Computing Research Center (GKY-2022CQJG-1) by the Guangdong University of Science and Technology, as well as the Fundamental Research Grant (FRGS) by the Ministry of Higher Education Malaysia (MOHE), FRGS/1/2022/STG06/USM/02/11.

Conflict of interest

All authors declare no conflicts of interest in this paper.