Is it necessary to map integers to bits in a genetic algorithm?

Question

From what I've read, genetic algorithms are usually (always?) applied to chromosomes of bits. So if a problem involves maximizing a function that takes integer values, the integers are first encoded as bits.

Is this mapping necessary? It seems that you could take chromosomes of integers and apply crossover and mutation directly. So, if I have a function that takes 35 integer inputs, I can just apply the genetic operators to those integers, rather than on the 35xB bits (where B is the number of bits needed to encode an integer). Is there a reason this isn't done?

Perhaps the algorithm would suffer because the problem is defined more coarsely (that is, a problem can be defined with shorter chromosomes if we're not using bits), but I'm curious if anyone has a better answer.

Answer 1

Encoding the values as bits isn't necessary. Look at 2d box car (don't waste too much time on it) for an example where the crossover is done on whole (float) values. Entire 'assemblies' are crossed over, this adds to the recognizability of the source (part of the aesthetics of the game), but makes it it so that the variations between a given chromosome and its parents are more limited.

The reason to consider using bits instead of integers has to do with the range of data that the pool is seeded with. Having 35 integers means that cross over can only occur on 35 values that are taken as whole values. having 1120 bits (35 * 32 bit integers) gives a finer granularity (consider traditional 'genetic algorithms' work on ATCG - not entire 'values' of amino acids or proteins).

Having bits lets you have 'cleaner' mutations (flip a bit) and crossover that takes the top part of one integer and the bottom part of another. Both of these things help increase the potential variety of offspring.

Consider the chromosome of just two bytes (we're doing bytes rather than integers to make it easier to see):

chromosome 1: 0xA3 0xB2
chromosome 2: 0x12 0x34

Cross over between these two chromosomes can happen only at limited places. You'll end up with:

chromosome 1': 0x12 0xB2
chromosome 2': 0xA3 0x34

If this was done as bits instead:

chromosome 1: 1010001110110010
chromosome 2: 0001001000110100
                    ^   ^     

Now you can select the ^ sites for crossover giving:

chromosome 1': 1010001000110010
chromosome 2': 0001001110110100
                     ^   ^     

This provides a richer model with more possible variations between two chromosomes.

Answer 2

As long as you have a crossover and mutate, you're in business. The underlying type doesn't matter. I've seen GAs on graph structures where the crossover and mutate operate on graphs directly, adding or combining nodes.

Actually, I usually encode everything to chars and then provide crossover and mutate at the byte level, rather than on bits. Adding a bit mask to take it to the bit level isn't hard, but life is just too short.

Answer 3

In GA all the chromosomes are usually represented as bit strings. You can have exceptions, but let´s forget them for now.

A chromosome is a possible solution to your problem, so if your solution is an integer number, it must have a binary representation to be worked by the genetic operations. Fortunately, integer numbers already have this binary representation (in fact, they *are natively bit strings), so you don´t have to do anything, just apply the operators over individuals of your population along the evolution process.

Answer 4

The mapping is not necessary.

Differential evolution (DE) is a very successful "subset" of the broader space of genetic algorithms.

The first big change is that DE is using actual real/integer numbers instead of bit strings (usually real numbers for numerical optimization, integers in other fields).

Anyway it's nice to be able to represent things as actual numbers.

It's a way to use computer resources efficiently and also makes input and output transparent for the user: parameters can be input, manipulated and output as ordinary numbers without ever being reformatted as genes with a different binary representation.

For the problem of being "defined more coarsely", DE adopts modified mutation / crossover operators that make use of the difference between two or more integer/real vectors in the population to create a new vector (e.g. by adding some random proportion of the difference to one of the existing vectors, plus a small amount of random noise).

_{From Differential Evolution - A Practical Approach to Global Optimization}