本記事の対象者
- 何かしらの機械学習に興味がある人
- 勾配降下法以外の機械学習に興味がある人
- 遺伝的アルゴリズムを始めたので色々と探している人
- 数学的な知識なしで機械学習を初めたい人
本記事は個人が学んで理解したことを主に記載しており、間違いを含んでいる可能性があります。
間違い等ありましたら、お教えくださいますと助かります。
本記事は座学的です。実装に関しては後日別記事に書きます。
また、各実装における収束までの世代数や最終結果、相性などの考察した結果に関しても別記事にまとめたいと思います。
概要
遺伝的アルゴリズムに関して学んだことを記していきます。
heuristicsについて簡単に説明したあと、遺伝的アルゴリズムの流れや各処理について述べています。
heuristic について
遺伝的アルゴリズムはheuristicsの１つです。
heuristicsとは解の精度は保証できないが、ある程度有用な範囲にある解を暫定的な到達点として提供するための手法です。
内容としては
- 以前の経験・結果を評価する
- 1.を元に次の戦略を考える
- 2.で考えた内容を実施する そしてまた 1.に戻る を繰り返します
トライアンドエラーに近いです。
開発者が気がついていなかった優れた解が発見される可能性もあります。
NTM1的に機能できるため、NP困難な問題に関しても取り組むことができます。
また、特定の問題のみに焦点を絞らずに汎用的に利用できるheuristicsはmetaheuristics2とも呼ばれます。
遺伝的アルゴリズムも該当しますし、他には焼きなまし法(simulated annealing)やtabu searchもmetaheuristicsな手法です。
遺伝的アルゴリズム について
遺伝的アルゴリズムは環境への適応度の最大化を目的とし、世代交代を繰り返し、その結果として優秀な個体（解）を生み出そうというものです。
その解の適用範囲としてはある集合の問題に対しての最適順列の特定から、最適値の特定まで出来ます。
最適値の特定として機械学習などの初期パラメータの設定にも使用されています。
流れとしては、
上記のようなアルゴリズムのため、遺伝子の符号化や評価関数の違いはあれど、基本的な考えに関しては汎用的に利用しやすいという利点があります。
また、遺伝的アルゴリズムでは世代として複数の解を保持して管理しています。
以降の説明では当記事でも様々なサイトに倣って問題への解の配列を染色体、そして各々の解の構成要素を遺伝子と呼びます。
(※アミノ酸まで使用している文献はありましたので、私がまだ読めてないだけで塩基やエクソンを構成単位とした文献なども普通にありそうです。)
遺伝的アルゴリズムの処理に関して
符号化
問題への解をどう遺伝子として表現するか。
二進数を使う場合や数値・文字列をそのまま使う場合があります。
二進数にて表現する場合には問題によっては、要素が取りうる状態の数を表現するのに十分なビット数をワンセットとみなし、そのセットをひとつの遺伝子として扱う必要があります。
評価関数
遺伝子の優劣を判定するための関数。
問題ごとに設定が必要で、評価結果が高いほど優秀な個体となるように設定することが多いです。
例えば...
・OneMax問題では全てを１に近づけたいので、全要素の総和
・サラリーマン巡回問題では移動距離の合計値が小さいほうが優秀なため、1 / 移動距離
などのようにします。
初期集団
染色体を内部に維持している個体を一定数集めて集団を作成します。
似たような事例の結果から初期集団を作成することもありますし、ランダムな染色体を持った個体を作成して初期集団とすることもあります。
世代交代
集団の中から２つの親を選択し、その親の染色体を交叉することにより子を生成し、世代交代をしていきます。
隔離的世代交代
世代が変わる際に完全に個体が入れ替わり、新しい世代の個体たちはその親の世代の子のみとします。
個体を全て入れ替えてしますため、似た染色体が世代毎に増大することは防げますが、優秀な染色体の引き継ぎができず、適用度の収束に時間がかかります。
継続的世代交代
一部の優秀な個体は残してそれ以外を入れ替えて世代交代とします。
優秀な個体を残しつつ世代交代をするため、優秀な染色体の保存ができ、収束の高速化が図れますが、その分近似した染色体の増大が懸念され、局所的な解に収束する可能性があります。
どちらもメリット・デメリットとあるのですが、継続的世代交代の方が収束・適用度とともに優秀な気がします。
ただ、個人的には継続的世代交代は同一個体がずっと生き続ける可能性もある訳で、少し違和感を覚えます...
選択
子孫を残す・世代交代をするなどのタイミングで親の選択が行われます。
選択は、全くの無作為にというよりは、方法により差はあれど、ある程度個体の適用度に影響されることが多いです。
そのため、優秀な個体ほど子孫を残しやすくなります。
また、使用する選択形式によって優秀な個体の生成速度や局所解への陥りやすさが異なりますので様々なパラメータを調整して行く必要があります。
エリート選択
優秀な個体を残すため、適用度の高い順に個体を選択します。
優秀な遺伝子を保存できるため、適応度の最大値を保証できますが、集団内での個体が一定数固定さえてしまうため、染色体の多様性を損ね、局所解に陥る可能性があります。
ルーレット選択
個体の選択をある程度無作為に行います。
個体の選択されるパーセンタイルは適用度に依存し、適用度の高い個体ほど選択される確率が高くなります。
完全な無作為ではないので、エリート選択ほどには局所解へ収束はしないものの、個体間の適用度の差によっては優秀な個体のみが選択されてしまい、依然として初期収束や局所解への収束の可能性は残ってしまいます。
ランキング選択
ルーレット選択を少し改変したのがランキング選択となります。
個体の選択されるパーセンタイルのテーブルを予め作成しておき、個体の適用度が高い順に大きいパーセンタイルが割り振られていきます。
パーセンタイルテーブルを予め用意しておくことでルーレット選択ほど選択が個体の適用度依存でなくなります。
しかし、パーセンタイルの作成に際に、個体の適用度による優先度が低すぎると解が収束しませんし、高すぎると局所解への収束の可能性が高くなってしまいます。また、各パーセンタイルの差の付け方によって、本来適用度的には差は無いものが、パーセンタイルに紐付けられた際に有意な差を持ってしまう可能性もあります。
トーナメント選択
トーナメント選択ではトーナメントサイズ分の個体を集団から無作為に取り出し、その中で最も優秀な個体を選択します。
この方法でもトーナメントグループの作成方法は無作為のため、優秀な個体の選択される確率は高いものの、劣勢な個体の染色体も保存できる確率が残り、染色体の多様性は確保できます。
しかし、多様性という意味では最劣勢個体は選択されませんので、パーセンタイルテーブルの作成など煩雑なことは多いですが、ランキング選択の方が多様性の確保はしやすいかもしれません。
世代交代の方法の継続的世代交代は、エリート選択にルーレット選択やトーナメント選択・ランキング選択を合わせたものになります。
交叉
子形成の際には親同士の染色体を組み合わせ、新たな遺伝子を作成してそれを子に引き継がせます。
その際の染色体の組み合わせ方法が交叉パターンになります。
交叉方法によって多少の優劣はあるものの、対象の問題における適度もあるため、一概にはどれが良いとは言いにくいとこではあります。
色々な方のサイトや文献を参考にすると、簡単な例や解の精度を求めない際には簡易性を重視して点交叉や一様交叉を用いた遺伝的アルゴリズムを紹介しているところが多く見られました。
また、点交叉・一様交叉は染色体内での遺伝子重複の可能性があるため、染色体の唯一性が染色体中で確保できません。
そのため、サラリーマン巡回問題のように各都市を一度しか訪ねてはいけない場合などには、順序交叉・一様順序交叉・一様位置交叉を用いる必要があります。
それに対してOneMax問題やナップザック問題では遺伝子を唯一性を確保する必要は無く、それぞれの遺伝子座での表現系のみに意味があるため遺伝子の唯一性をキーに用いた交叉方法は使えません。
点交叉
親の染色体にて遺伝子座を一つ決定し、その前後にて染色体を分割、親同士で染色体の交換をして子の染色体を作成します。
例を挙げると以下の様になります。赤いアルファベットが選択された遺伝子座でその遺伝子以降を交叉に用いています。
(下記例では親１の遺伝子を小文字、親２の遺伝子を大文字で表記してますが、本質的には差分はなく、理解の容易化のためだけに表記に差分をつけています。)
親１： a b b a b b a a b a b
親２： A A B A A A B B A A B
↓
子１： a b b a b A B B A A B
子２： A A B A A b a a b a b
上記方法では単点ですが、複数点においてその都度交換させる場合もあります。
点交叉では親の染色体が極端に崩れて子に引き継がれる事が少ないため、優秀な箇所を崩さずに受け継げる確立が高くなります。
親の染色体同士が優れた適用度を互いに保持している場合には有用な場合もありますが、初期の場合などでは適用度を上げることが難しく、収束に世代数が多くかかります。
一様交叉
子供の染色体を作成する際に、どちらの親の遺伝子を引き継ぐかを確率的に結成するアルゴリズムです。
親１： a b a a b a b a a a b
親２： A B B A B B A B B A B
↓
仮に子１が親１の遺伝子を引き継ぐ確率が0.5だったとし、マスクが以下だったとします。
0 0 1 0 1 0 0 1 0 1 1
0: 親１の遺伝子を子１が引き継ぐ 1: 親１の遺伝子を子２が引き継ぐ
↓
子１： a b B a B a b B a A B
子２： A B a A b B A a B a b
循環交叉
まず親の遺伝子間で閉循環を作成します。親の遺伝子座を決めたら、その遺伝子を子供に引き継ぎ、次に引き継ぐ遺伝子は対する親の遺伝子座での遺伝子を自身の染色体内で探索しその箇所にその遺伝子を引き継ぐ、の作業を対する親の遺伝子が自身の最初の遺伝子に一致し、循環が閉鎖するまで繰り返します。
その後はまだ未確定の箇所の遺伝子に親の遺伝子を引き継いで埋めて行きます。
親１： a c h e g d b f
親２： C H G E A B F D
↓
循環しながら子の染色体の作成
未確定の遺伝子はxで表しています
親１の最初の遺伝子をスタート点とし、a → C → c → H → h → G → g → Aと循環しますので、
親１の遺伝子を子１に、親２の遺伝子を子２に引き継がせます。
子１： a c h x g x x x
子２： C H G x A x x x
↓
最後の空いた隙間に、上記循環の際に引き継いでいない方の親の遺伝子を引き継いで行きます
子１： a c h E g B F D
子２： C H G e A d b f
順位交叉
親の染色体にて遺伝子座を一つ決定し、その前の染色体はそのまま子に引き継ぎ、その後の染色体は他方の親の遺伝子の出現順序に従って配列し直して引き継ぎます。
親１： a c h e | g d b f
親２： C H G E | A B F D
↓
子１： a c h e G B F D
子２： C H G E a d b f
一様順序交叉
まず一様交叉同様にマスクを作成し、そのマスクに該当する箇所の遺伝子を片親(親B)から取得します。
子染色体形成の際に、他方の親(親A)の遺伝子を順々に子の遺伝子に引き継ぐが、引き継ぐ遺伝子が親Bから抽出した遺伝子の中に含まれる場合のみ親Bから取得した遺伝子を取得した順に従って引き継がせます。
親１： a c h e g d b f
親２： C H G E A B F D
↓
マスクが以下のようだったと仮定する
0 1 0 0 0 1 0 1
0: 親１の遺伝子を引き継ぐ 1: 親２から取得した遺伝子を引き継ぐ
↓
マスクに従って親２のコドンを抽出する
{ H, B, D }
↓
子： a c H e g B D f
一様位置交叉
この手法でも一様交叉同様にマスクを作成し、そのマスクに該当する箇所の遺伝子を片親(親B)から取得します。
子染色体形成の際に、まずマスクの箇所の遺伝子には親Bから取得した遺伝子を使用し、それ以外の空いている箇所には親Aの遺伝子のうち、親Bから取得した遺伝子に被らない遺伝子を、出現順に使用していきます。
親１： a c h e g d b f
親２： C H G E A B F D
↓
マスクが以下のようだったと仮定する
0 1 0 0 0 1 0 1
0: 親１の遺伝子を引き継ぐ 1: 親２から取得した遺伝子を引き継ぐ
↓
マスクに従って親２の遺伝子を場所を保持したまま子に引き継がせる
子： x H x x x B x D
↓
残りの箇所に親１の遺伝子を埋めて行きます
子： a H c e g B f D
サブツアー交換交叉
両親の染色体内で共通した組み合えわせの遺伝子を有する箇所は優れた組み合わせである可能性が高いことに着目した方法です。
親の染色体内で共通した遺伝子の組合せの箇所を探し出し、それを親同士で交換する事により交叉とする方法です。
また、その順列を逆にした遺伝子列でも子染色体を作成して、計４種類の子染色体を作成します。
親１： a c h e g d b f
親２： C H G E A B F D
↓
共通の組み合わせの遺伝子列を探す
親１： a c h e g d b f
親２： C H G E A B F D
↓
共通している箇所(今回は青文字の箇所)を利用して交差する
子１： a c H G E d b f
子２： C h e g A B F D
子３： a c E G H d b f
子４： C g e h A B F D
子５： a c h e g B F D
子６： C H G E A d b f
子７： a c E G H D F B
子８： C g e h A f b d
上記例では探索する部分集合の最大数を３としています。
最大数を５にすれば a c h e g と C H G E A に一致が見られますが、最大数を大きくすればするほど部分集合の特異性が失われますので、最大数に関しては大きすぎず、小さすぎずな値を問題ごとに模索してください。
染色体内の遺伝子数に一定の値をかけてそれを最大数にしてもいいかもしれません。
また、上記例ではそれぞれの発見箇所の遺伝子を入れ替えたもの及び反転させて入れ替えたもののみを想定しており、発見した共通集合をそれぞれ独立に処理しておりますが、文献によっては共通集合を独立させず、混ぜて処理をしているものもありました。
サブツアー交換交叉では全ての共通集合を検索するため、処理に$O(n^5)$を要するため、その改善策として完全サブツアー交換交叉3というのも提案されています。
サブツアー交換交叉では部分集合としてサブツアーを検索していましたが、完全サブツアー交換交叉ではサブツアーの検索に方向性をもたせています。つまり同一の並びの箇所を探しています。
上記例に当てはめますと e g と D E という箇所が該当します。
変異
子供の生成の際、親同士の単純交配だけでは遺伝子の多様性が保てなくなるため、稀に変異を起こさせます。
変異によって遺伝子の配列に乱れを生じ、偶然性を入れます。
変異の種類に応じては染色体長が変化するため、その後の処理において対応する必要が出てきます。
染色体長に異常があるものは個体を評価・子孫形成の際に
- 評価を低くし、次世代に引き継がせない
- ある特定の染色体長までは許容するが、一定値を超えたら引き継がせない
- 特に染色体長には関与せずに評価をする
- 染色体長を規定の長さになる様にカットする
などとする必要があります。
変異の種類によっては遺伝子の染色体内での一意性を確保できないために、命題に反する可能性もあります。
置換
無作為に選ばれた遺伝子を対立遺伝子に置き換えます。
置換する対象の遺伝子の個数は固定もしくは無作為、全遺伝子が対象など様々です。
対立遺伝子への置き換えが必要なため、対立遺伝子が定義できない場合では使用できません。
交換
無作為に選ばれた２つの遺伝子を入れ替えます。
挿入
遺伝子を無作為に挿入します。染色体長に変化があります。
摂動
摂動って言いますと粒子や天体のことを思い浮かべますが... 遺伝的アルゴリズムも同様である値に外部からの力により微少な乱れを生じさせています。
無作為に選ばれた遺伝子の値に微少値の加算もしくは減算を行います。
逆位
無作為に選ばれた一連の遺伝子の並びを反転させます。
転座
無作為に選ばれた一連の遺伝子を他の染色体上の遺伝子座に移動させます。
欠損
無作為に遺伝子座を選定し、その遺伝子座にある遺伝子を染色体上から削除します。
結構長くなってしまったので... ヒッチハイクや初期収束などに関しては別記事に書こうと思います。
参考学習サイト
遺伝的アルゴリズム（Genetic Algorithm）を始めよう！
静岡理工科大学情報学部コンピュータシステム学科・知能インタラクション研究室