• DEPARTMENT OF PHYSICS AND ASTRONOMY
• HEIDELBERG UNIVERSITY
Björn Kindler

Evolutionary Algorithms

The most extensive Evolutionary Algorithm (EA) has started billions of years ago with the Big Bang. Thanks to it humanity evolved just recently and is able to enjoy all those other mind-blowing things that arose at the same time. Thus it is no wonder that one day someone had the idea to model the principles of evolution and use it for solving complex problems.

Evolutionary Algorithm (EA) is the umbrella term for all computational models that are inspired by evolutionary mechanisms. There is a variety of implementations of EAs available. The most important ones are Genetic Algorithms (GAs), Genetic Programming (GP), Evolutionary Programming (EP), Classifier Systems and Artificial Life (AI). Although the particular representations can heavily differ from each other they all share basic principles. Every algorithm organizes a population of individuals (e.g. construction plans, configuration data, DNA ...). The individuals are developed through mutation and crossover operations and then evaluated by measuring their fitness that indicates how good they fit into their environment. Problems to be solved are defined by the shape of the fitness landscape.

Genetic Algorithms

Our evolvable hardware system - FPTA - is working on transistor level. Configurable CMOS transistors are arranged in an array of 16 x 16 cells. Each transistor terminal can be connected to one of the cells outside connections (N S W E), vdd or gnd. Additionally, it is possible to directly connect the nodes (N S W E) to each other which provides flexible routing capabilities. The array is enclosed by IO cells that can apply voltages to the border cells or measure the output voltages of the evolved circuit.

Therefore our individuals contain the configuration data of how the terminals and connections of the transistor array are set up. A Genetic Algorithm (GA) is used to control the evolution of the transistor circuits. According to the working principles of Evolutionary Algorithms (EA) a mutation operator and a crossover operator are defined to modify the individuals that make up a population. Each individual represents a genotype -> the configuration string for the FPTA. For testing and evaluating, the genotype is mapped to the phenotype that describes a circuit in the FPTA's format.

Mutation operator

The mutation operator randomly enables or disables connections between nodes and terminals of a selected individual. As an example, two partly configured transistor cells are shown that turn into a running inverter circuit by mutating one connection.

Crossover operator

The crossover operator selects two individuals that become the parents of a new one. This is done by randomly choosing a variable block of cells of one parent and exchanging it with the corresponding block of the second. Again an inverter circuit serves to visualize how things work.

As shown on the picture, two useful parts that were spread over two individuals happened to merge and again a running inverter circuit is formed.

Other applications of EAs within our group...