VII. Parameters of GA


交叉と突然変異の確率

GAには基本的なパラメータとして2つのものがありす。 交叉確率と突然変異確率です。

There are two basic parameters of GA - crossover probability and mutation probability.

交叉確率はどのくらいの頻度で交叉が行われるかを示しています。 もし交叉が起こらなければ、子孫は両親の完全なコピーとなります。 もし交叉が起これば、子孫は両親質の染色体の一部分づつからできあがります。 もし交叉確率が100%であれば、すべての子孫は交叉によりできあがります。 もし0%であれば、新しい世代は前の個体群の染色体の完全なコピーとなります。 (しかしこれは新しい世代が同じ物であるということではありません!)
交叉は新しい染色体が古い染色体の良い部分をもっているという期待と、新しいものがよりよくなるという期待を込めてつくられます。 しかしながら個体群のいくつかの部分を次の世代へ残すのもよいことです。

Crossover probability says how often will be crossover performed. If there is no crossover, offspring is exact copy of parents. If there is a crossover, offspring is made from parts of parents' chromosome. If crossover probability is 100%, then all offspring is made by crossover. If it is 0%, whole new generation is made from exact copies of chromosomes from old population (but this does not mean that the new generation is the same!).
Crossover is made in hope that new chromosomes will have good parts of old chromosomes and maybe the new chromosomes will be better. However it is good to leave some part of population survive to next generation.

突然変異確率は染色体の一部がどれくらいの頻度で突然変異を起こすかをあらわしています。 もし突然変異がなければ子孫はなんの変更もなしに交叉(またはコピー)をbe taken after 突然変異が行われると染色体の一部分が変更されます。 もし0%であると変更されません
突然変異はGAが局所解に陥るのを防ぐために作られています、しかしあまりそれは頻繁にはおこりません、なぜならGAは実際はランダムサーチに変更されているからです。

Mutation probability says how often will be parts of chromosome mutated. If there is no mutation, offspring is taken after crossover (or copy) without any change. If mutation is performed, part of chromosome is changed. If mutation probability is 100%, whole chromosome is changed, if it is 0%, nothing is changed.
Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to random search.




他のパラメータ

GAには他にもパラメータがあります。 そのうちの1つで重要なパラメータとして個体群の数があります。

There are also some other parameters of GA. One also important parameter is population size.

個体群の数は個体群(1つの世代)の中にどれだけの染色体があるのかを示しています。 GAの数が少なすぎると、交叉を行う小さな確率があり、そして小さな探索スペースだけが探索されます。 一方でもしたくさんの染色体がたくさんありすぎると、GAは遅くなってしまいます。 調査の結果は、ある制限(主にコード化と、問題に依存しています) 個体群のサイズを増加させるのは役立ちません。 なぜなら問題をより速く解けないからです。

Population size says how many chromosomes are in population (in one generation). If there are too few chromosomes, GA have a few possibilities to perform crossover and only a small part of search space is explored. On the other hand, if there are too many chromosomes, GA slows down. Research shows that after some limit (which depends mainly on encoding and the problem) it is not useful to increase population size, because it does not make solving the problem faster.

すべてのパラメータに対する推奨値はこの先の章みつかるでしょう

Some recommendations for all parameters can be found in one of the following chapters.

Example
Here you can see example similar to previous one. But here you can try to change crossover and mutation probability. You can also control elitism.
On the graph below you can see performance of GA. Red is the best solution, blue is average value (fitness) of all population.
Try to change parameters and look how GA behaves.


Here is applet, but your browser does not support Java. If you want to see applets, please check browser requirements.

Question: If you try to increase mutation probability to 100%, GA will start to behave very strange, nearly like if the mutation probability is 0%. Do you know why? You can use a hint and if you still do not know, look at solution!



prev             next


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