# Optimized Weighted Nearest Neighbours Matching Algorithm for Control Group Selection
## 3 Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA)
### Conflicting Candidates  
The WNNSA algorithm solves the pairing of the proper individuals using metaheuristic population-based optimization. Each state in the search space represents a possible solution for the control group selection (a possible pairing of the individuals of the treated and control groups). The goal of the algorithm is to find the best pairing. To achieve this goal, the algorithm utilizes simulated annealing to select the best pairs for the treated individuals, and the goal is to minimize the sum of the pairwise distances of the paired individuals. The probability for selecting the candidate \(\textbf{X}_{j}\in X_{C}\) for the individual \(\textbf{X}_{i}\in X_{T}\) is calculated as:  
\[p(\textbf{X}_{i},\textbf{X}_{j})=\frac{p_{temp}(\textbf{X}_{i},\textbf{X}_{j} )}{\sum_{j}p_{temp}(\textbf{X}_{i},\textbf{X}_{j})}, \tag{4}\]  
where  
\[p_{temp}(\textbf{X}_{i},\textbf{X}_{j})=\frac{1}{dist(\textbf{X}_{i},\textbf {X}_{j})^{I}} \tag{5}\]  
and \(t\) is the temperature of the simulated annealing process. The energy function (\(e\)) determining the fitness of the candidate solutions is given by Equation (6). \[e=\sum_{(\textbf{X}_{i},\textbf{X}_{j})\in M}dist(\textbf{X}_{i},\textbf{X}_{ j}), \tag{6}\]  
where \(M=\{M_{1},M_{2},\ldots,M_{m}\}\) yields the pairing of the elements. In case of 1:1 matching, \(m=|X_{T}|\). For later use, denote \(M_{i1}\) the first and \(M_{i2}\) the second element from the \(i\)-th pair from \(M(i=1,2,\ldots,m)\). In cases when individuals to be paired can be selected from many candidates, many possible pairings are conceivable. To reduce the runtime of the algorithm, the WNNSA algorithm looks for the optimal solution in a reduced search space. The applied heuristic constraints the search space in such a way that the individual of the treated group can only be paired to their \(k\)-nearest neighbours from the candidate set. Further neighbours are not considered for the pairing. Denote \(NN_{k}(\textbf{X}_{i},Y)\) the \(k\)-closest neighbours of \(\textbf{X}_{i}\) from the set \(Y\). Using this notation, the \(k\)_-size reduced environment_ for an individual \(\textbf{X}_{i}\in X_{T}\) is given by \(NN_{k}(\textbf{X}_{i},X_{C})\). The detailed algorithm of the Weighted Nearest Neighbours Control Group Selection with Simulated Annealing method is presented in Algorithm 1. After the initialization of the variables (Step 1) and the normalization of the features (Step 2), the algorithm determines the sets of the \(k\)-nearest neighbours for all \(\textbf{X}_{i}\in X_{T}\) individuals (Steps 3 and 4). Steps 5 to 9 describe the simulated annealing optimization of the matching. In Step 5, the probabilities are calculated using the temperature parameter of the simulated annealing by Equation (4), and they are assigned to the elements. Step 8 describes the probability-based matching, while the detection of the conflicted candidates can be found in Step 9. The resolution of conflicts is made iteratively by repeating Steps 7 to 9. After finding a possible solution, the fitness value of the matching is calculated in Step 11. Following this, the actual matching is compared to the best result up to this point, and the better solution is saved as the best matching (Step 12). Finally, the temperature is reduced (Step 13). The simulated annealing process continues until the temperature reaches 0 (Step 14). The algorithm returns the control group with the lowest \(e^{(t)}\) energy with the corresponding matching result (Step 15). For the sake of clarity, it should be noted that \(ActualMatching^{(t)}\) denotes a transient set of matched pairs that the algorithm generates at temperature \(t\). Furthermore, \(ActualMatching^{(t)}_{i}\) yields an element of this set, that is a specific matching of a treated element with a candidate element. Moreover, \(ActualMatching^{(t)}_{i1}\) denotes the first and \(ActualMatching^{(t)}_{i2}\) the second element of the matched pair of the \(i\)-th element from the set \(ActualMatching^{(t)}\).