ソフトコンピューティング

ソフトコンピューティング
第３回
遺伝的アルゴリズム（ＧＡ）
1
遺伝的アルゴリズム（ＧＡ）とは？
 遺伝的アルゴリズム（ＧＡ）とは、解探索ア
ルゴリズムである
 ソフトコンピューティングの代表選手
→解探索（解探索問題）とは？
2
解探索問題とは？

与えられた答えの候補の中から、制約条件を満たしつつ
最も評価の高いものを探す






例：ディーゼルエンジンの多目的効率化
評価：NOxの量＋CO2の量＋使用燃料の量（少ないほど良い）
解の候補（解空間）：燃料噴射タイミングx，排気還流量y，触媒
温度z
制約条件：出力 100ps 以上
連続系の場合：ある関数の最大値を探す
離散系の場合：最高の組み合わせを探す
3
ＧＡが効く解探索問題

離散系の解探索問題
（特に組み合わせ最適化問題）

解の候補同士の間に関係があまりない

遺伝子CGATと生じる形質は直接関係ない
→変化方向が計算できない

非常に複雑な連続系の解探索問題
非線形関数の場合、最小値（最大値）を式で表せない
ことが多い
→探さないといけない

4
遺伝的アルゴリズムとは
 GA
(genetic algorithm)
 規模の大きな問題の解探索を行う手法。
 生物の「適者生存」がベースアイデア。
 良い親（解候補）の特徴を組み合わせると、よ
り良い子（解候補）が現れることを期待する。
 様々な発見的手法のオペレータを含む。
 結果は初期状態に依存
 最適性の保障なし。
5
ＧＡの一世代
準備
①遺伝子のコード化、個体数決定、評価関数決定
②淘汰と複製
繰り返し
（一世代）
③交叉
④突然変異
6
ＧＡの概略
①遺伝子のコード化
例：燃料噴射タイミング 3bit，排気還流量 2bit, 触媒温度2bit
1001001
8段階 4段階 4段階
評価：１０分間運転時のNOx, CO2, 消費燃料量を
シミュレータで推測
拘束：出力100ps以上
7
ＧＡの概略
初期化：コードをランダムに生成
1011010
1111010
1011011
1111011
1011011
0011010
1000111
0011010
1000111
1011000
個体総数（ポピュレーション）は決めておく
8
ＧＡの概略
②淘汰と複製：「良さ」を評価、点数に応じて淘汰・複製
1011011
1011010
90
83
1111011
66
1011011
72
1000111
70
良さ＝適合度（点数）
9
ＧＡの概略
③交叉：親を選んで子を作る
1011010
1011010
1111010
1011011
1011011
1011011
1011011
1000111
1011111
遺伝子の一部を入れ替える
1000011
10
ＧＡの概略
④突然変異：遺伝子を突然変える
1011110
1011010
1111010
1011011
1011011
1011011
1011011
1000011
1000111
1011111
再び②に戻る
12
淘汰と複製 (Selection)
•
•
•
個体数を一定に保ち、優秀な個体（＝良い
解）に収束させていくためのプロセス
「良さ」は事前に決めておいた「適合度」関数
の値で決める
淘汰と複製はセットで考えられるのが普通
大きく２種類の考え方がある
 適合度の低い個体でも生き残るチャンスがある
 適合度の低い個体は必ず死ぬ
13
（１）ルーレット選択法
適合度の低い個体でも生き残る可能性がある
•
•
•
•
適合度に応じて、面積の異なる「ルーレット」を作る
適合度が大きいほどルーレット上の面積も大きい
ダーツを投げて、当たったところの個体を複製
個体数分ダーツを投げる
（実際には乱数を使って決める）
個体iの適合度
複製確率
pi 
f ( si )
N
 f (s )
j
j 1
全個体の適合度の和
14
（２）期待値選択法
適合度の低い個体は生き残れない
•
•
•
適合度を個体数で割り、「期待値」を算出
期待値に応じた（四捨五入など）数に複製
個体数の少ないＧＡに適する
適合度
6
1
10
11
17
32
4
12
5
2
期待値
0.6
0.1
1.0
1.1
1.7
3.2
0.4
1.2
0.5
0.2
再生数
1
0
1
1
2
3
0
1
1
0
個体数１０の場合の例
15
（３）ランキング選択法
適合度の低い個体は生き残れない
•
•
適合度の高い順にランキング（順位付け）
順位に応じた数を複製する
順位
1
2
3
4
.
.
.
複製数
個体 5
個体 2
個体 8
個体 1
.
.
.
10
9
8
7
.
.
.
10
6
4
3
.
.
.
(線形)
(非線形)
16
交叉 (Crossover)
•
•
•
２つの親個体の遺伝子を入れ替えて子を作る
親の遺伝形質（その解の特徴）を引き継ぐことが望ましい
入れ替え方でいくつか種類がある
（１）単純交叉（１点交叉、Simple Crossover）
親１： 11000|0001
親２： 10111|0100
子１： 110000100
子２： 101110001
遺伝子入れ替え区切りはランダムに決める
17
（２）多点交叉 (Multipoint Crossover)
親１： 11|0000|001
親２： 10|1110|100
子１： 111110001
子２： 100000100
親１： 11|000|000|1
３点交叉 親２： 10|111|010|0
子１： 111110000
子２： 100000101
２点交叉
（３）一様交叉 (Uniform Crossover)
マスクパターンを使う
親１
親２
110000001
101110100
マスク
101101101
子１
子２
100010001
111000100
18
突然変異 (Mutation)
•
•
ランダムに遺伝子の内容を変える
変えすぎるとランダムサーチになってしまう
<1011101000> → <1001101000>
突然変異の例
19
ＧＡのキモ
 致死遺伝子：実行不可能な（制約条件を満た
