遺伝的アルゴリズムの実現方法

• 全体方式の決定： 現在，解こうとしている問題を分析し，GAが適当であるか，既存の他の方式例えば動的計画法などの数理計画法が適していないか，などを 検討する．さらにGAを適用するに際してGA単独で処理するか他の方法と組合わせた例えばハイブリッド方式にするかなども検討する．その際，すでに解かれている前例などを参考にするとよい．
  　GAを適用すると決定したらさらにGAのプログラムをどのようにして作成するかを決定する．GAの基本部分である遺伝子操作関係は標準プログラムとしてパッケージ化されているものがあるので，これを利用する場合が多い．多くのパッケージプログラムが利用可能なので，どれを使用するかが問題となる．この場合，対象分野に関するプログラムは自分で作成する必要があるので，その検討も併せて行う必要がある． 場合によってはすべてを自分で作る場合もある．
• 遺伝子表現方法の決定： GAで問題を解くためには先ず問題を遺伝子で表現する必要がある．生物の遺伝子と異なりGAは人工物なので多様な表現が可能であり，実際に各種表現方法が使用されている．
• 適合値計算方法の決定： 遺伝子表現が決まるとつぎに重要なのが適合値の計算方法を決定することである． GAでは適合値を指標にして進化を行うので，最も重要な要素の１つである． 適合値の計算部分は簡単なものから複雑なものと多様である．全体システムで 述べてようにこの部分がGAに匹敵するプログラムになる場合もある．
• 遺伝的オペレータの決定： 実際にGAを適用する方法がこの遺伝的オペレータであり，選択，交叉，突然変異などの 方式を検討し，決定する．これは遺伝子表現とも関係が深く，その表現方法により 方式も変わってくる．
• パラメータ値の決定の決定： GAの性能を決定する各種パラメータ値を決める必要がある．これらは 多くはシミュレーションを通して決定する．
• その他： 入出力の与え方やグラフィック表現など，プログラムを作成するに必要な 各種の事項を定める．特にGAとしてパッケージソフトを使用する場合に 十分な検討が必要である．

全体方式の決定

GAの最大の特長は対象とするものを遺伝子で表現でき，それに従って適合値を計算できれば，いかなる問題も解くことができることである．数値計画法のように問題種類ごとにアルゴリズムを考える必要がない．その意味で汎用性のある手法といえる．しかし，一方こうして得られた解が最適であるとの保証はなく，多くの場合準最適値となる点は承知しておく必要があるが，実用的な問題では必ずしも最適値ではなくてもそれに近い解が得られれば十分な場合が多い．またGAの行う探索はランダム探索の一種であり，広帯域の探索を行うので極値解を抜け出ることができる優れた点を持っている．

GAの基本的な考えは適合値を指標にしてこれを最大にする方向に遺伝子を進化させることにある．従って，プログラムの基本的な部分は適合値を入力として最適な遺伝子を出力とするように作られる．この部分は対象とするシステムには直接関係しないので，標準プログラムとしてパッケージ化が可能であり，そのようなパッケージがパブリックドメインソフトとして流通している．一方，遺伝子が与えられてその適合値を求める部分は対象システムに直接関係するので，対象ごとにプログラムを作成する必要がある．従って多くの場合，図に示すように標準のパッケージソフトと個別の対象システムごとに作成した適合値計算ソフトと組合わせて全体システムを作成する方法を採用する場合が多い． GAのパッケージソフトについては別に GA用ツール にて説明している． この他，得られた結果のグラフィックによる表示プログラムなどは個別に作成する必要がある． もちろん全てのプログラムを一体として作成する場合もある．

遺伝子表現の決定

GAを適用する際に決めねばならないことがいくつかあるが，その中でも最も基本的なものがこの遺伝子表現である．GAは人工物なので生物と異なり各種の表し方があるが， その中でも代表的なものがつぎの２つである．

