さまざまな確率分布(先週の復習)

二項分布

ポアソン分布

負の二項分布

正規分布

指数分布

---

遺伝的アルゴリズム GA
進化的アルゴリズム EA

進化的アルゴリズム

進化的アルゴリズム（evolutionary algorithm，EAと略記される)は進化的計算 の一分野であり，複雑な問題，解の探索空間が広大である問題， NP-hard な問題の最適解の近似解を求めるための アルゴリズムです。 個体群ベースのメタヒューリスティックな最適化アルゴリズムです。 生殖，突然変異，遺伝子組み換え，自然淘汰，適者生存，などという概念が用いられ， これが生物進化に着想を得た操作であることから，進化論的計算などと呼ばれています。 最適化問題の解の候補群が生物の個体群の役割を果たし， コスト関数によってどの解が生き残るかを決定し， 生き残った個体群の中で交配を繰返します。その過程で，突然変異を導入します。 これによってより良い個体が生き残るという進化に似た過程が起こります。 この操作を繰り返すことにより， 最適解を得るためのアルゴリズムのことを進化的アルゴリズムと呼んでいます。

EA 工学，芸術，生物学，経済学，遺伝学，オペレーションズリサーチ， ロボット工学，社会科学，物理学，化学などの幅広い分野で応用されています。

一般的な計算の流れは，以下のとおり：

1. 解の候補を染色体（遺伝子）として表現する
2. どの染色体（遺伝子）を選ぶかを決める
3. 交叉（交配）相手を選ぶ
4. 突然変異を起こす確率を決め適用する
5. 次世代の個体数を決める
6. 上記の計算（世代回数）を繰り返す

EAには以下の4つがあります。 それぞれ得意とする分野が異なります。

遺伝的アルゴリズム: (Genetic Algorithm:GA)

EA の中で最も一般的な手法。 問題の解を探索するにあたって数値の列を使用します。 もっともシンプルな遺伝的アルゴリズムでは 2 進数が用いられます。 しかし，解決すべき問題に合わせて最適な形式が選択可能であり， 2 進数になるとは限りません。 選択，変異，交叉などの操作が実施されます。

遺伝的プログラミング: (Genetic Programming:GP)

基本は遺伝的アルゴリズムと同じです。 遺伝的プログラミングの特徴としては， 解が木構造で表現されている点が挙げられます。 このため数式やプログラムのコードを表現するときに強みを発揮する。 適応度関数はその計算能力などで評価されます。

進化的プログラミング: (Evolutionary Programming:EP)

解の適応度関数に，集団中におけるその解の優位性を表した確率的な関数を用います。

進化的戦略: (Evolutionary Strategy:ES)

解の形式が実数ベクトルで表現される点が特徴です。 また，探索を行うと同時に自己変異も用いて更新されます。

これらは適応度地形にいかなる仮定も持たないので， 進化的アルゴリズムがあらゆるタイプの問題でおどろくほどうまく機能します。 ただし，ノーフリーランチ定理という定理があって，この「ただの昼飯はない」という定理は， 「関数の近似を考える場合，一般的な関数近似機を用いれば， いかなる場合でも望むだけの精度で関数の近似が行なえる」 あるいは「特定のアルゴリズムがすべての問題に対してすぐれているわけではない」 と言うことを主張する定理です。 このことから， EA による関数近似解が真の解であることを保証するわけではないことに注意が必要です。

また， EA は進化と自然淘汰の仮説の正当性を実験検証するのにも使われてきました。 EA を用いることで，おどろくほど短時間の繰り返しで解が求まるからです。 ただし，EAは一般に小進化に限定されます （もちろん，大進化のシミュレートする試みもなされています）。

ちなみに「大進化」とは，

大進化とは、 長期間にわたる遺伝子頻度の大規模な変化であり、通常その結果、 種分化や新種への進化をもたらす。 小進化の過程が観測可能であるのに対して、 大進化は化石記録や、現存している生物の形質、 遺伝子の情報（DNA）から推論するしかないと考えられていたため、 小進化のプロセスでは大進化を説明できないと考える人がいた。(ウィキペディア「進化」より)

