# Evolutionary System Design with Answer Set Programming
## 3 Evolutionary Design Space Exploration
### Distance between Implementations
If the missing option is not employed, the implementations are equal with respect to that option. Given two implementations \((b,r,s)\) and \((b^{\prime},r^{\prime},s^{\prime})\) of two system synthesis problems \((A,P)\) and \((A^{\prime},P^{\prime})\), respectively, we define the following distance functions:* _Binding distance_ \[D_{b}(m,m^{\prime},b,b^{\prime})=\sum_{(t,r)\in M_{m}\cup M_{m^{\prime}}}d_{b}(M_{ m},M_{m^{\prime}},b,b^{\prime},(t,r))\]
* _Routing distance_ \[D_{r}(A,A^{\prime},L,L^{\prime},r,r^{\prime})=\sum_{(d,l)\in L_{A,L}\cup L_{A^{ \prime},L^{\prime}}}d_{r}(L_{A,L^{\prime},L^{\prime}},r,r^{\prime},(d,l))\]
* _Scheduling distance_ \[D_{s}(A,A^{\prime},s,s^{\prime})=\sum_{t\in T_{A}\cup T_{A^{\prime}}}d_{s}(T_{A },T_{A^{\prime}},r,r^{\prime},t)\]
* _Overall distance_ \[D((A,P),(r,b,s),(A^{\prime},P^{\prime}),(r^{\prime},b^{\prime},s^{\prime}))=D_ {b}(m,m^{\prime},b,b^{\prime})+D_{r}(A,A^{\prime},L,L^{\prime},r,r^{\prime})+D _{s}(A,A^{\prime},s,s^{\prime})\]  
The binding distance \(D_{b}\), routing distance \(D_{r}\), and scheduling distance \(D_{s}\) now merely sum up values of the functions \(d_{b}\), \(d_{r}\), and \(d_{s}\), respectively, for all possible options of both system synthesis problems, depending on both implementations. To obtain the relative distance from zero (implementations are identical) to one (implementation are completely different), we can normalize the four absolute distances by dividing by \(|M_{m}\cup M_{m^{\prime}}|\), \(|L_{A,L}\cup L_{A^{\prime},L^{\prime}}|\), \(|T_{A}\cup T_{A^{\prime}}|\), and \(|M_{m}\cup M_{m^{\prime}}|+|L_{A,L}\cup L_{A^{\prime},L^{\prime}}|+|T_{A}\cup T _{A^{\prime}}|\), respectively. Returning to our child implementation in Figure 3, we can now select from among the 71,818 implementations using the distance measures. Figure 4 shows an implementation that is very similar to the implementation in Figure 2. In fact, if we let \((A,P)\) be the system synthesis problem in Figure 1, \((A^{\prime},P^{\prime})\) the system synthesis problem in Figure 3, \((b,r,s)\) the implementation in Figure 2, and \((b^{\prime},r^{\prime},s^{\prime})\) the implementation in Figure 4, then we have \(D_{b}(m,m^{\prime},b,b^{\prime})=1\), \(D_{r}(A,A^{\prime},L,L^{\prime},r,r^{\prime})=6\), and \(D_{s}(A,A^{\prime},s,s^{\prime})=8\). Here, the binding and routing distance are minimal because distance one and six, respectively, are the lower bound of changes induced by removing task \(t_{1}\). On the contrary, the scheduling distance has a maximum value of eight, as there are eight entities that have to be scheduled overall: four tasks and four dependencies, which are either removed or have different starting times. This shows that the scheduling distance as defined above might be too granular for an effective comparison; we also observed this in our experiments, which we present in Section 6. Different scheduling distances could be employed, such as absolute distance between two start points, but this is computationally difficult, and we relegate this task to future work. Just considering the minimal binding and routing distance, we actually obtain an non-dominated child implementation in Figure 3.