Why more than one chromosome per solution (or genotype)?

Question

I am trying to get started using the Jenetics JAVA library for genetic algorithms and there is something I don't understand from my GA limited backgroud;

As I understand a GA generates a population of Arrays of m elements, where each array is a potential solution to be evaluated, once evaluated, the potential solutions are sorted and the best are chosen to create a new population, etc. But I find that a solution (Genotype) in Jenetics is a list of arrays where each array is what I understand as a potential solution, also each array can have different lengths and I don't understand why to use this structure instead of a vector of genes.

See page six of the manual, section 3.1.3.

If possible I would like to know why is this. I hope to have made the question clear enough.

Answer 1

What you have described is population in basic genetic algorithm. There are many techniques to improve it, and one of them is adaptive coding.

The term you are looking for is (modified) gene pool recombination under adaptive coding techniques.

Gene pool recombination operates over entire population rather then single units and evolves population. It may or may not keep same structure.

Look at this idea from biology perspective:

• In nature, first there were simpler organisms and then they evolved into more complex organisms.

Same motivation can be used with genetic algorithms. At the begging there are simpler units which can evolve with time - in other words length and structure of solutions do not have to be constant.

There is no simple way to universally encode information for GA, so you have to consider it for every problem at hand. You may or may not need gene pool recombination, basic binary encoding or basic proportional selection. These options are largely dependent on the problem you are trying to solve, and precision of solution/time taken by algorithm which is acceptable.

Basic Binary encoding representing vector of genes is simple but GA has downside where it is inefficient in finding closest neighbors.

Consider following example:

• there are solutions 15 and 16 (01111, 10000)

• hamming distance between these two numbers is 5

For GA to change from 15 to 16, all 5 bits should be changed. So, GA have problems with neighbor discrete numbers. One way to improve this is by using Gray code which lets you have distance of 1 between all solutions.

Answer 2

The "array" of potential solutions (Phenotpyes/Genotypes) is collected in the Population. The Genotype represents one possible solution. Don't be confused by the 2-dimensional structure of the Genotype, it should give you additional flexibility for modeling more complicated problems. The Geneotype still represents one possible solution and one individual of the Population.

A Genotype for the classical binary GA can be easily created:

Genotype<BitGene> gt = Genotpe.of(BitChromosome.of(15));

Also have a look at the domain model, figure 3.1 in the manual. Section 6.1 tries to give you additional encoding examples.

jenetics, genetic-algorithm