遺伝的アルゴリズム-基礎

このセクションでは、GAを理解するために必要な基本的な用語を紹介します。また、GAの一般的な構造は、*擬似コード形式とグラフィカル形式*の両方で表示されます。読者は、このセクションで紹介したすべての概念を適切に理解し、このチュートリアルの他のセクションを読むときにも留意してください。

基本用語

遺伝的アルゴリズムに関する議論を始める前に、このチュートリアル全体で使用されるいくつかの基本的な用語に精通することが不可欠です。

人口-それは、与えられた問題に対するすべての可能な（エンコードされた）解決策のサブセットです。 GAの人口は、人間の代わりに人間を表すCandidate Solutionsがあることを除いて、人間の人口に類似しています。
染色体-染色体は、与えられた問題に対するそのような解決策の1つです。
遺伝子-遺伝子は染色体の1つの要素位置です。
アレル-遺伝子が特定の染色体に対して取る値です。

用語

遺伝子型-遺伝子型は計算空間の人口です。計算空間では、ソリューションはコンピューティングシステムを使用して簡単に理解および操作できる方法で表されます。
表現型-表現型は、現実世界の状況で表現されるようにソリューションが表現される、実際の現実世界のソリューション空間の人口です。
デコードとエンコーディング-単純な問題の場合、表現型と遺伝子型*のスペースは同じです。ただし、ほとんどの場合、表現型と遺伝子型のスペースは異なります。デコードはソリューションを遺伝子型から表現型空間に変換するプロセスであり、エンコードは表現型から遺伝子型空間に変換するプロセスです。フィットネス値の計算中にGAで繰り返し実行されるため、デコードは高速になります。 +たとえば、0/1ナップザック問題を考えます。表現型空間は、選択するアイテムのアイテム番号のみを含むソリューションで構成されます。 +ただし、遺伝子型空間では、長さn（nはアイテムの数）のバイナリ文字列として表すことができます。位置x *の 0は、 x ^ th ^ アイテムが選択されることを表し、1は逆を表します。これは、遺伝子型と表現型のスペースが異なる場合です。

表現型および遺伝子型空間

フィットネス関数-単に定義されたフィットネス関数は、入力としてソリューションを取り、出力としてソリューションの適合性を生成する関数です。場合によっては、フィットネス関数と目的関数が同じである場合もあれば、問題に基づいて異なる場合もあります。
遺伝演算子-これらは子孫の遺伝的組成を変更します。これらには、クロスオーバー、突然変異、選択などが含まれます。

基本構造

GAの基本構造は次のとおりです-

最初の母集団（ランダムに生成されるか、他のヒューリスティックによってシードされる）から始め、この母集団から交配のために親を選択します。親に交叉演算子と突然変異演算子を適用して、新しい子孫を生成します。そして最後に、これらの子孫が人口の既存の個人に取って代わり、プロセスが繰り返されます。このようにして、遺伝的アルゴリズムは実際にある程度人間の進化を模倣しようとします。

次の各ステップは、このチュートリアルの後半で個別の章として扱われます。

基本構造

GAの一般化された擬似コードは、次のプログラムで説明されています-

GA()
   initialize population
   find fitness of population

   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

Genetic-algorithms-fundamentals

遺伝的アルゴリズム-基礎

基本用語

基本構造