# X. Encoding

### Introduction

Encoding of chromosomes is one of the problems, when you are starting to solve problem with GA. Encoding very depends on the problem.

この章では、以前に成功したいくつかのコード化の方法を紹介します。

In this chapter will be introduced some encodings, which have been already used with some success.

### バイナリーエンコーディング(Binary Encoding)

バイナリーエンコーディングは最も一般的なものです。

Binary encoding is the most common, mainly because first works about GA used this type of encoding.

バイナリーエンコーディングではすべての染色体は、0または1ビットの文字列となります。

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

 染色体 A 101100101100101011100101 染色体 B 111111100000110000011111

バイナリーエンコーディングによる染色体の例

バイナリーエンコーディングは 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.

エンコーディング: 各ビットはナップザックの中の荷物に対応します。

 Chromosome A 101100101100101011100101 Chromosome B 111111100000110000011111

Example of chromosomes with binary encoding

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 things with given value and size. The knapsack has given capacity. Select things to maximize the value of things in knapsack, but do not extend knapsack capacity.
Encoding: Each bit says, if the corresponding thing is in knapsack.

### 順列コーディング(Permutation Encoding)

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

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

 Chromosome A 1  5  3  2  6  4  7  9  8 Chromosome B 8  5  6  7  2  3  1  4  9

Example of chromosomes with permutation encoding

Permutation encoding is only useful for ordering problems. Even for this problems for some types of crossover and mutation corrections must be made to leave the chromosome consistent (i.e. have real sequence in it).

Example of Problem: Travelling salesman problem (TSP)
The problem: There are cities and given distances between them.Travelling salesman has to visit all of them, but he does not to travel very much. Find a sequence of cities to minimize travelled distance.
Encoding: Chromosome says order of cities, in which salesman will visit them.

### 実数値コーディング

Direct value encoding can be used in problems, where some complicated value, such as real numbers, are used. Use of binary encoding for this type of problems would be very difficult.

In value encoding, every chromosome is a string of some values. Values can be anything connected to problem, form numbers, real numbers or chars to some complicated objects.

 Chromosome A 1.2324  5.3243  0.4556  2.3293  2.4545 Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT Chromosome C (back), (back), (right), (forward), (left)

Example of chromosomes with value encoding

Value encoding is very good for some special problems. On the other hand, for this encoding is often necessary to develop some new crossover and mutation specific for the problem.

コード化: 染色体の実数は入力に対応する重みを表現しています。

Example of Problem: Finding weights for neural network
The problem: There is some neural network with given architecture. Find weights for inputs of neurons to train the network for wanted output.
Encoding: Real values in chromosomes represent 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 some objects, such as functions or commands in programming language.

 染色体 A 染色体 B ( +  x  ( /  5  y ) ) ( do_until  step  wall )

 Chromosome A Chromosome B ( +  x  ( /  5  y ) ) ( do_until  step  wall )

Example of chromosomes with tree encoding

コード化: 染色体は木で表現された関数です。

Tree encoding is good for evolving programs. Programing language LISP is often used to this, because programs in it are represented in this form and can be easily parsed as a tree, so the crossover and mutation can be done relatively easily.

Example of Problem: Finding a function from given values
The problem: Some input and output values are given. Task is to find a function, which will give the best (closest to wanted) output to all inputs.
Encoding: Chromosome are functions represented in a tree.

(c) Marek Obitko, 1998
Japanese translation (c) Ishii Manabu, 1999