X. Encoding

---

Introduction

Choosing an encoding for chromosomes is one of the first issues you face when solving a problem with a GA. The right encoding depends strongly on the problem.

This chapter introduces several encodings that have been used successfully in genetic algorithms.

---

Binary Encoding

Binary encoding is the most common approach, mainly because the earliest work on genetic algorithms used this type of encoding.

In binary encoding, every chromosome is a string of bits, 0 or 1.

Binary encoding gives many possible chromosomes even with a small number of alleles. On the other hand, this encoding is often not natural for many problems, and sometimes corrections must be made after crossover and/or mutation.

Example of Problem: Knapsack problem
The problem: There are items with given values and sizes. The knapsack has a fixed capacity. Select items to maximize the total value in the knapsack without exceeding its capacity.
Encoding: Each bit indicates whether the corresponding item is in the knapsack.

---

Permutation Encoding

Permutation encoding can be used for ordering problems, such as the travelling salesman problem or task ordering.

In permutation encoding, every chromosome is a string of numbers, which represents a number in a sequence.

Permutation encoding is useful only for ordering problems. Even in those problems, some types of crossover and mutation require corrections to keep the chromosome consistent (that is, to preserve a valid sequence).

Example of Problem: Travelling salesman problem (TSP)
The problem: There are cities and given distances between them. The travelling salesman has to visit all of them while traveling as little as possible. Find a sequence of cities that minimizes the total distance traveled.
Encoding: The chromosome specifies the order in which the salesman visits the cities.

---

Value Encoding

Direct value encoding can be used in problems where more complex values, such as real numbers, are needed. Using binary encoding for these problems would often be very difficult.

In value encoding, every chromosome is a string of some values. Values can be anything related to the problem, from numbers, real numbers, or characters to more complicated objects.

Value encoding works very well for some specialized problems. On the other hand, it is often necessary to develop new crossover and mutation operators that are specific to the problem.

Example of Problem: Finding weights for neural network
The problem: There is a neural network with a given architecture. Find weights for the neuron inputs so that the network produces the desired output.
Encoding: Real values in the chromosomes represent the corresponding weights for inputs.

---

Tree Encoding

Tree encoding is used mainly for evolving programs or expressions, for genetic programming.

In tree encoding, every chromosome is a tree of objects such as functions or commands in a programming language.

Tree encoding is well suited to evolving programs. The programming language LISP is often used for this, because its programs are naturally represented in this form and can be easily parsed as trees, so crossover and mutation can be performed relatively easily.

Example of Problem: Finding a function from given values
The problem: Some input and output values are given. The task is to find a function that gives the best (closest to the desired) output for all inputs.
Encoding: Chromosomes are functions represented as trees.