It is about time to write something on the broader topics I covered in my
diploma thesis “Improving a Hierarchical Evolutionary
Algorithm with Applications in Optimization and Machine Learning”. Even so,
the word *Graph* does not appear in the title, the thesis was mainly about
optimizing graphs, more specifically (spiking) neural networks.

- But what is
*Evolutionary Graph Optimization*actually? - What is it good for?
- What were the challenges we had to face? (part 2)
- Did we come up with something new? (part 2)

Many questions, to which there are even more answers. In case you are able to understand german language, feel free to read through the 150 pages of my thesis (it covers a lot more than just the four questions above).

To keep you motivated, let’s first take a look at the screenshot below,
showing HyperNSGA in action, a graphical software written in
Rust that I created as part of the thesis to *visualize* and
*interact* with the process of evolutionary graph optimization. HyperNSGA
is an abbreviation in the style of HyperNEAT and stands for
“Hyper-cube based neural net optimization using NSGA-II”, the latter which
is again an abbreviation for “Non-Dominated Sorting Genetic Algorithm II”.
In the top half of the screenshot, you see the the individual genomes,
whereas in the bottom half you see the final networks. The genomes itself
are a special kind of graph, so-called *Compositional pattern-producing
networks* or CPPNs. These are smaller networks that we use to produce
larger graphs with hierarchical and repetetive patterns. The pane on the
right shows settings and performance metrics. Most settings can be modified
in real-time, while an optimization is running.

## What is Evolutionary Graph Optimization?

Evolutionary algorithms are a class of randomized algorithms, which are
more or less based upon Darwin’s theory of biological evolution. They use
three concepts: A *population* of solutions, *selection* of solutions
(“Survival of the Fittest”) and *reproduction* of new, “child” solutions.
The genetic algorithm (GA) is one of the best-known variants of an EA. It
uses a binary representation for each solution in the population, called
the “genome”, and genetic operators like crossover and mutation to produce
new genomes from existing genomes.

In evolutionary graph optimization, we make use of an evolutionary
algorithm (EA) to optimize some, or all attributes of a graph. Graphs are
made from nodes and edges, both of which can be attributed or weighted. So
what a graph optimization algorithm has to accomplish, is to modify the
node and edge weights in order to make the graph more “optimal” according
to some function, which we call the *fitness function*. To make things more
complex, the fitness function can be multivariate (i.e. not a single scalar
value), in which case we are talking about Pareto-optimization. More
advanced algorithms not only optimize the weighting of graphs but also
modify their topology. The topology is the structure of the graph, the
information, which nodes are connected to which other nodes via edges.
Optimizing either the weighting *or* the topology of a graph while keeping
the other constant is “easy”, whereas doing both at the same time is a lot
more “complex”. What I tried to accomplish in my thesis is to find or
develop an algorithm that is able to optimize both, topology and weighting
of graphs, at the same time.

## What is it good for?

An algorithm that optimizes the topology of a graph can also be used to
*create* graphs. And indeed, the main application for our evolutionary
graph optimization algorithm was as a *graph generation algorithm*.

In our case, we did research on *spiking neural networks*. Spiking neural
networks try to model and simulate biological neural networks, like the
ones that make up your nervous system (brain, medulla, etc.). In contrast
to artificial neural networks (buzz word “deep learning”), the propagation
of signals between connected neurons in spiking neural networks is not
immediate, it takes time. This timing contains further information, for
instance, the “phase” of a signal, and resembles the biological behavior.
The actual biological behavior is a very complex electro-chemical
physiological interaction and there are mathematical models, like the
Hodgkin-Huxley model, that model the processes inside biological neurons
(the flow of ions in both directions through the cell membrane). Obviously,
this requires a lot of computational power, so that scientists have
invented alternative mathematical models. The one I have chosen was the
model of Izhikevich, which is biologically plausible, very
well described in numerous papers, easy to implement
correctly and most importantly, computational efficient.

Spiking neural networks would be perfect if we would only know how to create them. While crafting small networks by hand is a challenge, for larger networks, this becomes an impossible undertaking. Because of that, artificial neural networks use a regular, often fully-connected, multi-layered topology, and back-propagation to “tune” the synapse weights. With spiking neural networks, this is just not possible. While you can use a layered topology, you would still have to tune the synaptic delays. And what about multiple connections between two neurons with different delays? It started in the 1990’s, when researchers first employed evolutionary algorithms to create and optimize those networks. But they quickly realized that by using simple genetic algorithms, too soon you run into limits, as the search-space explodes exponentially (you can optimize graphs with less than 100 nodes this way).

In short: Evolutionary graph optimization can be employed to create and optimize any kind of attributed graph, in our case, spiking neural networks. Spiking neural networks itself can be used for classification of data, in the same way as artifical neural networks are widely used today.

## Next up

In the second part of this article I will talk about the challenges we had to face and whether we came up with new solutions.