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

1.   Introduction

The Boolean satisfiability (SAT) problem is a classical issue in computational complexity theory and has been a significant research subject in computer science and artificial intelligence since the 1970s ^[1]. In 1971, S. A. Cook ^[2] proved that the SAT problem is the world's first NP-complete problem, meaning any NP problem can be reduced to the SAT problem for a polynomial-time solution. The SAT problem serves as a benchmark for the difficulty of a category of problems known as the core of NP-complete problems. It plays a crucial role in various areas of computer science, including theoretical computer science, complexity theory, cryptosystems, and artificial intelligence ^[3,4,5,6]. With the advancements in computer hardware performance and algorithm design, traditional SAT solvers have become effective in many practical applications ^[7,8,9,10]. However, as problems grow in size and complexity, traditional methods often face challenges such as inefficiency and high consumption of computational resources. This has prompted researchers to explore new solution methods and techniques. Among these, the discrete Hopfield neural network (DHNN) ^[11], a classical neural network model, has shown significant potential and effectiveness in solving combinatorial optimization problems since its inception. Hopfield ^[11] demonstrated the stability of network dynamics, highlighting that the evolution of network states is essentially a process of energy minimization. When the association weights are symmetric, the system reaches a stable state. This stable equilibrium point aligns with the correct storage state, providing a clear physical explanation for associative memory. The network, by emphasizing the collective function of neurons from a systems perspective, offers preliminary insights into the nature of associative memory. Due to its robust memory capabilities and parallel processing power, the DHNN is particularly effective in addressing combinatorial optimization problems such as SAT ^[12,13,14].

In the study of SAT problems, the 3-satisfiability (3SAT) logic has received significant attention from researchers because higher-order Boolean SAT can be converted or reduced to the 3SAT form ^[15]. In the 3SAT problem, each clause contains three literals, making it more complex and closer to practical logic constraint problems. To address the 3SAT problem, researchers have mapped the variables and clauses of a Boolean formula into the neurons and energy functions of a discrete Hopfield network. In this network, each variable and clause is encoded as a neuron's state and connection weights ^[16,17,18]. A satisfying solution to the Boolean formula is then found by adjusting the neuron states to minimize the energy function. This method of solving the 3-SAT problem implemented in a DHNN is referred to as the DHNN-3SAT model. The DHNN-3SAT model has garnered extensive attention and research interest due to its significant improvement in solving ability and effectiveness on 3SAT problems ^[19,20]. Early research efforts focused on basic discrete Hopfield network structures, utilizing simple connection weights and update rules. As research progressed, scholars proposed various improvement and optimization strategies to enhance the network's performance and efficiency. In 1992, Wan Abdullah successfully integrated special logic programming as symbolic rules into a DHNN ^[21], and in 2011, Sathasivam and Abdullah extended this approach and formally named it the Wan Abdullah method (WA method) ^[22]. In 2014, Sathasivam et al. embedded higher-order SAT into DHNN ^[23]. Kasihmuddin et al. ^[24] applied k-satisfiability planning in DHNN. In 2017, Mansor et al. ^[25] demonstrated the hybrid use of the DHNN artificial immune system for the 3-SAT problem. Subsequently, Kasihmuddin et al. ^[26] proposed a genetic algorithm for k-satisfiability logic programming based on DHNN. In 2021, Mansor and Sathasivam ^[12] proposed a DHNN-3SAT optimal performance index. In 2023, Azizan and Sathasivam ^[27] proposed a DHNN model with a 3SAT fuzzy logic model of DHNN. However, as researchers delved deeper into the DHNN-SAT model, they found that its computational efficiency is not optimal for large-scale problems due to the inherent limitations of the DHNN, with a tendency to fall into local minima. To address these issues, researchers have been working to integrate heuristic algorithms into the optimization process ^{[28,29,30,31]} to enhance the accuracy of the DHNN-SAT model. Currently, these research methods are achieving high global minimum ratios in DHNN-SAT models with fewer neurons. By adjusting the structure and parameters of the neural network, researchers ^[32] have been exploring various model variations and optimization strategies to further enhance the performance and generalizability of the model. These efforts not only offer a new perspective and approach to understanding and solving SAT problems but also make significant contributions and provide inspiration for the application of DHNNs in combinatorial optimization and discrete problem-solving.

Although the DHNN-3SAT model has been successful in addressing certain problems, it still has some challenges and limitations. First, the model's computational complexity and storage requirements may increase significantly with the problem size, leading to performance issues when dealing with large-scale SAT problems. Second, the model's training and optimization process may be sensitive to parameter tuning and initialization, necessitating more experimental validation and tuning. Third, it may take a longer time to reach a stable solution when dealing with complex problems, which can impact its practical application in engineering and other fields. Lastly, in real-life scenarios, the constraints of SAT problems often change over time, leading to the need for network redesign and the generation of a large number of redundant computations with the increase, decrease, and update of large-scale constraints, ultimately limiting the traditional DHNN-3SAT model's performance.

To address the changing constraints of the SAT problem and the increasing size and complexity of the network, this paper proposes a WA method based on basic logical clauses. This method utilizes information about the synaptic weights of the original SAT problem in the DHNN, leading to significant savings in repetitive calculations. In addition, to tackle the issue of increasing Boolean variables and logical clauses leading to a rapidly expanding solution space and the traditional DHNN-WA model being prone to oscillations and local minima, this paper introduces a DHNN 3SAT model, based on a genetic algorithm-optimized K-modes clustering. This approach uses the genetic optimization K-modes clustering algorithm to cluster the initial space, reducing the retrieval space and avoiding repeated searches, thus improving retrieval efficiency.

