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