CODEWITHSUNDEEP
genetic-algorithmevolutionary-algorithm
Thermodynamix
Thermodynamix

Reputation: 367

Genetic algorithm individual representation

Typically introductions to genetic algorithms include the binary representation for individuals, where mutations occur by flipping bits. Are there any other representations that are commonly used?

Binary representations seem inconvenient when you would like to start from a solution of specific decimal values. Are there any other schemes for representing individuals in decimal form?

Upvotes: 1

Views: 1150

Answers (2)

zegkljan
zegkljan

Reputation: 8411

Basically, the genotype can be made of anything you want it to be made of. The only catch is that it must be "evolvable", i.e. you must have some recombination and mutation operator defined (or at least the mutation). As long as you have this, you are good to go.

I have written a blog post about the troubles with the binary representation when dealing with floating point numbers. The solution is not to represent the numbers in binary but rather use the numbers directly as a parto of the genotype. Once your genotype is a sequence of real numbers (as opposed to the sequence of 0s and 1s), your mutation and recombination operators change dramatically - you usually use stochastic procedures for generating and combining new solutions.

Another example is (tree-based) genetic programming - again, it's nothing more than a genetic algorithm where the representation is other than the binary string. Though it is much more complex thing than ordinary GA, it is still the same idea - a representation with a crossover and mutation operator defined.

Another approach is the genotype-phenotype procedure. Take e.g. the Grammatical Evolution algoritm. It does genetic programming but the representation that is modified during evolution is a binary string (but variable length) and a context-free grammar is used to translate it to a program.

The possibilities are endless :).

Upvotes: 2

manlio
manlio

Reputation: 18962

Linear binary representation is the original representation, but there are many other well known alternatives.

You can have arrays of other types that can be used in essentially the same way.

You can also mix the types. E.g. concatenating several types of heterogenously encoded genes allows...

...for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

(from Wikipedia)

Just to name an example, Differential evolution is based on real valued vectors and can outperform "standard" Genetic Algorithms on many numerical optimization problems (see also What's differential evolution and how does it compare to a genetic algorithm?).

What seldom changes is the representation length (variable length representations were also explored, but crossover implementation is more complex).

Upvotes: 1

Related Questions