土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 井上一哉（神戸大） 遺伝的アルゴリズム（Genetic Algorithms: GA）入門 1 はじめに 逆問題とは，ある対象やある現象を構成する知りたい未知情報を観測や測定を通して抽出するこ とであり，逆問題の解析を逆解析という．X 線 CT により断面像の構築したり，熱伝導方程式にお ける熱伝導係数を推定することが逆問題の代表例であり，デジタルホログラムや画像処理など身近 なところで逆解析は適用されている． 推定の対象とする物理量が観測結果に等しい結果を導くように物理量の値を更新する，言い換え れば，観測値と推定値の差を最小にすることが多くの逆解析において採用されている過程であり， 逆問題は最適化問題の 1 つとして位置づけることもできる．数理計画法をはじめとして，最小二乗 法やベイズ法，カルマンフィルタなど最適化問題を解く多くの解析手法が存在する． 生命プロセスと進化を研究する人工生命の分野では，生物学的現象をコンピュータ上で再現する 技法を応用した最適化アルゴリズムが開発されており，遺伝的アルゴリズム（Genetic Algorithms: 以下，GA と記す）は人工生命の最も代表的な例である．GA は生物の進化過程を模擬した技法で あり，自然淘汰や突然変異を繰り返すことにより環境への適応度が低い遺伝子配列が徐々に淘汰さ れる一方で，適応度の高い配列が生き残っていくアルゴリズムである．GA では，遺伝子配列を多 変数を未知量としたパラメータ群に置き換え，解を求める可能性を高める方向に遺伝子配列を進化 させることで，最適化問題で頻繁に遭遇する複雑な解空間での未知量探索が可能である． 本稿では，GA の概略について述べる． 2 遺伝的アルゴリズム 2.1 概要 遺伝的アルゴリズムは, 1975 年にミシガン大学の John Henry Holland によって提案された, 近似 解を探索する確率的探索アルゴリズムの一種である．生物の進化過程を考慮すると，母集団の中で 環境への適応性が高い個体は高い確率で生き残り，次の世代を残すことになる．この点をモデル化 することで，最も適応性の高い個体，すなわち，最適解を計算機上で求めるものである．GA では 遺伝子コードである個体を生成するために決定変数，つまりは未知量をバイナリ化することで表現 し，複数の個体を構築して個体群を作り出す．その後，各々の個体に対して環境への適応度，すな わち，対象とする問題へのあてはまりの良さが決定され，これが高いものほど次世代に選択されや すく，交叉や突然変異などの遺伝的作用により次世代の個体群を生み出す．この遺伝子操作を繰り 返すことで世代の進行とともに適応度の上昇が期待され，最終的に得られた適応度の最も高い個体 が推定すべき未知量の解を与えることになる． 2.2 初期世代 GA ではまず，対象とする推定量をビット列で表現するために，細胞内の染色体に相当する遺伝 子コードを生成する．たとえば，変数 x の定義域が −5.12 ≤ x ≤ 5.12 で定められた条件において， 1 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 井上一哉（神戸大） ある関数の最大値を求めることを対象とすると，解探索の最小幅を 0.01 に設定した場合， 5.12 × 2 = 1024 = 210 0.01 となり，推定パラメータ x を遺伝子コード化するには，10 ビットが必要になる．つまりは， → −5.12 → −5.11 0000000000 0000000001 ··· → → 1111111110 1111111111 5.11 5.12 のように，2 進ビット列と実数が対応づけられる． たとえば，一様乱数を用いて，10 ビットから成るビット列を 10 個生成してみると， 1 : 0111111011 2 : 0011101111 3 : 1011000000 4 : 0110100011 5 : 1010010100 6 : 0001111100 7 : 0001100100 8 : 1100010000 9 : 0100100011 10 : 1000010000 のような配列になる．一様乱数の生成には，メルセンヌ・ツイスターを用いている．このようにし て生成された遺伝子コード群が世代 0（初期世代）であり，各ビット列を個体（individual），個体 群のことを集団（population） ，個体群の数（ここでは，10）のことを集団の数という．乱数により 生成した初期世代に，選択，交叉，突然変異などの遺伝的操作を与えることにより，次世代の集団 を生成する．集団の数を定める方法は無いため，問題設定に応じて，試行錯誤的に定めることにな る．基本的に，集団の数が増えるほど，計算量は増えることになる． 2.3 適応度評価 遺伝的操作による世代交代の前に，初期生成した個体の環境への適応性，すなわち，適応度 （fitness）を評価する．適応度は適合度とも呼ばれる．これにより，次世代へ残す遺伝子配列の候 補を定めるだけでなく，確率は低いものの，最適解が求まる可能性も有している．言い換えると， GA では，適応度を前もって定義することで，最適化すべき目標を事前に設定していることになる． 一般に GA では，適応度関数は最大化，あるいは，最小化の形で定義され，たとえば，適応度関 数を F とすると， M ( )2 F = ∑ Ci − Cˆi → min i=1 のように表される．ここに，Ci は i 番目の観測データ，Cˆi は i 番目の計算値，M は観測データ総数 である．つまりは，観測データと解析値の残差二乗和が最小となるようなパラメータ，あるいは， 2 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 井上一哉（神戸大） パラメータ群を探索している．この場合，適応度の値が小さい個体ほど，最適解に近い値を有して いると考えられるため，次世代へ残る可能性が高くなるように，選択を実行することになる．な お，適応度関数の最大化を目的とする場合には， F= 1 ( )2 ∑ Ci − Cˆi M → max i=1 のように，逆数をとる方法が簡単である． 2.4 選択 新しい世代を生み出す際には，適合度の高い個体ほど多くの子どもを生むようにすることが GA の選択において基本的な原則となる． ルーレット方式（roulette wheel selection）は一般的に用いられる選択方法であり，適応度に比例 した割合で個体を選択する方法である．たとえば，個体 fi の適応度の値が， f1 : 1.0 f2 : 1.5 f3 : 3.0 f4 : 2.0 f5 : 2.5 であるような場合， f1 + f2 + · · · + f5 = 10.0 であるので，0 から 10 までの乱数 R を一様に発生させる．次に，得られた乱数値 R に従って， 0.0 ≤ R < 1.0 → f1 の個体を選択 1.0 ≤ R < 2.5 → f2 の個体を選択 2.5 ≤ R < 5.5 → f3 の個体を選択 5.5 ≤ R < 7.5 → f4 の個体を選択 7.5 ≤ R ≤ 10. → f5 の個体を選択 のように個体を選択する． ルーレット方式にて選択操作する場合，飛び抜けて適応度の高い個体が存在すると，特定の個体 のみが次世代に残ることになり，多様性の低下につながる．すなわち，淘汰圧が高くなる状況に陥 る可能性を有している． トーナメント方式（tournament selection）は，淘汰圧をある程度制御できる方式であり，集団の 中からある個体数をランダムに選び出して，その中で最も適応度の高い個体を次世代に残す選択方 式である．この操作を集団の数だけ繰り返すことにより，次世代の集団が得られることになる．集 団から取り出す個体数のことをトーナメントサイズ Nt といい，Nt = 3 としたトーナメント選択の 例を図 1 に示す． トーナメント方式はルーレット方式と異なり，トーナメントサイズ Nt の設定によっては，適応 度の低い個体であっても次世代に残る可能性が高まるため，多様性を保持する観点からは有用な方 3 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 Candidates 井上一哉（神戸大） Winners Candidate 1 - Fitness 0.6 Trial 1 Candidate 2 - Fitness 0.8 Winner 1 - Fitness 0.8 Candidate 3 - Fitness 0.2 Candidate 1 - Fitness 0.9 Trial 2 Candidate 2 - Fitness 0.4 Winner 2 - Fitness 0.9 Candidate 3 - Fitness 0.8 . . . . . . Candidate 1 - Fitness 0.1 Trial N Candidate 2 - Fitness 0.1 Winner N - Fitness 0.2 Candidate 3 - Fitness 0.2 図 1 トーナメント選択 Crossover mask Parent 1 1111111 Crossover point 111 Offspring 1 1111111 0100111001 Parent 1 1110100100 1110100100 Offspring 1 & 2 1110100110 1010010101 Parent 2 1010010111 1010010111 Parent 2 0000000 000 Offspring 2 000 0000000 111 図 2 1 点交叉 図 3 一様交叉 式である．また，トーナメントサイズの変更やランダム抽出された個体数の中で最も適応度の高い 個体を決定する操作は容易であることから，トーナメント方式の方がルーレット方式よりもコー ディングしやすいと言える． 2.5 交叉 交叉（crossover）とは，基本的には選択によって選出された個体に対して，ある交叉位置で双方 の染色体の一部ずつを採ってきて，子孫の染色体を作る操作である．交叉は親同士の遺伝子を掛け 合わせる操作であるため，ランダムに 2 つの個体を選んだ上で実行される． 最も単純な交叉方法は，遺伝子配列のある位置を交叉点（crossover point）として一か所選び， 交叉点の前と後で遺伝子を入れ替える方法であり，1 点交叉という．図 2 に 1 点交叉の例を示すま た，交叉点を n 箇所に設ける交叉方法を n 点交叉といい，2 点交叉はよく用いられる方法である． 探査能力の観点から交叉オペレータの能力を評価すると，一般には， 1 点交叉 < n 点交叉 < 一様交叉 の順に効率が良いとされている． 一様交叉（uniform crossover）とは，任意個の交叉点を取れる交叉方法であり，0 と 1 から成 るビット列のマスクを用いて操作される．図 3 に示すように，0 と 1 から成るビット列をマスク 4 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 井上一哉（神戸大） （crossover mask）として発生させ，子ども 1（offspring 1）の遺伝子は対応するマスクが 1 の場合 には，親 1（parent 1）から遺伝子を受け継ぎ，マスクが 0 の場合には，親 2 から遺伝子を受け継ぐ 方法である．逆に，子ども 2 の遺伝子は対応するマスクが 1 の場合には，親 2 から，マスクが 1 の 場合には，親 1 から遺伝子を受け継ぐことになる． 交叉を実行する上で，すべての親から子どもが生まれることを想定することは現実的ではない． そのため実際には，0.7 ∼ 0.9 程度の確率で交叉の実施の有無に関する判定がなされることになる． Individual 1110100110 1010101110 図 4 突然変異 2.6 突然変異 突然変異（mutation）は，ある確率で一部の遺伝子コードの値を変える操作である．基本的に交 叉だけでは，個体の親に依存する限られた範囲の子どものみを生成することになるため，染色体上 のある遺伝子を一定の突然変異率で他の遺伝子に置き換えることにより，交叉だけでは生成でき ない子どもを生成する．そのため，突然変異は個体群の多様性を維持する働きを有しているといえ る．図 4 に突然変異の例を示す．図 4 では 2 か所の遺伝子コードが書き換えられている．突然変 異の確率としては，遺伝子コード長の逆数が候補となる設定値である．これは，各個体のうち，平 均 1 つの遺伝子コードが突然変異により変化することを意味している． 突然変異の操作の後に，適応度関数から各個体の適応度を求め，前述した選択，交叉，突然変異 の過程を繰り返すことで，世代交代しつつ最適解を探索することになる．世代交代の過程で最適解 が得られたと判断されれば，その時点で GA は終了となる．たとえば，残差二乗和がある基準 ε よ りも小さくなったケースを最適解と考える．あるいは，世代交代数を設定しておき，最終世代まで 残った集団の中で最も適応度の高い個体を最適解と見なす． 2.7 GA の長所と短所 これまでのまとめとして，図 5 に GA の流れ示す．対象とする問題によっては，集団の数や交 叉，突然変異の確率を変えることで最終的に得られる解に変化が生じる場合がある．GA に関わる 設定値については，一般的な設定方法は無いため，試行錯誤的に値を変える状況も出てくる． 最適化問題に GA を適用する上での短所として， (1) GA の理論は確立していない． (2) GA は確率的要素を多く含むため，時間をかけても解が見つかる保証はない．簡単には，集 団数や世代交代数を増やしても最適解が見つかるとは限らない． (3) 経験的要素が大きく，特に，GA オペレータの設定に対する一般的な基準がない． ことが挙げられる．一方で，長所を挙げると， (1) アルゴリズムがシンプルであり，実装（コーディング）しやすい． 5 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 START 井上一哉（神戸大） ? Generation of population using random numbers Input of computational conditions ? Decoding into real numbers for each individual Forward analysis ? Evaluation of fitness for all individuals Objective function ? HH H HH HH Have the stopping H HH criteria been met? HH HH H H Yes GA operations No ? Selection ? Crossover ? Random search mutation ? END 図 5 GA のフローチャート (2) 幅広い応用範囲を有しており，多点探索アルゴリズムのため，関数の連続性の影響を受けに くい． (3) 集団数と世代交代数の設定条件に依存するものの，実用時間内に比較的良好な解を求めるこ とができる． である．最適解とは言えないまでも, 最適解に近く，実用に耐え得る解を得られるケースが多いの は GA の特徴であり，時間的効率を考えると，利用価値は高い方法と考えられる． 3 おわりに GA は一長一短ある手法ではあるものの，基本的には，与えられた環境に適応する適応度を決め る情報のみを必要として，数理モデルなど解くべき問題の性質に関する情報をほとんど必要としな い点は，大域的な探索が可能である点と合わせて，適用価値のある手法と考えられる．GA の適用 例としては，巡回セールスマン問題やナップサック問題が有名であるが，土木工学や地盤工学の分 野においても多くの適用事例がある． 6 土木学会応用力学委員会逆問題小委員会ホームページ 逆問題副読本 井上一哉（神戸大） 参考文献 [1] 伊庭斉志 : 遺伝的アルゴリズムの基礎 –GA の謎を解く–，オーム社，254p., 1994. [2] Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning, AddisonWesley Publishing,Inc., 412p., 1989. [3] 坂和正敏，田中雅博：日本ファジィ学会編 ソフトコンピューティングシリーズ 遺伝的アル ゴリズム，朝倉書店，1995． [4] 北野宏明：遺伝的アルゴリズム，産業図書，328p.，1993． [5] Reed P., C. Minsker, and A.J. Valocchi: Cost-Effective Long-Term Groundwater Monitoring Design Using a Genetic Algorithm and Global Mass Interpolation, Water Resources Research, Vol.36, No.12, pp.3731–3741, 2000. [6] 風間基樹，朴 燦燻，柳澤栄司，内藤秀信: 遺伝的アルゴリズムを用いた有機塩素化合物地下 水汚染源の推定法とその適用, 土木学会論文集, Vol.631, No.III-482, pp.71–81, 1999. [7] 井上一哉・松永尚子・正木一平・田中勉：分散性の異なる不均質多孔質体内における縦分散 現象に関する実験的検討，水工学論文集, Vol.52, pp.403–408，2008. 7
© Copyright 2024 ExpyDoc
