# A Population-Based Search Approach to Solve Continuous Distributed Constraint Optimization Problems
## 3 Our Algorithms
### Population-Based Global Search Algorithm  
Similar to PLSA, PGSA, represented by Algorithm 2, includes three phases: Initialization, Decision, and Update phases.  
**The Initialization phase:** PGSA starts the \(initialization()\) after constructing a BFS pseudo-tree and assigning \(\Gamma\) to \(+\infty\), where \(\Gamma\) records the best aggregate utility. In addition, each agent \(x_{i}\) sets the \(Gbest_{i}\) to complete the assignment combination of the best aggregate utility (Algorithm 2: Lines 1-4).  
**The Decision phase:** Similarly, the agent calculates the sum of local utilities with neighbors (Algorithm 2: Lines 6-8). However, the agent \(x_{i}\) in PSGA sends the sum of local utilities to the parent agent \(P_{i}\). Each agent except the root agent does the same thing; the agent \(x_{i}\) waits to receive the sum of local utilities of children agents \(C_{i}\) and adds it to its sum of the local utilities \(S(U_{i})\) (Algorithm 2: Lines 9-15). Since the agents of each layer pass the sum of local utilities up the pseudo-tree and the utility function represented by each edge is calculated twice by the corresponding two agents, the root agent calculates the aggregate utility of each solution by Equation (4). The root agent compares the minimum aggregate utility with \(\Gamma\). If the minimum aggregate utility is less than \(\Gamma\), the _update_ is assigned the \"Assign\" and sent by the root agent to neighbors (Algorithm 2: Lines 27-37).  
\[\mathbf{U}=\frac{1}{2}\sum_{\alpha_{i}\in X}U_{i} \tag{4}\]  
**The Update phase:** The agent \(x_{i}\) updates \(Gbest_{i}\) according to the value of _update_ (Algorithm 2: Lines 20-21). In addition, each agent updates its state and value assignments. As an extension of PLSA, we consider the same weighted combination method to update the solution, but we extend the local search to the global search, as shown in Equation (5), where the \(S_{0}\) and \(S_{K-1}\) are the solutions with minimum and maximum aggregate utility, respectively. And the \(S_{1}\) is the solution with the second smallest aggregate utility.  
\[S_{k}.x_{i}=(1-\lambda)*S_{k}.x_{i}+\lambda*(S_{0}.x_{i}+S_{1}.x_{i}-S_{K-1}.x _{i}) \tag{5}\]```
1 Construct BFS pseudo-tree ;
2 Root agent sets the \(\Gamma\leftarrow+\infty\); // Root agent records the best aggregate utility. Initialization() ;
3 Each agent \(x_{i}\) sets the \(\mathit{Gbest}_{i}\gets 0\);
4 while Termination condition not met each agent \(x_{i}\)do
5 for\(S.x_{j}\) received from \(N_{i_{j}}\in N_{i}\)do
6 foreach\(\mathit{solution}\)\(S_{k}\in S\)do
7 Calculate \(S_{k}(U_{i})\) according to Equation (2) ;
8
9 Send \(S(U_{i})\) to \(P_{i}\); // Send sum of local utilities to parent agent.
10 Wait until \(S(U_{i})\) is received from agent \(x_{j}\in C_{i}\);
11 if\(S(U_{i})\) is received from all agent in \(C_{i}\)then
12 ifagent \(x_{i}\
eq\) root then
13 foreach\(\mathit{solution}\)\(S_{k}\in S\)do
14\(S_{k}(U_{i})\leftarrow\sum_{x_{j}\in C_{i}}S_{k}(U_{j})\);
15 Send \(S(U_{i})\) to agent \(P_{i}\)
16 ifagent \(x_{i}=\) root then
17 Evaluation();
18 Wait until **Messages** is received from \(P_{i}\);
19 if\(\mathit{Messages}\) is received from \(P_{i}\)then
20 if\(\mathit{Update}=\) Assign then
21\(\mathit{Gbest}_{i}\gets\mathit{Sbest}_{i}.x_{i}\); // Each agent records the value that minimizes the aggregation utility.
22 StateUpdate(\(\mathit{Gbest}_{i}^{t},\mathit{Gbest}_{i}^{t-1}\)) ;
23 ValueUpdate(\(\mathit{S}.x_{i}\), \(\mathit{Gbest}_{i}\), Equation (5)) ;
24 Send **Messages** to \(N_{i}\);
25 Send \(S.x_{i}^{t}\) to \(N_{i}\) ;
26
27 FunctionEvaluation():
28\(\mathit{Messages}\leftarrow\{\mathit{Index}=\{\},Update=\mathrm{Null}\}\);
29 foreach\(\mathit{solution}\)\(S_{k}\in S\)do
30\(\mathit{best}\)\(\leftarrow\)\(\underset{k\in K}{\arg\min}\,S(\mathbf{U})\) ;
31\(\mathit{Index}\leftarrow\underset{k\in K}{\mathit{Sort}}\,S(\mathbf{U})\) ;
32 // Sort the solution set from smallest to largest by aggregation utility to obtain the subscript index.
33 if\(\mathit{S}_{\mathit{best}\)\(\mathbf{U})\(<\)\(\