• ストリング表現：最も基本的な表現方法であり，多く使用されている． ストリング表現の中でも通常はバイナリビットストリングが使用されている． これは生物の表現に近いものである．生物ではアデニン(A)，チミン(T)， グアニン(G)，シトシン(C)という４つの塩基の組合せで表されている． バイナリビットストリングを適当なサブストリングに区分けして，対象の性質を 表すようにしている．従って，ここでは遺伝子で表現すべき内容とそれを 表すサブストリングの長さと全体すなわち染色体を決定する．
• 順序数表現：この表現は人工物用として考え出されたものである． 通常，１から所要の整数ｎまでの順序数により表すものである．代表的な適用例は セールスマン巡回問題であり，この場合は巡回する都市を順序数で表している． この表現は以外に応用分野が多く，使いなれると便利な方法である． この表現方法では交叉，突然変異などの遺伝子操作がストリングとは全く異なった方式を採用する必要がある．

上記が代表的な表現方法であるが，この他に多くの表現方法が用いられている． その中でいくつか挙げるとつぎのものがある．

• 実数表現：これはストリング表現の拡張であり，内部的には実数をストリングに 変換しているので，広い意味ではこれに入るが，使用しやすさを考えて実数で直接表せるようにしている．この中には整数も含まれるがこれはストリングと全く同一である．
• ハイブリッド表現：遺伝的プログラミングではツリー表現が使用されているが， これと同等な表現を整数と順序数の組合せで作ることができる．このように異なった 表現を組合わせて表現能力を高めることも可能である．
• 複数染色体：生物に準じて一連の遺伝子の集まりを染色体と呼ぶことにして， このような染色体を複数使用し，それぞれに固有の遺伝子操作をさせる方式もある．

対象を遺伝子に表現する方法はひとつではなく，複数考えられる場合が多い．その場合にどれを採用するかは以下の点を考慮して決めるのがよい．

• 無駄な表現のない方法を採用する：最適問題などでは制約条件がつく場合が 多い． もし遺伝子が制約条件を外れるものも表現している場合にはそれを対象から除くか， あるいは適合値の計算にて述べるようにその計算に配慮する必要がある． これらにより探索範囲が無駄な探索を含めて広くなりすぎたり，あるいは特別な処理が 生じ時間がかかる．このような問題をなくすためには制約条件外を表現しないような 遺伝子表現が望ましい．
• 探索領域の狭い方法を採用する：前項とも関連するが，GAによる探索を効率的に 行うためにも探索領域ができるだけ狭くなるような表現方法を採用する．

適合値計算方法の決定

適合値の計算方法は適用する問題により大きく変わってくる．例えばセールスマン巡回問題では適合値は都市間の巡回距離の合計が使用されるので その計算は簡単であるが，シート材の最適切断で順序数表現を使用した場合は 所要のシートの長さを適合値に採用しているが，順序数で表した並べ方の順番から シートの長さを求めるにはかなり複雑な処理を必要とする． 従って，このような適合値の計算アルゴリズムが求まれば問題の大半が解けたと言っても過言ではない．この方法は問題によって大きく異なってくるので，具体的な問題の取り扱いを通して学ぶより他に方法はない．しかし，例えば最適問題を解く際にそのための アルゴリズムを考え出すのに比べて適合値の計算アルゴリズムを求めるのは一般に 容易であり，このことがGAの特長になっている．
なお，適合値は必ずしも計算でのみ求める必要はなく，例えば人間の感性を問題にする場合には人間の感性により与える方法もある．

制約条件付き最適化問題或いは多目的最適化問題などでは，それを処理する方法として 適合値の計算でつぎの扱いをすることが多い．

• 制約条件の扱い：遺伝子が制約条件外を表す場合にそれを除外する方法として， 遺伝子が制約条件外を表現する場合には適合値を最小にして，選択されないようにする方法が通常使用されている．
• 多目的最適化問題の扱い：一般に多目的最適化問題では 全ての目的関数を最適にする完全最適解を求めることは不可能であり，妥協解を 求めることになる．このような解をパレート最適解と呼んでいる． このような問題の処理として，それぞれの目的関数ごとに適合値を求め，その重み付き和によりひとつの適合値にまとめる方法を採用する場合が多い． そして重みを調整することにより，それぞれの目的の達成の程度を調整し妥協を図ったパレート最適解のひとつを求めることができる．
  なおGAではこのようなパレート解を直接求めるパレートGAと呼ばれる方式もある．

遺伝的オペレータの決定

