Graph grammars for complex behavior

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA GRADO EN INGENIERÍA INFORMÁTICA GRAMÁTICA DE GRAFOS PARA COMPORTAMIENTO COMPLEJO GRAPH GRAMMARS FOR COMPLEX BEHAVIOR Realizado por Pablo Andrés Martínez Tutorizado por Francisco J. Vico Vela Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, JUNIO 2016 Fecha defensa: El Secretario del Tribunal Resumen Actividad de fondo (background activity) es el nombre dado al fen´ omeno biol´ ogico por el que el cerebro de un organismo vivo nunca est´ a en completo reposo. La comunidad neurocient´ ıfica lo relaciona con funciones cognitivas como la memoria y la exploraci´ on de experiencias sensoriales previas. Las redes neuronales artificiales surgieron originalmente como modelo del sistema nervioso. En la inform´ atica, han sido especialmente utilizadas para la aproximaci´ on de funciones y reconocimiento de patrones. No obstante, la din´ amica y topolog´ ıa de los paradigmas t´ ıpicamente utilizados no son adecuados para modelar procesos como la actividad de fondo. Cuando se pretende replicar comportamientos de redes neuronales reales, el modelo m´ as apropiado es el denominado “red neuronal de disparos” (spiking neural network, SNN), cuyos elementos siguen una din´ amica m´ as fiel a las neuronas biol´ ogicas. Nuestro objetivo es desarrollar un algoritmo que genere topolog´ ıas de redes SNN capaces de mantener actividad de fondo. La topolog´ ıa de una SNN es descrita mediante un grafo, por lo que el primer aporte de este trabajo es un formalismo gramatical para la generaci´ on de ´ estos. Dicho formalismo es empleado por un proceso autom´ atico de b´ usqueda para encontrar SNN que mantengan actividad de fondo. La b´ usqueda es realizada por un algoritmo evolutivo, que aplica sucesivas transformaciones a una poblaci´ on de SNN, haci´ endolas gradualmente m´ as aptas para cumplir el objetivo propuesto. Dado que las distintas SNN de la poblaci´ on son independientes entre s´ ı, el tiempo de ejecuci´ on del algoritmo puede ser notablemente menor al paralelizarse. Los resultados de este trabajo se han obtenido en el nodo de la Universidad de M´ alaga de la Red Espa˜ nola de Supercomputaci´ on, utilizando 40 n´ ucleos para dichas ejecuciones. En la pr´ actica, el tiempo de simulaci´ on se reduce un orden de magnitud respecto a un procesador de cuatro n´ ucleos convencional, mejorando sustancialmente la interacci´ on en el proceso de obtenci´ on y estudio de los resultados. Palabras clave: actividad de fondo, gram´ atica, grafo, red neuronal de disparos, algoritmo evolutivo, computaci´ on bioinspirada. Abstract Background activity is the biological phenomenon that prevents the brain of an alive organism from reaching a state of complete inactivity. The neuroscientist community claims that it is related to cognitive functions such as memory and the exploration of previously sensed experiences. Artificial neural networks were originally developed as a nervous system model. In Computer Science, they have been applied in function approximation and pattern recognition problems. However, dynamics of the typically used paradigms are not appropriate for the replication of processes such as background activity. When the goal is to reproduce the behavior of real neural networks, the most adequate model is the Spiking Neural Network (SNN), whose elements closely resemble the biological neurons. Our objective is to develop an algorithm that generates SNN topologies able to maintain background activity. The topology of an SNN is described as a graph, thus, the first contribution of this project is a grammar formalism to generate them. That formalism is applied by an automated search process in order to find SNNs that are able to maintain background activity. This search is done by an evolutionary algorithm, which develops a population of SNNs and applies successive transformations to them, gradually increasing their ability to fulfill the proposed objective. Considering that the different SNNs of the population are independent of each other, the time required to execute the algorithm can be noticeably reduced when using parallel computation. In order to obtain the results discussed in this document, the program was run over 40 cores of the local supercomputing node, which is part of the Spanish Supercomputing Network. The resulting execution time is decreased in an order of magnitude compared to the one that would be required in a quad-core personal computer. This was crucial for the development of the project, as it considerably improved our ability to manage the process of obtaining and studying the results. Keywords: background activity, grammars, graphs, spiking neural network, evolutionary algorithm, bioinspired computation. Contents 1 Introduction 1 1.1 On the interest of background activity . . . . . . . . . . . . . . . . . . . 1 1.2 The objective of this project . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 State of the art in artificial neural networks . . . . . . . . . . . . . . . . . 3 1.4 Evolutionary algorithm as a searching method . . . . . . . . . . . . . . . 5 1.5 Structure of the document . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 A grammatical formalism for graph generation 8 2.1 Brief overview on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Grammar for tree generation . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Grammar for graph generation . . . . . . . . . . . . . . . . . . . . . . . 11 3 A Spiking Neural Network model 16 4 Optimization of SNNs with evolutionary algorithms 21 4.1 Theproposedmodel............................. 23 4.1.1 Set of mutation rules . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.2 Fitnessfunction............................ 29 4.2 Amorerefinedmodel ............................ 31 4.3 Variations of the model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Results 34 5.1 Maintaining background activity . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 A more realistic physiology . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Analysis of the resulting network . . . . . . . . . . . . . . . . . . . . . . 40 6 Conclusions 43 6.1 Furtherresearch ............................... 44 6.2 Othercontributions.............................. 45 6.3 Technical aspects of the project . . . . . . . . . . . . . . . . . . . . . . . 46 7 Conclusiones 47 7.1 Investigaciones futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 vii Contents 7.2 Otrascontribuciones............................. 49 7.3 Aspectos t´ ecnicosdeltrabajo........................ 50 Bibliography 51 A Software used 52 A.1 Linux...................................... 52 A.2 GNUOctave ................................. 52 A.3 Mercurial ................................... 53 B On supercomputers 54 B.1 Running a program on a supercomputing node . . . . . . . . . . . . . . 55 viii Chapter 1 Introduction 1.1 On the interest of background activity In recent years, the phenomenon of background activity has drawn an increasing amount of attention. It is a continuous and spontaneous activity, present in the cerebral cortex even when the organism is sleeping or anesthetized. As explained in a doctoral thesis focused in this phenomenon (Seamari, 2016), its existence was verified during the 1930s when the electroencephalography started to develop. However, at first it was interpreted as ‘neuronal noise’, i.e. activity that does not imply relevant information or that is derived from physiological processes, such as breathing and heart beating. In the last decades, this point of view has been changed, as it was confirmed that this ever-present spontaneous fluctuations were relevant on some computational functions of the brain. Examples of those functions are the exploration of previous sensorial experiences and the ability to create new memories. Neuroscientist are interested in knowing more about this phenomenon: what causes it, which are the conditions needed for it to happen and how it interacts with other brain processes. This study could yield important advancements on the way we understand how the brain works. That, in turn, could help to detect malfunctions on brain activity and be relevant in solving mental health issues or problems related to brain physiology. However, analysis on real specimens is limited. The information that is acquired from an electroencephalography can not tell anything about individual neurons. Other methods require to insert an electrode in the brain through surgery. None of them give decisive information on how neurons interact with each other either. Therefore, much 1 Chapter 2 A grammatical formalism for graph generation Formal grammars are an important tool applied in many aspects of Computer Science. Their main goal is to define a syntax, i.e. how symbols can be combined to create strings that satisfy certain properties. For example, all programming languages have an associated grammar that defines how valid programs must be written. The set of well-formed formulas in any logic are also defined through grammars and, in general, any representation that depends on arranging symbols in a certain format has its own grammar. The whole set of strings that follow a given grammar is known as the language generated by it. Grammars are defined as a tuple (N, T, P, S)where each element corresponds to: •Non-terminal symbols (N): A set of symbols that help in defining the grammar but will never appear in a string of the generated language. •Terminal symbols (T): The set of all symbols that can appear in the strings of the generated language. •Derivation rules (P): The set of rules that determine how to generate the language. This rules are defined as A→B, where Aand Bare strings made up from non-terminal and terminal symbols. It means that if Ais found inside a string then Acan be removed, placing Binstead. •Axiom (S): A special non-terminal symbol. 8 A grammatical formalism for graph generation If a sequence of derivation rules can transform the axiom into a string of terminal symbols, then the obtained string is an element of the language generated by the grammar. Defining a grammar is one of the different options to formalize a language of strings. Others, such as explicitly defining the set or designing language recognition automatas have their own advantages. In the case of grammars, their main benefit is that the strings in the language are defined recursively, through the repetitive application of the same derivation rules. That characteristic is useful when the strings are going to be given a specific meaning (i.e. a semantic is defined over the syntax). Then, the algorithm that decodes these strings to obtain the object represented by them (e.g. the program object out of the source code) is easily designed. It is only needed to define the changes that each of the derivation rules apply to the represented object. We will use this formalism to define a language which strings are then interpreted as a representation of a graph. These strings will be used as the genomes for the evolutionary algorithm already mentioned in the introduction chapter. Thus, we must be sure that all strings follow a specific format. Then, an automated process is needed to obtain the graph represented by each one of them, which is designed taking advantage of the grammar formalism. 2.1 Brief overview on graphs A graph defines how a set of elements, known as vertices, are connected to each other. Those connections are known as edges. Therefore, a graph Gis a set of vertices V and edges E=V×V, represented as G= (V, E). If the set of edges verifies that ∀(u, v)∈E⇒(v, u)∈E, then it is said that the corresponding graph is undirected. On the other hand, if the property is not verified, the associated directed graph (usually referred to as digraph) can define the topology of a system where the connection between its nodes work just in one direction. An interesting subset of graphs are tree graphs. Those are acyclic undirected graphs, meaning that there is only one path to traverse it from a vertex to another. In computer engineering, trees are widely applied given their desirable characteristics to describe hierarchies. This hierarchy is defined by choosing a vertex, which will be the only element in the highest hierarchy level, known as the root vertex. Then, the rest of the 9 A grammatical formalism for graph generation vertices are ordered depending on the length of the path from each one of them to the root. 2.2 Grammar for tree generation Given trees are a simpler version of graphs, there are already many efficient ways to represent and generate them. We will introduce one of them, as it is the formalism we started with and extended in order to be able to generate any graph. Any tree can be expressed as a sequence of balanced brackets. The language of those strings can be generated by the following grammar: N={A, T} T={[,]} P={A→[T] T→TT T→[T] T→[ ]} S=A (2.1) The result of any sequence of derivation rules yields a balanced bracket string: A→[T]→[TT]→2[[T][T]] →2[[[ ]][TT]→2[[[ ]][[ ][ ]]] (2.2) A tree is built from a string of balanced brackets by creating a vertex for each pair of brackets. The process of obtaining it is illustrated in Figure 2.1 and defined case by case following the derivation rules: •Given A→[T], all strings will be enclosed between a pair of brackets. This rule creates the root vertex and shows it is connected to a group of subtrees. •T→TT indicates that another subtree is created. The root of both subtrees is connected to the same vertex of a higher hierarchy (its parent). 10 A grammatical formalism for graph generation •T→[T]creates a root vertex for the subtree. That vertex will be connected to the corresponding subtrees generated by the bracketed non-terminal symbol. •T→[ ] creates another vertex. This vertex will not be connected to any other subtree (it is a leaf). FIGURE 2.1: Building a tree from a balanced bracket string 2.3 Grammar for graph generation As it was already explained, trees are acyclic graphs, meaning that there is only one path to traverse it from one vertex to another. On the other hand, generic graphs can have an arbitrary amount of paths between any pair of vertices. Therefore, any graph can be defined by set of trees that overall covers each and every of the paths in it. This is known as graph partitioning into trees and is the core idea of our proposed formalism. To define a graph from a set of trees is necessary that they have some vertex in common. Otherwise, the graph would just be a disconnected set of trees. This means that a labelling system is necessary in order to define which vertices are shared by different trees. The following grammar is similar to the one introduced before, but adding the ability to generate those labels and more than one tree in a single sequence: Definition 2.1: Grammar for graph expressions It is defined as G= (N, T, P, S): 11 A grammatical formalism for graph generation N={E, L} T={[,],|} P={E→EE E→[LE] E→ε L→ |L L→ε} S=E (2.3) Where the εsymbol represents the empty string  Definition 2.2: GE Language The language generated by the grammar formalized in Definition 1.1. will be referred to as the Graph Expression Language.  Given the set of strings GE, the next step is to define the functions needed to obtain the graph represented by it. This functions are defined recursively, covering all cases of the grammar derivation rules in order to ensure all possible strings are taken into account. Definition 2.3: Labels function n This function associates a natural number to each sequence of vertical bars, n:{|}∗→ N n(s) = (n(s0)+1 if s =|s0 0if s =ε(2.4)  12 A grammatical formalism for graph generation Definition 2.4: Root labels function l The function l:GE →2Nreturns the set of root vertex of the different trees in the given expression w∈GE l(w) =      l(v)∪l(u)if w =uv {n(s)}if w = [sv] ∅if w =ε (2.5) Where u, v ∈GE, s ∈ {|}∗  An example of the application of this function should help in understanding it: l([ |[|| ]][ ||| [|||| [|| ]]]) = l([ |[|| ]]) ∪l([ ||| [|||| [|| ]]]) = {1} ∪ {3}={1,3}(2.6) Definition 2.5: Graph function g Given the universal set of digraphs U, we define the function g:GE →Uthat associates each w∈GE with its corresponding graph. g(w) =      g(v)∪g(u)if w =vu g(v)∪({n(s)} ∪ l(v),{(n(s), m)|m∈l(v)})if w = [sv] (∅,∅)if w =ε (2.7) Where u, v ∈GE, s ∈ {|}∗and the union operation applied is the union defined over graphs: (V, E)∪(V0, E0) = (V∪V0, E ∪E0)  Then, again an example is convenient to show how the graph is built. The graph generated is illustrated in Figure 2.2: 13 A grammatical formalism for graph generation g([ |[|| ][ ||| ]][ |||| [||| [|| ]]]) = g([ |[|| ][ ||| ]]) ∪g([ |||| [||| [|| ]]]) = =g([ || ][ ||| ]) ∪({1,2,3},{(1,2),(1,3)})∪g([ ||| [|| ]]) ∪({3,4},{(4,3)}) = =g([ || ]) ∪g([ ||| ]) ∪({1,2,3,4},{(1,2),(1,3),(4,3)})∪({2,3},{(3,2)}) = = ({2},∅})∪({3},∅})∪({1,2,3,4},{(1,2),(1,3),(4,3),(3,2)}) = = ({1,2,3,4},{(1,2),(1,3),(4,3),(3,2)}) (2.8) FIGURE 2.2: Graph represented by the string [|[|| ][ ||| ]][ |||| [||| [|| ]]]. It must be noted that building a digraph from a set of trees has an additional advantage. As trees define certain hierarchy between its vertices, it can be (and is) applied as the criteria to decide the direction of the edges. As shown through the previous example (Figure 2.2), the direction of the edge goes from the vertex closer to the root to the one further from it. The first property that should be studied is whether or not this formalism can represent any digraph as a string. As the following proposition shows, this holds for our graph formalism: Proposition 2.1: Every digraph has a string in GE that represents it Given a digraph G= (VG, EG), a string w∈GE exists such that g(w) = G. To prove this, we define the function s:U→GE: s(G) =      ε if G = (∅,∅) [|n]·s((VG− {n},∅)) if n ∈VGand EG=∅ [|n[|m]] ·s((VG, EG− {(n, m)})) if (n, m)∈EG (2.9)  The previous proof is quite trivial, as any edge can be independently expressed in a bracketed section (i.e. a substring enclosed between an opening bracket and a closing 14 A grammatical formalism for graph generation bracket). However, it should be noticed that this formalism allows different string representations of the same digraph. For example, the digraph illustrated in Figure 2.2, was built from a different string that the one obtained through the application of the function defined in the previous proposition. The same digraph can also be expressed through the string [|[|| ][ ||| [|| ]]][ |||| [||| ]]. All of these representations are equivalent, being the one defined in Proposition 2.1 very similar to the typical mathematical representation of a graph (i.e. just a set of edges over a set of vertex). However, the other two strings that have been associated with the graph illustrated in Figure 2.2 are more interesting. The difference is that the connectivity of the graph is dependent on the structure of the string. This characteristic is the fundamental advantage of this formalization. All bracketed sections create a local topology, based on that of a tree-graph. In this way, the distribution of the brackets within the string gives explicit information about the connectivity of the graph. Therefore, there is no need to process the whole string in order to obtain relevant information about the graph represented by it. This property allows us to define a search algorithm that creates new graphs from existing ones through changes that either preserve the overall topology of the graph or modify it in a smart way. 15 Chapter 3 A Spiking Neural Network model As it was already explained in the introduction of this document, we applied a different neural network model than the one classically applied in Computer Science. This model, known as Spiking Neural Network (SNN) is focused on simulating, with a higher level of detail, the process of every single neuron being stimulated during certain amount of time, until the point it fires its own output to the network. The most relevant characteristic is that the stimuli that a neuron receives and sends are always the result of individual neurons firing a single spike. Each neuron stores the information of its own membrane potential (i.e. the state of excitation that it has at the moment). The dynamics of this model are intrinsically time dependent, as a neuron will not fire if it receives a single stimulation, but rather increase its membrane potential with every received spike. Although biological neural network develop their activity over time in an asynchronous fashion, we chose to simplify our approach and consider time to be a discrete variable. Therefore, all membrane potentials are updated synchronously every unit of time. This unit is what we call a time step of the simulation. In order to explain the dynamics of our model, some key constants affecting the membrane potential must be defined: •Threshold potential (θ): The membrane potential which, once reached, causes the neuron to quickly increase its potential (through a process called depolarization in biological neurons), resulting in the emission of an energy pulse into the network (the spike). The value used in our model is −30mV , as it is a typical one in biological neurons. 16 A Spiking Neural Network model •Spiking potential (p): The membrane potential that the neuron reaches when firing a spike. A typical biological value is 10mV and is the one applied in our model. •Hyperpolarization potential (h): Once a spike has been fired, the neuron quickly changes its potential again, now acquiring the lowest value of it. This value is set at −70mV in our model, again inspired in the potential of biological neurons. •Resting potential (r): If a neuron is not being stimulated, its membrane potential tends to stabilize at this potential value. A typical biological value is −50mV and is the one applied in our model. •Decay rate (d): If the neuron is not receiving any stimuli, its potential gradually changes until reaching the resting potential value. This change happens either when the membrane potential is higher than the resting value (decreasing it) or when it is lower (increasing it). The rate of this change is defined in our model for every time step as the approximation to the resting value by a 10% of the difference between the current membrane potential and the resting potential. •Spike Strength (δ): This value determines how much the membrane potential of a neuron is increased when receiving a single spike. In biological neurons, this value is dependent to physiological variables, and neurons do not linearly increase their potential with every spike. Our model simplifies this aspect of the neuron dynamic and gives a fixed value to the parameter. The simulation of the activity in the network is done by applying the dynamic of each neuron at every time step. Figure 3.1 shows the curve described by the membrane potential when a neuron fires. In this project, the dynamic follows an Integrate & Fire model. This model is applied for every neuron at each time step. To explain it, we will consider a binary matrix Wthat describes the topology of any given SNN. Its elements are represented by W(i, j)and determine whether or not there is a connection from the i-th neuron to the j-th neuron. Also, the membrane potential of each i-th neuron is given by a variable, x(i, t), that indicates its value at the t-th time step. The dynamic is described in two stages: 17 Optimization of SNNs with evolutionary algorithms done, in order to justify each of the characteristics they show, explaining why they are needed. In the proposed model, the evolutionary algorithm tries to develop a SNN from a starting set of unconnected neurons. It searches for a topology to connect them in order to maintain background activity. The population that is given to the algorithm in its initialization is a set of neural networks that already have a certain number (N) of neurons. This parameter is defined for each execution of the algorithm and determines the approximate size of the network that will be generated. The genome of each of the individuals of the initial population is: [ ][ |][ || ]. . . [|N−1](4.1) The next step is to define the set of mutation rules. Those change the genome of the population of the last iteration to yield new genomes. Therefore, they are the way the evolutionary algorithm takes advantage of the genome representation, exploiting its characteristics to make local changes on the topology of the SNN. Given that the main property of the developed genome expression is that the graph is built up from the union of tree-like structures, the mutation rules must then focus on managing this structures. 4.1.1 Set of mutation rules To explain the mutation rules designed, we need to formalize some concepts that will help us manage the information contained in the genome. We will be using the mathematical concept of vector, defining some functions over it: Definition 4.1: Relevant operations over vectors •Given any vector x, we define ||x|| as the number of elements in it. •Given any vector x, the i-th element of the vector is defined as x(i). •Given any two vectors x, y we define their concatenation as the binary operation: x∗y=hx(1), x(2), . . . , x(||x||), y(1), y(2), . . . , y(||y||)i(4.2) 24 Optimization of SNNs with evolutionary algorithms  Definition 4.2: The structure vector, S Given a certain genome w∈GE, we define a vector which elements are in N∪{0,−1}. It comprises the distribution of brackets throughout the genome, pairing together the balanced brackets by indicating the distance between the opening and closing one. We define it through a recursive function that parses the whole genome: S(w) =      S(u)∗S(v)if w =uv h2 + ||S(v)||,0i ∗ S(v)∗ h−1iif w = [sv] ∅if w =ε (4.3) Where u, v ∈GE, s ∈ {|}∗and the operator (∗) is the previously defined concatenation of vectors.  Definition 4.3: The labels vector, L Given a certain genome w∈GE, we define a vector which elements are in N∪{0,−1}. It comprises the information about the different labels in the genome: L(w) =      L(u)∗L(v)if w =uv h−1, n(s)i ∗ L(v)∗ h−1iif w = [sv] ∅if w =ε (4.4) Where u, v ∈GE, s ∈ {|}∗and the operator (∗) is the previously defined concatenation of vectors. The function nis the one introduced in Definition 2.3.  Given a pair of these vectors representing the same genome, recovering it is trivial: The non zero elements of the structure vector indicate the appearance of a bracket, while non negative elements of the labels vector indicate how many vertical bars appear in that certain position. We will refer to this function as r(S(w), L(w)) = w. Then, we define the set of mutation rules by obtaining these vectors from the original genome and changing them as the mutation requires. 25 Optimization of SNNs with evolutionary algorithms Definition 4.4: Leaf duplication Given any genome w∈GE we first obtain both vectors S(w)and L(w). We will refer to them as sand lrespectively. Then, the mutation rule generates two new vectors s0and l0. First, a random index 1≤i≤ ||s|| is selected, such that s(i)=2. This index is used to obtain the section of the vectors to be duplicated: sd=hs(i), s(i+ 1), s(i+ 2)i ld=hl(i), l(i+ 1), l(i+ 2)i Then, a second random index 1≤j≤ ||s|| is selected, such that s(j)>0. The section is placed where the index determines. s0=hs(1), . . . , s(j), s(j+ 1)i ∗ sd∗ hs(j+ 2), s(j+ 3), . . . , s(||s||)i l0=hl(1), . . . , l(j), l(j+ 1)i ∗ ld∗ hl(j+ 2), l(j+ 3), . . . , l(||l||)i The genome retrieved is the one resulting from r(s0, l0).  Definition 4.5: Tree duplication Given any genome w∈GE we first obtain both vectors S(w)and L(w). We will refer to them as sand lrespectively. Then, the mutation rule generates two new vectors s0and l0. First, a random index 1≤i≤ ||s|| is selected, such that s(i)>2. This index is used to obtain the section of the vectors to be duplicated: sd=hs(i+ 2), s(i+ 3), . . . , s(i+s(i)−1)i ld=hl(i+ 2), l(i+ 3), . . . , l(i+s(i)−1)i Then, a second random index 1≤j≤ ||s|| is selected, such that s(j)>0. The section is placed where the index determines. However, its labels must be changed first: 26 Optimization of SNNs with evolutionary algorithms l0 d(x) = (ld(x)if ld(x)=0 |ld(x) + l(j+ 1) −l(i+ 1)|if ld(x)6= 0 (4.5) It is important to notice that when the label is updated, the absolute value of it is taken. This is due to negative labels can not be represented by a genome, so when a label reaches zero vertical bars, the rule starts adding them instead of subtracting. Finally, both sections are placed at their respective position. s0=hs(1), . . . , s(j), s(j+ 1)i ∗ sd∗ hs(j+ 2), s(j+ 3), . . . , s(||s||)i l0=hl(1), . . . , l(j), l(j+ 1)i ∗ l0 d∗ hl(j+ 2), l(j+ 3), . . . , l(||l||)i The genome retrieved is the one resulting from r(s0, l0).  Definition 4.6: Tree removal Given any genome w∈GE we first obtain both vectors S(w)and L(w). We will refer to them as sand lrespectively. Then, the mutation rule generates two new vectors s0and l0. A random index 1≤i≤ ||s|| is selected, such that s(i)>0. This index is used to decide what section of the vectors will be removed: s0=hs(1), . . . , s(i−2), s(i−1), s(i+s(i) + 1), s(i+s(i) + 2), . . . , s(||s||)i l0=hl(1), . . . , l(i−2), l(i−1), l(i+s(i) + 1), l(i+s(i) + 2), . . . , l(||l||)i The genome retrieved is the one resulting from r(s0, l0).  These mutation rules do not change the network by adding or deleting individual connections, but rather managing already existing structures: •Leaf duplication: This rule extends already existing structures in the genome, creating an additional connection. It is needed for the algorithm to create the 27 Optimization of SNNs with evolutionary algorithms structures that the other two rules will manage. Therefore, it is of most importance at the first iterations of the algorithm. •Tree duplication: This rule copies an already existing structure and repeats it in another place of the network. The duplicated structure connects a different group of neurons thanks to the change applied to the labels. It is important to notice that this mutation rule can create new neurons that were not included in the initial individual. This mutation rule is the most important of the set, as is the one that makes possible that a beneficial structure (i.e. one that helped some neurons to reciprocally activate each other) is repeated in other places of the network, increasing the global ability of the SNN to maintain background activity. •Tree removal: This rule takes out a whole structure from the genome. It is relevant in the last iterations of the algorithm, as it can prune unnecessary structures. This management of groups of edges is made possible by the representation of the genome, as it is in it where the explicit structures are shown through the nested brackets hierarchy. These mutation rules would be difficult and inefficient to apply using the typical mathematical representation of graphs, due to the need to look for edges that share vertex in common. Besides, it should be noticed that the criteria to make the random choice of the substring to be duplicated in leaf duplication and tree duplication are mutually excluding. This enables us to define both in a single mutation rule: Definition 4.7: General duplication Given any genome w∈GE we first obtain both vectors S(w)and L(w). We will refer to them as sand lrespectively. Then, a random index 1≤i≤ ||s|| is selected, such that s(i)≥2. This index is used to obtain the section of the vectors to be duplicated. If the index selected verifies s(i)=2, then the process described in Definition 4.4 is applied, resulting on a leaf duplication mutation. Otherwise, s(i)>2, and the process described in Definition 4.5 is applied, resulting on a tree duplication mutation.  The evolutionary algorithm randomly chooses which mutation to apply, either general duplication or tree removal. However, if both rules had the same probability to happen, the tree removal rule would end up destroying any structure created by the general duplication rule. In order to prevent it, we assign a relative frequency of them happening. 28 Optimization of SNNs with evolutionary algorithms After testing different values, it was finally set to be twice probable to duplicate than to remove. This value is enough for the general duplication rule to create structures that will persist in time. We must also analyze if the desirable properties for the set of mutation rules are met. These are defined at the beginning of this chapter and ask the mutation rules to be neither lethal nor disruptive. We first discuss that the defined mutation rules are not be lethal. This is trivially verified as all rules duplicate or remove sections enclosed between brackets, maintaining the brackets balanced. The duplication rules always place the copied section right after a label, where bracketed sections can appear in any valid genome. Therefore, the resulting genome is always an element of GE. Then, we explain why these mutation rules are not highly disruptive. The duplication rules add more connections to the graph. This will only affect on increasing the overall ability of the neurons to activate each other. On one hand, the leaf duplication rule just creates a single connection, having a low impact on the dynamic of the network. On the other hand, the tree duplication rule copies a structure that is already present in the network. Thus, its complexity and contribution to the fitness of the network is relative to what the SNN already shows, not making any sudden change to the dynamic it already had. The tree removal rule must also be considered. Its application is actually potentially disruptive, as whole structures could disappear. However, taking into account that it is applied half the amount of times that the general duplication rule, it is intuitive to understand that at the moment this rule removes part of a structure, it would have already been duplicated elsewhere in the genome. Therefore, this rule will rarely take out a structure which disappearance causes the dynamic of the network to dramatically change, as there should be plenty of structures throughout the network. All of these structures should have similar relevance, as they are copies of each other. Then, rather than being an obstacle, this rule helps in the development of the network, as it changes the structures, giving an increased diversity of them. 4.1.2 Fitness function Having defined and analyzed the mutation rules, now it is necessary to give the fitness function. By it, we give the algorithm the specification of the objective it must try to satisfy. This objective is to develop SNNs that are able to maintain background activity. 29 Optimization of SNNs with evolutionary algorithms Therefore, the fitness function will simulate the behavior of the neural networks and give a score to each one of them. The score will be greater for the SNNs that maintain activity for a longer period of time. The fitness function is applied to every individual of the population, at each iteration of the algorithm. First, the topology of the SNN of each individual must be obtained through the decodification of its genome. Then, the neural network is simulated, following the model described in the chapter of this document titled ‘A Spiking Neural Network model’. A starting stimulation is needed in order to make any activity happen. This is due to the neurons being stable at their resting potential if no spikes reach them. This starting stimulation is done at the beginning of the simulation by forcing a percentage of the neurons to be at their spiking potential (i.e. firing just when the simulation starts). The percentage that proved to be most adequate is 30%, being a balance between activating enough neurons to excite others while not leaving too many neurons hyperpolarized at the next time step. The spikes of the activated neurons at the start of the simulation should increase the membrane potential of other neurons. The potential of these neurons may get to the point of making them fire in the next time step of the simulation. If the topology of the SNN allows it, then the starting stimulation could be enough to provoke the activation of an amount of neurons that will in turn activate others. Through this time step simulation, neurons will follow a cycle of firing a spike, resetting their potential, receiving spikes from other neurons and integrating them to rise their membrane potential to the point of firing again. The chain reaction will last for a period of time steps. This process of neurons being able to activate others is not helped by any kind of external stimulation, excluding the activation of neurons at the start of the simulation. Thus, all the stimuli that the neurons receive comes from another neuron which was active one time step ago. This is interpreted as background activity, in the sense it is maintained by its own, not requiring any external input. Therefore, the score given to the SNN is the amount of time-steps that at least had an active neuron. As the activity could be maintained indefinitely, a maximum amount of time steps, T is defined. When this value is reached, the simulation stops. This simulations trace is stored in a binary matrix P, which each element P(t, i)shows if the i-th neuron was firing at the t-th time step. The score (α) given to the SNN is in the range of 0 to 1, and is calculated as the proportion of time steps at which at least a neuron fired: α=||{t| ∃i, P(t, i)=1}|| T(4.6) 30 Optimization of SNNs with evolutionary algorithms This method of calculating the fitness score puts each SNN of the population to test. It simulates them and measures their ability to maintain background activity, assigning each of them an individual score. That score is higher the better they manage to fulfill the objective. Thus, it happens to be a valid fitness function, as the activity of two similar neural networks (i.e. only distinguished by a few number of mutations) will slightly differ, and the one that lasted longer will be assigned a higher score. This whole model is appropriate enough to satisfy the objective we had established. The neural networks obtained by applying it are able to maintain background activity, as it will be shown and discussed in the chapter dedicated to the results. However, we decided to consider an additional criteria in the fitness function evaluation. This criteria is explained in the following section. 4.2 A more refined model The problem that the previous model had is understood when studying the activity of the neural networks that it generated. This study is shown in the chapter of this document dedicated to the analysis of the results. What was found is that their neurons fired at a rate too quick compared to a biological neuron. As we wanted the resulting SNNs to be as close to their biological counterpart as possible, we decided to consider an additional criteria in the fitness function evaluation. This criteria aims to favor those neural networks that not only maintained background activity, but also presented a slower activation rate of their neurons. To define this criteria, a new parameter was added, namely G. This parameter determines the desired amount of time steps between any pair of consecutive spikes of any given neuron. Analyzing the simulation trace, P, we can obtain the vector of gaps between spikes for each neuron: gi(k) = tk−1−tk−2, k ∈[1, ..., n](4.7) where tn−1< tn, P(tn−1, i) = 1, P(tn, i) = 1,∀t0∈(tn−1, tn) : P(t0, i) = 0 The arithmetical average of the vector is calculated and represented as gi. Using this value, another score is obtained, which also ranges from 0 to 1. The way to calculate it is to compare the average gap of each neuron with the Gparameter. The closer the 31 Optimization of SNNs with evolutionary algorithms value is to that parameter, the better score the neuron receives. The comparison is done by applying the following function: χ(i) =      gi/G if gi≤G 2−gi/G if gi> G (4.8) Then, the arithmetical average of these values is computed (β), obtaining a representative score for the whole neural network. Finally, the fitness score (γ) is given by the combination of this average gap score (β) and the activity score (α) calculated by the original fitness function: γ=(α if α < 1 α+β if α ≥1(4.9) This implies that the criteria just explained is only applied when the maximum activity score is reached (i.e. the network maintains background activity throughout the simulation). Therefore, the evolutionary algorithm first searches for SNNs that are able to present background activity and, once obtained, optimizes those neural networks to make their activity the most similar to a biological system as possible. Calculating the sum of both scores is the simplest way to combine their information and allows that the overall fitness score is easily interpreted: if it is below 1, the network has not yet developed a satisfying background activity; if it is in the range from 1 to 2, the network is being refined using the criteria defined by G. 4.3 Variations of the model The model just explained was the final product of a process of designing different approaches, testing them and analyzing their properties. These took a considerable portion of the time dedicated to the project, and each one of them helped to get a better insight on the objective that we set as our goal. Thus, the most important ones are worth to be briefly discussed: •Developing increasingly larger SNN: The original approach was to create an initial population of networks that were comprised by a single neuron. Specifically designed mutation rules would then add additional genome sections and increase 32 Optimization of SNNs with evolutionary algorithms the length of the labels, gradually increasing the amount of neurons in the network. This approach proved to be unworkable, as an unreasonable amount of iterations were needed in order to create SNNs with enough neurons to be able to maintain background activity. •Weightening the connections: Following the principle of the classical model of neural networks, we decided to test what would happen if we specified in the genome the weight of the connection between each pair of neurons. The resulting SNNs tended to create networks where the connections were too heterogeneous: the activity was maintained by a small proportion of the network, that was strongly connected. This behavior is opposed to the way biological neurons interact with each other, thus the approach was discarded. •Considering a slightly different SNN model: Based on a letter published in Nature (Debanne, D. Bialowas, A. & Rama, S., 2012, see bibliography), we considered the option of designing a different SNN model. In it, the update of the membrane potentials of neurons would not only be affected by the spikes that reached them, but also depending on the value of the membrane potentials of the neurons connected to them. Although this approach would have helped the gradual development of the fitness score during the algorithm execution, we finally decided that such a complex interaction between neurons was not in concordance with the level of detail present in our SNN model. •Applying a learning algorithm after the evolution: We considered the option of applying a certain learning algorithm used in SNN models, the STDP (Spiketiming dependent plasticity, see bibliography) after the evolution phase had finished. That would have helped giving a final refinement of the generated networks. We finally decided against using it, as we considered more important to focus on obtaining the best result using the tools initially proposed. 33 Results To prove that our algorithm was able to find networks that perform better than randomly generated SNNs, the new implementation of the program was executed. Figure 5.5, shows the increase of the fitness score of the best SNN of each generation. Only the last iterations are shown, from the point the population already presented background activity. FIGURE 5.5: Average gap between spikes of the best individual in each generation. Although the goal of 20 time steps between spikes was not reached, the average gap obtained was larger than the one present in randomly generated SNNs (it was almost doubled). This proves that our algorithm is a well guided search that can be oriented to fulfill a goal related to the activity of a SNN. 5.3 Analysis of the resulting network We now focus on how neurons in the evolved SNNs interact with each other. In this section we study the relation between neurons that fired in a certain instant and those that were active during the previous time steps. First, we consider all pairs of networks and check how many times one fired either a single or two time steps before the other did. This number is represented in Figure 5.6 (left). As this amount increases, the pixel relating both neurons gets darker. 40 Results When a vertical or horizontal white line appears in the figure, it is showing that the corresponding neuron did not fire at all during the whole simulation. This is a consequence of the way the labels in the genome (i.e. sequences of vertical bars) are changed by the tree duplication mutation rule. The genome of the initial individuals had 40 neurons, and the tree duplication rule increased this amount to a value of 88. But it is not necessary that all labels in the range between these values appear in the genome. The inactive neurons do not have any connection with other neurons, so they can not receive stimuli and be excited. (The diagonal white line indicates that a neuron never activates twice in a lapse of three consecutive time steps.) FIGURE 5.6: Frequency of a neuron firing after another has fired (left), where white means no previous activation, and black represents a maximum value of 17. Neurons that are significantly relevant on the activation of others (right) are marked with black dots. If the white lines are ignored, the image is essentially gray. This means there is no clear pattern of activation between groups of neurons as there are a few amount of neurons that consistently fire after other one did (i.e. there are not that many dark pixels). As we already discussed, if no patterns are repeated, the neural network must be maintaining a non cyclic activity. However, some pair of neurons seems to actually be related, as some sporadic black pixels appear. Figure 5.6 (right) gives a clearer insight of this correspondence. In this second graphic, a dot appears if the neuron on the horizontal axis noticeably tends to fire before the neuron on the vertical axis does. Thus, it is interpreted that the activation of the first neuron is specially relevant in triggering the activation of the latter. This graph shows that there are some neurons which are more influential than others, as the 25th neuron triggers the consistent activation of 11 neurons, while others do not seem to have any special relevance. We thus detected some kind of hierarchy between 41 Results neurons. Considering genomes are defined by a tree-like inspired representation, it seems to be natural that the networks evolved tend to maintain tree structures. This would justify why some neurons are more relevant than others, depending on them being the root of a tree structure, influencing all neurons that form it. Lastly, we consider the correlation between neurons, determined by their tendency to both activate after certain similar patterns. Figure 5.7 shows, in darker gray, when two neurons share a similar set of trigger neurons. In this case, a great amount of them seem to be clearly related to each other. On the other hand, when the trigger neurons do not match, the correlation is negative and it is represented in lighter gray. FIGURE 5.7: Correlation of neurons activated by similar groups of neurons (triggers). Darker pixels indicate a higher positive correlation. Light gray indicates negative correlation. The fact that some pair of neurons share a strong bound to be activated by the same neurons strengthens the previous assumption. The activity of the network seems to reflect the tendency of the topology to be structured in trees. In this case, groups of highly correlated neurons would match with the different descendants of a particular root neuron, which is a relevant trigger of their activation. 42 Chapter 6 Conclusions Neuroscientists claim that all the cognitive abilities are given by the way the cells of nervous systems interact with each other. The brain is a versatile machine that is built up by a huge amount of neurons. They work locally, receiving inputs of their neighbour cells and firing output according to their dynamics. However, the signal that a neuron generates is propagated throughout the network, affecting distant cells. The cooperation of all of them elicits a behavior that is not inherent to the neuron itself. When systems are formed by elements that show this capability of fulfilling more complex tasks when cooperating in large groups, it is said that they exhibit emergent properties. The SNNs that we have obtained are able to reproduce certain complex behavior: maintaining a signal over time, which is actually an emergent property. The fact that these networks are obtained through an evolutionary process, that achieves better performance than random search, is quite relevant. It implies that a well informed selection was applied (through the fitness function evaluation), being able to recognize that some topologies were more beneficial than others. Thus, this emergent property is not only given by the elements of the system (which in our case were considerably simplified), but also by the actual way of them cooperating. This aspect is what neuroscientists are now trying to understand: how neurons interact with each other to execute complex tasks. Creating programs like the one developed in this project helps to achieve this goal, as the generated neural networks can be freely examined, in contrast to the limited experimentation that can be done on real specimens. This project describes an algorithm that generates simplified neural networks capable of maintaining background activity. Thus, it gives the opportunity to conduct further research on what type of topologies favor it. Besides, the fitness function can be redefined to guide the search of a different activity property, as it was shown by adding the 43 Conclusions criteria of favoring larger gaps between spikes. Thus, the program should also be valued as an infrastructure to search neural network topologies that show any observable behavior specified in the fitness function. The mutation rules and fitness function designed were key to the fulfilment of our objective. But the contribution of the genome expression should not be overlooked either. It is by its means that the mutation rules can operate in a way that favors the appearance of complex structures. If the genome had not explicitly informed about the overall structure of the network, the mutation rules would have been left to operate with unrelated groups of connections. As it has already been discussed in the previous chapter, one interesting characteristic of the SNNs developed by our algorithm is the fact that the activity maintained in them is not cyclic. Designing a network that has a cyclic activity is trivial: connecting groups of neurons in a ring structure is enough. Maintaining a signal without it entering a loop is much more demanding. The mathematical study of this kind of behavior is known as Chaos Theory, and has a wide research effort behind it. We have not checked that this behavior is in fact chaotic, but it seems like so given no repetitive pattern can be found. What we can claim for sure is that the behavior we obtained is given by the physiology of the membrane potential. Without it, the neurons in the networks would always respond the same way for a given input. That would imply the appearance of well defined patterns when cooperating in groups, which in turn would lead to a cyclic behavior. 6.1 Further research The objective of the project was successfully met, but it leaves open an interesting field of study about the topologies that have been obtained. What now follows is to analyze what structures are built by the algorithm, and understand why they are capable of displaying complex emergent behaviors such as a seemingly chaotic activity. Background activity maintains brain neurons in a constant fluctuation of their membrane potential. Therefore, when an input is given to the network, it propagates through it while combining with its background signal. The resulting output might be affected in a relevant way, thus being dependent to these fluctuations. We could then consider an agent able to interact with its environment (e.g. a robot) controlled by one of our SNNs. Its background activity would determine its internal state, affecting the way it reacts to the stimuli received from the environment. If the topology of the SNN could be 44 Conclusions adapted through a learning process for the agent to fulfil tasks, it could yield interesting properties applicable on the Artificial Intelligence field. 6.2 Other contributions Apart from being a formal piece of research, this project was also an academic experience. Its contribution to my education can be considered in two aspects. On one hand, I have applied the knowledge that I, as a student, have accumulated through my stay in this university. Specifically, the theoretical courses on formal languages (both their syntax and semantics) have been most helpful. In those, we learnt how to formally define the format and meaning given to strings of symbols, focusing in its application to design programming languages. However, this formalization has proven to be equally effective to describe a language of genomes representing graphs, and all the functions related to them. Realising the flexibility of these formalisms was, in itself, an instructive experience. The familiarity I have developed with them will surely be helpful in the future. On the other hand, while working in this project, I have learnt and developed some capabilities that were not taught during any of the degree courses. Those relating to technical resource management have been discussed in the appendices of this document. Gaining experience on using version control software is fundamental for any computer engineer, and having the opportunity to use a supercomputer was very valuable, as it is an important tool on the scientific discipline. I have also broaden my knowledge about models of computing, by working with evolutionary algorithms and an unconventional type of neural networks. Both are interesting fields of study that are receiving an increasing amount of attention. This project was done not only for completing my degree, but also as research supported by a scholarship from our University. The scholarship, referred to as ‘Beca de Iniciaci´ on a la Investigaci´ on’ is granted to students interested in starting their career as researchers. It was the main motivation for orienting this project to be a scientific study, giving me the opportunity to experience for the first time how research is conducted. What I have learnt by developing this project alongside my tutor, Francisco J. Vico, will undoubtedly be relevant in my future. Understanding how to manage time and effort to be efficient, remaining true to the principles of research and being constant until reaching the objective, are some aspects that can not be learnt in any other way. 45 Conclusions 6.3 Technical aspects of the project Considering this project was oriented in a scientific approach, we decided to maintain this focus when writing its document. Thus, we prioritized analyzing the properties of the algorithm developed and the obtained results, rather than focusing on the technical considerations of the work done. In order to maintain a fluent structure throughout the document, we decided not to include technical considerations in its body. This follows the goal of presenting the project as a formal piece of research where the relevant information is the method applied in itself, and not how it was implemented. The most relevant technical aspects of the project are summarized in the two appendices of this document. Besides, no software engineering abstractions were needed to develop the program, as the system designed does not require complex interactions between its modules. It is based on four clearly separated tasks: the genome decodification, the application of mutation rules, the network simulation and the fitness function evaluation. Each one receives the output given by the module that acted before it, iteratively repeating the cycle until the maximum amount of generations are reached. Each one of these modules was scripted in its own file, and a Main script coordinates their iterative execution. 46 Chapter 7 Conclusiones La comunidad neurocient´ ıfica afirma que toda habilidad cognitiva proviene del modo en que las c´ elulas de los sistemas nerviosos interact´ uan entre s´ ı. El cerebro es una m´ aquina vers´ atil formada por una enorme cantidad de neuronas. ´ Estas trabajan localmente, recibiendo est´ ımulos provenientes de c´ elulas vecinas y lanzando se˜ nales seg´ un la din´ amica interna que tengan. No obstante, la se˜ nal que una neurona produce es propagada por toda la red, afectando a c´ elulas distantes. La cooperaci´ on de todas ellas permite la aparici´ on de comportamientos que no son inherentes a la propia neurona. Cuando un sistema est´ a formado por elementos que muestran la capacidad de llevar a cabo tareas m´ as complejas al cooperar en grandes grupos, se dice que ´ este exhibe propiedades emergentes. Las SNN que hemos obtenido son capaces de reproducir cierto comportamiento complejo: mantener una se˜ nal a lo largo del tiempo, lo que es considerado una propiedad emergente. El hecho de que estas redes se hayan obtenido por un proceso evolutivo, que logra mejores resultados que una b´ usqueda aleatoria, es considerablemente relevante. Implica que un criterio de selecci´ on adecuado fue aplicado (mediante la evaluaci´ on de la funci´ on objetivo, fitness function), siendo capaz de diferenciar que ciertas topolog´ ıas eran m´ as beneficiosas que otras. Por ello, esta propiedad emergente no viene dada s´ olo por los elementos del sistema (que en nuestro caso fueron considerablemente simplificados), sino que tambi´ en es influida por el modo en que ´ estos cooperan entre s´ ı. Este aspecto es lo que los neurocient´ ıficos se est´ an centrando en entender actualmente: c´ omo interact´ uan las neuronas entre s´ ı para realizar tareas complejas. Crear programas como el desarrollado a lo largo de este proyecto ayuda a satisfacer este objetivo, ya que las redes neuronales generadas pueden ser examinadas libremente, a diferencia de la limitada experimentaci´ on disponible sobre espec´ ımenes reales. 47 Conclusiones Este trabajo describe un algoritmo que genera redes neuronales simplificadas, pero capaces de mantener actividad de fondo. Por tanto, da la posibilidad de continuar con el estudio de las topolog´ ıas que han favorecido esto. Aparte, la funci´ on objetivo (fitness function) puede ser redefinida para guiar la b´ usqueda de otra propiedad de la actividad, tal y como fue demostrado al a˜ nadir el criterio para favorecer mayores distancias entre disparos. Por tanto, el programa debe ser tambi´ en valorado como una infraestructura para la b´ usqueda de topolog´ ıas de redes neuronales que presenten un comportamiento observable especificado en la funci´ on objetivo. El dise˜ no de las reglas de mutaci´ on y funci´ on objetivo (fitness function) ha sido clave para el cumplimiento de nuestro objetivo. Pero la contribuci´ on de la expresi´ on gen´ etica tampoco debe ser subestimada. Es gracias a ella que las reglas de mutaci´ on pueden operar de un modo tal que favorezca la aparici´ on de estructuras complejas. Si el genoma no informase expl´ ıcitamente de la estructura general de la red, las mutaciones no podr´ ıan haber sido aplicadas con el mismo ´ exito. Sin la gu´ ıa de los par´ entesis balanceados, las reglas de mutaci´ on se habr´ ıan limitado a trabajar con grupos de conexiones no relacionados entre s´ ı. Como ya ha sido discutido previamente, una de las caracter´ ısticas interesantes de las SNN desarrolladas por nuestro algoritmo es el hecho de que la actividad mantenida en ellas no es c´ ıclica. Desarrollar una red que presente actividad c´ ıclica es trivial, basta con conectar grupos de neuronas en una estructura de anillo. Mantener una se˜ nal sin entrar en bucle es mucho m´ as dif´ ıcil. La rama de las matem´ aticas dedicada al estudio de este tipo de comportamiento es conocida como Teor´ ıa del Caos, y tiene un amplio esfuerzo investigador dedicado a ella. No hemos comprobado que el comportamiento de las redes generadas sea realmente ca´ otico, pero as´ ı lo parece, dado que no ha sido posible encontrar patrones repetitivos. Lo que podemos asegurar es que, en nuestro caso, este comportamiento viene dado por la fisiolog´ ıa del potencial de membrana. Sin ´ el, las neuronas de la red responder´ ıan siempre del mismo modo cuando recibiesen el mismo est´ ımulo. Esto supondr´ ıa la aparici´ on de patrones bien definidos cuando cooperasen en grupos, que a su vez llevar´ ıa a un comportamiento c´ ıclico. 7.1 Investigaciones futuras El objetivo del proyecto ha sido cumplido satisfactoriamente, pero deja abierto el estudio en profundidad de las topolog´ ıas que han sido obtenidas. Lo que corresponder´ ıa 48 Conclusiones continuar investigando es qu´ e estructuras son desarrolladas por el algoritmo, y entender por qu´ e´ estas son capaces de mostrar comportamientos emergentes complejos tales como una actividad aparentemente ca´ otica. La actividad de fondo mantiene las neuronas en una constante fluctuaci´ on de su potencial de membrana. Por ello, cuando un est´ ımulo es dado a la red, ´ este se propaga por ella, combin´ andose con la se˜ nal de fondo. La salida resultante puede haber sido afectada de un modo relevante, siendo por tanto dependiente de estas fluctuaciones. Podr´ ıamos considerar un agente capaz de interactuar con su entorno (e.g. un robot) controlado por una de nuestras SNN. Su actividad de fondo determinar´ ıa el estado interno, afectando el modo en que ´ este reacciona a los est´ ımulos que recibe de su entorno. Si la topolog´ ıa de la SNN pudiese ser adaptada mediante un proceso de aprendizaje que llevase al agente a cumplir la tarea encomendada, podr´ ıa resultar en propiedades interesantes aplicables en el campo de la Inteligencia Artificial. 7.2 Otras contribuciones Aparte de ser un trabajo de investigaci´ on, este proyecto ha supuesto tambi´ en una experiencia acad´ emica. Su contribuci´ on a mi educaci´ on puede ser considerada en dos aspectos principales. Por un lado, he aplicado el conocimiento que, como estudiante, he acumulado a lo largo de mi estancia en esta universidad. Concretamente, las asignaturas que trataban sobre lenguajes formales (tanto su sint´ axis como sem´ antica) han sido especialmente ´ utiles. En ellas, aprendimos a definir formalmente el formato y significado dado a cadenas de s´ ımbolos, centr´ andonos en su aplicaci´ on para el dise˜ no de lenguajes de programaci´ on. Sin embargo, esta formalizaci´ on ha probado ser igualmente efectiva para describir el lenguaje de genomas que representa grafos, y todas las funciones relacionadas con ´ estos. Descubrir la flexibilidad de estos m´ etodos de formalizaci´ on ha sido, en s´ ı mismo, una experiencia instructiva. La familiaridad que he desarrollado con ellos me ser´ a sin duda de ayuda en el futuro. Por otro lado, mientras trabajaba en este proyecto, he aprendido y desarrollado algunas capacidades que no han sido ense˜ nadas en ninguna de las asignaturas de la carrera. Aquellas relacionadas con cuestiones t´ ecnicas han sido explicadas en los ap´ endices de este documento. Obtener experiencia en el uso de software para control de versiones es fundamental para cualquier ingeniero inform´ atico, y haber tenido la oportunidad de usar un supercomputador es muy valioso, al ser una importante herramienta en la disciplina cient´ ıfica. Adem´ as, he expandido mis conocimientos en modelos de computaci´ on, trabajando con algoritmos evolutivos y un tipo no convencional 49 On supercomputers Then, a similar procedure is done to access the supercomputing node through ssh. Once the authentication of the account is done, it is possible to manage your private directory, execute basic shell commands (i.e. cd,mkdir,vi. . . ) and launch jobs to be executed in the supercomputing node. The computer where the user is logged acts as an interface. In order to execute programs, a script has to be run. The script indicates the software to be used to execute the program (i.e. octave in our case), the location of the program itself and the specification of the resources requested. All files created during the execution are placed in the user’s private directory. The program to be executed must be prepared to be run in parallel. This is quite simple in Octave, as the parallel package offers a function that manages the execution. It asks the system to create the number of process specified, which will be distributed among the available cores. Then it assigns the execution of a given source code to each of them. The source code is the same for all processes, being the input for each one (specified in a cell array) what differs the executions. Thus, in our program, the source code specified to be executed in parallel is the mutation, decodification of the genome, and simulation of each individual. The input for each process is the genome of the different individuals in the population. 56