# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Similar to _clingo[DL]_, our Pareto optimization framework adds symbols to the answer set and describes the quality of the solution. Specifically, we add symbols of the form pref(\(n\),\(t\),\(v\)), where \(n\) is the name, \(t\) is the type, and \(v\) is the objective value. ```
1 preference(cost,sum). 2 preference(cost,(1,1),1,for(atom(allocated(R))),(C))
3:- cost(R,C). 4 holds(atom(allocated(R)),0):- allocated(R). 5
6 preference(energy,sum). 7 preference(energy,(2,1),1,for(atom(allocated(R))),(S))
8:- static_energy(R,S). 9 holds(atom(allocated(R)),0)
10:- allocated(R). 11 preference(energy,(2,2),1,for(atom(route((T,T'),R,R'))),(E))
12:- link(R,R'),send(T,T'),routing_energy(E). 13 holds(atom(route((T,T'),R,R')),0)
14:- route((T,T'),R,R'). 15 preference(energy,(2,3),1,for(atom(bind(T,R))),(D))
16:- mapping(R,T),dynamic_energy(R,T,D). 17 holds(atom(bind(T,R)),0)
18:- bind(T,R). 19
20 preference(latency,max). 21 preference(latency,(3,1),1,for(atom(bind(T,R))),(T,E))
22:- mapping(R,T),execution(R,T,E). 23 holds(atom(bind(T,R)),0)
24:- bind(T,R). ```
**Listing 11** Encoding preferences cost, energy consumption, and latency. For instance, our parent implementation in Figure 2 has quality pref(cost,sum,10), pref(energy,sum,43), and pref(latency,max,15). ## 5 Encoding Evolutionary Design Space Exploration

In this section, we describe how we implement an evolutionary design space exploration with our ASP-based framework. We start by outlining how we encode the similarity measure between a parent and child implementation. For that, we only focus on the binding and routing distance as the scheduling similarity performed badly in our empirical analysis (cf. Section 6). Then, we present three techniques for facilitating similar child implementations: strategies, preferences, and domain-specific heuristics. In essence, _strategies_ restrict the search space via integrity constraints to only contain similar implementations, and _preferences_ use the distance measures as another entry in the quality and therefore make it subject to Pareto optimization; _domain-specific heuristics_ adapt the solver's heuristics in such a way that similar implementations are emphasized. Note that only strategies remove solutions while preferences and heuristics consider the whole search space. For all of these techniques, we consider both encouraging similarity and discouraging dissimilarity. ### Encoding the Similarity Measure

To establish the similarity measure between parent and child, we first reify all atoms of the parent specification and parent implementation in atoms over predicated parent/1. For instance, the atom link(r1,r5) is a member of the parent specification in Figure 1, and route((t1,t2),r1,r5) is contained in the parent implementation in Figure 2; so, we add facts parent(link(r1,r5)) and parent(route((t1,t2),r1,r5)), respectively. Listing 12 shows the facts that are relevant to establish similarity between parent and child in our running example. Listing 13 shows the encoding of the similarity measure; it derives two kinds of atoms: equal/1 atoms that indicate that an aspect of the parent and child implementation are equal and unequal/1 atoms capturing a difference between the parent and child implementation. The encodings closely follow the cases of the definition of functions \(d_{b}\) and \(d_{r}\). Lines 1 to 5 establish equal bindings of the parent and child, i.e., the \"otherwise\" case of \(d_{b}\). Parent and child implementation are equal for the binding of task \(t\) on resource \(r\) if they either both bound \(t\) to \(r\) or the mapping exists in either the child or parent specification but both did not use this mapping. For instance, we derive equal(bind(t4,r1)) and equal(bind(t1,r4)) for our running example; the first is derived because both the parent and child implementation have the same binding, and the second is derived because the binding exists in the parent specification but both implementations do not use it. The encoding of unequal bindings in Lines 6 to 13 follows the remaining cases of function \(d_{b}\).