# Dual-Neighborhood Tabu Search for Computing Stable Extensions in Abstract Argumentation Frameworks
## 3 Main Framework of DNTS  
HAYWOOD [17] implements a local search algorithm with stochastic selection and restart operations to calculate the stable extension. Inspired by HAYWOOD, this paper proposes the DNTS algorithm. The algorithm uses a meta-heuristic strategy that makes local search-based and integrates two neighborhood moves operators to extend the search space. Further, by adding a tabu strategy and perturbation technique, the DNTS algorithm optimizes the search process by effectively stepping out of the local optimum. We implement Definition 8 through the function \(definition\) but excluding the label undec. If an argument is labeled as in, then all arguments attacking it must be labeled as out. If an argument is labeled as out, then at least one of the arguments attacking it must be labeled out. The function \(\delta\) is designed to determine if the argument \(v\) is incorrectly labeled under \(L\). The correctness is judged on the basis of \(definition\). The \(\delta\) function returns 0 if the label is correctly labeled or 1 if it is not. \[\delta(v,L)=\left\{ \begin{array}{ll}0,\ if\ definition(v,L)\ is\ true\\ 1,\ if\ definition(v,L)\ is\ false\end{array} \right. \tag{1}\]  
Figure 4: Stable labeling. On this basis, the DNTS algorithm proposed in this paper minimizes the following objective function:  
\[F(L)=\sum_{v\in V}\delta(v,L) \tag{2}\]  
The current labeling \(L\) represents a stable labeling if \(F(L)=0\). The objective function computes the number of incorrectly labeled arguments given a known labeling \(L\). In this paper, we introduce a tabu search approach to search for a stable labeling. The search space of the proposed DNTS algorithm consists of all possible labelings including infeasible ones. Algorithm 1 illustrates the main framework of our proposed DNTS algorithm, implementing a local search strategy for the SE-ST problem. It receives an input of abstract argumentation framework \(AF\) and outputs stable labeling \(L^{*}\) if it finds one. The algorithm begins with an initialization phase, followed by a tabu search phase. ```
1:\(AF(A,R)\)
2:A stable labeling \(L^{*}\)
3:procedureLS_DNTS
4:\(perturbIter\gets 0\), \(iter\gets 0\),
5:\((L,mislabel)\gets INITIALISATION(AF)\)
6:\(L^{*}\gets L\)
7:\(F_{best}\leftarrow mislabel\_number(mislabel)\)
8:repeat
9:if\(F(L^{*})=0\)then
10:return\(L^{*}\)
11:endif
12:for\(v\in mislabel\)do
13:\(NEIGHBOREVALULATE(v,L^{*})\)
14:endfor
15:repeat
16:\(bestv\gets SELECTMIN(EvaluateHeap)\)
17:until\(tabutable(bestv)<iter\)
18:\(L^{*}\gets EXECUTINGMOVE(bestv,iter,L^{*})\)
19:\((F_{best},mislabel)\gets UPDATEMISALABL(L^{*})\)
20:\((perturbIter,L^{*})\gets DISTURB\_RAND(perturbIter,F_{best},L^{*})\)
21:\(iter\gets iter+1\)
22:until termination condition
23:endprocedure
```  
**Algorithm 1** Main framework of the DNTS algorithm  
In Algorithm 1, the initialization takes place from lines 2 to 5. During the initialization phase, variables \(iter\) and \(perturbIter\), \(F_{best}\), labeling \(L\) and \(L^{*}\), and the set \(mislabel\) are initialized. Notations \(iter\) denotes the iteration count of the local search procedure, and \(perturbIter\) is the maximum iteration count before triggering the perturbation technique. \(mislabel\) stores all mislabeled arguments. \(F_{best}\) denotes the best objective value found during the local search. With the function \(INITIALISATION\), we obtain the initial \(L\) and \(mislabel\). Then we assign \(L\) to \(L^{*}\) and obtain the initial \(F_{best}\) via set \(mislabel\). Subsequently, the algorithm enters the tabu search phase where the target set is identified through a series of search and flip moves. If the modified set of labels \(L^{*}\) meets the conditions for stable labeling, where all labels comply with Definition 8, all arguments labeled in form a stable extension and the result is output; otherwise, the process repeats until the termination condition is met.