The paper is organized as follows: Section 2 introduces the knowledge related to the research, including 3SAT and DHNN. Section 3 details the implementation and workflow for determining the synaptic weights of the DHNN 3SAT model using the WA method. To address the issue of a large number of redundant computations caused by the changing constraints of the 3SAT problem, the basic logic clause-based WA (BLC-WA) method is proposed. Section 4 introduces the K-modes clustering algorithm optimized by a genetic algorithm. Section 5 details the implementation steps and development process of the DHNN 3SAT model based on genetic algorithm-optimized K-modes clustering. Section 6 presents an experimental comparative analysis of the DHNN-3SAT model based on the genetic optimization K-modes clustering algorithm (DHNN-3SAT-GAKM) model proposed in this paper, and the three models DHNN-3SAT-WA, the DHNN-3SAT-WA model by using the Genetic Algorithm (DHNN-3SAT-GA), and the DHNN-3SAT-WA model by using Competition Algorithm (DHNN-3SAT-ICA), which are comprehensively evaluated using four evaluation metrics. Finally, Section 7 summarizes the work presented in this paper.

2.   Theoretical background

2.1.   Boolean 3SAT Logic

Definition 2.1. 3SAT is a satisfiability problem for a set of logical clauses consisting strictly of 3 literal variables. 3SAT problems can be expressed in 3 conjunctive normal forms (CNFs). Let the set of Boolean variables be $\left\{{S}_{1}, {S}_{2}, \cdots, {S}_{n}\right\}$ and the set of logical clauses be $\left\{{C}_{1}, {C}_{2}, \cdots, {C}_{m}\right\}$, then the general form of a CNF 3SAT formula $P$ containing $n$ Boolean variables and $m$ logical clauses is defined as:

where the clause ${C}_{k}$ consists of 3 literals connected by the classical operator or ($\vee$): ${C}_{k} = {Z}_{\left(k, 1\right)}\vee {Z}_{\left(k, 2\right)}\vee {Z}_{\left(k, 3\right)}$, and the state of the literals can be either a positive variable or the negation of a positive variable, i.e., ${Z}_{\left(k, i\right)} = {S}_{j}$ or ${Z}_{\left(k, i\right)} = {\neg S}_{j}$, $1\le k\le m$, $1\le i\le 3$, $1\le j\le n$. Each literal variable takes on the binary discrete value $\left\{1, -1\right\}$, where $1$ denotes true and $-1$ denotes false. Each clause in 3SAT contains unique variables, meaning there is no repetition of the same variable (variable or negation of a variable) in clause ${C}_{k}$. Additionally, there are no repeated logical clauses within logical rules.

The problem denoted by 3SAT can be formally described as follows: Given a 3SAT formula, the task is to determine if there is an assignment of Boolean variables that makes the entire formula true. In particular, each clause in the formula must have at least one true literal for the whole formula to be true.

Instance. Suppose that for given a 3SAT problem, the conversion to the CNF 3SAT formula is:

In Eq (2), $P$ is satisfiable if there exists a set of values for the variable ${S}_{1}, {S}_{2}, {S}_{3}, {S}_{4}$ such that $P = 1$; otherwise, $P$ is unsatisfiable.

The problem regarding 3SAT is a fundamental issue in computational complexity theory. Its NP-completeness and wide range of applications make it a crucial subject of research in both theoretical and practical contexts. Through a thorough examination of the 3SAT problem, a better understanding of computational complexity theory can be achieved, and effective tools and methods for solving practical problems can be provided. This study contributes to the advancement of computer science by exploring solution methods for 3SAT problems.

2.2.   DHNN

Neural networks can be divided into two types based on the flow of information: Feed-forward and feedback neural networks. The output of a feedforward neural network depends only on the current input vector and weight matrix, independent of the network's previous input state. An example of this is the commonly used back propagation (BP) neural network. In 1982, physicist professor J. J. Hopfield proposed ^[11] a single-layer feedback neural network, later called the Hopfield neural network. This network is of two types: Continuous Hopfield neural network (CHNN) and discrete Hopfield neural network (DHNN) ^[33,34]. DHNN has garnered significant attention due to its concise network structure and powerful memory function. It holds potential practical value in image recovery and optimization problems ^[35,36,37]. Figure 1 depicts the topology of a DHNN network with $n$ neurons. Each neuron is functionally identical and interconnected in pairs. The neurons are represented by the set $O = \left\{{o}_{1}, {o}_{2}, \cdots, {o}_{n}\right\}$, and their corresponding states are denoted by the vector $X = \left({x}_{1}, {x}_{2}, \cdots, {x}_{n}\right)$, and the value of ${x}_{i}$ takes binary discrete values, typically $\left\{-1, 1\right\}$ or $\left\{0, 1\right\}$. The state of the network is described as $X\left(t\right) = \left({x}_{1}\left(t\right), {x}_{1}\left(t\right), \cdots, {x}_{n}\left(t\right)\right)$ at time $t$, and the DHNN is stimulated by an external input to start its evolution. The outputs of localized lots are generated before the final state. The output of the local lot of the double link is:

where ${w}_{i}$ denotes a predefined threshold. The output of higher-order linked local lots is represented by Eq (4) as proposed by Mansor et al ^[22].

The output state of the neuron ${o}_{i}$ at the time $t+1$ is denoted as:

where $"sgn"$ denotes the sign function and ${w}_{ij}$ denotes the connection weights of neuron ${o}_{i}$ and neuron ${o}_{j}$, with the weights specified as follows.

In the network training phase, the Hebbian rule is usually used to calculate the weights ${w}_{ij}$ as:

where $\mathrm{m}$ denotes the number of samples to be memorized.

The DHNN is essentially a nonlinear dynamical system. The network starts evolving from an initial state, and the DHNN is considered stable when its state no longer changes after a finite number of iterations. In DHNN, stability is determined by introducing the Lyapunov function as the energy function, which serves as an indicator of stability ^[38]. The system reaches stability when the energy function reaches a minimum point of invariance. The energy function in DHNN is defined as:

