遺伝的アルゴリズムー数学

遺伝的アルゴリズムは最適化の問題を解決するために使用されます。このような問題の例として、ニューロネットワークの学習、つまりエラーを最小限にするための、このような重み値の選択を用いることができます。遺伝的アルゴリズムのベースにはランダム探索法があります。ランダム探索法の主な短所は、問題を解決する為にどれ程の時間がかかるかわからない点です。膨大な時間の浪費を避ける為に、生物学で構築された方法、つまり種と進化の過程の研究の際に構築された方法です。進化の過程では、最も適応したものが生き残るということは明らかです。変化した条件でより生き残らせる集団の適応性を増大させることに繋がります。

初めにこのようなアルゴリズムは１９７５年にミシガン州立大学のジョン・ホーランド(John Holland)によって提唱されました。それは『ホーランドの再生計画』と名付けられ、遺伝的アルゴリズムのほぼ全てのバリエーションをベースとしました。しかしながら、これを詳しく見てみると、現実世界のオブジェクトは遺伝的アルゴリズムでどのようにコード化することができるのかという点で足を止める必要があります。

オブジェクトの紹介

生物学から、あらゆる生物は現実世界でオブジェクトが何であるかを事実上明確にする、自分の表現型や、染色体の組み合わせレベルでオブジェクトの全ての情報を含む遺伝子型によって成っていることを私たちは知っています。この時、各遺伝子は、つまり遺伝子型の情報要素は、表現型に反映されます。したがって、問題を解決するためには、遺伝的アルゴリズムで使用するのに適した形で各オブジェクトの符号を表現する必要があります。全ての今後の遺伝的アルゴリズムのメカニズムの機能は、様々な課題における幅広い用途を条件づけるオブジェクトの内部構造に関する情報の必要性を排除しつつ、遺伝子型レベルで実行されます。

オブジェクトの遺伝子型表現の為の最もよく見られる遺伝的アルゴリズムの多様性には、ビット型が使用されます。この際、表現型のオブジェクトの各属性は、オブジェクトの遺伝子型の1つの遺伝子に相当します。遺伝子はこの特性の値を表す（多くの場合）固定長のビット列です。

整数で表される特性のコーディング

このような特性のコーディングの最も簡単な方法は、その属性のビット値を使用することです。そうすると、このような特性の全てのあり得る数値を表すのに十分な一定の長さの遺伝子を使用することが非常に簡単になります。しかし、残念ながら、このようなコーディングに欠点がないわけではありません。主な欠点は、隣接する数字がいくつかのビット値と異なることであり、例えば、ビット表示の７と８は、４つのポジションで異なっており、これが遺伝的アルゴリズムの操作を困難にし、収束に要する時間が長くなります。この問題を回避するためには、隣接する数字がより小さい異なり（理想は、１つのビット値のみ）のものをコーディングしたほうが良いです。このようなコードは、遺伝的アルゴリズムを実装するのに適切なグレイコードとなります。グレイコードの値は以下の表の通りです。

バイナリコーディング			グレイコーディング
１０進 コード	バイナリ 値	１６進 値	１０進 コード	バイナリ 値	１６進 値
0	0000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

表１１０進コードとグレイコードの適合

このようにして、整数の特性のコーディングでは、私達はこれを4分子に分割し、各４分子をグレーコードに従って変換します。

遺伝的アルゴリズムの実地的実装では、特性の値を遺伝子値に変換する必要はありません。実際には逆の問題として、遺伝子値によってこれに対応する特性の値を明らかにする必要があります。

このように、整数特性に対応する遺伝子値のデコードの課題は些細なことです。

浮動小数点に対応する特性のコーディング

最も簡単なコーディングの方法は、ビット表現を使用することです。とは言っても、この方法は整数の場合と同じ欠点を持っています。したがって、実際には通常次の操作を適用します。

1. 特性の許容値の全てのインターバルを必要な精度を持つ部分に分割します。
2. 遺伝子値をインターバルの番号を決める整数とします。（グレイコードを使用して）
3. このインターバルの中央値をパラメータ値とします。

上記の一連の動作を例として見てみましょう。

特性値が[0,1]のインターバルにあるとしましょう。コーディングには、256のインターバルへの分割が使用されます。これらの番号をコーディングするために、私達には8ビットが必要になります。遺伝子値が00100101bGであるとします。（大文字のGはグレイコードによるコーディングが使用されていることを意味します）始めにグレイコードを使用して、これに対応するインターバル番号を見つけます。（25hG->36h->54d）ここでどのインターバルが対応しているかを見てみましょう。簡単な計算の後、私達はインターバル[0,20703125, 0,2109375]を得ます。つまり、私たちのパラメータ値は(0,20703125+0,2109375)/2=0,208984375となります。

非数値データのコーディング

非数値データのコーディングの際には、これらを数値に変換する必要があります。詳細は、ニューラルネットワークの使用についての私たちのサイト内の記事に書かれています。

遺伝子型によるオブジェクトの表現型の定義

オブジェクトの表現型を定義する為には（つまり、オブジェクトの特性値）これらの特性に対応する遺伝子値（つまり、オブジェクトの表現型）を知る必要があります。オブジェクトの遺伝子型が書かれた遺伝子の集合は、染色体を表します。いくつかの実施では、これを標本とも呼びます。このように、遺伝的アルゴリズムの実装では、染色体は固定長のビット列を表します。この時、列の各部分は遺伝子に対応します。染色体内の遺伝子の長さは、同一または異なる場合があります。多くの場合、遺伝子の長さが同じものが使用されます。染色体の例とその数値の解釈例を見てみましょう。オブジェクトには５つの属性があるとし、それぞれが４つの要素の遺伝子長で符号化されいるとします。その場合、染色体の長さは5×4=20ビットとなります。