GAを適用するに際してこれまで述べてきたほかに各種のものを決める必要がある． その主なものを簡単に述べる．

• 選択の方法：優れた形質を持った個体を後の世代に残すために，集団より選択する方法で各種の方法が使用されている．以下，代表的な方式を挙げておく．
  1. ルーレットホイール方式：最も基本的な方式であり，各個体の適合値に比例した確率で選択して次世代に残す方法である．この際，通常スケーリング関数を使用して適合値の差異を拡大または縮小するのが普通である．スケーリング関数には通常線形関数が 使用されるが非線形関数を使用する場合もある．スケーリングを考える際には適合値の 最大値や最小値およびその変化様相，即ち遺伝子表現の変化に応じてどのように適合値が変化するか，を考慮する．スケーリングの状況により収束状況が変化するので，実際の パラメータ値はシミュレーションの結果を見ながら決める場合が多い．
  2. ランク方式：各個体を適合値が大きくなる順番に並べて，その順番の数に比例した確率で選択を行う方法である．パラメータとしては比例の傾斜値があり，それにより 選択の程度を変えることができる．この方式の特長は適合値による差がルーレットホイール方式ほどは出ないので初期収束の面でよい結果がでる場合があることである． また選択確率値は適合値そのものには直接関係しないので，適合値による調整は必要としないので使用しやすい．
  3. トーナメント選択：集団から所定の数の個体をランダムに取り出し，その中から適合値の高い個体（通常は1個体）を次世代に残す方法である． 取り出す個体は通常は2個体が使用されている．
  4. エリート保存選択：各世代において最も優れた個体即ち適合値の最大の個体を エリートとしてそのまま残す方式である．これにより集団は常に適合値の非減少方向に 進化することが約束される．
• 交叉の方法：ここではストリング表現の場合の交叉方法について述べる． 順序数表現の場合は方法が全く異なるので，別に述べる． 代表的な交叉方法としてはつぎのものがある．
  1. 1点交叉：染色体の中でランダムに選んだ1点で交叉を行う方法であり，最も基本的な方法である．
  2. 2点交叉：染色体の中でランダムに選んだ2点間で交叉を行う方法である．
  3. 多点交叉：3点以上をランダムに選んで交叉する方法である． 通常はマスクパターンを用意し，これにより交叉するビットパターンを決め， これにより交叉する箇所を指定し，その点のビットを確率により変化させる． 交叉する点が増える分，多様な交叉が実現できるが反面ビルディング仮説の面からは 必ずしもよくはならない．
• 突然変異の方法：これも順序数表現の場合は特殊になるので，ストリング表現の 場合について述べる． 染色体の中から突然変異を行わせる場所を所定の確率で選び，確率で対立遺伝子に 変化させる方法である．これにより集団が局所解に陥り，遺伝的操作による進化を 止めてしまうのを防止できる．しかし，変化の隔離が高すぎると収束せずに変動を 繰り返す恐れがでてくる．これを防止するため，初期世代では確率値を高めて遺伝子の 変化の程度を高めて，広域探索が可能になるようにし，世代の進化に応じて 確率値を小さくして最適地近傍から逸脱するのを防止する可変突然変異確率方式も 採用されている．

パラメータ値の決定

GAを適用する際にはつぎに述べる各種パラーメータ値を決める必要がある． 一般にこれらの値は理論的に定めることが難しく，多くの場合は類似のシステムから推定される適当値を最初に与え，シミュレーションを通じて最適値を見つけ出す方法を用いる場合が多い．

• 集団の個体数
• 最大世代数
• 適合値計算のパラメータ値
• 各種確率値：交叉，突然変異などに関連する確率値

その他

以上に述べた他につぎの事項を検討する必要がある．

• 入出力関係の与え方：特に標準パッケージのGAを使用する場合にはそれぞれのパッケージに固有の方法で与えることになっているので，それぞれに応じた方法を採用する必要がある．特にGAに関するパラメータ値の与え方，GA部と他の部分との信号のやりとりの仕方，例えば適合値と遺伝子表現のやりとり方法などがある．
• グラフィック表現：最終的に得られた結果を図などで表現する場合が多い． 一般に標準パッケージのGAにはこの部分は含まれていないので，ユーザ側で作る必要がある．