EA への批判としては， 遺伝子型 genotype と 表現型 phenotype の区別が不明確である点が挙げられます。 実際，受精した卵細胞は， 胚発生という複雑なプロセスを経て円熟した表現型になります。 この点を実現したアルゴリズムは少ないと言って良いでしょう。 これが実現されれば，生物の進化可能性も改善されると考えられています。 人工胚発生や人工発生システムの研究では， これらの懸念への対処が行なわれています。

計算量とアルゴリズム

計算手順のことをアルゴリズム algorithm と言いますが （日本語では算法と訳されます）。生物学に限らず，コンピュータに計算させるには， このアルゴリズムが決まっている必要があるわけです。 最適化問題を解くアルゴリズムは多数提案されていますが， 複雑な問題になればなるほど，CPU の処理速度やメモリ容量が問題となります。

効率の良いアルゴリズムのある問題は，多項式時間帰着可能問題，あるいはクラス P と言います。 クラス P の問題はデータが増えるに従って，計算時間が増加しますが， どのくらい計算時間が増加するのかによって 2 乗のオーダー，階乗のオーダー， などになります。 いかなるオーダーに属するにせよ，どのくらい計算時間がかかるのかを計算することができます。

これに対して計算の手順が簡単には決まらない問題が存在します。 このクラスの問題をクラス NP と言います。

ナップザック問題

ナップザック問題とは，NP (Non-deterministic Polynomial) 問題と呼ばれる問 題のクラスに属します。

容量 C のナップザックがあり， この中に n 個の品物を効率良く詰めるにはどうするかという問題です。 各々の品物は容積 c_i であり， その価値は p_i と表したとき， ナップザックの容量 C を超えないという制約のもと， いくつかの品物をザックに詰め， 入れた物品の価値の和を最大化するにはどの品物を選べばよいか」という問題です。

i 番目の物品をザック入れることを x_i=1， 入れないことを x_i=0 で表わせば， 物品の数を m とすれば，

であり，かつ

x∈{0,1} (i=1,2,...,m) と表現することができます。

遺伝的アルゴリズム

遺伝的アルゴリズム（Genetic Algorithm，GA）とは，1975年にミシガン大学の John Henry Holland によって提案された近似解を探索する ためのアルゴリズムです。偶然（突然変異 mutation）の要素でコンピュータの 挙動を制御する進化的アルゴリズムの一つです。その中でも最も一般的に使用されている。

遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数 用意し，適応度の高い個体を優先的に選択して交叉（組み換え）， 突然変異と交配の操作を繰り返しながら解を探索する。 適応度は適応度関数によって与えられるのが一般的です。

この手法の利点は，評価関数の微分可能性や単峰性などの知識がいらないことです。 必要とされる条件は評価関数の全順序性と， 探索空間が位相性（トポロジー）を持っていることだけです。 また，遺伝子の表現の仕方によっては， 組合せ最適化問題や NP ハードな問題にも適用可能です。

アルゴリズムの流れ

遺伝的アルゴリズムは一般に次のような計算手順で実施されます。

1. 個体数 N 個が入る配列を 2 つ用意する。 この二つの集合を「現世代」，「次世代」と呼ぶ。
2. 現世代に N 個の個体をランダムに生成する。
3. 評価関数により，現世代の各個体の適応度を計算する。
4. ある確率で次の 3 つの動作のどれかを行い，その結果を次世代に保存する。
   • 個体を二つ選択して交叉を行う。
   • 個体を一つ選択して突然変異を行う。
   • 個体を一つ選択してそのままコピーする。
5. 次世代の個体数が N 個になるまで上記の動作を繰り返す。
6. 次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。
7. 3. 以降の動作を最大世代数 G 回まで繰り返す。求める解は「現世代」の中で最も適応度の高い個体である。

個体の表現

