GAに関する用語

遺伝子

遺伝形質を規定する因子．メンデルのエンドウ豆における 遺伝の研究において遺伝を規定するものとして仮想的な遺伝因子が考えられた． この遺伝因子がのちに遺伝子と名付られた．具体的にはDNA分子中の遺伝的に何らかの固有の意味を持つ，決まった長さのヌクレオチドの配列である． この遺伝子が線状に並んだものが染色体である． GA では一つの意味がある１個または数個のビットコードの集まりを遺伝子という．例えばあるパラメータをバイナリーのコードで表わした場合そのバイナリーコードを 遺伝子という．

遺伝子座(locus)

染色体上で１個の遺伝子が占める位置をいう． GAではバイナリビットストリング表現の場合に各ビットの位置をいう．

遺伝子型(genotype)

１個あるいは数個の対立遺伝子の遺伝子座の遺伝的 構成をいう．GA では遺伝子のコード組み合わせパターンをいう．バイナリビットストリングの場合は0と1からなるパターンになる．このパターンにより表される個体の形質を 表現型という．

遺伝的アルゴリズム(genetic algorithms, GA)

J.Holland やD.E.Golodberg らが中心になって推進してきた方式で生物の 遺伝機構を模擬し，対象を生物の遺伝子に相当するビットストリングなどで表現し， 選択，交叉，突然変異の操作を通じて進化させ，例えば最適解などを得るのに用いる 方式． この種の類似の方式の代名詞にもなっている．

遺伝的プログラミング(genetic programming)

J.R.Kozaにより推進された方式で遺伝子の表現にプログラムを導入したもので ある．従って，掛け算，加算，減算などの演算子を使用して表現し， 木構造の問題にも適用できる． 交叉や突然変異などの方式も遺伝的アルゴリズムのものとは異なってくる． 演算子を扱うことからそれに適したLisp言語で当初は開発されたが，現在は各種言語で 実現されている．

エピスタシス(epistasis)

ある個体の適合値が多数の遺伝子の相互作用に依存する場合にそれをを表わす． GA では適合値が，染色体を表わすストリングの各要素の非線形組み合わせにより 決まる場合をいう，すなわち非線形性がある場合をいう．

エリート選択(elitist selection)

その世代の最良の個体を必ず次世代に残す選択方式をいう．

クラシファイヤシステム(classifier system)

事例や推論により学習のできるルールベースシステムであり， ルールの集合よりなる集団に対してGAを適用することによりルールの進化を行なう． ルールの記述方法から現在，２つの取り組み方がある． ひとつはミシガン方式(Michigan approach)といわれ，集団の各個体がひとつのルールを表し，集団全体で一組のルール集合を表している． 今ひとつがピッツバーグ方式(Pittsburg approac)といわれ， 各個体が一組のルール集合になっている．従って集団は各種のルール集合の集まり となっている．

グレイコード(Gray code)

整数を表す2進コードで，隣り合った整数間のハミング距離が１となる方式． 遺伝子表現の中で使用される場合がある．

交叉(crossover)

２個の遺伝子間で互いにその一部を交換する操作をいう． GA では遺伝子を１点で切りその前後を入れ換える１点交叉や，２点で切りその間を 入れ換える２点交叉のほか多点交叉など各種の方法が用いられている．なお， 日本語の用語では「交差」も使用されている．

ゲノム(genome)

生物の全遺伝情報をいう．

勾配法(gradient method)

最適化の手法のひとつであり，目的関数の微係数， すなわち勾配方向に変数を変化させることにより， 最適解を求める方法である．問題の特性よっては最適解に到達せず 途中で留まることがあり，それを極値解と呼んでいる．山登り法あるいは最大傾斜法ともいわれる．

初期収束(premature convergence)

世代の初期に集団の各個体の遺伝子が殆ど同じになり， 多様性が失われてしまい，交叉などの遺伝的操作によっても それ以上集団の適合値が改善されなくなることがあり，これをいう． GA の収束のためには初期収束を回避する必要があり，選択操作などに 種々工夫されている．

進化型計算(evolution computation , EC)

GA，GPなど生物の進化様式を取り入れた計算方法の総称として最近使用されるようになってきた．

進化戦略(evolution strategy, ES)

I.Rechenberg, H-P.Schwefelらにより研究された方式で， 主として実数パラメータを対象にしている．選択と突然変異を主としている．

進化プログラミング(evolutionary programming, EP)

L.Fogelらにより推進された方式で当初はオートマトンの進化用として 研究された．基本的な演算子は突然変異であり，交叉は使用されていない．

染色体(chromosome)

当初は細胞分裂時に現われる塩基性色素によく染まる糸状構造体を指していた． その後この構造体が遺伝子の実体であることが判明してから線状に並んだ遺伝子を 指すようになった．染色体の実体はDNA分子であり，これが糸状に結合してできた 巨大分子である．GA ではある問題を表わす全体をいい，遺伝子の集合でもある． 通常はビットストリングにて表わされる．染色体が1遺伝子で構成されている場合は 遺伝子と染色体は同じになることもあり，染色体と遺伝子が同意義で使用される 場合もある．

