XIII. 推奨値

ＧＡのパラメータ

この章では、遺伝的アルゴリズムを実行する際に、目安となるいくつかの基本的な推奨値を与えたいと思います。これらの推奨値は非常に一般的です。たぶん、特定の問題にたいして自分のGAで実験したいとおもうでしょう。なぜなら、今日、いかなる問題に対してのGAのパラメータが述べられた一般的な理論がありません。

This chapter should give you some basic recommendations if you have decided to implement your genetic algorithm. These recommendations are very general. Probably you will want to experiment with your own GA for specific problem, because today there is no general theory which would describe parameters of GA for any problem.

推奨値は、しばしばバイナリーコーディングのみで行われたGAの経験的な値の結果です。

Recommendations are often results of some empiric studies of GAs, which were often performed only on binary encoding.

交叉率
交差率は一般的にほぼ80%-95%のように高く設定されます。（しかしある結果では問題があり、交差率は60％が最も良いという結果が出ています）
突然変異率
いっぽい腕、突然変異率は非常に低くなっています。最も良い率は、だいたい0.5%-1%と報告されています。
個体群の大きさ
驚くかもしれませんが、非常に大きな個体群の大きさがいつもＧＡのパフォーマンスを改善させません。（解を見つける速さという目的で）良い個体群の大きさは20-30です。しかし50-100が最も良いという報告もあります。ある研究では最も良い個体群の大きさはコード化、コード化された文字列の大きさに依存するとしています。それはもし３２ビットの大きさの染色体であれば、個体群は３２がよいということです。しかし、確実に１６ビットの染色体に対するもっとも良い個体群の大きさの２倍以上です。
選択
基本的にはルーレット選択方式 が使われます。しかし時々ランク方式の方が良い場合もあります選択に関する章で長所と短所を調べてみてください。またほかにももっと洗練された方法もあります。それはＧＡの実行中に選択のパラメータをかえることです。基本的にはシミュレーティッドアニーリング（訳注：やきなまし）のように振る舞います。しかし、エリート主義（もし最も良い解を保存するのに他の方法を使いたくないのであれば）が確実に使われます。また定常状態選択を試すことできます。
コード化
コード化は問題に依存します そしてまた、問題の事例にも依存します。コード化に関する章で提案を調べてみてください。もしくはother resourcesを参照してみてください。
交叉と突然変異のタイプ
オペレータはコード化と問題に依存します。chapter about operatorsで提案をみてください。またother sitesを見てみてください。

Crossover rate
Crossover rate generally should be high, about 80%-95%. (However some results show that for some problems crossover rate about 60% is the best.)
Mutation rate
On the other side, mutation rate should be very low. Best rates reported are about 0.5%-1%.
Population size
It may be surprising, that very big population size usually does not improve performance of GA (in meaning of speed of finding solution). Good population size is about 20-30, however sometimes sizes 50-100 are reported as best. Some research also shows, that best population size depends on encoding, on size of encoded string. It means, if you have chromosome with 32 bits, the population should be say 32, but surely two times more than the best population size for chromosome with 16 bits.
Selection
Basic roulette wheel selection can be used, but sometimes rank selection can be better. Check chapter about selection for advantages and disadvantages. There are also some more sophisticated method, which changes parameters of selection during run of GA. Basically they behaves like simulated annealing. But surely elitism should be used (if you do not use other method for saving the best found solution). You can also try steady state selection.
Encoding
Encoding depends on the problem and also on the size of instance of the problem. Check chapter about encoding for some suggestions or look to other resources.
Crossover and mutation type
Operators depend on encoding and on the problem. Check chapter about operators for some suggestions. You can also check other sites.

ＧＡの応用例

遺伝的アルゴリズムは難しい問題（例えばＮＰハード問題）、機械学習や単純進化的プログラムに使われます。また芸術や、進化的な画像や音楽にも使われます。

ＧＡの利点はその並列にあります。ＧＡは個体を越えて（そして表現形(phenotype)よりむしろ遺伝子形(genotype)で）探索空間を飛びまわります、そして他の方法のような局所解に懸命に取り組むようなことはあまりありません。

また実行が簡単です。１度あるＧＡを使えば、別の問題を解くときには新しい染色体を書くだけでよいのです。また同じコード化を使うのなら、適合度関数をかえるだけでも良いのです。一方でコード化の方法や、適合度関数を選ぶことが難しいです。

ＧＡの欠点は計算時間にあります。ＧＡは他の方法にくらべて遅くなる可能性があります。しかし今日のコンピュータでは大した問題にはなりません。

ＧＡによって問題を解決するアイデアを得るためにここに短い応用例のリストがあります。:

非線形動的システム - 予測、データ分析
ニューラルネットワークの設計、構造と重みの両方
ロボット制御（Robot trajectory）
進化的ＬＩＳＰプログラム（遺伝的プログラミング）
戦略計画
タンパク質分子構造の発見
巡回セールスマン問題(TSP)とスケジューリング
イメージを創るための関数

より多くの情報はこの付録(appendix)を通してみつけることができます

Applications of GA

Genetic algorithms has been used for difficult problems (such as NP-hard problems), for machine learning and also for evolving simple programs. They have been also used for some art, for evolving pictures and music.

Advantage of GAs is in their parallelism. GA is travelling in a search space with more individuals (and with genotype rather than phenotype) so they are less likely to get stuck in a local extreme like some other methods.

They are also easy to implement. Once you have some GA, you just have to write new chromosome (just one object) to solve another problem. With the same encoding you just change the fitness function and it is all.On the other hand, choosing encoding and fitness function can be difficult.

Disadvantage of GAs is in their computational time. They can be slower than some other methods. But with todays computers it is not so big problem.

To get an idea about problems solved by GA, here is a short list of some applications:

Nonlinear dynamical systems - predicting, data analysis
Designing neural networks, both architecture and weights
Robot trajectory
Evolving LISP programs (genetic programming)
Strategy planning
Finding shape of protein molecules
TSP and sequence scheduling
Functions for creating images

More information can be found through links in the appendix.