よく知られているとおり，地球上の生物の遺伝情報は， アデニン，シトシン，グアニン，チミンと呼ばれる塩基，すなわち， デオキシリボ核酸 DNA によって構成されています。 すなわち 4 通りであって，アナログ情報ではなく，デジタル情報との親和性が高いのです。 このことが進化論的計算，遺伝的アルゴリズムがコンピュータサイエンスの分野で， 特に発展してきたことと密接に関連します。

遺伝子の長さが m であれば 4^m とおりの表現が可能 です。遺伝的アルゴリズム GA では， 最適化すべき対象をベクトル表現して x={x₁, x₂,...,x_m} と表現します。生物学からのアナロジーにより，x_i が取りうる値を対立遺伝子， 各遺伝子が入る染色体の場所を遺伝子座と呼びます。

ナップザック問題を考えれば，i 番目の物品をザックに入れることを x_i=1, 入れないことを x_i=0 と表現できます。

個体の適応度

GA の考え方に従えば，各個体は（その遺伝情報ゆえに）環境への適応度が異なり， その適応度に応じて自然選択されます。 適応度の高い個体は，次の世代へ子孫をより多く残し， 反対に適応度の低い個体は子孫を残すことができなくなります。 GA ではこのような考え方により， 各個体に適応度 f を付加します。 最適化すべき目的関数 g(x) が最大となるような適応度を持つ個体が選ばれます。

ナップザック問題の場合には， 制約条件としてザックの容量を越えないという条件が存在するので， 容量をオーバーした個体は致死遺伝子(lethal gene)として， 低い適応度を与えるなどの工夫が必要になります。

遺伝的操作

遺伝的アルゴリズムでは一般的に次のような操作が用いられます。

1. 選択（淘汰，再生）
2. 交叉（組み換え）
3. 突然変異

交叉する確率を交叉率，突然変異する確率を突然変異率と呼びます。 突然変異率は低く抑えられることが普通です。 このことは，突然変異がまれにしか起こらないという生物学的事実と 対応していることを意味します。 またこのようなアルゴリズムの流れから，

です。

選択

選択とは生物の自然淘汰をモデル化したものです。 おのおのの適応度にもとづいて，個体を増やしたり減らしたりする操作をさします。 選択のアルゴリズムには以下のようなものがあります。

ルーレット選択

ルーレット選択とは，個体 i の適応度を f_i とし， 個体 i の選択確率を p_i としたときに，次式，

に従って選択する方式です。例えば，以下の表のように選択確率を決めます。

この方式はホランドが最初に提案したときに使われた選択方式であるとされており， 最も有名な選択方式です。ただし，適応度に負の数があるときには使えないので， 全適応度を正の値に変換するなどの工夫が必要になることがあります。 さらに，各個体の適応度の差が著しい場合， 適応度の高い個体のみが選択される確率が高くなり， 局所最大（最適化問題でいうところの局所最小）に収束してしまい， 最適解を求められない場合があるとされています。

ランキング選択

ランキング選択は各個体を適応度によってランク付けして，

1 位なら確率 p₁,
2 位なら確率 p₂,
3 位なら ....

というように，ランクごとにあらかじめ確率を決めておく選択方式です。 この方法は，ルーレット選択と違い選択確率が適応度の格差にあまり影響されません。 しかし，これは逆に，適応度にあまり差がない個体間でも選択確率に大きな差が生じる可能性があるということを意味します。

トーナメント選択

トーナメント選択とは， あらかじめ決めた数（トーナメントサイズ）だけ集団の中からランダムに個体を取り出し， その中で最も適応度の高い個体を選択する方式です。 トーナメントサイズを変更する事で選択圧をコントロールできるという特徴があります。 しかし， 初期収束による局所（的）最適解に陥りやすくなるという欠点も併せもっています。 トーナメントサイズを大きくすると， そのなかで最大の適応度を持つ個体だけが選ばれることになり， 適応度の低い個体が生き残ることが難しくなります。 つまり集団の中がエリートばかりになり易いということを意味します。

