Download presentation
Presentation is loading. Please wait.
1
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部 2005年11月8日
2
GA 個体( ビットの列) → 正実数（適合度） 世代交代によって、集団に適合度 の高い個体 が含まれるようにする ビット ビット ビット
個体( ビットの列) → 正実数（適合度） ビット ビット ビット 個体 1 個体 1 個体 1 個体 2 個体 2 個体 2 集団 集団 集団 個体 個体 個体 世代 １ 世代 2 世代 世代交代によって、集団に適合度 の高い個体 が含まれるようにする は、十分に大きい ( が小さければ全探索)
3
遺伝的操作 選択： 交叉： 突然変異 に比例する確率で個体 を選択 1点交叉
に比例する確率で個体 を選択 ： 個体 の頻度 1 2 3 d 1 2 3 4 1点交叉 a b c 4 a b c d (他に複数点交叉、一様交叉など) a B c d a b c d ( 選択2回 → 交叉1回 → 1個体をランダムに選択 → 突然変異 ) x 回
4
エルゴードな有限マルコフ連鎖 集団内の個体の順序は気にしない (0,0,0,3), (0,0,1,2), (0,0,2,1), (0,0,3,0), (0,1,0,2), (0,1,1,1), (0,1,2,0), (0,2,0,1), (0,2,1,0), (0,3,0,0), (1,0,0,2), (1,0,1,1), (1,0,2,0), (1,1,0,1), (1,1,1,0), (1,2,0,0), (2,0,0,1), (2,0,1,0), (2,1,0,0), (3,0,0,0) ： 推移確率行列 有限マルコフ連鎖がエルゴード的： の各成分 > 0 となる有限の 突然変異確率> エルゴード よい解が早く見つかるのなら、交叉、突然変異にこだわることはない
5
ボルツマン分布ありきとしてのGA 最大 最大 交叉なし、突然変異なしであれば、 (温度の逆数が増えていく) 最大 （ の指数時間）
6
なぜGA 交叉なし、突然変異なし エルゴードではない (David Goldberg) GAは、エルゴード性を維持しながら、
GAは進化の過程を模倣しているので、適合性の高い個体だけが生き残る (John Holland) 飛行機が飛ぶことを誰も証明していないが、皆安心して乗っている (David Goldberg) GAは、エルゴード性を維持しながら、 ボルツマン分布を推定しながら、 温度を下げている (Heinz Mulenbein)
7
Estimation of Distribution Algorithms
初期集団をランダムに発生、 世代目の集団に基づいて、 2a. 個中、適合度の高い 個体を選択 2b. 個の個体に基づいて、 を推定 2c. に基づいて、 世代の 個の個体をランダムに生成 停止条件が満足されない場合、 として、2へ エルゴードな有限マルコフ連鎖 (公理論的なGAの範囲内)
8
BN 確率変数間の条件付独立性を有向グラフで図示
P(C,A,R,E,B) = P(B) P(C|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B) Burglary Earthquake Alarm Radio Announcement Call
9
BN P(C,A,R,E,B) = P(B) P(E|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B)
確率変数間の条件付独立性を有向グラフで図示 P(C,A,R,E,B) = P(B) P(E|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B) Burglary Earthquake Alarm Radio Announcement Call
10
BN 確率変数間の条件付独立性を有向グラフで図示
P(C,A,R,E,B) = P(B) P(E|B) P(R|E,B) P(A|R,E,B) P(C|A,R,E,B) P(C,A,R,E,B) = P(B) P(E) P(R|E) P(A|E,B) P(C|A) Burglary Earthquake Alarm Radio Announcement Call
11
BNの推定との関係 個の例から を推定 個体数 個体長 の集団と みなせる 構造推定も、パラメータ推定も の指数時間かかる
12
GAにおける平均場近似 各変数を独立 とみなして、 のパラメータ推定のみを行う(相対頻度) の計算量だが、K-L情報量 大
13
GAにおけるベータ近似 分布 のグラフを 最小の木で近似
14
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
15
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
16
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
17
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
18
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
19
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
20
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
21
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
22
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
23
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
24
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
25
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
26
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
27
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ 6 ３ ４ 5 4 3 2 1． がループを持たない
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) 1 2 3 4 １ ２ 1 2 6 ３ ４ 3 5 4 4 3 2 1 ＫKｋ
28
Chow-Liuアルゴリズム として、 となる を に加えていく ( が最小) １ ２ ３ ４ 1． がループを持たない ２． が最大
1． がループを持たない ２． が最大 となる を に加えていく ( が最小) １ ２ ３ ４ ＫKｋ
29
ボルツマン分布の因数分解 自明な因数分解 というよりは、 によらない定数個数の変数の因子の積に が大 スキーマ の適合度大
というよりは、 によらない定数個数の変数の因子の積に が大 スキーマ の適合度大 スキーマ仮説: GAは、適合度の高いスキーマを学習する情報処理 が大きくなっても、ボルツマン分布の因数分解は同じ（事前に行えるはず）
30
場合1: が加法的に分解可能
31
Running Intersection Property
1. 各 について、 2. 3. について、 なる RIPを満たさない
32
Running Intersection Property
RIPを満たす
33
RIPまとめ の非巡回性 ( を頂点とするJunction Tree が存在） RIPが満足されないとき １． の順序を変える
１． の順序を変える ２． の一部をマージする
34
有向グラフ： ベイジアンネットワーク(BN)
場合2： スキーマが無向グラフで表現 有向グラフ： ベイジアンネットワーク(BN) 無向： マルコフネットワーク(MN) 確率変数間の条件付独立性 が無向グラフ のJunction Tree 各 に対して、 の各クリーク に対して となる が存在 を結ぶ各 に対して、
35
Junction Tree アルゴリズム に辺を加えて長さ4以上のサイクルを無くす (三角化) を のクリークとし、
に辺を加えて長さ4以上のサイクルを無くす (三角化) を のクリークとし、 以下の2条件を満たす を に加える。 3a． がループを持たない 3b． が最大 ： の各要素 を で置き換えた集合
40
Junction Tree
41
最適なJTを求める Junction Treeは、各無向グラフに対して、複数個存在 分子の各因数の変数の個数の和を最小にすることは、NP困難
42
まとめ GAは、統計力学的にみると、もっとよくわかる GAは、エルゴードな有限マルコフ連鎖の中で、よいものを選べばよい。
個体長 が十分に大きいので、 の多項式時間で実行せよ。 構造推定 vs 因数分解。因数分解もそれなりに難しい。
43
今後に向けて: GA vs 変分方程式 定数 平均場近似であれば
44
ベーテ近似、菊池近似でも最適化問題は解ける
確率の和=1の制約条件の下で、 に関するラグランジュ未定係数法を解く 問題： GAによる解法と変分方程式の解法で、相互乗り入れはあるのか
Similar presentations
