X. Encoding



Introduction

染色体のコード化は、GAを使って問題を解こうと始めるたときに、問題になることの1つです。 コード化は非常に問題に依存します。

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).


例題: 巡回セールスマン問題 (TSP)
問題: 都市とそれぞれの都市間の距離が与えられています。巡回セールスマンは与えられた都市をすべて回る必要があります。しかし彼はあまり旅が好きではありません。もっとも旅行する距離が短い順番を探します。 コード化: 染色体は都市の順番を表わします。セールスマンはその順番でまわります.
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.


例題: ニューラルネットワークの重み付けを探す
問題: There is some neural network with given architecture. Find weights for inputs of neurons to train the network for wanted output.
コード化: 染色体の実数は入力に対応する重みを表現しています。




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

木コード化は進化的プログラムに適しています。 LISPというプログラム言語はこれに対して、しばしば使われます。 なぜならば、それの中のプログラムはこの型を表現します。 また簡単に解剖することができます。 ですから、交叉や突然変異を相対的に簡単に行うことができます。


例題: 与えられた値から関数を見つける
問題: 入力と出力の値が与えられます。問題はすべての入力に対して最も良い(ほしいものにもっともちかいもの)を与える関数を探すことです。
コード化: 染色体は木で表現された関数です。

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.



prev             next


(c) Marek Obitko, 1998
Japanese translation (c) Ishii Manabu, 1999
- Terms of use