その他

上記の選択とは別に適応度が高い個体（エリート）を一定個数， 次世代に残すという方略が用いられることがあります。これをエリート選択と呼びます。 エリート選択をとることにより，選択によって解が悪い方向に向かわないということが 保証されます。すなわち，適応度の最大値が下がらないことを意味します。 しかし，これも， エリートの遺伝子が集団の中に広まりすぎて解の多様性が失われるという問題を持っています。

交叉（組み換え）

交叉（組み換え）とは，生物が交配によって子孫を残すことをモデル化したものです。 個体の遺伝子の一部を，他の個体の遺伝子と入れ換える操作です。 交叉はその性質上，最も重要な遺伝的操作と言うことができます。 交叉のアルゴリズムには次のようなものがあります。

例として次の二つの個体を交叉する場合を考えます。

個体A: 0100111010
個体B: 1010101011

一点交叉

遺伝子が交叉する場所（交叉点）をランダムに 1 箇所選び， その場所より後ろを入れ換える方式。 ホランドが最初に提案したときの交叉方法であるとされています。 現在ではあまりもちいられていません。効率が悪いからです。

個体A: 01001｜11010 → 01001 01011
個体B: 10101｜01011 → 10101 11010

二点交叉

交叉点をランダムに 2 箇所選び， 2 つの交叉点に挟まれている部分を入れ換える方式。

個体A: 010 | 01110 | 10 → 010 01010 10
個体B: 101 | 01010 | 11 → 101 01110 11

多点交叉

3 点以上の交叉点をもつ方法を多点交叉と言います。 しかし， 多点交叉は二点交叉と下記の一様交叉のどちらかよりも良い値が出ることはないとされ， あまり使われません。

一様交叉

各要素ごと独立に 1/2 の確率で入れ換える交叉方法です。 後述するヒッチハイキングの問題をおさえることが可能であるとされています。 一般に 2 点交叉が得意とする問題を苦手とし， 逆に，二点交叉が苦手とする問題を得意とするような性質があることが知られています。

個体A: 0 1 0 0 1 1 1 0 1 0 → 0 0 1 0 1 1 1 0 1 1
個体B: 1 0 1 0 1 0 1 0 1 1 → 1 1 0 0 1 0 1 0 1 0

突然変異

突然変異は，生物に見られる遺伝子の突然変異をモデル化したもので， 個体の遺伝子の一部を変化させる操作を指します。 局所最適解から抜け出す効果があります。 ランダムに選んだ任意の遺伝子座において， 遺伝子の値を対立遺伝子に置き換えるます。たとえば対立遺伝子が {0,1} であるとき

1010

の2番目の遺伝子座に変異が起きたとすれば

1110

のようになります。対立遺伝子が n 個の整数で表現されていれば， 0 から n までの乱数を使って置き換えるというような操作がなされます。 %他にも遺伝子座の位置を変更するなどの方法がとられる。

突然変異の確率は 0.1%〜1% 程度であり，高くても数 % 程度にされます。 確率が低すぎると，局所最大値からなかなか抜け出せなくなり，逆に高すぎるとランダム 探索になり解の探索効率が落ちてしまいます。

GA の問題点

GA は，さまざまな問題に適用できる手法ですが， 問題と使う方式によっては上手くいかない場合があります。 よく起きる（よく指摘されている） GA の問題点は以下のようなものです。

初期収束

初期収束とは， 最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれた場合， その個体の遺伝子が集団中に爆発的に増えて，解の探索が早い段階で収束してしまう現象です。 ルーレット選択の設定が甘い場合や，突然変異の効果が上手く表れないときに生じやすい とされています。

対策としては，ルーレット選択を使う場合の適切な設定や， 適用する問題に合わせて効果的になるように突然変異の操作を変更したり， 突然変異率を増やしたり， または集団の数を増やすなどの設定を行うことが行われます。 しかし，明確な解決法というものはなく，試行錯誤的に各パラメータを設定しながら 解を見出すということが行われます。

