遺伝的アルゴリズム概説 An Outline of Parallel Distributed Genetic Algorithms 同志社大学工学部知識工学科 知的システムデザイン研究室 分散遺伝的アルゴリズム研究グループ 佐野 正樹，上浦 二郎，水田 伯典 ○福永 隆宏，花田 良子，片浦 哲平 遺伝的アルゴリズムの基になる生物の進化プロセス 生物の進化プロセス 有性生殖によって両親の形質 を子孫に伝える 遺伝子のコピーミスによる 新しい形質の獲得 環境に適合した個体ほど 子孫を残しやすい GAのプロセス 遺伝子を組み替えて新しい個体を生成 個体間の情報交換 親個体が持たないビットを生み出す 母集団内の多様性の維持 環境に適合した個体ほど 子孫を残しやすい GAの特長・問題点 目的関数の形質を直接利用しない 確率的な多点探索 最適なパラメータ設定が困難 パラメータチューニング 計算コストが大きい 並列処理・並列GA 並列分散GA 母集団を複数のサブ母集団に分割 特徴 一定世代ごとに移住（移住率，移住間隔） 並列計算機との親和性が高い 連続関数最適化への適用 連続関数最適化問題への 適用 最適化問題 連続関数でモデル化が可能なものが多い GAの特性 設計変数間の依存関係によって難易度が異なる 依存関係がない 解きやすい 依存関係がある 解きにくい これらの性質を持つテスト関数を解くことで 非線形最適化問題全般に有効と考えられる 対象問題 多峰性関数 変数間に依存関係なし 多峰性関数 変数間に依存関係なし 多峰性関数 変数間に中程度の依存関係 単峰性関数 変数間に依存関係あり 単峰性関数 変数間に依存関係あり 遺伝的アルゴリズム ＜身近な最適化問題の例＞ 遺伝的アルゴリズムは・・・ 生物の進化を模倣した 最適化手法 最適化問題 与えられた制約条件の下で ある目的関数を最大にする 解を求める. ex） 携帯電話の料金プラン 生物の進化とGAの対応 生物の進化 GAのオペレータ 生物の進化とGAの対応 選択 個体を評価，適合度を計算 次の世代の個体を決定 適合度の高い個体ほど 子孫を残しやすい 突然変異 親個体が持たないビットを生み出す 母集団内の多様性の維持 突然変異率に応じてビットを 反転させる 遺伝子を組み替えて新しい個体を生成 個体間の情報交換 交叉 連続関数最適化への適用 連続最適化問題への適用 ２変数のRastrigin関数にGAを適用する Rastrigin関数の外形 Rastrigin関数の等高線 初期化 GAの適用(1) 適用1: 初期化 ランダムにビット列を生成 10011 00011 デコード 0.2 -0.2 x y 初期母集団が形成される 2D-Rastrigin GAの適用(2) 交叉 適用2: 交叉 Parent 1 10011 0 0011 Parent 2 01010 1 0101 Child 1 10011 0 0101 Child 2 01010 1 0011 ランダムに設定された 交叉点で遺伝子を交換 GAの適用(3) 突然変異 適用3: 突然 変異 11010 10101 11010 00101 突然変異率に応じて ビットを反転 母集団内の多様性を維持 GAの適用(4) 評価・選択 評 価 適用4: 評価・選択 10011 00011 デコード x= 0.4 y = 0.8 F(x,y)を計算，評価値を求める 評価値をもとに適合度が求まる 選 択 適合度に応じて次の世代に 残る個体が選択される 世代 t 世代 t+1 GAの適用(1) 符号化 f （ x, y ）= x 2+ y 2 01001 11001 （x, y）= （-3, 2） 10011 00011 （ x, y ）=（1 , -4） 探索領域内にランダムに個体を生成 設計変数を符号化＝コーディング GAの適用(2) 交叉 01001 1 1001 = （-3, 2） 10011 0 0011 = （1, -4） 01001 1 0011 = （-3, 1） 10011 0 1001 = （1, -2） ランダムに設定された交叉点で遺伝子を交換 GAの適用(3) 突然変異 （x, y）= （-3, 2） 01001 11001 （x, y）= （-3, -2） 01001 01001 突然変異率に応じてビットを反転 選択 GAの適用(4) 評価 （x, y）= （-3, 2） 01001 f （ x, y ）= x 2+ y 2 11001 2 2 f （x, y）= -（（-3） + 2 ） = -13 選択 適合度に応じて次の世代の個体を決定 適合度の高いものほど選択されやすい
© Copyright 2024 ExpyDoc
