# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Parent and child implementation are unequal for a binding of task \(t\) on resource \(r\) if a mapping is only possible in either the child or parent specification and the respective binding is part of the respective implementation or the mapping is possible in both, but is unequal in the parent and child implementations. Returning to the examples, we would have unequal(bind(t1,r1)) because t1 no longer exists in the child specification. Other than that, the binding of the parent and child implementation in Figure 2 and 4 are identical. Establishing similarity with respect to the routing follows a very similar pattern. Lines 15 to 22 encode the equality of the routing, again corresponding to the \"otherwise\" case of function \(d_{r}\). Parent and child implementation are equal for a link \((r,r^{\prime})\) and communication \(d\) if either both implementations use link \((r,r^{\prime})\) for routing communication \(d\) or neither uses it but the possibility exists in either the parent or child specification; in our example, we have equal(route((t3,t5),r3,r7)) because both parent and child implementation use this route and equal(route((t1,t2),r5,r6)) because neither implementation contains it, but it is possible in the parent specification. The similarity encoding for the unequal parts of the parent and child implementation follows the cases of function \(d_{r}\). Parent and child implementation are unequal for a link \((u,u^{\prime})\) and communication \(d\) if \(d\) is part of only either child or parent implementation and \((u,u^{\prime})\) belongs to the routing of \(d\) in the respective implementation or if \(d\) is part of both specifications, but \((u,u^{\prime})\) is part of the routing of \(d\) in either the child or parent implementation only. Note that we do not need to specifically refer to all possible links in the rules because route/3 atoms are grounded over all possible links, and only the existence of a route in either parent or child implementation can lead to a dissimilarity. Let us return to our example. All routes that involve communications with task t1 are unequal from parent to child implementation. Specifically, we derive:

unequal(route((t1,t2),r1,r5)) unequal(route((t1,t2),r5,r7)) unequal(route((t1,t3),r1,r5)) unequal(route((t1,t3),r1,r5)) unequal(route((t1,t3),r5,r7)) unequal(route((t1,t3),r7,r3))

All other aspects of routing are identical. Note that we obtain the value for functions \(D_{b}\) and \(D_{r}\) if we count the unequal/1 atoms for binding and routing, respectively. For our example, we have one unequal atom for binding and six for routing, which are the values calculated by the distance functions. Note that we could derive equal/1 atomsfrom unequal/1 atoms and vice-versa but decided to give an independent definition to make all cases explicit. Furthermore, we can see that equal/1 atoms are derived for all possibilities in both specifications, not only for bindings and routings that are used in either the child or parent implementation. On the other hand, unequal/1 atoms are possible for bindings and routings that are part of at least one implementation. We therefore suspect different behaviors when using one or the other. In the following strategies, preferences, and heuristics, we separate the use of both kinds of atoms, and in Section 6, we empirically analyze the different impact. ### Strategies

Listings 14 and 15 show how we use strategies that forbid unequal and enforce equal implementations with respect to binding and routing, respectively. The integrity constraints in Listing 14 simply forbid that any binding or routing is unequal. On the other hand, Listing 15 forbids that any possible mapping or routing is not equal. Note that we have to use negation in Listing 15; therefore, we need to provide the domain of the equal/1 atoms, which are the possible mappings and routings in both the parent and child specifications. These strategies are our most invasive way to foster similar implementations.