ヒッチハイキング

例えば最適解が

-101-

という問題があるとします。このとき

-111-
-000-

という二つの個体が交叉して最適解を得る確率を求める場合， 交叉の方式が 2 点交叉では，交差点が，

-1|1|1- → -101-
-0|0|0- → -010-

で最適解が得られます。このとき遺伝子型の長さを l とおくと， 最適解が得られる確率 p は

と求められます。 これは l が長くなるにつれ加速度的に確率が低くなります。 つまり l が長いとほとんどの確率で上記の 2 つの個体は最適解と一致しないビットを新しく生成した個体に受け継がせてしまうことになります。 このように最適解と一致するビットの近くにいて最適解の生成を妨げる現象を ヒッチハイキングといい，そのビットをヒッチハイカーといいます。

このヒッチハイキングは一様交叉によって防ぐことができます。 一様交叉は各要素が独立で交叉するので，上の場合は

-111- → -101-
-000- → -010-

か

-111- → -010-
-000- → -101-

で最適解を得ます。このとき，最適解を生成する確率は

であり，この確率は l の長さが長くなっても変化しません。

GA の理論

遺伝的アルゴリズムは他のメタヒューリスティックス手法に比べて， 主要な探索手段である交叉が局所探索ではないことに大きな特徴があります。 この性質のため，GA は提唱されて以来有効性に関して疑問が投げかけられてきました。 しかし GA の有効性を理論的に検証するのは難しいという事実から理論的考察がすすまなかった， という事実があります。

1980年代後半になって，ようやく GA の理論的な考察が行われるようにりました。 ここではその基本的な部分をいくつか紹介します。

SGA

SGA とは Simple Genetic Algorithm（単純 GA）のことです。 GA を通常のまま解析するとあまりにも複雑なので， 処理を単純にした GA を用いて解析を進めるのが一般的です。 SGA は具体的には

1. 遺伝子表現は 1 と 0 のみ
2. ルーレット選択
3. 一点交叉
4. 突然変異は1箇所の遺伝子座の値を反転させる

という遺伝的アルゴリズムです。

本日はこれを実習してみましょー。いつものとおりファイルをコピーして cd してから

./SGA.pl

とすると SGA のシミュレータが走ります。

スキーマ理論

スキーマ理論とは，遺伝子型の部分集合（スキーマ） の有無が適応度に大きな影響を与えることを前提とした解析理論です。 スキーマとは例えば

H = * * 0 1 * 1 *

のような形で表現します。ここで * （アスタリスク）はワイルドカードのことであり， この部分には 0 と 1 のどちらが入っても良いことを意味しています。 このとき，

0 1 0 1 1 1 0
1 1 0 1 0 1 0

のように * 以外の部分が一致している遺伝子型を持つ個体のことを 「スキーマ H を含む個体」と表現します。

スキーマ理論特有の用語として，定義長とオーダがある。 定義長とはスキーマの一番左のアスタリスク以外の文字と一番右のアスタリスク以外の文字との距離 のことを言います。これは δ(H) という形で表現します。 上記の例の場合は δ(H)=4 となります。

オーダとは，スキーマ内のアスタリスク以外の文字の数のことを言います。 これは O(H) という形で表します。上記の例の場合は O(H) = 3 であると言います。

スキーマ定理と積み木仮説

スキーマ定理とは，ある世代 t でスキーマ H を含む個体の数を m(H,t) と表したとき，次の世代のスキーマ H を含む個体の数 m(H,t+1) は SGA において 以下のように表すことができるという定理です。

ここで，f(H) はスキーマ H を含む個体の適合度の平均， は全個体の適合度の平均， l は遺伝子型の長さ， p_c, p_m は交叉率と突然変異率です。

このとき，p_c >> p_m, δ(H) > O(H) であるので， 括弧内の O(H)... p_m はほとんど無視できます。 そのため，この定理は

• 定義長 δ(H) が小さく
• f(H) が全体の平均より常に大きい

