IX. 選択(Selection)


Introduction

GA outlineで、すでにご存知のとおり、個体群から交叉を行うための両親となる染色体が選ばれます。 問題はどうやって染色体を選ぶかということです。 ダーウィンの進化論によると、もっともよい物は生き残り、新しい子孫を作るべきだといっています。 もっともよい染色体を選ぶ方法は沢山あります。 ルーレット方式、ボルツマン選択、トーナメント選択、ランキング方式、定常状態再生 などといったものです。

As you already know from the GA outline, chromosomes are selected from the population to be parents to crossover. The problem is how to select these chromosomes. According to Darwin's evolution theory the best ones should survive and create new offspring. There are many methods how to select the best chromosomes, for example roulette wheel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others.

それらのうちいくつかをこの章で紹介します。

Some of them will be described in this chapter.




ルーレット方式(Roulette Wheel Selection)

適合度によって両親が選択されます。 他よりも良い染色体は、選ばれるチャンスも広がります。 個体群のすべての染色体がおかれている。ルーレットを想像してみてください。 どの染色体も、彼らの適合度関数に従って決められた大きさが割り当てられています。

Parents are selected according to their fitness. The better the chromosomes are, the more chances to be selected they have. Imagine a roulette wheel where are placed all chromosomes in the population, every has its place big accordingly to its fitness function, like on the following picture.

そしてビーダマをなげて、染色体が選ばれます。 より大きな適合度をもった染色体は何度も選ばれるかもしれません。

Then a marble is thrown there and selects the chromosome. Chromosome with bigger fitness will be selected more times.

これは次のようなアルゴリズムでシミュレートできます。

  1. [和を求めるSum] 個体群内のすべての染色体の適合度の合計をもとめます。 - sum S.
  2. [選択] (0,S)の間の数をランダムに選びます。 - r.
  3. [ループ] 個体から染色体を1つづつ取り出して適合度を足していきます。足した合計をsとします。 そして、srを越えたら、そこで加算のループをやめます。 そして現在の染色体を返します。

This can be simulated by following algorithm.

  1. [Sum] Calculate sum of all chromosome fitnesses in population - sum S.
  2. [Select] Generate random number from interval (0,S) - r.
  3. [Loop] Go through the population and sum fitnesses from 0 - sum s. When the sum s is greater then r, stop and return the chromosome where you are.

もちろん step 1は、どの個体群にも1度だけ行われます。
(訳注:1世代に1回だと思う)

Of course, step 1 is performed only once for each population.




ランキング方式(Rank Selection)

上の選択法式だと、適合度に非常に大きな差がある場合に問題が発生してしまうかもしれません。 例えば、最も適合度の良い染色体がルーレットの90%をしめてしまうと、他の染色体は非常に選ばれにくくなってしまいます。

The previous selection will have problems when the fitnesses differs very much. For example, if the best chromosome fitness is 90% of all the roulette wheel then the other chromosomes will have very few chances to be selected.

ランキング方式は、まず個体群にランク付けを行います。染色体はこのランクから適合度を受けます。 もっとも悪いものは、適合度1をもらいます. 下から2番目のものは2が適合度となります。 これを続けていきます。 そうすると最も良い個体の適合度はN(個体群内の染色体の数)になります。

Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population).

You can see in following picture, how the situation changes after changing fitness to order number.

Situation before ranking (graph of fitnesses)

Situation after ranking (graph of order numbers)

これですべての染色体に選ばれる可能性がでてきました。 しかしこの方法はゆっくりとした収束になる可能性があります。 それは、もっともよい個体が他のものに比べて大きな違いがないからです。

After this all the chromosomes have a chance to be selected. But this method can lead to slower convergence, because the best chromosomes do not differ so much from other ones.




Steady-State Selection

これは両親を選択する方法として特別なものではありません。 主な考え方は、染色体の大部分がつぎの世代へ生き残るということです。

This is not particular method of selecting parents. Main idea of this selection is that big part of chromosomes should survive to next generation.

GAは次のようのな方法で動きます。 どの世代でも少しの染色体(良い、高い適合度のもの)を子孫を作るために選びます。 そしていくつかの染色体(悪い、適合度が低いもの)を取り除き、新しい染色体をその場所に加えます。 個体群の残りはそのまま新しい世代へ生き残ります。

GA then works in a following way. In every generation are selected a few (good - with high fitness) chromosomes for creating a new offspring. Then some (bad - with low fitness) chromosomes are removed and the new offspring is placed in their place. The rest of population survives to new generation.




エリート主義(Elitism)

エリート主義の考え方はすでに紹介されています。 新しい個体群を交叉と突然変異を用いてつくるとき、

Idea of elitism has been already introduced. When creating new population by crossover and mutation, we have a big chance, that we will loose the best chromosome.

エリート主義というのは、まず最も良い染色体(または複数の良い染色体)を新しい世代へコピーするという方法の名前です。 残りは、古典的な方法で選ばれます。 エリート主義は、非常に急速にGAのパフォーマンスを増加させます。 なぜならば、見つかった解で最も良いものを失わずにすむからです。

Elitism is name of method, which first copies the best chromosome (or a few best chromosomes) to new population. The rest is done in classical way. Elitism can very rapidly increase performance of GA, because it prevents losing the best found solution.



prev             next


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