In 1983, Cohen and S. Grossberg showed that DHNNs evolve with a decreasing energy function and that a stable state of the network corresponds to a minimal value of the energy function. Consequently, for each stable state, we can check whether this state represents a global minimum by determining whether the energy function has reached a minimum ^[28]. If Eq (9) is satisfied, the stable state is considered a global minimum; otherwise, it is a local minimum.

where ${E}_{min}$ denotes the minimum value of the energy function and $\delta$ is the user-defined tolerance value.

3.   Design of DHNN-3SAT model weights

In this section, we will start by determining the synaptic weights of the DHNN 3SAT model using the WA method ^[21]. This method is a computational approach for deriving the synaptic weights of a network by aligning the cost function with the DHNN energy function. Our study acknowledges some challenges in this comparative method of deriving network synaptic weights, particularly as the number of variables and logical clauses increase. Additionally, the addition, deletion, and updating of logical clauses result in a large number of redundant computations. To tackle these issues, this section will outline the cost function of the basic logical clauses and compute the network synaptic weights by establishing the basic logical clauses of the CNF 3SAT formulae. This approach will allow for a more adaptable implementation in computing the network synaptic weights of the 3SAT when incorporated in a DHNN. The method is termed the BLC-WA method. Furthermore, the detailed calculation process using the BLC-WA method will be demonstrated with specific examples as logical clauses are added, deleted, and updated.

3.1.   WA method

The WA method introduces a cost function based on propositional logic rules for the first time. It derives the synaptic weights of the network by comparing the cost function with the DHNN energy function, presenting a novel approach to using DHNN for solving the SAT problem. In this study, the WA method is used to incorporate the 3SAT problem into the DHNN for computing the network synaptic weights. The flowchart illustrating the implementation of the WA method is shown in Figure 2. The specific steps are as follows:

Step 1. Given any 3SAT problem, transform it into a CNF 3SAT formula $P$. Suppose the formula $P$ contains $n$ Boolean variables and $m$ logical clauses.

Step 2. The 3SAT formula $P$ is embedded into the DHNN, and for each Boolean variable, a unique neuron is specified. At moment $t$, the state of these neurons is denoted by $\left\{{S}_{1}^{t}, {S}_{2}^{t}, \cdots, {S}_{n}^{t}\right\}$.

Step 3. Applying De. Morgan's law to obtain $\neg P$. When $\neg P = 0$, correspond to the consistency interpretation of $\mathrm{P}$; when $\neg P =$ 1, correspond to the fact that at least one clause of $P$ is not satisfied.

Step 4. Deriving the cost function ${E}_{P}$. When the literal variable in $\neg P$ is represented by $\frac{1}{2}\left(1-{S}_{i}\right)$ when it is ${\neg S}_{i}$ and $\frac{1}{2}\left(1+{S}_{i}\right)$ when it is ${S}_{i}$, the logical clauses are internally connected by the multiplication operation and between logical clauses by addition. This creates the cost function ${E}_{P}$. The magnitude of ${E}_{P}$ corresponds to the degree to which all logical clauses are satisfied. When ${E}_{P} = 0$ it represents a consistent interpretation of $P$. A larger value of ${E}_{P}$ represents a larger number of unsatisfied logical clauses.

Step 5. Comparing the cost function ${E}_{P}$ with the energy function $E\left(X\right)$, the DHNN synaptic weight matrix $W$ corresponding to the 3SAT formula P is obtained.

3.2.   WA method applied to 3SAT instance

In this section, we use the problem of Eq (2) in Section 2.1 as an example to illustrate the process of computing synaptic weights in the DHNN using the WA method of embedding logical clauses into the DHNN.

To determine whether Eq (2) is satisfiable, the negation of Eq (2) is applied to De Morgan's law, which results in:

Since seeking a consistent interpretation of the terms of Eq (2) is the same as finding the smallest combination of inconsistent interpretations of Eq (10), the cost function can be defined as follows:

When the formula of Eq (2) provided The 3SAT formula is satisfied, the cost function ${E}_{P}$ reaches the minimum value of 0. At this point, the energy function for the corresponding DHNN converges to the global minimum, causing both the cost function and energy function to reach their minimum values. The network's synaptic weight matrix ${W}_{P}$, embedded in the DHNN by Eq (2), is derived by comparing the cost function (11) with the energy function (8) using the WA method, and the results are shown in Table 1.

3.3.   BLC-WA method

Definition 3.1. For any CNF formula containing n Boolean variables and m logical clauses, it can be viewed as consisting of the following eight basic logical clauses:

where $l$ denotes the index at which the basic logical clause is looked up.

Applying De Morgan's law to the eight basic logical clauses in Eq (12) yields the corresponding negative basic logical clauses:

The consistency clause of each basic logic clause in seeking pair Eq (12) is equal to the minimum of the inconsistency clause of the negated basic logic clause in seeking pair Eq (13). The corresponding cost function for each basic logic clause is defined as follows:

Each basic logic clause is embedded into a DHNN separately. When each basic logic clause is satisfiable, the corresponding DHNN converges to the global minimum. At this point, the cost function and the corresponding energy function of the basic logic clause reach their minimum values. By comparing the cost function (14) of the basic logic clauses with the energy function (8), the basic logic clause weight matrix of the 3SAT formula can be derived. This weight matrix is abbreviated as 3SAT-BLCWM, and the results are shown in Table 2.