せない）コード
 コード化：個々の解の特徴をうまく表現
 交差・突然変異：致死遺伝子を発生させない
20
適用例
図の関数 f(x)の最大値を与えるxを求める
要求精度 :
10-5
f(x) = x sin (10x) + 2.0
(-1.0≦x ≦ 2.0)
21
コード化
要求精度 10-5でxを調べるために、22ビットの２進数でコード化
１つ１つの遺伝子は、xのある値に対応する
s1=<1000101110110101000111>
xの範囲を考えて
<0000000000000000000000>=-1.0
<1111111111111111111111>= 2.0.
初期状態では、ランダムに個体（遺伝子）を生成する
22
適合度
f(x) が大きければ良いので
ある遺伝子に対する関数値 f(s*) を適合度とする
s1=<1000101110110101000111>
s2=<0000000111000000010000>
s3=<1110000000111111000101>
f(s1) = 2.586345
f(s2) = 1.078878
f(s3) = 3.250650 BEST
適用結果
23
真の値
1.850542
個体数 = 50, 突然変異確率 = 0.01
単純交叉、交叉確率 = 0.25
ルーレット選択
24
ＧＡアルゴリズムを組んでみよう
 第１回の問題Ｂについて、以下の項目を決
めてＧＡを完成させよう。
 遺伝子コーディング
 評価関数
 選択（淘汰）と複製方法
 交叉方法
 突然変異方法
25
行商人問題(TSP)をGAで解く
行商人問題とは
•
ある行商人が、自分の町から出発して、地図に載っている全ての町
を訪問し、また自分の町に帰ってくることを考える。
•
最も効率よく（＝移動時間が少なく）この行商をこなすためには、ど
のような順序で地図上の町を訪問するのがよいのかを答える問題
が行商人問題である。
•
地図上の全ての都市間に何らかの移動方法があり、さらにそれら全
てについて所要時間が分かっているとすると、解を求めるために必
要な情報は全て分かっていることになる。
•
しかし、最適な解を求めることは非常に困難である。
26
行商人問題の計算量
巡回順序数 =
(都市数 –1)!
2
多すぎて調べきれない→ＧＡの出番
27
問題Ｂを解くＧＡ（１）
 遺伝子コーディング
→ 都市の番号を並べたもの（番号列）
 評価関数
→ 番号列の前から順に移動距離を足し、
全て巡回し終わったときの総距離
28
問題Bを解くＧＡ（２）
 選択と再生
→ルーレット選択（何でも可）
 交叉方法
→？？？
 突然変異方法
→ランダムに番号列の数字を入れ替える
29
コード化の問題
単純に都市名（番号）の列を遺伝子にしてみると・・・
1
2
5
4
3
6
7
8
s1=<12345|6789>
s2=<19283|7465>
s’1=<12345|7465>
s’2=<19283|6789>
9
（致死遺伝子）
単純交叉が適用できない
交叉方法を変えなくてはいけない
30
行商人問題用交叉法
任意の遺伝子間で交叉を行ってもキチンと実現可能な
解を出すための交叉法が複数提案されている
•
部分一致交叉 (Partially Matched Crossover, PMX)
•
順序交叉 (Ordered Crossover, OX)
•
周期交叉 (Cycle crossover ,CX)
31
周期交差（ＣＸ）
(i) 親
部分的な巡回順序を保持
情報の遺伝子上の位置を保持
致死遺伝子ができない
s1=<123456789>
s2=<412876935>
(ii) サイクルを見つける
s’1=< 1 2 3 4 * * * 8 * >
s1=< 1 2 3 4 5 6 7 8 9 >
s2=< 4 1 2 8 7 6 9 3 5 >
(iii) 残りの遺伝子を入れ替える
s’1=< 1 2 3 4 7 6 9 8 5 >
(s’2 も同様)
32
まとめ
 遺伝的アルゴリズムは自然淘汰の考えを
取り入れた解探索手法
 最適性の保障はないが高速である
 問題の性質（コード化）によっては、単純な
交叉法が適用できず、適切な方法を考え
なくてはならない