# Evolutionary System Design with Answer Set Programming
## 3 Evolutionary Design Space Exploration
### Distance between Implementations  
As mentioned above, we are using distance information to foster high-quality implementations for novel but similar system synthesis problems. To this end, we start from a system synthesis problem wherein a high-quality implementation is known; this is called the _parent specification_ and _parent implementation_, respectively. In our example, Figure 1 constitutes the parent specification and Figure 2 constitutes the parent implementation. Then, the parent specification is changed or updated to a so-called _child specification_. Such a child specification for our example is given in Figure 3. Here, task \(t_{1}\) was deleted, which can be seen as a software update as this task is no longer needed to execute the application; updates to the hardware platform are marked in green. Essentially, we replace resource \(r_{1}\) with a more costly version that saves energy. Everything else remains unchanged from the parent specification in Figure 1.  
Next, we define a distance measure that allows us to compare implementations. We divide the distance between two implementations of a system synthesis problem into the distance between binding, routing, and scheduling. Before accomplishing this, we require some intermediate definitions. Figure 3: Example system synthesis problem (child specification). Given a system synthesis problem\((A,((R,L),rd,c,se,re,p,m,e,de))\), we define the sets:  
\[M_{m} =\{(t,r)\ |\ t\in m(r),r\in R,t\in T\}\] \[L_{A,L} =\bigcup_{(T,D)\in A}\{(d,l)\ |\ d\in D,l\in L\}\] \[T_{A} =\bigcup_{(T,D)\in A}\{t\ |\ t\in T\cup D\}\]  
Intuitively, the set \(M_{m}\) contains all possible bindings given a mapping function; \(L_{A,L}\) contains all possible pairs of dependencies and links to collect which communication routes are possible; finally, \(T_{A}\) is the set of all entities that are scheduled, i.e., all tasks and communications. Given two system synthesis problems \((A,((R,L),rd,c,se,re,p,m,e,de))\) and \((A^{\prime},((R^{\prime},L^{\prime}),rd^{\prime},c^{\prime},se^{\prime},re^{ \prime},p^{\prime},m^{\prime},e^{\prime},de^{\prime}))\), we define three functions:  
* For two bindings \(b\) and \(b^{\prime}\) and \((t,r)\in M_{m}\cup M_{m}^{\prime}\), we define \[d_{b}(M_{m},M_{m^{\prime}},b,b^{\prime},(t,r))= \begin{cases}1,\text{ if }(t,r)\
ot\in M_{m},(t,r)\in M_{m^{\prime}},b^{\prime}(t)=r\\ 1,\text{ if }(t,r)\in M_{m},(t,r)\
ot\in M_{m^{\prime}},b(t)=r\\ 1,\text{ if }(t,r)\in M_{m},(t,r)\in M_{m^{\prime}},b(t)=r,b^{\prime}(t)\
eq r \\ 1,\text{ if }(t,r)\in M_{m},(t,r)\in M_{m^{\prime}},b(t)\
eq r,b^{\prime}(t)=r \\ 0,\text{ otherwise}\end{cases} \]
* For two routings \(r\) and \(r^{\prime}\) and \((d,l)\in L_{A,L}\cup L_{A^{\prime},L^{\prime}}\), we define \[d_{r}(L_{A,L},L_{A^{\prime},L^{\prime}},r,r^{\prime},(d,l))= \begin{cases}1, \text{ if }(d,l)\
ot\in L_{A,L^{\prime}},(d,l)\in L_{A^{\prime},L^{\prime}},l \in r^{\prime}(d)\\ 1,\text{ if }(d,l)\in L_{A,L},(d,l)\
ot\in L_{A^{\prime},L^{\prime}},l\in r(d) \\ 1,\text{ if }(d,l)\in L_{A,L},(d,l)\in L_{A^{\prime},L^{\prime}},l\
ot\in r(d),l\
ot\in r^{\prime}(d)\\ 0,\text{ otherwise}\end{cases} \]
* For two schedulings \(s\) and \(s^{\prime}\) and \(t\in T_{A}\cup T_{A^{\prime}}\), we define \[d_{s}(T_{A},T_{A^{\prime}},s,s^{\prime},t)= \begin{cases}1,\text{ if }t\
ot\in T_{A},t\in T_{A^{\prime}}\\ 1,\text{ if }t\in T_{A},t\
ot\in T_{A^{\prime}}\\ 1,\text{ if }t\in T_{A^{\prime}},t\in T_{A^{\prime}},s(t)\
eq s^{\prime}(t)\\ 0,\text{ otherwise}\end{cases} \]  
These four functions determine one specific possible mapping, communication link, and start time, and whether a different decision has been made in two bindings, routings, and schedulings, respectively. The multiple cases stem from the possibility that both system synthesis problems are different. We have to take into account that certain possibilities do not exist in one or the other system synthesis problem. In case an option is unavailable but used by the other implementation, it should constitute a difference.