## 4 Methodology
### Beam Ant Colony System (BACS)  
We now provide details of the multi-objective BACS approach proposed for this study. A key component of the method is to use bounds or estimates to assist in the search. For this purpose, we make use of three different problem specific bounds and also stochastic sampling. This leads to four different variants of multi-objective BACS. The algorithm presented in the previous section is extended to BACS [5] to solve our highly constrained software component deployment problem. The reasons for this are twofold. Firstly, BACS is known to be better at finding feasible solutions compared to ACS on several problems [36; 37; 38; 39; 40]. Givenfeasibility has already been showed to be problematic for the component deployment problem [7; 41], focusing on solving this issue is of high priority. Secondly, BACS can also be tuned to provide improved solution quality compared to ACS [36; 37; 38; 39; 40]. Thus, BACS provides a natural extension to ACS described earlier. Algorithm 1 remains the same. However, line 6 of Algorithm 2, uses a Beam search with pheromones instead. This procedure is presented in Algorithm 3. ```
1:input: \((\theta,\mu,\mathcal{T})\)
2:\(B_{0}=\{\pi_{1}=(),\ldots,\pi_{\theta}=()\}\)
3:\(i\gets 0\)
4:while\(i<n\)and\(|B_{i}|>0\)do
5:for\(t\in B_{i}\)do
6:\(k\gets 0,D=\textsc{Domain}(\pi_{i}^{t})\)
7:while\(k<\mu\wedge D\
eq\emptyset\)do
8:\(\hat{\pi}=\pi_{t}\)
9:\(j=\textsc{select}\textsc{HU}(D,\tau)\)
10:\(B_{i+1}=B_{i+1}\cup\pi^{k}\)
11:\(k\gets k+1,D=D\setminus j\)
12:endwhile
13:endfor
14:\(B_{i+1}=\textsc{Reduce}((B_{i+1},\theta))\)
15:\(i\gets i+1\)
16:endwhile
17:OUTPUT:\(\arg\max\{f(\pi)\mid\pi\in B_{n-1}\}\)
```  
**Algorithm 3** BACS  
The Beam (\(B\)), initially consists of \(\theta\) empty solutions. Between lines 4-16, each of these solutions is built incrementally. For each solution in the Beam, \(\mu\) solutions for the next software component are generated (lines 7-12). Each of these solutions is unique, each with different assignment of hardware units. Note, the pheromone trails are used in \(j=\textsc{select}\textsc{HU}(D,\tau)\) to bias the selection of the hardware units for each component. Once all solutions for the \(i^{th}\) components have been determined, the Beam potentially consists of \(\theta\times\mu\) solutions. These have to be restricted to \(\theta\) solutions and this is achieved in line 14: \(B_{i+1}=\textsc{Reduce}(B_{i+1},\theta)\). For each solution, an estimate is computed (discussed next) which gives each solution a rank. From these, the top \(\theta\) ranked solutions are selected. In Beam search, when extending a solution with a component, estimates of the 'goodness' of the component are critical to finding good areas of a search space. A bound is a value which an optimal solution cannot improve upon. Consider a minimisation problem with optimal solution \(x^{*}\) and lower bound \(lb\). Then, \(x^{*}\geq lb\). For the problem being considered, a good estimate is one that leads the search towards (1) feasible regions and (2) high quality regions. Problem specific bounds can be used to obtain such estimates. In Algorithm 3, line 14 uses an estimate to reduce the set of solutions to \(\theta\) solutions. In this study we explore four different bounds focused on finding feasibility. 1. Stochastic sampling: this estimate has been successfully used earlier and often outperforms problem specific bounds [36; 37; 38; 39; 40]. The idea implemented here is straightforward. Given a partial solution (\(\pi_{1}\ldots\pi_{i-1}\) components are assigned), a number of samples are generated by assigning hardware units to the remaining components using the pheromone bias. The best of these samples (considering violations, reliability and communication overhead) is used as the estimate for this solution. 2. Communication estimate: given a partial solution (\(\pi_{1}\ldots\pi_{i-1}\) components are assigned), the remaining software components are assigned hardware units ensuring the communication constraint is always satisfied.