0010

1010

1001

0100

1101

ここで、特性値を定義することができます。

特性			遺伝子値			特性のバイナリ値			特性の10進値
特性1			0010			0011			3
特性2			1010			1100			12
特性3			1001			1110			14
特性4			0100			0111			7
特性5			1101			1001			9

基本的な遺伝的演算子

周知のように、進化論において、親の特性が子孫に引き継がれる方法は重要な役割を果たしています。遺伝的アルゴリズムでは、親の特性の子への引き継ぎは、交叉と呼ばれる（『クロスオーバー』や『組み換え』とも呼ばれる）演算子が行います。 これは次のように作用します。

1. 集団の中から親となる２つの個体が選ばれます。
2. ブレークポイントが決定されます。（通常はランダムに）
3. 子孫は第１および第２の親の部分の連結として定義されます。

この演算子の動作を見てみましょう。

Chromosome_1：			0000000000
Chromosome_2:			1111111111

ブレークポイントが染色体の第３ビットの後に起こったとすると、

Chromosome_1：			0000000000			>>			000			1111111			Resulting_chromosome_1
Chromosome_2:			1111111111			>>			111			0000000			Resulting_chromosome_2

それから、0.5の確立で子として得られた染色体の一つが定義されます。

次の遺伝的演算子は、集団からの個体の多様性をサポートする為に設計されています。これは変異演算子と呼ばれています。この演算子を使用すると、染色体の各ビットは、一定の確率で反転されます。

また、染色体を二つに分割し、それから位置を取り替える反転と呼ばれる演算子を使用します。これを以下のように概略的に表すことができます。

000

1111111

>>

1111111

000

理論的には、これらの２つの遺伝的演算子は、遺伝的アルゴリズムを機能させるのに十分なものです。しかし、実際にはいくつかの追加の演算子またはこれらの２つの演算子の修正が使用されます。例えば、いくつかのブレークポイントが形成される場合（多くの場合２つ）、交叉は単一ではなく複数の場合があります（上述の通り）。また、アルゴリズムのいくつかの実装では、変異演算子はランダムに選択された染色体のビットを一つだけ反転させます。

遺伝的アルゴリズムのフローチャート

遺伝子値の解釈の仕方を知ったところで、遺伝的アルゴリズムの機能の詳細に移っていきましょう。古典的な方法で遺伝的アルゴリズムのフローチャートを見てみましょう。

1. 開始時間を初期化します：t=0。ランダムに個体ｋからなる初期の集団を形成します。B0 = {A1,A2,…,Ak)
2. 各個体の適応性（FAi = fit(Ai) , i=1…k）と集団全体の適応性（Ft = fit(Bt)）を計算します。（時に適合性と呼ばれる）この関数の値は、問題の解決の為に、この染色体によって書かれた個体がどれ程適しているかを判定します。
3. 集団からACの個体を選択します。Ac = Get(Bt)
4. 一定の確率で（PCの交叉確率）集団から二つ目の個体を選択（Аc1 = Get(Bt)）し、交叉演算子が生成します（Ac = Crossing(Ac,Ac1)）。
5. 一定の確率で（変異確率Pmで）変異演算を実行します。Ac = mutation(Ac)
6. 一定の確率で（反転確率Piで）反転演算を実行します：Ac = inversion(Ac)。
7. 取得した染色体を新しい集団へ挿入します：insert(Bt+1,Ac)。
8. 項目３からｋ回演算を実行します。
9. 現在の期間の番号を増やします：t=t+1。
10. 停止の条件が満たされた場合、作業を終了し、そうでない場合はステップ２へ進みます。

ここでアルゴリズムのいくつかのステップを詳しく見ていきましょう。

アルゴリズムの正常な動作の中で、最も重要な役割を果たすのは、ステップ３と４の染色体の親の選択です。これは、様々なバリエーションがあります。ルーレットと呼ばれる選択方法が最も多く使用されます。この方法を使用する場合、染色体の選択確率は、その適応性によって決定されます：PGet(Ai) ~ Fit(Ai)/Fit(Bt)。この方法を使用すると、より適合した個体を子孫に引き渡す可能性が高くなります。他のよく使用される方法は、トーナメント選択です。これは、集団からいくつかの個体がランダムに選択され（通常２つ）、より高い適合性を持つ個体が勝者として選択されます。またアルゴリズムのいくつかの実装では、新しい集団に移される確証がある最も高い適合性を持つ個体のエリート戦略と呼ばれる方法が使用されます。エリート戦略の使用により、通常、遺伝的アルゴリズムの収束を加速することができます。エリート戦略の使用の欠点は、局所的最小値にアルゴリズムが陥る可能性が高まることです。

もう一つの重要なポイントとして、停止基準の定義があります。通常、停止基準として、アルゴリズムの作動期間の最大値の制限、またはその収束性の定義が使用されます。（通常、このパラメータの安定化の際の停止にはいくつかの期間における集団の適応性の比較されます）

元の記事：スタリコフ・アレクセイ、BaseGroup Labs