In this paper we study the dynamics of self-adapting systems. Our main objective is to compare adaption dynamics of similar systems, i.e. systems that difer only in their organisational networks. We specify adaption in the formalisms of Hornets - a formalism that uses nets as tokens, i.e. they follow the nets-within-nets approach. We identify diferent abstractions of the reachability graph that focus on the adaption aspects of the processes. We develop key measures for adaption processes on these abstracted graphs. The key measures are used e.g. to compare two variations of the same adapting system. The approach is illustrated by a case study: We analyse a Hornet-model of Axelrod's well-known tournament where the playing agents adapt their strategies during the game.
itself – as the system net defines which object nets are involved and how adaption looks like. In the example of a workflow management system the object nets describe the set of workflows and the net-tokens are the workflow instances while the system net models the whole adaption process of workflows.
A state of a Hornet is a nested multiset, where a place of the system net is marked with ̂︀ net-tokens of the form [, ]; the topology of a net-token is defined by the object net and each net-token has its own marking :
system net net-token = ∑︁ ⏞⏟ [⏞ , ⏟ =1 ̂︀ ob⏟ject⏞net ON⏟mar⏞king ] For Hornets the gene pool of this state is given as the set of object nets, i.e. the set of possible net-token types: {1, . . . , }. We are interested in the dynamics of this set. More specifically, our main objective is to compare adaption dynamics of similar systems. For the example of a workflow management system we like to compare two companies with the same initial set of workflows but with diferent organisational networks, i.e. we like to study the impact of the network on the adaption dynamics. We like to develop key values for these dynamics to answer questions like: “Which company adapts faster?”, “Which company develops a gene pool of greater diversity?” etc.
The paper has the following structure: Section 2 recalls the definition of Hornets and
eHornets. The main purpose is to recall the defininition of the reachability graph of Hornets.
It can be skipped on first reading. The main contribution is given in Section 3, which describes
how adaption process can be studied in the formal framework of Hornets. We will derive a
structure describing the core adaption processes as an abstraction of the reachability graph of a
given Hornet. The dynamics of the gene pool is somehow in between two other dynamics: on
the one hand, it is much coarser than the dynamics of the whole Hornet as it abstracts from
the internal actions of the net-tokens; on the other hand is much finer than the dynamics of the
system net alone when considered as a normal p/t net. Diferent key values will be considered
to capture essential aspect of the adaption dynamics. In Section 4 we exemplify the theoretical
framework with a generalisation of Axelrod’s well-known tournament. The tournament is a
well-known example for adaption, especially in the context of genetic algorithms [
We have defined Hornets in [
With object nets we study Petri nets where the tokens are nets again, i.e. we have a nested marking. Events are also nested. We have three diferent kinds of events – as illustrated by the example given in Figure 1: 1. System-autonomous: The system net transition ̂︀fires autonomously, which moves the ̂︀
̂︀ net-token from 1 to 2 without changing its marking. to 2. The object net remains at its location 1.
̂︀ 2. Object autonomous: The object net fires transition 1 “moving” the black token from 1 3. Synchronisation: Whenever we add matching synchronisation inscriptions at the system ̂︀ net transition ̂︀and the object net transition 1, then both must fire synchronously: The object net is moved to 2 and the black token moves from 1 to 2 inside. Whenever synchronisation is specified, autonomous actions are forbidden.
For Hornets we extend object nets with algebraic concepts that allow to modify the structure
of the net-tokens as a result of a firing transition. This is a generalisation of the approach of
algebraic nets [
Z ⊐
q ZslHHj sl p ⌃ t (‖-)
r l N1 i1- - i- - ri- - i1
N3 3 h net-token produced on by h-1 - h- - rh- - h1 - rh - - h2 nesting to encode counters. Another possibility is to encode counters in the algebraic structure of the net operators.
The use of algebraic operations in Hornets relates them to algebraic higher-order (AHO)
systems [
Let us recall our results on complexity issues of Hornets. We introduced diferent restrictions
to guarantee that the system has a finite state space: First, we allow at most one token on each
place, which results in the class of safe Hornets. However, this restriction does not guarantee
ifnite state spaces, since we have the nesting depth as a second source of undecidability [
Safe, elementary Hornets have greater complexity when compared to their Eos counterpart:
On the one hand, we have shown in [
In [
In the following we recall the definition of eHornets from [
Multisets and P/T Nets A multiset m on the set is a mapping m : → N. Multisets can also be represented as a formal sum in the form m = ∑︀ =1 , where ∈ .
Multiset addition is defined component-wise: (m1 + m2)() := m1() + m2(). The empty multiset 0 is defined as 0() = 0 for all ∈ . Multiset-diference m1 − m2 is defined by (m1 − m2)() := max(m1() − m2(), 0).
The cardinality of a multiset is |m| := ∑︀∈ m(). A multiset m is finite if |m| < ∞. The set of all finite multisets over the set is denoted MS (). The domain of a multiset is dom(m) := { ∈ | m() > 0}.
Multiset notations are used for sets as well. The meaning will be apparent from its use.
Any mapping : → ′ extends to a multiset-homomorphism ♯ : MS () → MS (′) by ♯ (∑︀ =1 ().
=1 ) = ∑︀
A p/t net is a tuple = (, , pre, post), such that is a set of places, is a set of transitions, with ∩ = ∅, and pre, post : → MS ( ) are the pre- and post-condition functions. A marking of is a multiset of places: m ∈ MS ( ). We denote the enabling of in marking m by m→− . Firing of is denoted by m→− m′.
Net-Algebras We define the algebraic structure of object nets. For a general introduction of
algebraic specifications cf. [
Let be a set of net-types (kinds). A (many-sorted) specification (Σ, , ) consists of a signature Σ, a family of variables = ()∈ , and a family of axioms = ()∈ .
A signature is a disjoint family Σ = (Σ1· ,)1,· ,,∈ of operators. The set of terms of type over a signature Σ and variables is denoted TΣ ().
We use (many-sorted) predicate logic, where the terms are generated by a signature Σ and formulae are defined by a family of predicates Ψ = (Ψ)∈N. The set of formulae is denoted PLΓ, where Γ = (Σ, , , Ψ) is the logic structure.
Object Nets and Net-Algebras Let Σ be a signature over . A net-algebra assigns to each type ∈ a set of object nets – the net universe. Each object ∈ , ∈ net is a p/t net = ( , , pre , post ). We identify with ⋃︀∈ in the following. We assume the family = ()∈ to be disjoint.
The nodes of the object nets in are not disjoint, since the firing rule allows to transfer tokens between net tokens within the same set . Such a transfer is possible, if we assume that all nets ∈ have the same set of places . is the place universe for all object nets of kind . In the example of Fig. 2 the object nets 1, 2, and 3 must belong to the same type since otherwise it would be impossible to transfer the markings in 1 and 2 to the generated 3.
In general, is not finite. Since we like each object net to be finite in some sense, we require that the transitions of each ∈ use only a finite subset of , i.e. ∀ ∈ : |∙ ∪ ∙ | < ∞.
The family of object nets is the universe of the algebra. A net-algebra ( , ℐ) assigns to each constant ∈ Σ, an object net ℐ ∈ and to each operator ∈ Σ1· , with > 0 a mapping ℐ : (1 × · · · × ) → .
A net-algebra is called finite if is a finite set for each ∈ .
Since all nets ∈ have the same set of places , which is required to be finite for eHornets, there is an upper bound for the cardinality of .
Theorem 1 (Lemma 2.1 in [
A variable assignment = ( : → )∈ maps each variable onto an element of the algebra. For a variable assignment the evaluation of a term ∈ TΣ () is uniquely defined and will be denoted as ().
A net-algebra, such that all axioms of (Σ, , ) are valid, is called net-theory. Nested Markings A marking of an eHornet assigns to each system net place one or many net-tokens. The places of the system net are typed by the function k : ̂︀ → , meaning that a place contains net-tokens of kind k (). Since the net-tokens are instances of object nets, a ̂︀ ̂︀ marking is a nested multiset of the form:
= ∑︁ [, ] where ̂︀ ∈ ̂︀, ∈ k(), ∈ MS ( ), ∈ N
=1 ̂︀ ̂︀ Each addend [, ] denotes a net-token on the place that has the structure of the object ̂︀ ̂︀ net and the marking ∈ MS ( ). The set of all nested multisets is denoted as ℳ . We define the partial order ⊑ on nested multisets by setting 1 ⊑ 2 if ∃ : 2 = 1 + .
The projection Π1 ( ) is the multiset of all system-net places that contain the object net : Π1 (︁ ∑︁=1 ̂︀[, ]︁) := ∑︁=1 1 () · ̂︀ where the indicator function 1 is defined as: 1 () = 1 if = .
Analogously, the projection Π2 ( ) is the multiset of all net-tokens’ markings (that belong to the object net ):
Π2 (︁ ∑︁=1 ̂︀[, ]︁) := ∑︁=1 1() ·
The projection Π2( ) is the sum of all net-tokens’ markings belonging to the same type ∈ : Π2 ( ) := ∑︁ ∈ Π2 ( ) Synchronisation The transitions in an Hornet are labelled with synchronisation inscriptions. We assume a fixed set of channels = ()∈ .
• The function family ̂︀ = (̂︀ )∈ defines the synchronisation constraints. Each transition of the system net is labelled with a multiset ̂︀(̂︀) = (1, 1) + · · · + (, ), where the expression ∈ TΣ () describes the called object net and ∈ is a channel. The intention is that fires synchronously with a multiset of object net transitions with the ̂︀ same multiset of labels. Each variable assignment generates the function ̂︀ (̂︀) defined as: ̂︀ (̂︀)( ) := ∑︁ 1≤ ≤ for ̂︀(̂︀) = ∑︁ ()= 1≤ ≤ (, ) (4)
Each function ̂︀ (̂︀) assigns to each object net a multiset of channels. • For each ∈ the function assigns to each transition ∈ either a channel ∈ or ⊥, whenever fires without synchronisation, i.e. autonomously. (1) (2) (3) System Net Assume we have a fixed logic Γ = (Σ, , , Ψ) and a net-theory ( , ℐ). An elementary higher-order object net (eHornet) is composed of a system net ̂︀ and the set of object nets . W.l.o.g. we assume ̂︀ ̸∈ . To guarantee finite algebras for eHornets, we require that the net-theory ( , ℐ) is finite, i.e. each place universe is finite.
The system net is a net ̂︀ = (̂︀, ̂︀, pre, post, ̂︀), where each arc is labelled with a multiset of terms: pre, post : ̂︀ → (̂︀ → MS (TΣ())). Each transition is labelled by a guard predicate ̂︀ : ̂︀ → PLΓ. The places of the system net are typed by the function k : ̂︀ → . As a typing constraint we have that each arc inscription has to be a multiset of terms that are all of the kind that is assigned to the arc’s place: (5)
For each variable binding we obtain the evaluated functions pre , post : ̂︀ → (̂︀ → MS ( )) in the obvious way.
Definition 1 (Elementary Hornet, eHornet). Assume a fixed many-sorted predicate logic Γ = (Σ, , , Ψ).
An elementary Hornet is a tuple EH = (̂︀ , , ℐ, k , , 0) such that: 1. ̂︀ is an algebraic net, called the system net. 2. ( , ℐ) is a finite net-theory for the logic Γ. 3. k : ̂︀ → is the typing of the system net places. 4. = (̂︀, )∈ is the labelling.
5. 0 ∈ ℳ is the initial marking.
Events The synchronisation labelling generates the set of system events Θ. We have three kinds of events: 1. Synchronised firing: There is at least one object net that has to be synchronised, i.e. there is a such that ̂︀(̂︀)( ) is not empty.
Such an event is a pair = ̂︀ [], where ̂︀ is a system net transition, is a variable binding, and is a function that maps each object net to a multiset of its transitions, i.e. ( ) ∈ MS ( ). It is required that ̂︀and ( ) have matching multisets of labels, i.e. ̂︀(̂︀)( ) = ♯ (( )) for all ∈ . (Remember that ♯ denotes the multiset extension of .) The intended meaning is that ̂︀ fires synchronously with all the object net transitions ( ), ∈ . 2. System-autonomous firing: The transition ̂︀of the system net fires autonomously, whenever ̂︀(̂︀) is the empty multiset 0.
We consider system-autonomous firing as a special case of synchronised firing generated by the function id , defined as id ( ) = 0 for all ∈ . 3. Object autonomous firing: An object net transition in fires autonomously, whenever () = ⊥.
Object autonomous events are denoted as id , [], where ( ′) = {} if = ′ and ̂︀ 0 otherwise. The meaning is that in object net fires autonomously within the place . ̂︀ For the sake of uniformity we define for an arbitrary binding : {︃1 0 if ′ = ̂︀ ∧ ′ =
̂︀ otherwise.
The set of all events generated by the labelling is Θ := Θ1 ∪ Θ2, where Θ1 contains synchronous events (including system-autonomous events as a special case) and Θ2 contains the object autonomous events: Θ1 := Θ2 := {︁ []
̂︀ {︁id , [] | ̂︀ ∈ ̂︀, ∈ k(̂︀), ∈ }︁ ̂︀ | ∀ ∈ : ̂︀ (̂︀)( ) = ♯ (( ))}︁ (6) (7) Firing Rule A system event = ̂︀ [] removes net-tokens together with their individual internal markings. Firing the event replaces a nested multiset ∈ ℳ that is part of the current marking , i.e. ⊑ , by the nested multiset . The enabling condition is expressed by the enabling predicate EH (or just whenever EH is clear from the context): EH ( [], , ) ⇐⇒ ∀ ∈ : ̂︀ ∀̂︀ ∈ k − 1() : ∀ ∈ : Π1 ( )(̂︀) = pre (̂︀)(̂︀)( ) ∧ ∀Π̂2︀(∈ )k −≥ 1(∑︀):∈∀p∈re♯(:(Π1)() ∧)(̂︀) = post (̂︀)(̂︀)( ) ∧ Π2( ) = Π2( ) + ∑︀∈ post♯ (( )) − pre♯ (( ))
The predicate EH has the following meaning: Conjunct (1) states that the removed submarking contains on ̂︀ the right number of net-tokens, that are removed by ̂︀. Conjunct (2) states that generated sub-marking contains on ̂︀ the right number of net-tokens, that are generated by ̂︀. Conjunct (3) states that the sub-marking enables all synchronised transitions ( ) in the object . Conjunct (4) states that the marking of each object net is changed according to the firing of the synchronised transitions ( ).
Note, that conjunct (1) and (2) assures that only net-tokens relevant for the firing are included in and . Conditions (3) and (4) allow for additional tokens in the net-tokens.
For system-autonomous events ̂︀ [id ] the enabling predicate EH can be simplified further: Conjunct (3) is always true since pre (id ( )) = 0. Conjunct (4) simplifies to Π2( ) = Π2( ), which means that no token of the object nets get lost when a system-autonomous events fires.
Analogously, for an object autonomous event ̂︀[] we have an idle-transition ̂︀ = id ̂︀, and = for some . Conjunct (1) and (2) simplify to Π1′ ( ) = ̂︀ = Π1′ ( ) for ′ = and to Π1′ ( ) = 0 = Π1′ ( ) otherwise. This means that = ̂︀[ ], enables , and = ̂︀[ − pre (̂︀) + post (̂︀)].
Definition 2 (Firing Rule). Let EH be an eHornet and , ′ ∈ ℳ markings. • An event ̂︀ [] that is enabled in can fire – denoted →−− − − − − ̂︀ [E]H(, ) ′. • The event ̂︀ [] is enabled in for the mode (, ) ∈ ℳ2 if ⊑ ∧ EH (̂︀[], , ) holds and the guard ̂︀(̂︀) holds, i.e. |=ℐ ̂︀(̂︀). • The resulting successor marking is defined as ′ = − + .
Note, that the firing rule has no a-priori decision how to distribute the marking on the generated net-tokens. Therefore we need the mode (, ) to formulate the firing of ̂︀ [] in a functional way.
Firing is extended to sequences ∈ Θ* in the usual way: • The empty sequence = is enabled if ′ = .
• Whenever →−− EH ′ and →′−− E H ′′ then →−− − (E· H ) ′.
We denote →−− E* H ′ whenever there is some such that →−− EH ′ holds. We omit the subscript EH whenever it is clear from the context. The set of reachable markings is defined as: RS (EH ) := RS ( 0) := {︁ | →0−− E* H }︁
The reachability graph RG (EH ) = (, , 0) contains all nested markings = RS (EH ) as vertices (or: nodes), = {(, ′) | →− ′} as edges and the initial marking 0 as a distinguished node.
For eHornets it is quite obvious how to define the gene pool of a system state: Obviously, we are interested in the (multi-)set of object nets that are contained in the marking . These are given by the projection Π ( ): Π ︁( ∑︁ [, ]︁) := ∑︁
=1 ̂︀ =1 1 () · where the indicator function 1 is defined as: 1 () = 1 if ∈ .
For the complete universe we define:
Π ( ) := ∑︁∈ Π ( ) = ∑︁=1
We define Π˜ := dom ∘ Π to obtain the set of object nets. We use the metaphor that Π˜ ( ) = {1, . . . , } is the gene pool of the marking .
Note, that for safe Hornets we have no more object nets than system net places and therefore Π˜ ( ))| ≤ | Π ( )| ≤ | ̂︀|, i.e. the gene pool is bounded. | (8) (9) (10) (11)
The set of reachable object nets of EH , defined as: (EH ) := ( 0) :=
⋃︁
∈RS( 0)
Π˜ ( )
describes the universe of reachable genes, but it does not contain any information about the
adaption dynamics at all. So, we look at the reachability graph. But, the RG of a Hornet is
usually too large to analyse, since the reachability problem requires exponential space for safe
eHornets [
As we are interested in the adaption dynamics of object nets we start with the reachability graph and abstract from “irrelevant” events. Roughly speaking, an event is considered as irrelevant whenever the set of object nets Π^ ( ) doesn’t change when firing the event (i.e. the Hornet is stuttering with respect to the set of object nets).
Definition 3. The marking +1 is -reachable in (, ) from 1 whenever there is a sequence 1 2 · · · +1 such that for all ∈ {1, . . . , } we have:
∃ : →− +1 ∧ Π˜ ( ) = Π˜ ( +1) Given RG (EH ) = (, ) we define the following relations on reachable markings: • ( 1, 2) ∈ 1 if 2 is -reachable from 1 in (, ) – and vice versa. • ( 1, 2) ∈ 1′ if 2 is -reachable from 1 in (, ). • ( 1, 2) ∈ 2 if 2 is -reachable from 1 in the undirected graph (, ( ∪ − 1)). • ( 1, 2) ∈ 3 if Π˜ ( 1) = Π˜ ( 2)
In other words, 1 relates markings that are strongly connected in the reachability graph via irrelevant events; for 1′ the connection may hold in only one direction; and 2 relates markings that are weakly connected via irrelevant events. Unlike the other relations, 3 does not assume any reachability relation between the markings.
Obviously, the relations have the following properties: Lemma 1. • 1 is reflexive, symmetric, and transitive.
• 1′ is reflexive and transitive, but in general not symmetric. • 1 = 1′ ∩ (1′)− 1 • 2 is reflexive, symmetric, and transitive.
• 3 is reflexive, symmetric, and transitive.
Since 1, 2, and 3 are equivalences we can use them to factor the RG, i.e. equivalence classes are condensed to a single node. All these graphs have 0 := [0] as a designated initial node. Definition 4. Let = (, , 0) be a graph with initial node and let ≈ ⊆ on the vertices. The factorised graph is defined as /≈ = ( ′, ′, 0′) with 2 be an equivalence ′ = [ ]≈ , ′ = {([ ]≈ , [ ′]≈ ) | (, ′) ∈ }, and
Then, the abstracted graph RG (EH )/ where = 1, 2, 3 describes the evolution of the gene pool that is specified by the Hornet.
The three relations leads to diferent kinds of abstraction due to the following inclusions: Lemma 2 (Abstraction Hierarchy). 1 ⊆ 1′ ⊆ 2 ⊆ 3
Here, a finer equivalence leads to a larger factorised graph. With Lemma 2 we obtain that RG (EH )/1 is closer to the original RG, while RG (EH )/3 leads to a more abstract factorisation. More specifically: • The graph AG 1(EH ) := RG (EH )/1 collapses areas in the reachability graph where the set of used object nets (i.e. the gene pool) doesn’t change, i.e. it abstracts away from stuttering. • The graph AG 2(EH ) := RG (EH )/2 collapses greater areas in the RG since it is suficient that there is a weak connectivity of the markings in the RG. • The graph AG 3(EH ) := RG (EH )/3 collapses all markings into one single vertice whenever the projection Π˜ ( ) is the same.
In the following, we identify suitable graph theoretic measures to give key values of the abstract graph (, , 0). Assume that = | | and = ||. For more aspects of graph measures cf. [27, Chapter 17].
On a macroscopic scale the average degree 1 · ∑︀∈ deg () tells us about how many evolution options the system has. A higher value indicates that the system has many options to adapt.
Similarly, the density (− 1) tells us something about the specificity of the adaption process on a macroscopic scale, where a higher value indicates that the system has no specific direction to evolve.
Graph transitivity looks at density on a more microscopic scale. It is the probability that ’s neighbours are connected, too: := |{(, , ) | (, ), (, ), (, ) ∈ }| |{(, , ) | (, ), (, ) ∈ }| (12)
Transitivity tells us how dense the adaption process is on a small scale, i.e. when considering triplets of nodes. A higher value indicates that there are many ways of achieving the same adaption state, while a lower value indicates that some adaption states are reachable via a more specific process, only
We are interested in measurements of the length of the adaption process. The path length tells us something about the convergence speed. Let ( → ′) denote the shortest path length from node to ′. Then, the distances (0 → ) describes how long the adaption dynamics is extended from initial node. A greater path length means a longer adaption dynamics.
The maximal distance from a given node is called its eccentricity (): (13) (14) () := max ( → ′)
′∈ The eccentricity (0) tells us about the gene pool that is farthest away. We also consider the normalised variant (0)/.
We also identify the most “central” states in the dynamics, which are in some sense the discrete, graph-theoretical analogon of an attractor. There are several concepts of centrality in graph theory. Here, we use betweeness centrality () that is the probability for the shortest path between two nodes to go through that node .
() :=
1 ( − 1)( − 2) ∑︁
(→− ) ,∈ :̸=,̸=,̸= ( → )
Here, ( → ) is the number of shortest paths from node to node and (→− ) is the number of the shortest paths that go through node .
We use the stochastic distribution of betweeness centrality () to identify which of the nodes/genes are very central in the dynamics. The variance indicates whether the distribution is tight around its average value: a higher variance indicates that some nodes are more central than others.
Assumed that adaption always leads to an improvement, the abstract graph would contain no cycles. In general, a system will allow for some regression for exploration issues – a try-and-error strategy. But it is reasonable that on larger time scales adaption will lead to an improvement. So, longer cycles are typically less common than short ones. When “ignoring” cycles, the abstract graph describes a partial order. Therefore, we have to find a maximal sub-graph that describes a partial order, i.e. a maximal DAG (directed acyclic graph). This sub-graph is interpreted as an underlying dynamics of improvement – when ignoring small phases of regression. We require that all the nodes remain reachable from the initial node 0 in the DAG. So, we generate a maximal spanning DAG. The set of all such sub-graphs of = (, , 0) being a DAG is: (, , 0) := { | = (, , 0) is a DAG ∧ ⊆ ∧ ∀ ∈ : (0, ) ∈ *}
(15)
We are interested in a sub-DAG of maximal size:
0() := max{|| | (, , 0) ∈ ()} In other words, || − 0() is the minimal number of edges to be deleted to obtain an acyclic graph from the abstracted reachability graph .
Definition 5.
The degree of adaption directedness is dad () := |0(|) .
The degree of adaption directedness indicates, how much the dynamics is going into a certain direction (which can be interpreted as an improvement). When () is close to 1, then the RG is acyclic, and the adaption dynamics goes (almost) strictly into one direction; while a dad () close to 0 indicates an adaption process heavily running in cycles. Of course, we hope for a dynamics with dad () ≈ 1, since they are easier to interprete.
Any subgraph = (, , 0) of = (, , 0) being a DAG with maximally many edges, i.e. || = 0(), is a candidate for the underlying improvement dynamics.
0 () := {(, , 0) ∈ () | 0() = ||} We use depth and width of all the DAGs ∈ 0 (, , 0) as our central key measures: • The DAG-depth is the largest line, i.e. a maximal clique w.r.t. li, which is the dependence relation of a DAG = (, , 0) defined as li := * ∪ (* )− 1 ∪ id :
depth() := max{|| | is maximal li-clique } A greater depth tell us that the system is very productive with respect to adaption, since it is going very straight into one direction. • The DAG-width is the largest cut, i.e. a maximal independent set, or, alternatively, a maximal clique w.r.t. the independence relation co := li ∪ id :
width() := max{|| | is maximal co-clique } A greater width tells us that for a given gene pool there is a large amount of options to adapt – depending on structural aspects we have abstracted from in the adaption graph. • The depth-width ratio depth()/width() tells us something about the number of adaption options given per productive evolution step.
We average the depth and width over all the DAGs in 0 (, , 0): depth() :=
1 ∑︁ depth() Analogously for width(). 80–98 (16) (17) (18) (19) (20)
We can transform the DAG = (, , 0) into a tree by using a diferent copy of a node for each path from the initial node to this node. (The definition is unproblematic, since our DAGs have finitely many nodes, and therefore also only finitely many paths.) Definition 6. with
Define the tree unfolding of a DAG = (, , 0) as tree() = (, , 0) = = { | = 0 . . . is a path in } {(, ′) | ′ = · ′}
The tree structure reveals information about the relationship between exploration of the adaption space, i.e. when the systems tests diferent options (and this accepts regression), and its exploitation, i.e. when the systems sticks to a pretty good option and tries to improve it with minor changes instead of evaluating some completely other option.
When the tree is growing the systems explores the adaption space. When the growth stagnates the system exploits the information gained. We try to capture this in the following measures: The adaption tree has a diferent branching structure, i.e. less successors here and more over there; additionally, exploration and exploitation does not necessarily come in two successive phases, but in many, intertwined ones. So, we compare our tree with a very “tidy” reference tree, namely a tree that starts with the exploration phase followed by the exploitation phase. When the root is drawn at the top the tree has a △□ -like shape, where the triangle describes the exploration (with a high branching degree) and the rectangle describes the exploitation (with no branching). A dynamics that has a maximal exploration leads to a tree that consists of the triangle part only.
Assume that the original tree has height ℎ0 and 0 leaves and 0 nodes. Let ℎ be the height of the exploration-triangle and ℎ′ the height of the exploitation-rectangle in the reference tree. Similarly, the triangle has nodes and leaves; the rectangle has ′ nodes and ′ leaves. As the rectangle has no branching, it has the same number of leaves as the triangle: = ′. We want to have a △□ -like tree that the same height and also the same number of nodes as the original tree: ℎ0 = ℎ + ℎ′ and 0 = + ′. We also require that the number of leaves does not change: 0 = = ′.
The new tree must have a (yet unknown) branching such that ℎ = = 0 in the △-part of the △□ -like shape. Thus the complete triangle then has = ℎ+1− 1 nodes and = ℎ leaves. − 1 The rectangle has as many leaves as the triangle, as we have no branching here, and ′ = ℎ′ · ℎ nodes. So, we obtain: 0 = + ′ = ℎ+1 − 1 + ℎ′ · ℎ ≈ ℎ + ℎ′ · ℎ = ℎ(1 + ℎ′) = 0(1 + ℎ′)
− 1
Therefore, the exploitation rectangle □ has the height ℎ′ ≈ 00 − 1. From this we obtain the height ℎ of the exploration triangle △ as ℎ = ℎ0 − ℎ′ ≈ ℎ0 − 00 + 1.
Let = (, , 0) be a DAG and assume that its tree unfolding = tree() has 0 leaves, 0 nodes, and height ℎ0. Then, the exploitation rate of = tree(, , 0) is the ratio of the 80–98 (21) (22) rectangle height ℎ′ to the total height ℎ0: ( ) := ℎ′ Correspondingly, the exploration rate is given as (1 − ( )).
We are interested in the corresponding exploration and exploitation rates in the adaption dynamics.
Definition 7 (exploration and exploitation rates).
For the DAG we define () := (tree()). For an abstract reachability graph we define: () := 1 ∑︁
()
These rates are used to characterise adaption dynamics: Systems with a high exploration rate could be considered as adventurous, while systems with a high exploitation rate could be considered as more conservative.
is assumed.
In Axelrod’s Tournament [
defect (D) cooperate (C) defect (D) 3,3 5,0 0,5 1,1
In the tournament version agents are playing this game pairwise over several rounds. The agents are allowed to adapt their strategy over time. We assume that each agent remembers a ifnite history of games already played with a given opponent. Assuming a history of size 3 a history is ℎ = 321 = (3, 3)(2, 2)(1, 1) where , ∈ {, }. A strategy is therefore a function : {, }6
→ {, }. When describing strategies by automata each history ℎ ∈ {, }6 is a state and the action chosen for the current game is given by state changes.
Even for this very restricted history size we have 2 2 6 = 264 diferent strategies, i.e. the strategy space is far too large to be explored directly. The classical approach to adaption is genetic programming. The main idea is simple ([2, pg 80f]): Each strategy evaluates its payof so far. The higher the payof the higher the number of ofsprings. An ofspring is generated via a cross-over mechanism, i.e. the two parents’ histories are split at some fixed point and recombined in a cross-over fashion.
We generalise the setting: We assume that there is a network that connects the agents and only connected agents can play the game. We assume that a network also determines which agents may be chosen as parents when generating a cross-over. For simplicity we assume both networks to be equal.
We have specified this scenario as an eHornet. Here, the object nets specify the agents,
i.e. the strategy automata. The system net (shown in a simplified version in Fig. 3) specifies
which agents are chosen for playing the game. It also specifies which agents are chosen in the
adaption process for the cross-over. The system net is parametrised with the connection graph.
The details of this case study can be found in [
adaption dynamics average degree 1 · ∑︀∈ deg()
density (− 1) transitivity eccentricity (0) variance of betweeness centrality () adaption directedness dad () width()/depth() rate of exploitation ()
We study two diferent random graph topologies for the connection graph, namely a
ErdősRényi graph [
We generate the abstract adaption graphs AG 3(EH ), = 1, 2 for the two topologies. The key measures of the two abstracted reachability graphs are given in Table 1. One can observe, for example, that the Erdős-Rényi graph is more exploring than Watts-Strogatz graph as it has a higher average degree, a higher width/depth-ratio, and a lower exploitation rate (). One may hypothesize that the reason for this lies in the small world property of the Watts-Strogatz, i.e. we have long-range connections and therefore every node is only some steps away from any other node, which is not the case for an Erdős-Rényi graph. Therefore, the Watts-Strogatz graph is faster in spreading good genes over the entire population.
In this contribution we developed key measures to compare adaption processes, usually adaption processes of variants of the same system. We used the nets-within-nets formalism of Hornets as our formal model as they provide a natural description of what is adapted within the system: the set Π˜ ( )) of net-types occurring in the current marking . Here, the system net describes the general system, while the marking’s set of object net types describe the changing gene-pool. For the analysis we abstract from events in the Hornet that doesn’t efect the gene pool and use network theoretical measures to describe a fingerprint of the adaption process.
Here, we abstracted from events that do not change the gene-pool. Currently, we are relaxing this even further by ignoring events that change the gene-pool only slightly, i.e. we use a distance between gene-pools as an additional parameter. In future work we also like to analyse the adaption dynamics via static properties of the Petri nets, like invariants etc. For most cases it may be suficient to study an under- or an over-approximation of the state space.