Any 3SAT formula can be seen as made up of the basic logical clauses in Eq (12). Each logical clause in the 3SAT formula corresponds to a basic logical clause. So, when the DHNN learns a new logical clause, it only needs to identify the corresponding basic logical clauses, then refer to Table 2, and combine and calculate the network weight values to derive the network synaptic weights after adding a new logical clause. Figure 3 illustrates the flowchart of calculating network synaptic weights using the BLC-WA method. The specific steps for calculating network synaptic weights using the BLC-WA method are as follows:

Step 1. Given any 3SAT problem, transform it into CNF 3SAT formula $P$, which is assumed to contain N Boolean variables and M logical clauses;

Step 2. The 3SAT-BLCWM was established using the WA method (Table 2);

Step 3. Analyze CNF 3SAT formula $P$ to map each logical clause to the basic logical clause;

Step 4. Based on Table 2 (3SAT-BLCWM), the weights corresponding to each logical clause of the 3SAT formula $P$ are found. These weights are then spelled out by columns into the indexed result weight matrix ${W}^{\text{'}}$;

Step 5 The weight matrix $W$ of formula $P$ for 3SAT is obtained by combining and summing the result weight matrices ${W}^{\text{'}}$ by columns.

Next, we compute the 3SAT instances of Section 2.1 using the BLC-WA method based on Eq (2) which can be written in correspondence with the basic logical clause as:

According to Table 2 (3SAT-BLCWM), the network synaptic weights corresponding to each logical clause of formula $P$ can be found by indexing the results of the weight matrix ${W}^{\text{'}}$ using the columns. The results are shown in Table 3. The network synaptic weight matrix ${W}_{P}$ for the 3SAT formula $P$ can be obtained by merging and adding the indexing results according to the columns, which are also shown in Table 3.

3.4.   Design of weights for dynamic constraints for the 3SAT problem

In SAT problems, the constraints often change, with constraints increasing, decreasing, and updating. The traditional DHNN-SAT method requires redesigning the weights of the SAT problem and constructing a new DHNN when facing this type of problem, which does not utilize the original SAT problem's information. As the original SAT problem's constraints increase, the corresponding original CNF formulation also increases the logical clauses, leading to a large number of redundant computations when dealing with large-scale logical clauses. This severely limits the effectiveness of the traditional DHNN-SAT method in solving problems with large-scale increasing constraints. To address this issue, this study proposes the BLC-WA method, a new design method for the SAT problem with changing constraints. This method utilizes the synaptic weight information of the original SAT problem in DHNN, saving a significant amount of repeated calculations. In the following section, the network synaptic weight design method for SAT problems with increasing, decreasing, and updating constraints will be introduced, providing a new approach for solving SAT problems with constantly changing constraints.

3.4.1.   Adding constraints

The addition of constraints to the original SAT problem is equivalent to adding logical clauses to the CNF SAT formula.

There is a 3SAT problem that translates into the CNF 3SAT formula:

When $r$ logical clauses are added, the original CNF 3SAT formula becomes:

Figure 4 depicts the flowchart of the BLC-WA method for solving the original 3SAT problem with additional constraints. This method is implemented as follows:

Step 1. Let the original CNF 3SAT formula $P$ become ${P}_{add}$ by adding $r$ logical clauses (Eq 14);

Step 2. The basic logical clauses were mapped to the additional logical clauses, and the synaptic weights of the additional logical clauses were determined based on Table 2 (3SAT-BLCWM);

Step 3. The synaptic weights of the CNF 3SAT formula ${P}_{add}$ after adding the $r$ logical clauses were calculated using the following Eq (18).

The following is a concrete demonstration of the implementation process using the 3SAT instance from Section 2.1.

Assuming that Eq (2) combines the logical clauses ${C}_{2}^{2} = \neg {S}_{1}\vee {S}_{2}\vee {S}_{4}$ and ${C}_{3}^{2} = {S}_{1}\vee \neg {S}_{2}\vee {S}_{4}$, the new CNF formula at this point is notated as ${P}_{\mathrm{a}\mathrm{d}\mathrm{d}}$, specifically, as follows:

In Section 3.3, the synaptic weights (${W}_{P}$) of the formula $P$ in the network have been obtained using the BLC-WA method. Then, the synaptic weights of the newly added logical clauses (${C}_{2}^{2}$ and ${C}_{3}^{2}$) are obtained by searching for Table 2 (3SAT-BLCWM) and then combined and summed with the synaptic weights (${W}_{P}$) of the formula $P$ to obtain the new synaptic weights (${W}_{add}$) of the CNF formula 3SAT ${P}_{add}$. The calculation results are shown in Table 4.

3.4.2.   Declining constraints

Setting the original CNF 3SAT formula (16) reduces $\mathrm{d}$ logical clauses, and the original CNF 3SAT formula becomes:

The flowchart for solving the original 3SAT problem with reduced constraints based on the BLC-WA method is also shown in Figure 4. It is implemented as follows:

Step 1. The original CNF 3SAT formula $P$ is reduced by $d$ logical clauses to ${P}_{dec}$;

Step 2. The basic logical clauses were mapped to the reduced logical clauses, and the synaptic weights of the reduced logical clauses were determined based on Table 2 (3SAT-BLCWM);

Step 3. The synaptic weights of the CNF 3SAT formula ${P}_{dec}$ after declining the $d$ logical clauses were calculated using the following Eq (21).

The following is a concrete demonstration of the implementation process using the 3SAT instance from Section 2.1.

Assuming that Eq (2) reduces the logical clauses ${C}_{2}^{1} = \neg {S}_{1}\vee {S}_{2}\vee {S}_{3}$ and ${C}_{3}^{1} = {S}_{1}\vee {\neg S}_{2}\vee {S}_{3}$, the new CNF formula at this point is notated as ${P}_{dec}$, specifically, as follows:

To start, the synaptic weights for the reduced logical clauses ${C}_{2}^{1}$ and ${C}_{3}^{1}$ are determined by searching for Table 2 (3SAT-BLCWM). Next, the synaptic weights ${W}_{P}$ of the original 3SAT formula $P$ are subtracted from the synaptic weights of the reduced logical clauses. This process yields the synaptic weights ${W}_{dec}$ for the new CNF 3SAT formula ${P}_{dec}$. The computational results are also displayed in Table 4.

3.4.3.   Updating constraints

When the original CNF formula (16) is updated with $u$ logical clauses, it can be regarded as a reduction of $u$ logical clauses from the original formula and the addition of $u$ new logical clauses. The updated CNF formula is:

The flowchart when updating the constraints based on the BLC-WA method is also shown in Figure 4, which is implemented as follows:

Step 1. The original CNF 3SAT formula $P$ is updated by $u$ logical clauses to ${P}_{upd}$;

Step 2. The basic logical clauses were mapped to the updated logical clauses, and the synaptic weights of the updated logical clauses were determined based on Table 2 (3SAT-BLCWM);

Step 3. The synaptic weights of the CNF 3SAT formula ${P}_{upd}$ after updating the $u$ logical clauses were calculated using the following Eq (24).

The following is a concrete demonstration of the implementation process using the 3SAT instance from Section 2.1.

Suppose the logical clauses ${C}_{7}^{1} = {S}_{1}\vee {\neg S}_{2}\vee \neg {S}_{3}$ and ${C}_{1}^{2} = {S}_{1}\vee {S}_{2}\vee {S}_{4}$ in the original CNF 3SAT formula $P$ are updated to ${C}_{8}^{1} = \neg {S}_{1}\vee {\neg S}_{2}\vee \neg {S}_{3}$ and ${C}_{1}^{3} = {S}_{2}\vee {S}_{3}\vee {S}_{4}$, and the updated CNF 3SAT formula is now denoted as ${P}_{upd}$, specifically for:

To begin, find the synaptic weights of logical clauses ${C}_{7}^{1}$, ${C}_{1}^{2}$, ${C}_{8}^{1}$ and ${C}_{1}^{3}$ by searching for Table 2 (3SAT-BLCWM). Then, subtract the synaptic weights of logical clause ${C}_{7}^{1}$, ${C}_{1}^{2}$ from the original SAT formula $P$. Finally, the synaptic weights of logical clause ${C}_{8}^{1}$, ${C}_{1}^{3}$ are added to obtain the network synaptic weights ${W}_{upd}$ of the updated 3SAT formula ${P}_{upd}$. The results of the computation are also displayed in Table 4.

4.   Optimized K-modes clustering algorithm

4.1.   K-modes clustering algorithm

The K-modes clustering algorithm is a method specifically designed for handling discrete data ^{[39,40,41,42]}. It extends the traditional K-means algorithm, which is mainly used for datasets with continuous attributes. The K-modes algorithm uses the Hamming distance as a metric ^[43], where this distance measures the number of differing attribute values between two sample points. In this algorithm, the Hamming distance is computed by adding the number of different attribute values between two samples, representing the degree of difference for a given sample compared to a clustering center. Finally, the samples are classified into the category that belongs to the clustering center with the smallest degree of difference. We can see the clustering process of the K-modes algorithm in Figure 5.

Let $X = \left\{{X}_{1}, {X}_{2}, \cdots, {X}_{m}\right\}$ represent the set of samples to be clustered, and ${X}_{i} = \left({x}_{1}, {x}_{2}, \cdots, {x}_{n}\right)$ represent the $n$ -dimensional vector with each component taking discrete values. $Z = \left\{{Z}_{1}, {Z}_{2}, \cdots, {Z}_{k}\right\}$ represents the clustering center and ${Z}_{j} = \left({z}_{1}, {z}_{2}, \cdots, {z}_{n}\right), j = \mathrm{1, 2}, \cdots, k$. The objective function of the K-modes clustering algorithm is defined as:

where ${\varphi }_{ij}\in \left\{\mathrm{0, 1}\right\}$ , $\sum _{j = 1}^{k}{\varphi }_{ij} = 1, 1\le i\le n, \Phi$ is the matrix of one, $k$ denotes the number of clusters, ${\varphi }_{ij} = 1$ if the $\mathrm{i}$ th object is classified in the $j$ -th class, otherwise ${\varphi }_{ij} = 0$. ${Z}_{j}$ is the center of the $j$ -th class. $D\left({X}_{i}, {Z}_{j}\right)$ denotes the computation of the Hamming distance between ${X}_{i}$ and ${Z}_{j}$ :

where $d\left({x}_{i}, {z}_{i}\right) = \left\{\begin{array}{c}0, {x}_{i} = {z}_{i}\\ 1, {x}_{i}\ne {z}_{i}\end{array}\right.$.

The classification process must meet the following conditions: (1) every family must contain at least one sample; (2) each sample must belong to one and only one class. The fundamental steps of the K-modes clustering algorithm are as follows:

Step 1. Randomly identifying $\mathrm{k}$ clustering centers ${Z}_{1}, {Z}_{2}, {\cdots, Z}_{k}$.

Step 2. For each sample ${X}_{i}\left(i = \mathrm{1, 2}, \cdots, m\right)$ in the dataset, its Hamming distance from the $k$ clustering centers is calculated separately using Eq (27), and the sample ${X}_{i}$ is classified into the category closest to the centroid.

Step 3. After dividing all the samples into clusters, the cluster center " ${Z}_{j}$ " is recalculated, and each center component is updated to its plural.

Step 4. Repeat the process of Steps 2 and 3 above until the objective function $F$ no longer changes.

4.2.   K-modes clustering algorithm optimized by genetic algorithm

To address the limitations of the K-modes clustering algorithm, which make it difficult to determine the optimal number of clusters and easy to get stuck at a local optimum, researchers have incorporated a genetic algorithm with adaptive global optimization search capabilities into the K-modes clustering algorithm ^[44,45]. This involves using a fitness function to carry out genetic operations, primarily mutation, to automatically learn the cluster centroids for the K-modes algorithm. Figure 6. shows the workflow diagram of the K-modes clustering algorithm for genetic optimization, which was developed in the following steps:

Step 1. Parameter initialization. Set relevant parameters: Initial cluster number $k$, population size $\mathrm{m}$, crossover probability ${p}_{c}$, variation probability ${p}_{m}$, maximum number of iterations $t$.

Step 2. Randomly generate the initial population. Randomly generate $\mathrm{k}$ initial clustering centers ${Z}_{1}, {Z}_{2}, {\cdots, Z}_{k}$ as initial population individuals.

Step 3. Take the population individual ${Z}_{1}, {Z}_{2}, {\cdots, Z}_{k}$ as the clustering center and use K-modes clustering algorithm for clustering.

Step 4. Calculate the fitness value of individuals in the population. Here the fitness function is defined as follows:

where ${D}_{min}$ is the minimum class spacing and $\overline{D}\left(X\right)$ is the average class spacing which is defined as follows:

This fitness function is based on the idea that class separation should be maximized while intra-class spacing should be minimized. In other words, the goal is to maximize the distance between classes (${D}_{min}$) and minimize the variability within classes ($\overline{D}\left(X\right)$). Throughout the evolutionary process, the individual population size is represented by the $\mathrm{k}$ value. If the $k$ value is less than the optimal number of clusters, increasing $k$ leads to a decrease in ${D}_{min}$ and $\overline{D}\left(X\right)$, but the clustering division is not optimal. The decrease in $\overline{D}\left(X\right)$ is more significant than ${D}_{min}$, resulting in an increase in the fitness function value. Conversely, if the $\mathrm{k}$ value exceeds the optimal number of clusters, the change in $\overline{D}\left(X\right)$ is not significant, and the intra-class spacing becomes very small due to secondary clustering. As a result, ${D}_{min}$ becomes very small, leading to a decrease in the overall fitness function value. Therefore, this fitness function can guide the $k$ value toward the optimal number of clusters when the initial clustering center is optimized.

Step 5. Perform selection, crossover, and mutation operations to generate a new generation population.

Step 6. Repeat Step 3 to Step 5 until the maximum number of iterations is reached.

Step 7. Calculate the fitness value for each individual in the population and select the output with the highest fitness value.

5.   Development of DHNN-3SAT model based on genetic optimization K-modes clustering algorithm

The conventional DHNN-3SAT-WA model uses an exhaustive search (ES) during the retrieval phase ^[46], aiming to conduct a random search among individual candidate solutions to find a consistent interpretation that satisfies the 3SAT terms. Some researchers have proposed optimizing the traditional DHNN-3SAT-WA model by using heuristic algorithms such as the GA and ICA, denoted as DHNN-3SAT-GA ^[26] and DHNN-3SAT-ICA ^[38]. These methods can expedite the search for global or feasible solutions. However, unguided random initial assignment of candidate solutions leads to numerous repeated invalid solutions and fails to converge, often falling into a local optimum after DHNN evolution. Furthermore, as the number of Boolean variables and logical clauses increases, the size and logical complexity of the network expands, resulting in a rapid growth of the solution space. This makes the model susceptible to oscillations and more likely to land in local minima. Therefore, reducing the DHNN-3SAT-WA model's search time and preventing it from falling into local minima is a significant challenge in this field. The implementation process of the traditional DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models is depicted in Figure 7.

This study proposes a new solution to address these challenges: the DHNN-3SAT model based on the genetic optimization K-modes clustering algorithm referred to as DHNN-3SAT-GAKM. In this model, candidate solutions in the allocation space are clustered using the K-modes clustering algorithm, leading to initial allocation through a random search from each class. By reducing repeated initial candidate solutions and avoiding local optima to some extent, this process accelerates the search for the global minimum, improving the efficiency of global minimum retrieval. To determine the optimal number of clusters for the K-modes clustering algorithm, the genetic algorithm with adaptive global optimization search capability is introduced. The number of clusters is determined by calculating the value of the constructed fitness function, further enhancing global search capability.

The DHNN-3SAT-GAKM model aims to find a consistent set of Boolean variable values for the 3SAT problem. During the model's initialization phase, each neuron in the DHNN is connected to a specific Boolean variable in the CNF, and the connection weights represent the relationship between the variable and the clause. A WA method using basic logical clauses will be employed to determine the cost during the learning phase. In the retrieval phase, the DHNN is utilized to evolve, update, and iterate until the network reaches a stable equilibrium state, signified by a minimal energy function value. The energy function's primary purpose is to indicate whether this stable state corresponds to a global minimum of the 3SAT problem, which in turn represents a consistent interpretation of the CNF. Please see Figure 8 for the flowchart of the DHNN-3SAT-GAKM model development, and the implementation steps are summarized as follows:

Step 1. Model Preparation. For a given 3SAT problem, transform it into the corresponding CNF formulation, denoted as $P$. Assume it contains $n$ Boolean variables and $m$ logical clauses. Initialize the optimization algorithm parameters.

Step 2. Each Boolean variable of the 3SAT formula is uniquely assigned a Hopfield neuron in the DHNN design, which consists of $n$ neurons $O = \left\{{o}_{1}, {o}_{2}, \cdots, {o}_{n}\right\}$, with the state at moment $t$ denoted $X\left(t\right) = \left({x}_{1}\left(t\right), {x}_{1}\left(t\right), \cdots, {x}_{n}\left(t\right)\right)$.

Step 3. The BLC-WA method was used to calculate the 3SAT formula $P$ synaptic weights and derive its cost function ${E}_{p}$. When $P = 1$, ${E}_{p} = 0$, at which time the energy function reaches its minimum value, giving ${E}_{min} = -\frac{m}{8}$.

Step 4. Generate an initial candidate solution space by randomly creating $\mathrm{m}$ initial candidate solutions $\left\{{X}_{1}\left(t\right), {X}_{2}\left(t\right), \cdots, {X}_{m}\left(t\right)\right\}$.

Step 5. The initial candidate solution $\left\{{X}_{1}\left(t\right), {X}_{2}\left(t\right), \cdots, {X}_{m}\left(t\right)\right\}$ is clustered using the K-modes clustering algorithm based on genetic optimization to obtain the optimal number of clusters $k$.

Step 6. Determine the candidate subset for retrieval. Candidate subset denoted as $\left\{{Y}_{1}\left(t\right), {Y}_{2}\left(t\right), \cdots, {Y}_{c}\left(t\right)\right\}$, where $c = m/k$ , ${Y}_{l}\left(t\right) = \left({y}_{1}\left(t\right), {x、y}_{2}\left(t\right), \cdots, {y}_{n}\left(t\right)\right), l = \mathrm{1, 2}, \cdots, c$. ${y}_{i}\left(t\right)$ corresponds to the state of $t$ at the moment of the neuron ${o}_{i}$.

Step 7. DHNN Evolution. For ${Y}_{l}\left(t\right) = \left({y}_{1}\left(t\right), {y}_{1}\left(t\right), \cdots, {y}_{n}\left(t\right)\right)$, $l = 0, t = 0$, state updates are performed using Eq (5) until a stable state is reached. If ${Y}_{l}\left(t+1\right){\ne Y}_{l}\left(t\right)$, then $t = t+1$, and if ${Y}_{l}\left(t+1\right){ = Y}_{l}\left(t\right)$, the network reaches a steady state. Proceed to the next step.

Step 8. Retrieval Phase. Check if the energy of the steady state satisfies $\left|E-{E}_{min}\right| < \delta$. If it does, store the steady-state ${Y}_{l}\left(t\right)$ as a global minimum. If it doesn't, $l = l+1$ , consider it as a local minimum and go back to Step 6.

Step 9. Model Evaluation. The model is assessed using the metrics of global minimum ratio, Hamming distance, CPU time, steady-state retrieval rate, and global minimum retrieval rate.

6.   Data experiments

To thoroughly evaluate the performance of the DHNN-3SAT-GAKM model and its ability to solve real-world application problems, this section examines its performance alongside the conventional DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models on a benchmark dataset. Experimental analyses were conducted to compare their performance and demonstrate the superiority of the DHNN-3SAT-GAKM model proposed in this study. The experiments were carried out using MATLAB R2023b on a laptop computer running the Windows 10 operating system, equipped with an AMD Razor R5-3500U processor and 8 GB of RAM.

6.1.   Description of the dataset

This study utilizes the DIMACS Benchmark Instances AIM dataset from SATLIB, provided by Kazuo Iwama et al. (https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html). The AIM dataset comprises of 48 instances, with 24 being satisfiable and 24 unsatisfiable. To create a representative set of instances, 12 of these satisfiable instances are chosen for this study. Each instance contains three clauses, and you can find specific descriptions of the instances in Table 5.

6.2.   Parameter setting

In the search phase, the traditional DHNN-3SAT-WA model directly examines 10, 000 different combinations of initial neuron assignments ^[46]. DHNN-3SAT-GA and DHNN-3SAT-ICA guide the search among these 10, 000 combinations using a genetic algorithm and an imperialistic competition algorithm, respectively. This paper introduces the DHNN-3SAT-GAKM model, which utilizes genetic optimization K-modes clustering to preprocess these 10000 neuron initial allocation combinations. It then selects a candidate subset for search. This approach reduces the actual search space and minimizes repeated local searches to avoid getting stuck in local minima, thereby improving the efficiency of retrieving the global minimum. The tolerance values for the conventional DHNN-3SAT-WA model align with Sathasivam's work ^[16]. The CPU time thresholds are based on Zamri's settings ^[47]. The parameter settings can be found in Table 6. The parameter settings for the DHNN-3SAT-GA model are in line with Kasihmuddin's work ^[26] and are listed in Table 7. The parameter settings for the DHNN-3SAT-ICA model remain consistent with Shazli's work ^[38], as shown in Table 8. Table 9 details the parameter settings of the model in this paper, with optimization of the relevant parameters through iterative tuning.

6.3.   Experimental results and discussion

We use the global minimum ratio (GMR) ^[16] and the mean CPU time (MCT) to assess the model's performance in this paper. To provide a more comprehensive evaluation of the model's ability to find the global minimum, we introduce 2 new evaluation metrics: the mean minimum Hamming distance (MMHD) and the mean logical satisfiability ratio (MLSR). This study will utilize a total of 4 evaluation metrics, as detailed in Table 10. The calculations are based on the average of 100 repeated experiment runs for each instance, and the results are displayed in Tables 11 and 12. Figures 9 to 12 compare our model, DHNN-3SAT-GAKM, with the models DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA across the 4 evaluation metrics.

Tables 11 and 12 show the computational results of the DHNN-3SAT-GAKM model in this paper, as well as the DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models. The results are presented in terms of GMR, MCT, MMHD, and MLSR. These calculations are based on the metrics formulas provided in Table 10. Figures 9 to 12 illustrate the performance differences between this paper's DHNN-3SAT-GAKM model and the DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models. These differences are shown in the four evaluation metrics through radargram-based visualization. The DHNN-3SAT-GAKM model outperforms the DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models.

Figure 9 shows the GMR of each model in solving 3-SAT instances with varying levels of complexity. In this paper, the DHNN-3SAT-GAKM model achieved the highest GMR value, indicating its superior global retrieval ability and ability to avoid falling into local minima to some extent. Additionally, the DHNN-3SAT-GA and DHNN-3SAT-ICA models also demonstrated an improved ability over the traditional DHNN-3SAT-WA model to retrieve the global minimum to some extent. As the complexity of SAT problems, Boolean variables, and logical clauses increases, the GMRs of each model decrease rapidly. Hence, further optimization and improvement of the algorithms and architectures of the DHNN-3SAT models are needed to enhance their performance and efficiency when dealing with large-scale and complex SAT problems in the future.

In Figure 10, we can see the average time taken by each model to reach the global minimum. The MTC value of the DHNN-3SAT-GAKM model in this paper is the smallest, indicating that this model is more efficient in finding the global minimum. This is because the model initially clusters the allocation space using the K-modes clustering algorithm, enabling it to escape local minima more quickly and avoid repetitive retrieval of local minima. As a result, a large number of redundant calculations are reduced, leading to improved efficiency in converging to the global minimum. On the other hand, the traditional DHNN-3SAT-WA is more prone to getting stuck in local minima, especially as the number of local minimum solutions increases, resulting in a substantial number of repetitive evolutions and computations, ultimately affecting the efficiency of converging to the global minimum. While the DHNN-3SAT-GA and DHNN-3SAT-ICA models also use heuristic algorithms for guided search to some extent, helping to reduce the search space and speed up retrieval of the global minimum, the rapidly expanding search space due to the increasing complexity of the SAT problem can lead to longer retrieval times or even search failure. Consequently, for large-scale SAT problems, further improving the efficiency of searching for the global minimum is a future priority.

In dealing with large-scale SAT problems, the increasing logic complexity results in a progressively smaller solution space, making it very challenging to find a global minimum solution within a limited timeframe. Most attempts only end up finding the local minimum solution. The goal of model optimization at this stage is to make each retrieval result as close as possible to the global minimum solution. To evaluate the proximity of the model retrieval results to the global minimum solution, two new evaluation criteria are introduced in this study: the MMHD and the MLSR. These criteria reflect the proximity of the model retrieval results to the global optimum. A lower MMHD value and a higher MLSR value indicate that the model retrieval results are closer to the global minimum solution. Figures 11 and 12 illustrate the relationship between the MMHD and MLSR values of each model. These figures show that the DHNN-3SAT-GAKM model in this paper has the smallest MMHD value and the largest MLSR value, indicating that its retrieval results are closer to the global minimum than those of the DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA models. This suggests that the retrieval results of the DHNN-3SAT-GAKM model are closer to the global minimum solution overall. Conversely, the DHNN-3SAT-GA and DHNN-3SAT-ICA models are closer to the global minimum than the overall retrieval results of the conventional DHNN-3SAT-WA.

Based on the combined analyses above, it can be observed that the DHNN-3SAT-GAKM model, introduced in this paper, exhibits significant improvements when compared to the traditional DHNN-3SAT-WA model, as well as the DHNN-3SAT-GA and DHNN-3SAT-ICA models that directly utilize heuristic algorithms for bootstrap retrieval. This demonstrates the superior performance of the DHNN-3SAT-GAKM model in retrieving the global minima in the SAT problem, while also highlighting its potential for practical applications.

7.   Conclusions

This paper introduces a method for designing network synaptic weights based on basic logical clauses to handle dynamic changes in constraints in the SAT problem. This method aims to utilize synaptic weight information efficiently, reducing the need for repetitive calculations in the DHNN network. Additionally, it proposes a DHNN-3SAT model based on genetic algorithm optimized K-modes clustering to address the limitations of the traditional DHNN-3SAT-WA, which tends to get stuck in local minima. The new model uses genetic algorithms to cluster the initial space, effectively reducing the retrieval space and improving retrieval efficiency. Experimental results show that the DHNN-3SAT-GAKM model outperforms DHNN-3SAT-WA, DHNN-3SAT-GA, and DHNN-3SAT-ICA in terms of various evaluation metrics, including GMR, MCT, MMHD, and MLSR. This study not only expands the application of DHNN in solving the SAT problem but also offers valuable insights for future research.

The DHNN-3SAT model is an innovative approach to using deep learning technology to solve SAT problems, offering insights and potential for future research and applications. There are several areas for future work: first, optimizing and enhancing the algorithm and architecture of the DHNN-3SAT model to improve its performance on large-scale and complex SAT problems; second, exploring the model's extension to other NP-complete problems to demonstrate its versatility and applicability; and finally, conducting thorough research on the model in specific domains and practical applications to further promote the use of deep learning techniques in combinatorial optimization and decision-making problems. In summary, the proposal and study of the DHNN-3SAT model not only enhances methods in the field of SAT problem-solving but also provides new ideas and tools for solving complex problems using deep learning techniques. With ongoing technological and theoretical progress, the application of deep learning in combinatorial optimization problem-solving is expected to bring about broader development and deliver effective solutions for real-life complex problems.

Author contributions

Xiaojun Xie: Writing-review & editing, Writing-original draft, Methodology, Formal analysis, Conceptualization. Saratha Sathasivam: Writing-review & editing, Methodology, Funding acquisition, Conceptualization, Validation, Supervision. Hong Ma: Writing-review & editing, Writing-original draft, Methodology, Investigation, Formal analysis, Conceptualization. All authors have read and approved the final version of the manuscript for publication.

Acknowledgments

This research was supported by the Ministry of Higher Education Malaysia (MOHE) through the Fundamental Research Grant Scheme (FRGS), FRGS/1/2022/STG06/USM/02/11, and University Sains Malaysia.

Conflict of interest

All authors declare no conflicts of interest in this paper.