遺伝的アルゴリズムの基本的な考え方

GA は目的関数における入出力関係のみを用いて最適化を行うため，アルゴリズムそのものに ついての深い知識がなくても扱うことができる.しかし，最適化の結果を評価するためには基礎的な知識が必要となる.GA は生物の進化過程を模倣した近似最適化アルゴリズムである.GA では文字列で表現される個体集団に対して遺伝的操作を繰り返して適用することで，近似的な最適解を得ることが行われる.最適化は一般的には基準に対しての評価が最も適切とされる解を求めることを指すが，GA においての最適化とは目的関数に対しての評価が最も高い解を求めることである.以下の図にパラメータ空間と解空間を結びつける目的関数のイメージを示す.パラメータ空間 X と解空間 Y を考え，目的関数を f : X → Y とすれば，最適化は最大値 f′ ∈ Y と，そのときの x′ ∈ X を求める問題と表現することができる.

最適化アルゴリズムは対象となる問題を特定した手法と，対象とする問題を特に選ばない手法に分類される.対 象となる問題を特定した手法は，解くべき問題に関する情報を利用し，短時間で最適解を得ることができる.しかし，解くべき問題に関する情報が与えられない場合は目的関数における入出力関係のみを用いて最適化を行う.一般的に広範囲の最適化問題に対して適用可能な最適化アルゴリズムが考案されている.これをメタヒューリスティ クス (Metaheuristics) と呼ぶ.メタヒューリスティクスのほとんどは自然界に見られる法則を利用しており，より 大域解を見つけ出そうとしていることが特徴的である.メタヒューリスティクスの一種に生物の進化過程を模倣 した進化的アルゴリズム (Evolutionary Algorithm; EA) がある.GA は EA のなかで最も用いられている.
GA は 0 か 1 の文字列で表現される個体の集団に対し，遺伝的操作を繰り返すことで最適解を求める.以下に， 遺伝的アルゴリズムの手順について述べる.以下の図に単純な遺伝的アルゴリズム (Simple GA) の流れを示す.選択 (Selection)，交叉 (Crossover)，突然変異 (Mutation)，適応度 (Fitness) の評価の一連の流れが 1 世代分の操作に相当 する.この世代を重ねることによって個体集団の遺伝子を変化させ解を探索する.適応度は目的関数によって与えられる.

まず，初期集団生成の作業では遺伝子で表現された個体の集団を乱数によって生成することが行われる.ここで は個体集団における個体の数を人口数 (Population) と呼ぶことにする.選択は集団内で適応度が高い個体を選び， 次世代に遺伝子を残す作業である.代表的な選択方法にはルーレット法 (Roulette)，ランキング法，トーナメント 法があるが，いずれの方法も個体のもつ適応度の値が大きいものを多く残す.本研究で用いるルーレット法では個体と全体の適応度から算出した確率を用いており，適応度に比例した割合で選択する.ある集団 P に存在する個体 i の適応度を f_i とおくと，その個体 i が次世代に残される確率 p_i は，

で求める.適応度の高い個体ほど選択される確率が高くなる.以下に集団の個体が 6 体あった場合のルーレット法のイメージを示す.適応度の値に比例した角度で分割されたルーレットを回し，止まったところに対応する個体を選択するという発想から提案された手法である.ルーレット法には個体間での適応度の差がないときに，それ ぞれの個体の次世代に残される確率に差がつかなくなってしまう問題点も存在するが，シグマスケーリング (Sigma Scaling) という手法によって改善を図っている.

選択の次に行われる交叉は集団内から選ばれた 2 つの個体の間で遺伝子の一部を交換する操作である.それぞ れの個体に対してある確率で交叉が適用される.代表的なものには一点交叉，二点交叉，一様交叉などがある.一 点交叉は交叉を行う点をランダムに選び，その点以降の文字列を互いに交換する.二点交叉も同様にランダムに 選ばれた 2 点の間の文字列を交換する.一様交叉はビットマスクをランダムに生成して，ビットマスクの文字列 が 1 となっている位置で 1bit 分の遺伝子をそれぞれ交換する方法である.本研究では部分解がまとめて失われな いようにするため，一様交叉を採用している.遺伝的操作の最後に行われる突然変異は集団の多様性を維持するた めに，個体を構成する遺伝子の文字を他の文字に変換する操作である.突然変異も一定の確率で適用するが，数 %以下の非常に低い値を設定する.最近ではGA 以外にも PSOや差分進化 (Differential Evolution; DE)が多く用いられている.構造力学ではトポロジー最適化などもある.以下の図は形状などに応用する際の関係図である。