となるようなスキーマ H の数は，指数関数的に増大していくことを表しています。

ここから， 上記の条件を満たすスキーマを保持することが最適解を導くことになるような問題に対しては， GA は最適解を導き出すことが可能であるという考え方ができます。 このようなスキーマを積み木（Building Block）といい， この考え方を積み木仮説といいます。

遺伝的プログラミング

遺伝的プログラミング（Genetic Programming, GP）とは， 遺伝的アルゴリズムを拡張したものです。

遺伝的プログラミングは1990年にジョン・コザ（John Koza）によって提案されました。 他の進化的アルゴリズムの主要な方法論が， 同時期に提案され独立して研究が進められていたのに対して， 遺伝的プログラミングは最初から遺伝的アルゴリズムの拡張として提案されました。

具体的には， 遺伝的アルゴリズムにおける遺伝子型の表現が主に配列であるのに対して， 遺伝的プログラミングでは木構造を用います。 このため，遺伝的アルゴリズムでは表現できなかった数式やプログラムのコードなど， 構造を持ったデータを表現することができます。

GP のアルゴリズムの内容

当然ですが， 遺伝的プログラミングの探索の流れは遺伝的アルゴリズムと同じです。 ただし，遺伝子型の表現方法が違うため， 交叉や突然変異の方法が少しだけ異なります。

解の表現方法

遺伝的プログラミングでは遺伝子型の表現に木構造を使うため， 取り扱うことのできる問題が，遺伝的アルゴリズムとは異なってきます。 遺伝的プログラミングの適用分野としては，関数の同定問題や， ニューラルネットワークや，電子回路の設計，あるいはロボットの制御などがあげられます。 解の表現は，例えば関数同定問題なら解は関数であるために， 配列でこれを表現することは難しいのですが， 下図（ウィキペディアより）のような，

という木構造であれば x × (2 - x ) を表しているというように， 簡単に表現することができます。

交叉

交叉は主に部分木の取り換えという形で行われます。 具体的には下記の画像のような操作が行われる（ウィキペディアより）。

この例では関数 3 × ((x × 4) + x ) と関数 ( 3 + x ) - ( 2 / (x × x )) になる木を交叉させて， 関数 3 × (x × x) と 関数 (3 + x) - ( 2 /((x × 4) + x)) となる木が生成されたことを表しています。 交叉を行う部分木の場所は， ランダムに決めます。

進化戦略

進化戦略（Evolution Strategy, ES）は， 実数関数の非線形最適化問題を解く手法として， 1960 年代頃にベルリン工科大学の Rechenberg と Schwefel により開発されました。

遺伝的アルゴリズムと同時期に提案され， 内容も「進化的な要素を関数の探索に用いる」という全く同じコンセプトです。

進化的プログラミング

人工知能の生成を意図した学習過程として， シミュレーションされた進化を使った Lawrence J. Fogel が1960年に最初に使った用語です。 Fogel は予測機として有限状態機械を使い，それを発展させました。

その後，彼の息子の David B. Fogelにより， 実数関数の最適化問題を探索する手法に拡張され， 進化的戦略と類似した方法に発展した。

進化的プログラミングの中心となるのは突然変異である。 親ベクトルに対してランダムな変化を加えて子ベクトルを生成し， それらを評価して， ランダムに個体を選んで適用度を比較します。 これによって次の世代を選び，解が収束するまでこれを繰り返します。

現在，進化的プログラミングは他の3つの方法論に比べると特に決まった構造が無く， 進化的コンピューティング全般を漠然と指す用語となっています。 進化的プログラミングと進化的戦略を区別することは困難になってきていると言ってよいでしょう。

参考文献

• 伊庭斉志. (1994). 遺伝的アルゴリズムの基礎. 東京: オーム社.
• 伊庭斉志. (2002). 遺伝的アルゴリズムと進化のメカニズム. 東京: 岩波書店.
• 梅原嘉介, & 小川敬治. (2007). 進化ゲームと遺伝的アルゴリズム. 東京: 工学社.