# A Population-Based Search Approach to Solve Continuous Distributed Constraint Optimization Problems
## 3 Our Algorithms
### Population-Based Local Search Algorithm  
The PLSA consists of three phases: Initialization, Decision, and Update phases; the details of the algorithm can be found in Algorithm 1. **The Initialization phase:** Firstly, PLSA initializes some parameters and constructs a distributed population. Specifically, \(K\) represents the number of solutions, and \(T\) is the termination parameter, which is the threshold of the agent state change. \(\lambda\) and \(P_{m}\) represent the learning rate and mutation probability, respectively. Secondly, each agent sets the \(\delta\) to 0 and the **STATE** to \"ACTIVE\". The \(\delta\) records the change of the best value, and the **STATE** determines whether the value assignments are updated. In addition, each agent initializes the current dimension of each solution to a random value from its domain. Finally, the agent \(x_{i}\) sends the values \(S.x_{i}\) to neighbors \(N_{i}\) (Algorithm 1: Lines 3-10). **The Decision phase:** When receiving the value assignments \(S.x_{j}\) sent by the neighbor \(N_{i_{j}}\in N_{i}\), the agent \(x_{i}\) calculates the sum of local utilities \(U_{i}\) of each solution according to Equation (2) (Algorithm 1: Lines 12-14). In addition, agent \(x_{i}\) calculates the index of the best value \(best1\) and outputs \(S_{best1}\)-\(x_{i}\), which is the value that minimizes the sum of local utilities (Algorithm 1: Lines 15-16). Figure 2: A BFS pseudo-tree representation (**c**) of the C-DCOP depicted in Figure 0(a). ```
1 Initialization();
2 FunctionInitialization():
3 Initialize parameters: \(K\), \(T\), \(\lambda\), \(P_{m}\);
4\(S\leftarrow\) set of \(K\) solutions;
5// The set of solutions as shown in Table 1.
6 foreachagent\(x_{i}\)do
7\(\delta\gets 0\);
8// Set initial record to 0. 9\(\mathbf{STATE}\leftarrow\) ACTIVE;
10// Set initial state to active. 11 foreachsolution\(S_{k}\in S\)do
12\(S_{k}\):\(x_{i}\leftarrow\) a random value from \(D_{i}\);
13// Assign a random value from the value domain to \(S_{k}\).\(x_{i}\). 14
15 Send \(S.x_{i}\) to \(N_{i}\);
16// Agent \(x_{i}\) sends the value set, i.e., \(|K|\) values (\(S_{k}\).\(x_{i}\)) to neighboring agents. 17
18 while Termination condition not met each agent \(x_{i}\)do
19 for\(S.x_{j}\) received from \(N_{i_{j}}\in N_{i}\)do
20 foreachsolution\(S_{k}\in S\)do
21 Calculate \(S_{k}(U_{i})\) according to Equation (2) ;
22
23\(best1\leftarrow\underset{k\in K}{\arg\min}\,S(U_{i})\) ;
24
25 Output:\(S_{best1}.x_{i}\) ;
26 StateUpdate() ;
27// Compare the optimal value of the current iteration with that of the previous iteration. 28 ValueUpdate(\(S.x_{i}\), \(S_{best1}.x_{i}\), Equation (3)) ;
29// Update the value set. 30 Send \(S.x_{i}^{t}\) to \(N_{i}\) ;
31 FunctionStateUpdate(\(S_{best1}.x_{i}^{t}\), \(S_{best1}.x_{i}^{t-1}\)):
32 if\(S_{best1}.x_{i}^{t}=S_{best1}.x_{i}^{t-1}\)then
33\(\delta\) += 1;
34
35 else
36\(\delta=0\);
37 if\(\delta>T\)then
38\(\mathbf{STATE}\leftarrow\) HOLD ;
39// Set initial state to hold. 40
41 FunctionValueUpdate(\(S.x_{i}\), \(S_{best1}.x_{i}\), Equation (3)):
42 foreachsolution\(S_{k}\in S\)do
43 if\(\mathbf{STATE}\) = HOLD then
44\(S_{k}.x_{i}\gets S_{best1}.x_{i}\);
45 else
46 if\(r_{m}<P_{m}\)then
47\(S_{k}.x_{i}\leftarrow\) a random value from \(D_{i}\) ;
48
49 else
50 Calculate \(S_{k}.x_{i}\) according to Equation (3) ;
51
52
53
54
55
56
57
58 end if
59
60
61 end for
```  
**Algorithm 1**Population-based Local Search Algorithm  
**The Update phase:** This phase mainly includes state updates and value updates. On the one hand, the agent \(x_{i}\) compares the best value of the current and the previous iteration. The \(\delta\) is increased by one if the two values are equal, otherwise, the \(\delta\) is set to zero. Further, if \(\delta>T\), the agent \(x_{i}\) changes the **STATE** to \"Hold\" (Algorithm 1: Lines 21-26), where \(t\) represents the number of iterations. On the other hand, the agent \(x_{i}\) updates each value \(S_{k}\)-\(x_{i}\) and sends it to neighbors \(N_{i}\).