Representations of chromosomes

In this section, we will discuss how to represent a possible solution from its circuit elements. String representation and circuit constructing trees are two frequently used representations in evolvable hardware designs... (Read more)

Fitness

The first thing is to find our desired solution as of the fittest, we initially set up our desired solution as the Q, and randomly generate a trial solution Q' such that it equals to Q, then Q' would be assigned with the highest fitness value. There are many methods used to calculate how close is the Q' similar to Q, we could use correlation function between them. Here is... (Read more)

Crossover and mutation

Now, let's have a closer look of how the chromosome is manipulated by the GA in order to get the desired solution. In an algorithm, it must has some sort of operator such as plus, minus, multiply, etc. In this case, our operator would be selection, crossover (recombination) and mutation. The operators are acting upon the initial searching space which consists of... (Read more)

Selecting chromosomes from population

After we generated a new population from the previous one, the remaining question is how we can select the offsprings base on their levels of fitness. From here, we will focus on three ways of selection that are often used... (Read more)

Putting things together

With all these procedures, we for example, implement a program which iterates through generations of evolution on its own by using genetic algorithm. For simplicity, to do this, we may define the following functions... (Read more)

One of the roles of evolution in reproducing a new generation which differs from its parents in some ways. It means that evolution must produce new genetic informations other than simply inheriting from the old generation. There are two processes to achieve this. One is known as crossover. That is in detail, a chromosome, which is simply a DNA molecule, from a parent has a probability of exchanging genes at one or more random positions with the corresponding chromosome from the other parent to form a new one. Another process following crossover is mutation, that is when copying genetic materials from parents, there is a chance that errors would occur at any random positions. This would cause the final chromosome to have bits that are not inherited from either parents, therefore expands the existing library of genetic informations.

Since the process of producing new genetic informations described above is totally random, we cannot know for sure that such new genetic informations are superior compared with their parents from whom they inherited. Therefore the other role of evolution is allowing the fittest, that is better evolved ones, to have greater chances to survive and pass their genes to later generations.

In the design of an evolvable hardware, we seek similarities between evolving a living being and a hardware system. We may consider genes as data structures which can be manipulated by computers. Chromosomes can be visualised as circuits. Then we may further think of a genotype, defined as a set of genes from all chromosomes, could be used to define properties of circuit components, such as the value of resistance, the labels of input and output pins; while phenotypes defines the network formed with these circuit components. The goal of genetic algorithm is to evolve both genotypes and phenotypes, therefore optimising the better existing solutions to our tasks while discarding bad ones.

To learn about genetic algorithm, we will first look into how chromosomes can be represented with data structures.