遺伝的アルゴリズム遺伝的アルゴリズム(ＧＡとは) • 生物の、遺伝と進化の仕組みを真似て問題を解くアルゴリズム – 最適化や強化学習に用いられる進化と遺伝 – – – – – – – – – 染色体遺伝子遺伝子座対立遺伝子遺伝子型表現型突然変異交叉選択最適化問題 • いくつも答えがある中から一番優れた解を選び出す – 例 : ナップサック問題 • ナップサックに荷物を詰めることを考える – – – – Ｎ個の荷物がある各荷物には価値と重量が設定されている詰める荷物の価値の総和を最大にしたいナップサックには詰め込める重量の限界があり、全ての荷物を詰めることは出来ない • 全ての組み合わせを調べれば(前回探索法)、最良解が見つかる(当たり前) • しかし荷物数Ｎが増えると、組み合わせの数が指数的爆発して現実的な時間で解けない • どうしようヒューリスティクス(発見的手法) – 必ず正しい答えが導けるわけではないが、ある程度のレベルで正解に近い解を得ることが出来る方法 – うまいルールを思いつければ、それに従って探索する。 – 思いつけないかも – 見つかった答えは本当に最良か？ルールによって見つかる解は決まる – 例:欲張り法遺伝的アルゴリズム • メタヒューリスティクス(何にでも使えるアルゴリズム、その代わり、特化されたものより性能が低い)の一種 • 全ての解をではないが、色々比較検討する • ある程度のところで我慢する • １個体とその遺伝子型 – 遺伝子型ｓ長さＮの記号列(とりあえずバイナリ列) • s = s1 s2 …. sN • Ｍ個体からなる個体集合 • Ｓの様な個体がＭ個集まって１世代分の個体集合 • とりあえずＭ全世代で一定にしとく遺伝演算子 – 交叉 • 個体集合の中から２個体をランダムに選び、ある確率 (交叉確率)で遺伝子列を交換 – 突然変異 • 各個体においてある確率(突然変異確率)で各遺伝子座の値を変える – 選択 • 環境に適応した個体ほどたくさんコピーを残すようにする • 適応度ｇ • ステップ1：初期化ランダムにM 個の個体の遺伝子型（N 文字からなる文字列）を生成して，初期世代 • における個体集合P(0) を作る．世代を表すループ変数t は，t = 0 と設定する． • ステップ2-1：評価個体集合P(t) に含まれる全M 個体に対して，その表現型xi に応じて決まる適応度 • gi (i = 1, . . . , M) を求める． • ステップ2-2：選択個体集合P(t) に対して，各個体の適応度gi に基づき，前節2.2 に示した選択操作を • ほどこし，その結果得られた新たなM 個体からなる集合P(t) を生成する． • ステップ3：交叉個体集合P(t) に対して，前節2.2 に示した交叉操作をほどこし，その結果得られた新 • たなM 個体からなる集合P(t) を生成する． • ステップ4：突然変異個体集合P(t) に対して，前節2.2 に示した突然変異操作をほどこし，その結果得 • られた新たなM 個体からなる集合を生成し，それをもって次世代の個体集合P(t+1) とする．t を • t + 1 に1 増加する． • ステップ5：終了判定進化過程の最終世代数T をあらかじめ設定しておき，t < T ならば，上記のステッ • プ2-1 に戻る．t ≥ T となった時点で，計算のループを終了させる．終了時点までに得られた最大適 • 応度をもつ個体をもって，一番良い個体とする．