スキーマ(単数:schema, 複数:schemata)

GA の染色体を表わすストリングにおいて意味のあるパターンをスキーマと いう．これは染色体間の類似性を表わす型紙のようなものである． 例えば染色体がバイナリストリングの場合， スキーマは1, 0, * の組み合わせで表わされる． 一例を挙げると1*01**0** のとおりになる．ここで * は 0,1 のいずれが来てよい ことを表わしている． 0 または 1 となっている場所を固定位置ということにすると，最初と最後の固定位置 間の距離（この例では6）を定義長（defining length）， 固定位置の数（この例では4）を次数（order）という． スキーマの内，特に定義長が短く，次数が低く，かつ 適合度の大きなものをビルディングブロックと呼んでいる．

ゼネレーション・ギャップ(generation gap)

集団の個体の内，各世代で新しくなる個体の割合をいう． 残りの個体はそのまま次世代に受け継がれる．

選択(selection)

生物の世界における適者生存に相当するもので， GA においては交叉などのために各個体を集団より選択的に取り出す操作をいう． 選択の方法としては各種研究されている．代表的な方式にルーレットホイール選択， ランク選択およびトーナメント選択がある．

ダーウイン主義(Darwinism)

Darwinにより提唱された生物の進化の原理である． 生物は遺伝における特性の変化（突然変異）と環境への適合から くる自然選択により進化したものとの考え方．

対立遺伝子(allele)

同じ遺伝子座を占めることができる幾種類の遺伝子をいう． GA では各遺伝子座が表わすことができる値をいう．バイナリビットストリングでは 0,1をいう．

だまし(deceptive)

適合値の高い個体はビルディング仮説により世代の進行に応じて増加するはずで あるが，これが成り立たない場合をいう． この現象は，よいビルディングブロックの集まりが，全体として適合値の増加を もたらさず，かえって減少させる場合に起こる．

デオキシリポ核酸(DNA)

生物の遺伝子の本体であり，二重らせん構造をしている． DNAの鎖はD-デオキシリボースという糖とリン酸が交互に結合しており，各々の 糖には１つの塩基が結合している．塩基にはアデニン(A)，グアニン(G)，シトシン(C)， チミン(T)の４種類がある．２本の鎖はこれら塩基をとおして結合しており， その塩基の配列により遺伝情報が表わされている．これら4種類の塩基は互いに結合 する相手が決まっており，AとT，GとCしか結合しない．従ってA-T結合とG-C結合の 組み合わせにより遺伝情報が表わされることになる．

適合関数(fitness function)，適合値(fitness value)

適合値は GA にて各個体の望ましい状態への接近の程度を表わすものとして， 遺伝子の値より計算される値であり，適合関数はそれを計算する関数である． 適合関数は適合値が目的とする状態に近いほど大きな値となるように決められる．

トーナメント選択(tournament selection)

集団から所定の数の個体をランダムに取り出し，その中で最も適合値の高い 個体（通常は１つ）を次世代に残す方式である．取り出す個体の数としては２個体の 場合が多い．

突然変異(mutation)

遺伝子の状態が外界よりの刺激，例えば光や放射線により変化する現象をいい， 進化に大きく貢献している． GA では一部の遺伝子の値を確率的に変更する操作をいう．通常は染色体の始めから 操作しつつ各遺伝子座の値を確率的に変化させる操作を行なう．

ハミング距離(Hamming distance)

２つの2進ベクトル間でビットが異なったものの数をいう．

表現型(phenotype)

遺伝子によって表わされる生物の形質をいう． GA では遺伝子により表わされる情報，例えばパラメータの値，などをいう．

ビルディングブロック(building block)，ビルディングブロック仮説(building block hypothesis)

スキーマの内，特に定義長が短く，次数が低く，かつ適合度の高いものをビルディングブロックという． ビルディングブロックは交叉，選択を通じて残り，世代の進行に応じてその数を増す． これをビルディング仮説と呼んでおり，GA の働きの中心をなす考え方である．

ボルドウイン主義（Baldwinism）

後天的に学習や適応の結果が遺伝により子孫に継承されなくとも進化を 加速するという考え方をいう．このような作用をボルドウイン効果と呼ぶ． GAにもこのような考えを取り入れた方式が研究されている．

ラマルキズム（ラマルク主義，Lamarckism）

後天的に獲得した形質が遺伝により子孫に伝えられるとの主張であり， 生物の世界では殆ど支持されていないが人工的なGAの世界では可能であり， この思想を取り入れた方式が研究されている．

ランク選択(rank selection)

選択操作の一方式．個体を適合値の順に並べ，その順番に比例した確率で 選択する方式． 適合値の差による選択確率の差がルーレットホイール選択ほど大きく出ないため， 初期収束の点でよい結果がでる場合もある．

ランドスケープ(landscape)

適合度のランドスケープのことで，すべての可能な遺伝子型空間における 適合度の表現である． 例えば長さmビットの遺伝子型の適合度のランドスケープはm+1次元空間における軌跡で表すことができる．

ルーレットホイール選択(roulette wheel selection)

選択操作において適合値に比例した確率で選択する方式をいう．