遺伝的アルゴリズム 5分で理解
English Follows
遺伝的アルゴリズムは、生命の進化のメカニズムを模した、最適化問題を解くための手順である。具体的な適用例についてはすでに多くのサイトで紹介されているので、ここでは、遺伝的アルゴリズムが一体何をやっているのか？なんで答えがでるのか？について簡略に説明したい。
一般的に、最適化問題の解法にはＮ次元ニュートンラプソン（再急降下法）が用いられてきたが、不連続な関数には対応できないし、ローカルミニマムに陥るなど、汎用性を欠いていた。
遺伝的アルゴリズムは、結婚、突然変異、継承、適者生存という進化の仕組みを模倣することで、Ｎ次元の解の空間を効率的に絞り込み、グローバルミニマムの探索を可能にした。
遺伝子記号は、Ａ・Ｇ・Ｃ・Ｔという４進数の塩基配列の組み合わせからなる。生物の個体の多様性はこの塩基配列の違いだけだ。そしてその配列は、結婚、突然変異により個体ごとに変わり、自然環境が適応しない個体を淘汰する。
遺伝的アルゴリズムではこれを真似て、解の空間を有限個数に細分化し、n進法の数のベクトルで表わす。まず、第一世代は多数の個体を乱数で発生させ生成、その後、その個体同士を結婚（n進法数の桁の上半分と下半分の交換）、突然変異（乱数で数字をわざと乱す）、継承（そのまま引き継ぐ）し、結果を目的関数にかけて、結果が悪いものを淘汰することで、第二世代を作る。
第一世代はＮ次元空間に一様に散布された状態だが、世代を経るごとに、グローバルミニマムに集中してくる。十分に集中した時点で解が求められたことになる。
余談だが、この出来すぎた生命の進化の仕組みを見て、背筋が寒くなるのは私だけだろうか？
余談だが、この出来すぎた生命の進化の仕組みを見て、背筋が寒くなるのは私だけだろうか？
Genetic Algorithm
5 min Real Understanding
Genetic algorithm is a procedure to solve optimize problem mimicking mechanism of life evolution. Since practical applications are already introduced extensive in other sites, here I wish to focus what it is all about and why we can get solution out of this procedure.
In general, N-dimensional Newton Raphson method (steepest gradient method) has been used for optimization problem however, it could not cope with noncontinuous function and also easy to fall into local minimum, thus lacked robustness.
Genetic algorithm made search of global minimum possible by mimicking the mechanism of evolution, i.e., marriage, mutation, inheritance and survival of fittest, then narrow the solution of N dimensional space efficiently.
Genetic code is composed of combination of quaternary (A, G, C, T) base sequence. Individual variation comes only from the difference of sequence. Then the sequence differs by individual due to marriage, mutation while keeping only fittest.
Mimicking this framework, Genetic Algorithm makes finite discretization of the solution space representing in vector of n-ary system. 1st generation is made randomly, then let them get married (exchanging upper-half/lower-half digits), mutated (disturb digits randomly), inherit (no change), then apply to objective function to keep better fit ones mainly to be the 2nd generation.
1st generation looks uniformly spread over population in N-dimensional space, while as generation goes by, population will converge concentrating close to global minimum. Solution is obtained once we see sufficient convergence.
By the way, is it only me who feel a bit shivering by revisiting this too-well-made mechanism of life evolution?