遺伝的アルゴリズムに関する用語の簡単な説明を記載したものです．
INDEX :
A :
B :
C :
D :
E :
F :
G :
H :
I :
J :
K :
L :
M :
N :
O :
P :
Q :
R :
S :
T :
U : V : W : X : Y : Z :
|
[ A ]
対立遺伝子（allele）
各遺伝子座に入りうる遺伝子の候補．例えば，ビット型GAならば“0”と“1”が対立遺伝子となる．
[ B ]
ベイジアンネットワーク（bayesian network）
多くの変数があるときに，変数間の定性的な依存関係をグラフ構造によって表し，定量的な関係を条件付き確率で表したモデル．任意の確率分布を表現できる．
関連リンク : [
ベイジアン最適化アルゴリズムに関する調査（１） ] [ 第49回研究報告 ]
ビルディングブロック（積木）仮説（building block hypothesis）
最適解に近い良い解は，部分解が組み合わされて生成されるという仮説．この仮説が成立するには，表現型が近い個体は遺伝子型も類似していること，遺伝子座間での干渉が少ないこと，といった条件が必要になる．
[ C ]
形質遺伝（characteristic preserving）
親が持つ解の構成要素（building blocks）を子に適切に継承させること．
染色体（chromosome）
複数の遺伝子の集まり．
染色体長（chromosome length）
粗粒度並列化モデル（coarse grained parallel model）
通信量と比較して相対的に各プロセスに割り当てられる計算量が多い並列化モデル．島モデルがこれにあたる．
Compact Genetic Algorithm : compact GA
G.R. Harik ＆ F.G. Lobo ＆ D.E. Goldberg（ IlliGAL ）によって考案された，設計変数間の依存関係を考慮しない，ビットストリング型の確率モデル GA．母集団は，各ビットの割合を示した1つの確率ベクトルによって表現される．選択は確率ベクトルの更新で，交叉は確率ベクトルからの個体の生成で，それぞれシミュレートする． オーダ1の問題に対しては，トーナメント選択（サイズ2），一様交叉を採用したsimple GA（sGA）と同等の振る舞いをする．メモリ使用量が少ないという利点があるが，エピスタシス性が強い場合には適さない．
関連リンク : [ IlliGAL Home Page ] [ 第36回研究報告 ] [ 第38回研究報告 ]
交叉（crossover）
遺伝的操作の1つで，複数の個体内の染色体の一部を組み替えて新たな個体を生成する操作のこと．一般的には，2つの親個体から2つの子個体が生成される．また，交叉は交叉率と呼ばれる確率に従って個体に適用する．
交叉率（crossover rate）
ある個体の組で交叉が起こる確率．例えば交叉率が0.8なら，母集団のうちおよそ8割の個体が交叉を行う．sGAでは0.6が良いとされている．
[ D ]
定義長（defining length）
スキーマにおいて，左から見て最初のワイルドカードでない記号から，最後のワイルドカードでない記号までの距離をいう．たとえば，スキーマ{*0*1*}の定義長は2である．
設計変数（design variable）
分散遺伝的アルゴリズム（Distributed Genetic Algorithm）
Taneseによって提案された．GAの母集団を複数の分割母集団（島）に分割し， 各島内で遺伝的操作を行うというGAの並列化モデルの１つである．DGAでは各島間で解探索の情報を交換するために，移住という操作を行う．島モデルともいう．
関連リンク : [ISDL Report：分散遺伝的アルゴリズム(DGA)の基礎 ，分散GAを応用したアルゴリズム]
[ E ]
エピスタシス（epistasis）
表現型や適合度が，複数個の遺伝子座の影響を受けて複雑に決定されること．
Estimation of Bayesian Network Algorithm : EBNA
R. Etxeberria ＆ P. Larrañaga によって提案された確率モデル GA．ビットストリング型であり，設計変数間の依存関係を考慮する．確率モデルに ベイジアンネットワークを採用する．できるだけ高速かつ正確に 確率モデルを構築することを重視しており，最適なベイジアンネットワークの探索などに近似を用いている．
関連 : [ 第49回研究報告 ]
進化的停滞（evolutionary stagnation）
探索が進み個体間の適合度に差がなくなってきたとき，選択圧がかかりにくくなるために，最適解の方向に探索が進まない現象のこと．
[ F ]
細粒度並列化モデル（fine grained parallel model）
プロセッサ1つに割り当てられる個体は1つまたは比較的少数となる並列化モデル．各プロセスの計算量と比較して相対的に通信量が多い．セルラーモデルはこれにあたる．
Fisher の「自然選択の基本定理」
進化速度と集団の分散は比例する．
関連 : [ 第10回研究報告 ]
適合度（fitness）
各個体の評価指標のこと．対象関数の評価値（evaluation value）に基づいて算出される．適合度は一般的に非負であり，高い値ほど最適値に近い評価値を持つ個体を示す．
[ G ]
遺伝子（gene）
個体の形質を規定する基本構成要素
genetic drift
同じ適合度を持つ複数の異なる遺伝子型が存在する時に，淘汰圧がかからなくなる現象．ただし，有限の母集団においては，最終的にいずれかの染色体に収束する．
関連 : [ 第35回研究報告 ]
世代（generation）
遺伝的操作の手順の繰り返しの1単位．
世代交代モデル（generation alternation model）
子を生成する親の選択(複製選択)と，次世代に生き残る個体の選択(生存選択)を規定するもの．
関連リンク：[ISDL Report：20050809004]
世代交代の連続化（generation order）
子を生成した親個体にも生存の機会を与える戦略．
遺伝子型（genotype）
遺伝子型はオペレータの操作対象となる染色体構造である．表現型は設計空間内での構造であり，設計変数値のこと．交叉，突然変異などは遺伝子型で行う．表現型は染色体の評価などに利用する．表現型から遺伝子型へ変換することをコード化といい，遺伝子型から表現型へ変換することをデコード化という．
[ H ]
ハミング距離（hamming distance）
2つの個体の染色体において異なる遺伝子の数．
Hill Climbing with Learning : HCwL
Kvasnicka ら（1995）によって提案された最適化アルゴリズム．PBILを拡張したものである．
関連リンク : [ 第41回研究報告 ] [ 第44回研究報告 ]
Stochastic Hill Climbing with Learning by Vectors of Normal Distributions : HCwLbVoND
Stephan Rudlof らによって提案された，設計変数の依存関係を考慮しない，実数値型の確率モデル GA．Kvasnicka らの，HCwL を拡張したものである．候補解の各設計変数を確率ベクトルで表現する．compact GAや，PBILで用いられている確率ベクトルの考え方を，実数値に拡張している．確率ベクトルの各要素は，正規分布（ガウス分布）である．正規分布の平均値 m は，ヘッブの学習則（Hebbian Learning） に従い，母集団内の良好な探索点群から推定される．標準偏差 s は世代を経るごとに等比的に小さくなる．
関連リンク : [ 第44回研究報告 ]
ヘブの学習則（Hebbian Learning Rule）
Hebb により提唱された学習則で，シナプス前細胞と時間的に一致してシナプス後細胞が興奮したときに，そのシナプスの伝達効率が増強されるというものである．ヘブの学習則をニューラルネットに組み込んだパーセプトロン では，発火した出力へのリンクに対応する重みを増加させる．
関連リンク : [ 第44回研究報告 ] [ NeuroDimension ] [ 山形大学工学部応用システム工学科北嶋研究室 ] [ 神戸大学国際文化学部 ]
[ I ]
IlliGAL Report
個体（individual）
GAが操作する遺伝子のこと．または，GAの探索点のこと．
島モデル（island model）
個体の母集団を複数のサブ母集団（島）に分割し，サブ母集団ごとに遺伝的操作を適用し，ある間隔で移住操作を行う．
[ J ]
ヤコビ法（Jacobi method）
実数の対象行列の固有値と固有ベクトルを同時に求める簡単な反復法．
関連リンク : [ 第37回研究報告 ]
[ L ]
線形正規化（linear normalization）
順序付けられた各個体に線形に増加（減少）するような適合度を生成するスケーリングである．
線形スケーリング（linear scaling）
各個体の評価値をある直線の方程式によって，適合度に変換するスケーリングである．
連鎖不均衡（linkage disequilibrium）
2箇所の遺伝子座の遺伝子が互いに相関を持つこと．逆に，相関が無い場合を連鎖均衡という．
linkage learning
ビルディングブロックの特定を行うこと．すなわち，染色体において，どのビットとどのビットが関連しているのかを，それに関する情報を与えられていない状態で学習すること．
例えば，染色体において，ビット b[2] = 0 の時に b[4] = 1 の個体の適合度が良く，逆に b[2] = 1 の時に b[4] = 0 の個体の適合度が良いとき，2 番目のビットと 4 番目のビットは相互に関連していると言える．
関連リンク : [ 第38回研究報告 ]
遺伝子座（locus）
染色体上の各遺伝子が置かれている位置．
[ M ]
マスタースレーブモデル（master slave model）
MGG（Minimal Generation Gap）
防衛大学校の佐藤らによって提案された世代交代モデルである．探索序盤における選択圧をできるだけ下げて初期収束を回避するとともに，探索の後半においても集団内に多種多様な個体を生存させやすくし，進化的停滞を抑制することを目的としている．複製選択では母集団から非復元抽出によってランダムに選ばれた２個体が選ばれ，任意の遺伝的操作により子を生成する．生存選択では，家族(親2個体，生成子個体)から，最良1個体とランクに基づくルーレット選択による1個体を次世代に残すモデルである．
関連リンク : [ ISDLレポートNo.20020612015 ]
移住個体（migrant）
移住する個体．
移住（migration）
ある世代に一度，各島内で選ばれた１つまたは複数個の個体を別の島と交換することである．このとき，各島内における移住個体の割合を移住率， 何世代おきに移住するかを移住間隔と呼ぶ．
移住間隔（migration interval）
移住を行う世代間隔．
移住率（migration rate）
各サブ母集団に属する個体のうち，どの程度の個体が移住するかを規定する値．サブ母集団の個体数に対する移住個体の割合．
突然変異（mutation）
遺伝的操作の1つで，染色体の一部をある確率で変化させること．突然変異を起こすことによって，個体群が局所解に陥りにくくなる．突然変異は，あらかじめ決めておいた突然変異率に従って，遺伝子ごとに起こる．
突然変異率（mutation rate）
[ N ]
近傍モデル（neighborhood model）
細粒度の並列GAに属し，可動範囲によって各個体の近傍が定義され，その近傍内で選択や交叉を行う．各個体の近傍の一部は，他の個体の近傍の一部と重なっており，それぞれの個体の及ぼす影響は次第に個体集団に波及していく．
[ O ]
最適解（optimal solution）
最適値（optimal value）
最適化（optimization）
与えられた制約条件のもとで，ある目的関数f(x)を最小(最大)にするような設計変数xを求めること．このときの設計変数の値を最適解，目的関数の値を最適値と呼ぶ
次数（order）
スキーマにおいて，値が定められたビットの数．たとえば，スキーマ{*10**1*}の次数は3．
[ P ]
Population-Based Incremental Learning : PBIL
Baluja＆Caruana（1995）によって提案された確率モデル遺伝的アルゴリズム．母集団を確率ベクトルによって表現する．確率ベクトルを用いて個体を生成し，個体の適合度をもとに同ベクトルを更新する．
関連リンク : [ 第36回研究報告 ] [ 第41回研究報告 ]
表現型（phenotype）
確率モデルGA（Probabilistic Model-Building GA : PMBGA）
良好な解の確率分布を推定して確率モデルを構築し，新しい個体を生成する GA．EDA とも呼ばれる．
母集団（population）
初期収束（premature convergence）
探索の初期に突出した適合度の個体が存在すると，その個体への過剰な選択圧がかかり，探索が進まないうちにその個体に収束してしまう現象．
[ R ]
ランキングルーレット選択（ranking roulette selection）
母集団内の各個体の適合度とその総計を線形正規化によって求め，適合度の総計において各個体の適合度が占める割合を選択確率とし個体を選択する．
ルーレット選択（roulette selection）
母集団内の各個体の適合度とその総計を線形スケーリングによって求め，適合度の総計において各個体の適合度が占める割合を選択確率とし個体を選択する．
ランキングルーレットトーナメント選択（roulette tournament selection）
ルーレットトーナメント選択（roulette tournament selection）
粒度
並列処理において各プロセッサに与えられるタスクの大きさ．粒度が小さくなれば相対的にプロセッサ間通信が多くなり，反対に粒度が大きくなればプロセッサ間通信が少なくなる．
[ S ]
スケーリング（scaling）
適合度の差異を明確にする手法．選択を行う際，探索終盤で適合度の差が微小になると探索効率が劣化することがある．こうした場合にも適切な探索を可能にするために適用される．スケーリングには，線形スケーリングや線形正規化などがある．
スキーマ（schema）
遺伝子型のビットパターンを3つの記号 {'0', '1', '*'} で表現したもの．'*' は，ワイルドカード記号（wild card symbol，don't care symbolとも呼ばれる）であり，'0'，'1'のいずれにも一致する．例えば，{11001}や，{10100}などは，スキーマ{1**0*}に属する．なお，スキーマHの適合度とは，スキーマHに属する全ての染色体の適合度の平均のことをいう．
スキーマ定理（schema theorem）
あるスキーマの数が世代間に度の程度変化するかを見積もるための定理．
関連リンク：[ISDL Report：スキーマ理論]
複製選択（selection for reproduction）
子を生成する親を選ぶための選択．
生存選択（selection for survival）
次世代に生き残る個体を選ぶための選択．
選択圧（selection pressure）
選択圧とは適合度の低い個体の淘汰されやすさのことであり，これが高いほど探索の収束が早くなる．淘汰圧ともいう．
単純GA（simple Genetic Algorithm）
イリノイ大学のD.E.Goldbergによって考案されたGA．所定の個体数からなる集団を用意する．各個体の遺伝子表現はビットストリングとする．集団から2個体を選択し，この2個体の間で交叉，突然変異からなる遺伝子操作が行なわれ，その結果得られた新しい2個体を新集団にいれる．この操作を集団の個体数分だけ実施すると新集団を元の集団に移す．この動作を所定の世代数だけ実行して終了する．
関連リンク :
[ IlliGAL Home Page ]
[ T ]
トーナメント選択（tournament selection）
母集団から定められた数（トーナメントサイズ）だけの個体をランダムに選出し，その中で最も適合度の高いものを次世代の親として選択する．
トーナメントサイズ（tournament size）
