Introduction to Soft Computing Yuji Sato 講義計画 １．遺伝的アルゴリズム（GA）とは ２．単純GAの実装 ３． GAの理論的基礎１：スキーマ定理と積木仮説 ４．GAの理論的基礎２：騙し問題 ５．Messy GA他 ６．進化戦略（ES）と進化的プログラミング（EP） ７．遺伝的プログラミング（GP） ８．応用（組合せ最適化、関数最適化、機械学習） ９．ニューロンのモデル、パーセプトロン １０．バックプロパゲーション １１．ホップフィールドモデル １２．教師なし学習 １３．連想記憶 評価方法 １．評価方法：試験＋出席率 ２．配点：試験：87点，出席：13点 ３．その他： （１）遅刻，早退：0．5点/回 欠席：0点/回 講義内容（第1回目） １．参考書紹介 ２．遺伝的アルゴリズムとは （１）遺伝的アルゴリズムの歴史 （２）遺伝的アルゴリズムの概要 参考書 １．坂和正敏、田中雅博 共著 「遺伝的アルゴリズム」 朝倉書店 ２．北野宏明 編著 「遺伝的アルゴリズム」、「遺伝的アルゴリズム２」、 「遺伝的アルゴリズム３」 、「遺伝的アルゴリズム４」 産業図書 ３．伊庭斉志 監訳 「遺伝的アルゴリズムの方法」 東京電機大学出版 局 ４．嘉数 監訳 「遺伝アルゴリズムの理論」 森北出版 ５．D.E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley (1989). ６．J.H. Holland , “Adaptation in Natural and Artificial Systems”, MIT Press (1975). 参考書 １．坂和，田中 共著：「ニューロコンピューティング入門」，森北出版 • 坂和，田中 共著：「ニューロコンピューティング ２．田中著：「ソフトコンピューティング入門」，科学技術出版 入門」， 進化的計算（Evolutionary Computation）と は？ →生物進化から着想を得た確率的探索手法 従来手法では解決が困難であったさまざまな最適化問題や 探索問題に対して、実用上の準最適解を速やかに得ること ができる適用範囲の広い多点探索アルゴリズムとして注目 されている 進化的計算 (Evolutionary Computation, EC) の代表例 • • • • 遺伝的アルゴリズム (Genetic Algorithms, GA) 遺伝的プログラミング (Genetic Programming, GP) 進化的プログラミング (Evolutionary Programming, EP) 進化的戦略 (Evolution Strategies, ES) 進化的計算の歴史（１） (1960年代後半) GA: J. Holland (1994年) GP ES: H.-P. Schwefel I. Rechenberg EP: L. Fogel (2000年） D.E. Goldberg K.A. DeJong J. Koza T. Baeck D. Fogel P. Angeline EC: IEEE 遺伝的アルゴリズムの概要 • 遺伝的アルゴリズム（GA）は，生物進化に着想 を得た，適用範囲の広い学習的アルゴリズム． 生物が何万年も何億年もかけて進化してきた遺 伝的な法則を工学的にモデル化したもの． 用語の説明（１） • • • • • • • • 個体 (individual)：染色体によって特徴付けられる単位 集団 (population)：個体の集合 遺伝子 (gene)：遺伝情報を表す構成要素 染色体 (chromosome)：複数個の遺伝子の並び 対立遺伝子 (alleles)：各遺伝子が取りうる値の候補 遺伝子座 (locus)：染色体上の各遺伝子の位置 遺伝子型 (genotype)：形質を規定する染色体の遺伝子表現 表現型 (phenotype)：遺伝子から発現される個体の形質表現 用語の説明（２） • • • • • • • • コード化 (coding)：表現型から遺伝子型への写像 デコード化 (decoding)：遺伝子型から表現型への逆写像 適応度 (fitness)：環境に対する個体の適応の度合 遺伝的操作 (genetic operation)：交叉、突然変異、選択など の操作 選択 (selection)：適応度に基づく個体の選択淘汰 交叉 (crossover)：個体間での遺伝子の組み換え 突然変異 (mutation)：対立遺伝子への確率的な置き換え 世代 (generation)：遺伝的操作の１サイクル、または、 ある時点での集団を構成する個体群 遺伝的アルゴリズムとは何か？ （特徴的な手続き） ・システムを文字列にコーディングする ・システム（文字列）の集団を対象とする →1点探索ではなく、多点探索を行う ・文字列をデコードして実現された、システムの挙動を評価 する ・淘汰により、次の世代の親となる集団を選ぶ ・選ばれた集団にオペレータ（genetic operator）を施すことに より新しいシステム（文字列）を生成する ・このサイクルを繰り返すことで、システム集団の評価点を 向上させる ゲノム (Genome)とフェノム (Phenome) ゲノムはフェノムを成長させるコードである Phenome Genome 成長 Genome 染色体と遺伝子（例） 染色体（遺伝子型）の例：0110110 染色体（遺伝子型）0110110の１番目の遺伝子座の 遺伝子：０、２番目の遺伝子座の遺伝子：１ 染色体の定義例 システム 入力 1 4 2 3 6 結合行列 出力 7 5 8 染色体 0001010000011010 ….. 00101000 12345678 100010100 200011010 300001001 411000010 501100001 610000000 701010000 800101000 遺伝的アルゴリズムの手順 個体群 次世代 １０１１０ 評価 １１００１ 評価関数 選択 遺伝的 操作 講義内容（第2回目A） GAの実装1 １．簡単な関数最適化の例 ２．適合度とスケーリング ３．選択 ４．演習1の準備問題1 簡単な関数最適化の例 • 1変数の簡単な関数 f ( x) x sin(10 x) 2.0 を，閉区間[-1, 2]で最大にするxを求める関数最適化問題 （図2.1） • f(x)はがi奇数となるxiに対して局所的最大値をとり， iが 偶数となるxiに対して局所的最小値となる． 簡単な関数最適化の例 1． コード化 個体を｛0, 1｝の2進文字列とすると22ビット必要 2． 初期個体群の生成 22ビットの2進文字列をランダムに生成 3． 適合度関数 最大化する関数をそのまま適合度関数 4． 遺伝的操作 1点交叉と突然変異 遺伝子の表現 ・ 遺伝的アルゴリズムでは，個体を表す文字列 （string）としてどのようなものを用いるかは任意． ・ 一方，Hollandの研究をはじめとして，ほとんど 全て2値｛0，1｝の並びである文字列，すなわち ビット列（bit string）によるコード化が用いられるこ とが多い． 評価 ー（適合度とスケーリング）－ １．適合度関数（または，適応度関数） 予め設計者が明示的に与えることにより、計算機の中で、 遺伝的操作が自動的に繰り返される。 精度に大きな影響を与える。 ２．スケーリング（scaling） （１）線形スケーリング：fi’ = a・fi + b （a, b: 係数） （２）シグマ切断： fi’ = fi – (f* - c・ s) （ f*：平均適合度、c:定数、 s : 適合度の標準偏差） （３）べき乗スケーリング： fi’ = （fi）k 線形スケーリングの手順 手順1：個体群の平均適合度f*，最大適合度fmax ，最小適合 度fminを求め，cmult = 2.0とおく． 手順2： fmin > (cmult f* - fmax)/(cmult – 1.0)ならば手順3へ，そう でなければ手順4へ進む． 手順3：a = (cmult – 1.0) f*/(fmax - f*), b = f*(fmax - cmult f*)/ (fmax - f*)として手順5へ進む． 手順4： a = f*/(f* - fmin), b = - fmin f*/ (f* - fmin)として手順５へ 進む． 手順5：i = 1, 2, …, Nに対してfi’ = a・fi + b （a, b: 係数）なる線 形スケーリングを行う． シグマ切断 • 線形スケーリングに対してfi’ < 0 となる場合が多いとき， すなわち個体群中の多くの個体が高い適合度をもち，残 りわずかな個体が非常に小さな値の適合度をもつ場合 が多いときには，個体群の適合度の標準偏差sを用いた シグマ切断が有効とされている． • シグマ切断（sigma truncation）は以下の式で定義される． fi’ = fi – (f* - c・s) ここで， cは1から3の値をとる定数で， fi’ < 0であればfi’ = 0とおく．標準偏差sは世代ごとに計算する必要がある． べき乗スケーリング • べき乗スケーリング（power law scaling）は，以下 に示すべき乗の写像として定義される． fi’ = （fi）k ここで，kは問題の構造に依存し，かつ世代の進 化に応じて変更する必要がある． 再生・選択 • 環境に対する適合度の高い個体が次の世代で より多くの子孫を残すという自然淘汰（natural selection）の考えは，GAでは，再生 （reproduction）あるいは選択（selection）とよばれ， 個体の中で問題（環境）への適合度の高い個体 は増殖し，逆に適合度の低い個体は淘汰される． 選択の種類 １．ルーレット選択： ・適応度に比例した確率で選択される ２．ランキング選択： ・ランクに対応した再生数を予め定義 ３．トーナメント選択： ・トーナメント方式で、次世代に残す個体を決定 ４．エリート保存選択： ・個体群の中で最も適応度の高い個体は無条件で次世代 に残す ルーレット選択 • ルーレット選択は，個体群の中の各個体の適合 度とその総計を求めて，適合度の総計に対する 各個体の割合を選択確率として個体を選択する． • 各個体siの適合度をf(si) (> 0), i = 1, …, Nとする とき，各個体の選択確率は以下の式で表すこと ができる． f (s ) pi i N f (s ) j j 1 ルーレット選択のアルゴリズム 手順1：世代tの個体群X(t)の中のN個の個体の適 合度fi, i = 1, …, Nとその総計fsumを求める． 手順2：[0, 1]の乱数rand()を発生させ，s = rand() x fsumとする． 手順3： f1 +, …, + fk > sとなるような最小のkを求め て，k番目の個体を世代t+1に生き残る個体の候 補とする． 手順4：候補となる個体数がNになるまで，手順2，3 を繰り返す． 期待値選択 • ルーレット選択に代表される確率的選択では，個 体数が十分に多くないときには，乱数の揺らぎに よって適合度を正確に反映しない選択となる可 能性がある．この問題に対処するために提案さ れた手法が期待値選択（expected-value selection）である． • 期待値選択では，個体群中の各個体の適合度と その総計を計算し，適合度の総計に対する各個 体の割合で個体数を調整する．（表2.2） ランキング選択 • 再生数が適合度の値により決定される選択手法 ではうまくいかない場合に適用される． • ランキング選択（ranking selection）は，適合度の 大きなものから順に再生する個数を予め決定し ておく．バランスのよい再生が可能である．一方， ランクと再生数の関係は，経験に基づき，設計者 が試行錯誤で決める必要がある．（表2.3） トーナメント選択 • トーナメント選択（tournament selection）は，個体 群中から予め定められた個数の個体をランダム に選択して，その中で最も適合度の高い個体を （トーナメント方式で）次世代に残すという手続き を次世代に残したい数の個体が選択されるまで 繰り返す方式． • Messy GAなどの手法（後述）で使用されている． エリート保存選択 • エリート保存選択（elitist preserving selection）は， 個体群中で最も適合度の高い個体は無条件に そのまま次世代に残すという方式． • De Jongは，エリート選択を，以下のように定義． 「s*(t)を，世代tまでに現れた最良の個体とする． もし， X(t+1)を通常の方法で生成したときに， X(t+1)の中に， s*(t)が存在しなければ， s*(t)を X(t+1)のN +1番目の個体として加える．」 演習１の準備問題１ • 個体数：100，染色体の全長：16ビット，適応度関 数f(x)は，長さ16ビットの文字列x内に存在す る”1”の数とする． １．初期集団生成のプログラムを作成せよ． ２．ルーレット選択のプログラムを作成せよ． 講義内容（第2回目B） GAの実装2 １．交叉 ２．突然変異 ３．設計変数 ４．演習1の準備問題2 交叉の一般的なアルゴリズム 手順1：i = 1として，i番目の個体と交叉する個体をN個の個体からなる 個体群の中から選ぶ． 手順2：[0, 1]の乱数rand()を発生させ，pc > rand()なら手順3へ，そうでな いなら手順4へ行く． 手順3：2つの個体をある交叉方法で交叉させ，手順5へ行く． 手順4：交叉させなかった2つの個体を一時的に保存して，手順6へ行く． 手順5：交叉させた2つの新しい個体を一時的に保存して，手順6へ行く． 手順6：i < Nならi = i+1として手順１へ戻り，そうでなければ手順7へ行く． 手順7：保存されている2N個の個体の中からNG個（0 < G < 1）をランダ ムに選び，もとのN個の個体群の中のNG個の個体と入れ替える． 交叉 １．１点交叉（単純交叉）： ・交叉点をランダムに１箇所選び、交叉点の右側の文字列 を交換する ２．多点交叉： ・交叉点をランダムに複数個選び、交叉点の間で交互に 部分文字列を交換する ３．一様交叉： ・マスクパターン上の１の遺伝子座には親１の遺伝子を、０ の遺伝子座には親２の遺伝子を受け継ぐ子と、その逆の 受け継ぎ方をする子を生成させる 交叉の例（１） ー １点交叉または単純交叉 － 1010110010101011 1010110010110101 1011001011110101 1011001011101011 交叉の例（２） ー 多点交叉 － 1010110010101011 1010110010101011 1010110010110101 1010111011101011 1011001011110101 1011001011110101 1011001011101011 1011000010110101 交叉の例（３） ー 一様交叉 － 親１： 親２： マスク： 子１： 子２： １１０００００１ １０１１１０１０ １０１１０１１０ １０００１０００ １１１１００１１ 突然変異のアルゴリズム 手順1： 2値｛0, 1｝の文字列，すなわちビット列で表 される個体の各遺伝子座に対して[0, 1]の乱数 rand()を発生させる． 手順2：pm > rand()ならば，遺伝子座の遺伝子を対 立遺伝子に置き換える．すなわち0ならば1，1な らば0とする． 手順3：個体群の中の全ての個体に対して手順1，2 を行って終了する． 突然変異 • 突然変異は，染色体上のある遺伝子座の値を他の対立 遺伝子に置き換えることにより，交叉だけでは生成できな い子を生成して，個体群の多様性を維持する． • 局所解からの脱出に有効． • 突然変異率は遺伝子座（各ビット）ことに定義される． 突然変異の例 1011100101 1111100001 逆位（inversion） • 個体上のランダムに選ばれた2点間の部分文字 列の順序を反転させる操作． 設計変数（GAパラメータ） • GAの精度，性能を向上させるためには，以下に示す パラメータを適切に設定する必要がある． (1) 個体数（個体群中に存在する個体総数） N (2) 交叉率 Pc (3) 突然変異率 Pm (4) 世代ギャップ（世代間で入れ替える新個体の割合） G (5) 世代交代数などの終了条件 単純GA simple genetic algorithm: SGA • GAにおいて、個体を２値｛0, 1｝の文字列、 すなわちビット列で表現して、再生をルー レット選択、交叉を１点交叉として、通常の 突然変異を加えて遺伝的オペレータを構 成したものを、単純GAと呼ぶ。 演習１の準備問題2 • 個体数：100，染色体の全長：16ビット，適応度関 数f(x)は，長さ16ビットの文字列x内に存在す る”1”の数とする． １．一点交叉のプログラムを作成せよ． ２．突然変異のプログラムを作成せよ． 演習1（単純GAの実装と評価 ） 1．適応度比例選択，ルーレット方式，個体数100，染色体の全長16ビッ ト，一点交叉率pc = 0.8，および突然変異率pm = 0.001である単純GAを プログラムせよ．但し，適応度関数f(x)は，長さ16ビットの文字列x内 に存在する”1”の数とする． 2．上記プログラムを40回実行し，全てのビットが”1”となる文字列を発 見する世代数の平均を求めよ． 3．上記プログラムにおいて，交叉を行わない（pc = 0）設定で同様の実験 をせよ．また，交叉と突然変異のどちらも行わない（pc = pm = 0）設定 で同様の実験をせよ．交叉を伴う突然変異の場合，突然変異のみの場 合，交叉も突然変異も行わない場合で，最適文字列発見までの最短時 間および平均時間を比較し考察せよ． 講義内容（第3回目） GAの理論的基礎1 １．暗黙の並列性（implicit parallelism） ２．スキーマ定理（schema theorem） ３．積木仮説（building block hypothesis） ハミング距離 (Hamming Distance) • 2つの個体を a = <anan-1…a1>, b = <bnbn-1…b1> ai , bi 0, 1, i 1,..., n とするとき，aとbのハミング距離d(a, b)は次式で 与えられる． n d ( a, b) a b i i 1 i スキーマとは ・スキーマ（schemata） S ：文字列の部分集合。 アルファベットの集合にドント・ケア記号*を加えた集合 から構成される文字列。 例： S = 01*1*0 →｛010100, 010110, 011100, 011110｝ ・スキーマS の次数（order） O(S) : （全長 L） - （*の数） 例：上記の例では、6 – 2 = 4 ・スキーマS の定義長（defining length） δ(S)： 最も左の0ま たは1と最も右の0または1の間の距離。 例：δ(*0110*) = 5 – 2 = 3, δ(**0*0*) = 4 – 2 = 2 スキーマの性質 0, 1よりなる長さlのコードである個体を考えるとき、 スキーマには以下の性質がある。 １．１つの特定の個体の属するスキーマは2l個ある。 ２．サイズnの個体群内に存在し得るスキーマの個 数は高々n2l個である。 ３．0, 1よりなる長さlのコードに関わるスキーマ数は 全部で3l通りある。 スキーマ数 • 各遺伝子座での0，1は当確率0.5で生起すると仮定する． このとき，n個の個体によるこの個体群中の異なるスキー マの期待値は以下の式で示される． n i l i 1 2 1 1 2 i i 0 l 暗黙的並列性 (implicit parallelism) • 個体数nの集団の遺伝的アルゴリズムにおいて， 同時に処理可能なスキーマ数の上限はn3のオー ダー． 遺伝子の全長をlとし，長さls以下のスキーマのみが生き 残ると仮定する．位置を固定して考えると，長さlsのス キーマ数はO(2ls)存在する．位置の取り方は(l-ls+1)通り． 個体数nは（平均を考えて）n=2ls/2と考える．従って，並列 処理可能なスキーマ数nsは， ns～2ls(1-ls+1)n=n2(l-ls+1)n =O(n3) スキーマ評価値 • 世代kにおけるスキーマHの評価値f(H, k)は以下の式で 与えられる． 1 f H , k H k f x xH ( k ) 但し，|H(k)|は世代kの個体群中でスキーマHに属する個 体数． 上記式から，kが異なると同じスキーマに対して評価値は 一定でないことが分かる． 遺伝的操作によるスキーマの変化 １．再生による個体数期待値 f (H , k ) m( H , k ) f (k ) ２．スキーマHが交叉で破壊されない確率 pc ( H ) 1 l 1 ３．スキーマHが突然変異で破壊されない確率 (1 pm )O( H ) 1 pmO( H ) スキーマ定理 （遺伝的アルゴリズムの基本定理） f (H , k ) (H ) m( H , k 1) m( H , k ) (1 pc p m O( H )) l 1 f (k ) • 定義長δ(H)が短く，次数O(H)が低く，平均評価値 f (k ) より高いパフォーマンスを示すスキーマHが，次 の世代で生き残る． 積木仮説 (building block hypothesis) • 定義長が短く，次数が低く，適応度が高いスキー マは，交叉により壊されることも少なく，探索過程 を通じて保存されやすい．このようなスキーマを 積木(building block)と呼ぶ．このような積木単位 に交叉した方が，ランダム交叉よりも，最適な遺 伝子が得られやすいと思われる．この希望的観 測を積木仮説(building block hypothesis)と呼ぶ． 積木仮説の成立条件 1. 表現型が近い個体は遺伝子型も類似し ている． 2. 遺伝子座間での干渉が少ない． 例：表現型の7が遺伝子型0111に対応し，8が 1000に対応するコード割当は（積木仮説によれ ば）望ましくない． 一般化スキーマ定理 n点交叉の場合のスキーマ定理は次式で示される． f (H , k ) m( H , k 1) m( H , k ) 1 pc f (k ) l l 1 (H ) n n p O( H ) m l 1 n 一様交叉とスキーマ定理 • 一様交叉では，交叉後にスキーマが壊れない 確率は (1/2)O(H)-1となり，スキーマ長(H)に依 存しない．従って，多くの問題で有効となる可 能性が大きい． 1点交叉とスキーマ定理 • 1点交叉では，2つの文字列の値の異なる遺伝 子座に着目すると，右と左の位置の間隔が広 いほどスキーマが壊れる確率が高くなる．この 間隔の大小によって生じる「バイアス」を除く方 法として，縮小代理方 (reduced surrogates method)が提案されている．遺伝子座間の距離 に関係なく，スキーマが壊される確率が等しく なるように確率を補正して1点交叉を行う方式 である． 講義内容（第4回目） GAの理論的基礎2 １． 2進コードとGrayコード ２．騙し問題 ３．GA困難な問題 Grayコード • Grayコード<gl-1gl-2…g0>と2進コード<bl-1bl-2…b0> との間の関係は，次式で定義される． bl 1 gk bk 1 bk k l 1 k l 2 • Grayコードは隣り合う値に対するコードはどれか 1ビットしか異ならない，すなわちハミング距離が 1であるという特徴を持つ． 2進コードとGrayコードの対応表 10進 2進 Gray 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 001 011 010 110 111 101 100 2進コードとGrayコードの比較 • f(x) = (x-4)2の最小化問題を3ビットの2進コードと Grayコードにより比較．(表3.5, 表3.6) • 2次以上のwjの値についてはGrayコードの方が 概して低く，積木仮説が成り立ちやすいことが予 想できる． 騙し問題 (GA-deceptive) • GAが正常に働かず，評価値の高い個体の生成 が妨げられるような問題を騙し問題（deceptive problem）という． • 騙し問題では，個体群の全個体中に占める，着目するス キーマ個体数の比率が重要．一方，個体数の比率は， GAの実行または個体数の理論的期待値計算が必要で あるために，大変時間がかかり，確率に基づく理論値の 計算は困難．従って，厳密性を犠牲にして，スキーマ個 体数の比率変化を無視して，騙し性に関する概念の定義 を行うことが一般的である． 競合スキーマ • HとH’が競合スキーマ (competiting schemata)で あるとは，*の位置が完全に一致して，しかも固 定されているいずれかの遺伝子座での値が異な るような場合をいう． 騙し的 • f(x)の最大値を与えるxの集合をX*とする．HはX*の要素 を含まない次数mのスキーマとする．このとき，あるHに 対してそれに競合する別のあるスキーマH’との間に， f(H) > f(H’) が成立するとき，fは次数mで「だまし的」という． だまし性は，本来最適でないスキーマが最適であるよう に振舞うものが存在していることを表している． 騙し関数の例 • f(111)が最大値のときの騙し関数の例（例3.6） 次数１： 次数2： f(**1) < f(**0), f(*1*) < f(*0*), f(1**) < f(0**) f(*11) < f(*00), f(1*1) < f(0*0), f(11*) < f(00*) f(*11) < f(*01), f(1*1) < f(0*1), f(11*) < f(01*) f(*11) < f(*10), f(1*1) < f(1*0), f(11*) < f(10*) 騙し関数のタイプ • 2ビットの最大化問題において，“11”が最適解で あるが，H(0*) > H(1*)である騙し問題を考える． この条件は，以下の式で定義できる． f (00) f (01) f (10) f (11) 2 2 騙し関数のタイプ • r=f(11)/f(00), c=f(01)/f(00), c’=f(10)/f(00)とおくと 騙し問題の条件は，以下のような式となる． r < 1 + c - c’ • c>1となるものをタイプI，c 1となるものをタイプII の騙し問題という．(図3.6) • タイプIはタイプIIよりもGAにより最適化を行うこ とが容易．タイプIIは最適解が孤立するので，よ り難しい問題となっている． 騙し問題と突然変異 • タイプIの問題：突然変異を含めない場合，GAは 繰り返し回数を増やせば最適解に収束する．一 方，突然変異率を高くしすぎると，最適解に収束 することが困難となる． • タイプIIの問題：突然変異を行わない場合，“00” と“11”がアトラクターになる．その際，騙し問題な ので“00”が大多数になる．一方，突然変異の割 合をある程度大きくさせていくと，2つの局所解を 隔てていた境界を越えて，最適解に収束する． コードによる騙し性の解消 (1) • 騙し問題は，目的関数に対する適合度関数の作 り方，および適合度関数とそれに対するコード化 が原因となり生じる場合が多い． • 図3.6に示される騙し問題は，適切なコードを用 いることにより，よりやさしいクラスの問題に置き 換えられる．（表3.7，表3.8，図3.7） コードによる騙し性の解消 (2) • コードを検討することにより，GAで解くのが容易 な問題やより簡単な騙し問題に帰着できる．一 方，そのようなコードを見つけることが実際は難 しい． • コード化の問題として，探索幅（コードにより表現 される最小単位）が粗すぎる場合がある．その場 合，探索するときに鋭く尖っている最適解が粗い 目にかかることは期待薄である． 適合度関数による騙し性の解消 • g(00)=128, g(01)=1, g(10)=g(11)=32と仮定する． 適合度関数をこのままf(x)=g(x)と定義すると f（0*）＝64.5，f(1*)=32 で騙し問題になっている． • 一方， f(x)=log2g(x)と定義すると f(00)=7, f(01)=0, f(10)=f(11)=5 f（0*）＝3.5，f(1*)=5 で騙し性が解消される．(例3.7) GA困難な問題 • GAの基本的な遺伝的操作である，再生，交叉， 突然変異と，標準的なパラメータを用いて大域的 な最適解を求めることができる問題をGA容易な 問題，そうでない問題をGA困難な問題という． • GA容易な完全騙し問題の例（例3.8） • 騙し問題ではないがGA困難な問題の例（例3.9） 単純GAと騙し問題 • 単純GAでは，GA-hard（単純な３種類の操作（増 殖，交叉，突然変異）のGAでは解法が困難な問 題）ではないのに，局所最適解に収束してしまう 場合が存在する． • 一方，一般的に，ほとんどのMDP(Minimal Deceptive Problem)はGA-hardではない． マルコフ連鎖解析 • GA解析における重要な問題は (1) 最適解を含む個体群がどれくらいの時点で現れる か？ (2) GAが得意とする問題のクラスはどのようなものか？ (3) 問題に対応して，どのようにGAパラメータを設定する のが最適なのか？ などである． • スキーマ定理のみでこれらの問題に対応するのは困難 なため，近年，マルコフ連鎖解析を用いたGAの理論的 研究も始まっている． 講義内容（第4回目B） GAの理論的基礎3 1．ローヤル・ロード関数を用いた，GAと他の山登 り法との比較 2．ランダム突然変異山登り法（RMHC） 3．理想的なGA（IGA） ロイヤル・ロード関数 • ロイヤル・ロード関数R1は，積木仮説を調べるた めに考案された適合度関数の一つ． • R1は一連のスキーマsiを使って定義される．各si には係数ciが与えられる．文字列xの適合度R1(x) は以下の式で定義される． R1 ( x) c ( x), i i i 1 ( x si ) i ( x) 0 ( x si ) ロイヤル・ロード関数を用いた GAと他の山登り法との比較 • 最急勾配山登り法（SAHC），逐次勾配山登り法 （NAHC），ランダム突然変異山登り法（RMHC）と GAを比較． • 乱数の種を変えて200回の試行を行い，最適文 字列を見つけるまでの関数評価回数を記録． （最大評価回数を256000 に設定） • 平均は，GA: 61334, SAHC: >256000, NAHC: >256000, RMHC: 6179 最急勾配山登り法 Steepest-ascent hill climbing(SAHC) １．１つの文字列をランダムに選ぶ．この文字列を「現頂上」 と呼ぶ． ２．左から右に順に各ビットを反転させてみて，反転結果の 文字列の適合度を記録する． ３．もし反転結果の文字列が適合度の増加をもたらすなら， 現頂上を反転結果の中で最高の適合度の文字列に変更 する． ４．もし適合度の増加がない場合は現頂上を保存し，ステッ プ１へ戻る．そうでなければステップ２に戻る． ５．設定した回数の関数評価が済んだら，見つかった最高 の頂上を返す． 逐次勾配山登り法 Next-ascent hill climbing(NAHC) １．１つの文字列をランダムに選ぶ．この文字列を「現頂上」と呼 ぶ． ２．iを1からl（lは文字列長）まで変えてビットiを反転する．反転に より適合度が増えればそれを新たに文字列とし，そうでなけれ ばビットは元に戻す．適合度の増加がみられた途端に，他の ビット反転を評価することなしに現頂上を適合度の増加した文 字列に移してしまう．ステップ2に戻り新たな現頂上について同 じ操作を繰り返す．但し，反転するビットの位置は先に適合度 の増加が見られたビット位置の隣から始める． ４．もし適合度の増加がない場合は，現頂上を保存しステップ１へ 戻る ５．設定した回数の関数評価が済んだら，見つかった最高の頂上 を返す． ランダム突然変異山登り法 Random-mutation hill climbing(RMHC) １．１つの文字列をランダムに選ぶ．この文字列を「最高評 価解」と呼ぶ. ２．反転のための遺伝子座をランダムに選ぶ．反転して現 在以上の適合度が得られるならば，反転結果を最高評 価解とする. ３．最適な文字列が見つかるか，定められた回数の関数評 価が済むまでステップ２に戻る. ４．最高評価解を返す. RMHCが最適文字列を見つける時間の期待値 ε(K, N) = ε(K, 1)N(1+1/2+1/3+…+1/N) = ε(K, 1)N(lnN+g) （証明は別紙参照） → 2K N(lnN+g) (K → ∞) • ε(K, N) : 適合度関数がK個の隣接する1からなるN個のブ ロックによるものとした時に，RMHCがオール1の最適文字 列を見つける時間（関数評価回数）の期待値 g：オイラー定数（0.5772 GAにおけるヒッチハイキング • 一旦高次のスキーマのインスタンスが見つかると，その 高い適合度がスキーマを集団内に急速に広めるが，そ のときスキーマの定義部分にある1にヒッチハイキングし て，他の位置にある0までも広まってしまう. • ヒッチハイキングは，ある遺伝子座でサンプリングされる スキーマを限定してしまうことにより， GAの暗黙の並列 化を大きく制限する. • ヒッチハイカーの最も起りやすい位置は，高適合度のス キーマの定義部分に近い部分. 理想的なGA Idealized GA: IGA １．各タイムステップで新たな文字列を各ビットについて一様 分布でランダムに選ぶ. ２．１つ以上の所望のスキーマを含む文字列が初めて見つ かったときは，その文字列を保存する. ３．１つ以上の未発見の（所望の）スキーマを含む文字列が 見つかったときは，即座に新たな文字列と保存しておい た文字列を交叉させ，保存した文字列がそれまでに見つ かった全ての所望のスキーマを持つようにする. IGAが最適文字列を見つける時間の期待値 εN(K, N) 2K (lnN+g) （証明は別紙参照） IGAは完全に暗黙の並列化を実行するために， RMHCよりもオーダーNだけ速い. なぜIGAはRMHCよりも速いか？ • IGAは完全に暗黙の並列化を実行する．すなわ ち，新たな文字列は直前の文字列と完全に独立 で，新たなサンプルはパーティションごとに独立 に得られる． • 一方，RMHCは文字列の空間をビットごとの突然 変異により元の文字列から動いていくので，新た なサンプルは直前のサンプルと1ビットを除いて 変わらない．よって，新たなサンプルは1つのス キーマパーティションだけに1つの新たなサンプ ルを与える． IGAに近づくためには？ • 独立なサンプル：集団を大きくとる．突然変異率を十分高 く設定する． • 望ましいスキーマの保存：突然変異率は必要以上に高く 設定しない． • 即座の交叉：交叉が望ましい２つのスキーマを組み合わ せるのに要する時間が，望ましいスキーマが見つかるの にかかる時間に対して十分小さくなるように交叉率を設 定する． • RMHCを超える高速化：N倍の高速化が効くほど、文字列 を長く設定する． 演習2（GAの理論的基礎 ） 1．スキーマ定理（別紙参照） 2．適応度関数f(x)が以下の式で表されるとする． 3（x ∈ 111*・・・*） f(x) = 2（x ∈ 0*・・・*） 0（上記以外） 以下のスキーマの平均適応度を求めよ． (a) 1**・・・* (b) 11*・・・* (c) 1*1*・・・* (d) *1*・・・* 3．3ビットの完全だまし適合度関数を設計せよ． 但し，”111”が最大値を与えると仮定する． 演習2（GAの理論的基礎 ） 4. n点交叉の場合のスキーマ定理は次式で示されることを 示せ． f (H , k ) m( H , k 1) m( H , k ) 1 pc f (k ) l l 1 (H ) n n p O( H ) m l 1 n 演習2（GAの理論的基礎 ）追加問題 5. 理想的なGA(IGA: Idealized GA)の解析において説明を省略した 以下の変形が正しいことを示せ． N N N N N 1 1 2 3 N p 1 2 3 ........ N N 1 ln N g p 但し，N:個体数，p:ランダムな文字列中にスキーマHが見つかる 確率，γ: オイラー定数．また，以下の関係は既知とする． N 1 n ln N g n1 講義内容（第5回目） SGAの弱点を改善するための拡張 1. CHC：SGAの操作の効率化が目的 2. 拡大GA：騙し問題対応が目的 3. Messy GA：離れた遺伝子座よりなるスキーマ 対応が目的 4. 並列GA：並列計算機上での効率向上が目的 CHC • CHCは以下の略語． C (Cross generational elitist selection)：2世代エリート選択 H (Heterogeneous recombination)：異種間交叉 C (Cataclysmic mutation)：大変動突然変異 • CHCがSGAと異なる点は，SGAが操作の単純さをその 特徴としているのに対して，CHCは単純性を犠牲にす る代わりに各操作をより効率的に行い，得られた優良 個体は確実に残すことを意図していること． CHCの特徴 (1) 1. a) b) c) d) 選択（2世代エリート選択） CHCでは，古い世代の個体群と，新しく交叉によって生 じた個体群を混ぜ合わせた中から優れた個体を（確率 を使わずに）順に選択する．従って，以下の特徴を持つ． エリート選択である より大きな個体群中の個体の多様性が保たれる ランキング選択なので，個体の評価値のスケーリング に左右されない 2世代個体群から選択する方法は他の方法にはあまり 見られない CHCの特徴 (2) 2. 交叉（異種間交叉） CHCでは，類似の個体間の交叉（近親間交叉）を行わ ないことで多様性を確保する．具体的には，修正一様 交叉を行う．修正一様交叉は，2つの親のビット値が異 なる遺伝子座がm個あるとき，そのうちm/2個の位置を ランダムに選んでその遺伝子座の親の値を交換する 交叉である．この交叉は必ず行うのではなく，ハミング 距離が閾値よりも小さい個体間の組み換えを避ける操 作が行われる．この閾値は個体群が収束するのと同 時にしだいに減少させるので生き残る個体数がほぼ一 定になるように制御される． CHCの特徴 (3) 3. 突然変異（大変動突然変異） CHCでは，突然変異は途中では行わず，個体群が収 束したときに個体群中の最良個体を用いて一部の個 体を初期化する．1個体中の遺伝子座のうちr（拡散率 という）の割合のものの値をランダムに決める．その際， 最良の個体そのものを1つ保存することにより進化が 逆戻りすることを防いでいる．拡散率rは0.35程度の値 が用いられることが多い． CHCのアルゴリズム • CHCの特徴 (3) Procedure CHC begin k = 0; /* k：世代数 */ d = L/4; /* L：個体長 */ P(k)の初期化（個体数N） P(k)の評価 終了条件が満たされるまで繰り返す begin k = k + 1; P(k – 1)をコピーしてシャッフルした個体群をC(k)とおく C(k)の中で組み換えを行い新しい個体群をC’(k)とする C’(k)の評価 C’(k)とP(k – 1) の中から選択 if P(k) == P(k – 1) d = d – 1; /* d：閾値 */ if d < 0 begin P(k)の初期化 d = r(1 – r)L /* r：拡散率 */ end end end end. CHCの組み換え Procedure CHCの組み換え begin C(k)中の個体をペアにしてそれぞれに対して begin ハミング距離を求める if ハミング距離/2 > d 修正一様交叉 else そのペアを個体群から消去 end end end. CHCの選択 Procedure CHCの選択 begin P(k - 1)を評価値順に並べP(k)とする C’(k)を評価値順に並べる while P(k)の最悪値 < C’(k)の最良値 その2値を入れ替える end end. CHCの一部初期化 Procedure CHCの一部初期化 begin P(k - 1)の最良個体をN個作ってP(k)とおく P(k)のN - 1個の個体に対して begin rLビットをランダムに選び，値もランダムに決める 個体評価 end end. 拡大GA • 全てのステップで完全騙し問題なら，GAを実 行して，収束した個体をビット反転すれば最適 解が得られる．現実的により難しい問題は部分 的騙し問題，すなわち，部分列が騙し問題に なっている場合である．このような部分的騙し 問題に対処するために考案されたGAが拡大 GA（augmented GA）である．拡大GAでは，各 ステップにおいて3倍個数の個体評価をするだ けで部分的騙し問題を解くことができる． 拡大GAのアルゴリズム Procedure 拡大GA begin k = 0; 個体群P(k)を初期化 P(k) （個体数N)の中の個体を評価 終了条件が満たされない間繰り返す begin k = k + 1; P(k – 1)からP(k)を選択 P(k)の中で交叉を行う P(k)の中の個体を全てビット反転してQ(k)を生成 P(k)，Q(k)の中から個体を確率的に選んで多点交叉を行いR(k)を生成 P(k)，Q(k)，R(k)の中の最良の個体を出力（記録）する． end end. Messy GA • • SGAでは，定義長の大きいスキーマは壊れや すく，小さな積木という形のスキーマからしか最 適解が構成されない欠点がある．この欠点を 補うためにGoldbergらにより考案された手法が， messy GAである． messy GAでは，スキーマの定義長に影響され ずに良いスキーマが増殖するように，遺伝子を タグを付けたペア（位置，値）の形で表現する． Messy GAの遺伝子表現の例 • 011101 • (1, 0) (2, 1) (3, 1) (4, 1) (5, 0) (6, 1) 或いは (2, 1) (5, 0) (1, 0) (3, 1) (6, 1) (4, 1) など SGAでの1点交叉では交叉点の右と左に分け ることしかできなかったのに対して，messy GA では，同じ1点交叉であらゆる2個の部分集合 への分割が可能になる． Messy GAのアルゴリズム 第一フェーズ（primordial phase） 1．第一フェーズ（primordial phase） 最高騙し次数の長さの全てのスキーマを発生 させ，その中で最適解を含む有用なスキーマを 残し逆に無用なスキーマを振り落とす．既に初 期個体群の中に必ず最適解を含む（騙されな い長さの）スキーマが存在するのであるから， 次の交叉操作を行うのが容易になる程度まで このフェーズで個体数を絞り込む． 第一フェーズの手順 1．最高騙し次数mを決定する． 2．次数mのスキーマを全て列挙する． 次数mのスキーマはkCm2m通り存在する． 3．競合テンプレート法（後述）により，初期世代の個体群中 に含まれる個体の評価を行う． 4．トーナメント選択で個体数を絞り込む． （図4.2参照） 5．個体数を減少させる． Messy GAのアルゴリズム 並列フェーズ（juxtapositional phase） 2．並列フェーズ（juxtapositional phase） 個体中から２つの個体が，切断（cut）と接合（splice）の ために，ランダムに選ばれる．切断確率は１つの切れ 目ごとに定数pcで定義する．個体長lの場合，１回の操 作で切断される確率は，近似的に， pc(l – 1)となる． 従って，個体長が長いほど１個体が切断される確率は 大きくなる． 一方，接合は，個体長には関係なく，個体単位に接合 の確率を定義する．従って，個体長が短い場合には切 断されずに接合のみが行われやすくなる． 切断と接合の例 個体1 個体2 (1, 0) (2, 1) (3, 1) (4, 1) (5, 0) (5, 1) (4, 0) (2, 0) (1, 1) 新個体1 (1, 0) (2, 1) (3, 1) (4, 1) (2, 0) (1, 1) 新個体2 (5, 1) (4, 0) (5, 0) 過不足のある個体の評価 • 先に述べた第一フェーズおよび並列フェーズの 中で過不足のある個体の評価値は次のように 与える． (1) 多重定義：最初に現れた定義を優先させる． (2) 不足定義：競合テンプレートと呼ばれる方法を 用いる． 競合テンプレート • a) b) c) 未定義の遺伝子座がlビットあるとするとき l ビットの文字列を1つランダムに生成する 1, 2, …, l をランダムに並べ替える b)で並び替えた数字の順にランダムな系列の 中の対応するビットの値を変化させ，元の系列 と変化させた系列の評価値を比較する．良い 方に固定する． d) この操作を一巡させる． 部分関数のスケーリング(1) • • トーナメント選択ではスキーマ同士を比較する ことになるが，異なる遺伝子座を定義している スキーマを比較評価することは無意味である． このような比較，選択を行わないようにするた めに，トーナメント選択において個体（スキー マ）の定義されている遺伝子座が一定個数以 上共通である場合のみ比較することが必要． また，比較できる別の個体がない個体は優先 的に次世代に残すことも有効． 部分関数のスケーリング(2) • • • 最高騙し次数kが4，積木の長さが3の場合を考える．3 ビットの積木に対して残り1ビットを寄生ビットと呼ぶ． 寄生ビットは，第一フェーズでは特に何の問題も起こさ ない．一方，並列フェーズでは，寄生ビットが有効な結 合表現の生成を妨げる可能性がある． この問題をさけるために，遺伝子座をk – 1ビット追加し， kに満たない長さの騙し次数をもつ部分列の寄生ビット に対応する部分にN (Null bit)というコードを使う． 並列GA Procedure 並列GA begin 初期個体の生成 終了条件が満たされない間以下繰り返す begin 近傍で個体を組み合わせる 交叉を行う 子の適合度が親より良ければ子を新しい個体群に入 れる end end.
© Copyright 2024 ExpyDoc
