Chromosome (evolutionary algorithm)

[1][2] The genome of an individual consists of one, more rarely of several,[3][4] chromosomes and corresponds to the genetic representation of the task to be solved.

[2] In the basic form of genetic algorithms, the chromosome is represented as a binary string,[5] while in later variants[6][7] and in EAs in general, a wide variety of other data structures are used.

The design of a chromosome translates these considerations into concrete data structures for which an EA then has to be selected, configured, extended, or, in the worst case, created.

[11] In this context, suitable mutation and crossover operators[2] must also be found or newly defined to fit the chosen chromosome design.

An important requirement for these operators is that they not only allow all points in the search space to be reached in principle, but also make this as easy as possible.

In their classical form, GAs use bit strings and map the decision variables to be optimized onto them.

For the processing of tasks with real-valued or mixed-integer decision variables, EAs such as the evolution strategy[15] or the real-coded GAs[16][17][18] are suited.

[19][20] For this purpose, the valid digits of real values are mapped to integers by multiplication with a suitable factor.

Combinatorial problems are mainly concerned with finding an optimal sequence of a set of elementary items.

As an example, consider the problem of the traveling salesman who wants to visit a given number of cities exactly once on the shortest possible tour.

[15] Another example is an additional gene to control a selection heuristic for resource allocation in a scheduling tasks.

The chromosomes presented above are well suited for processing tasks of continuous, mixed-integer, pure-integer or combinatorial optimization.

For a combination of these optimization areas, on the other hand, it becomes increasingly difficult to map them to simple strings of values, depending on the task.

For tasks with a combinatorial part, there are suitable genetic operators that can move or reposition genes as a whole, i.e. with their parameters.

The exemplary gene type definition of work step 15 with two resources, for which there are four and seven alternatives respectively, would then look as shown in the left image.

Since the parameters represent indices in lists of available resources for the respective work step, their value range starts at 0.

Mutation operators can rearrange, change or delete subtrees depending on the represented syntax structure.