V. Operators of GA

概観

遺伝的アルゴリズの概要をみてわかるように、交叉と突然変異は遺伝的アルゴリズムでもっとも重要な部分です。パフォーマンスは、主にこの２つのオペレータによって影響されます。交叉と突然変異をもっと説明する前に、染色体に関するいくつかの情報を与えたいと思います。

As you can see from the genetic algorithm outline, the crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators. Before we can explain more about crossover and mutation, some information about chromosomes will be given.

染色体の暗号化(Encoding of a Chromosome)

染色体はいろいろな方法で、それが表現する解に関する情報を含んでいます。もっともよく使われる暗号化の方法はバイナリー文字列です。その染色体はこのように見えます。

染色体 1	1101100100110110
染色体 2	1101111000011110

The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this:

Chromosome 1	1101100100110110
Chromosome 2	1101111000011110

どの染色体もバイナリー文字列を１つもっています。この文字列の中のどのビットも解の特徴を表現しています。または、文字列全体で１つの数を表わします。－これは基本GA applet.で使われています。

Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this has been used in the basic GA applet.

もちろん、他にもたくさんの暗号化の方法があります。これは解決すべき問題によります。例えば、直接整数や実数に暗号化することもできますし、順列などに暗号化するのも役立ちます。

Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers, sometimes it is useful to encode some permutations and so on.

交叉

どのような暗号化をするかを決めた後、交叉の手段を決めることができます。交叉は両親の染色体から遺伝子を選び、新しい子孫を作ります。これを行うもっとも単純な方法は、ランダムに交叉点をえらび、この点までを父親（染色体１）から、この点以降を母親（染色体２）からコピーすることです。

After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point point copy from a first parent and then everything after a crossover point copy from the second parent.

交叉はこのようになります。交叉点は | で表わされます

染色体 1	11011 \| 00100110110
染色体 2	11011 \| 11000011110
子孫 1	11011 \| 11000011110
子孫 2	11011 \| 00100110110

Crossover can then look like this ( | is the crossover point):

Chromosome 1	11011 \| 00100110110
Chromosome 2	11011 \| 11000011110
Offspring 1	11011 \| 11000011110
Offspring 2	11011 \| 00100110110

他にも交叉を行う方法はあります。例えばもっと多くの交叉点を選ぶことができます。交叉はより複雑で、染色体の暗号化の方法に非常に依存します。特殊な問題に対する特殊な交叉は遺伝的アルゴリズムのパフォーマンスを改善します。

There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm.

突然変異(Mutation)

交叉が行われた後で、突然変異がおこります。これは個体群のすべての解がが解決すべき問題の局所解に落ち込んでしまうことを防ぎます。突然変異は新しい子孫にランダムに変更を加えます。バイナリー暗号化ならば、ランダムに選ばれたいくつかのビットを０から１へ、また１から０へと反転させることができます。突然変異は次のようになります

元の子孫 1	1101111000011110
元の子孫 2	1101100100110110
突然変異した子孫 1	1100111000011110
突然変異した子孫 2	1101101100110110

After a crossover is performed, mutation take place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:

Original offspring 1	1101111000011110
Original offspring 2	1101100100110110
Mutated offspring 1	1100111000011110
Mutated offspring 2	1101101100110110

突然変異も交叉同様暗号化の方法に依存します。例えば、順列を暗号化したのであれば、突然変異は２つの遺伝子を交換することで行われます。

The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes.