母集団最適化アルゴリズム：2進数遺伝的アルゴリズム(BGA)（第１回）

内容

1.はじめに
2. 特徴提示の手法：実数と2進数
3.グレイ2進数コード表現の利点
4.選択法
5.交叉法の種類
6.突然変異法の種類
7.まとめ

1.はじめに

この記事では、カスタムソリューションで様々な最適化アルゴリズムを作成するためのツールやビルディングブロックとして役立つ遺伝的アルゴリズムで使用されるメソッドとテクニックを詳しく見ていきます。この記事の目的は、遺伝的アルゴリズムに限らず、あらゆる最適化アルゴリズムにおける最適化問題を研究するためのツールを説明し、提供することです。

2.特徴量提示の手法：実数と2進数

最適化問題の入力はしばしば「特徴量」と呼ばれ、最適化アルゴリズムのロジックで使用するためには、一定の方法で表現する必要があります。遺伝学では、これらの特徴は表現型と遺伝子型に分けられます。表現型は最適化されるパラメータの外見であり、遺伝子型はアルゴリズムにおける表現方法です。ほとんどの最適化アルゴリズムでは、表現型は遺伝子型と同じで実数で表されます。遺伝子は最適化されたパラメータであり、染色体は遺伝子の集合、すなわち最適化されたパラメータの集合です。

分数を表現するために実数データ表現が使用されます。実数には小数部と分数部があり、小数点で区切られています。例えば、3.14と0.5は実数です。

一方、データの2進表現は、2つの記号を使用して数値を表現する2進数システムを使用します。0と1で、各桁はビット（2進数）と呼ばれます。例えば、数字5を2進数で表すと101となります。

データの実数表現と2進表現の主な違いは、数値の符号化方法です。実数は通常、浮動小数点数を表現するための形式を定義したIEEE 754などの標準規格を使用してエンコードされます。MQL5言語では、doubleデータ型は実数に使用され、数字の有効数字16桁を表すことができます。つまり、合計桁数は16を超えることはできません。例えば、「9 999 999 999 999 999.0」、「9 999 999.999 999 99」、「0.999 999 999 999 999 9」では、小数点の前後に合計16桁の「9」が存在します。なぜこれが重要なのかは、もう少し後で説明します。

実数はプログラムを書いたり日常生活で使用するのに便利で、2進数は計算機システムや論理演算、ビット演算などの低レベルの演算をおこなうときに使用されます。

遺伝的アルゴリズムを含む最適化アルゴリズムの文脈では、データは実数または2進数として表現することができ、これらは決定を符号化し、それに対して演算を実行するために使用されます。

最適化アルゴリズムに実数を使用する利点は、連続的なパラメータ値を扱うことができることです。実数表現では、数値を使用して特徴を符号化し、その数値を使用して直接解探索演算をおこなうことができます。例えば、解が数値を持つベクトルであれば、ベクトルの各要素は実数で符号化できます。

しかし、実際の表現には欠点があります。最適化問題の個々の要素は独立であり、多次元の非重複空間を表すことができます。空間が独立した部分空間に分割されるため、探索が困難になり、大域解を局所化するのが難しくなります。

特徴量の2進表現の利点は、すべての特徴量を1つの多次元非オーバーラップ空間の記述にまとめることができることです。これにより、個々の多次元空間を共通の探索空間に結びつけることができます。また、2進表現では、「突然変異」演算子のような初歩的なビット演算を簡単におこなうことができます。このような演算をおこなうには、さらに時間のかかる演算が必要となる実数とは異なります。

最適化アルゴリズムにおける2進表現の欠点は、最適化タスクが最終的に操作する実数に変換する必要があることと、ビット表現を有意な配列長の形で保存するなどの追加的な時間のかかる操作が必要なことです。

このように、実数は連続的な値を扱う柔軟性を提供する一方、2進表現は特徴を1つにまとめ、ビット演算をより効率的に実行することができます。最適化アルゴリズムは、遺伝的なものだけでなく、両方の利点を得るために両方の表現手法を使用することもあります。

3.グレイ2進数コード表現の利点

2進表現にはあらゆる利点があるが、重大な欠点があります。2進表現では、近くにある2つの10進数が一度に数ビット異なることがあるのです。例えば、2進数コードでは、7（0111）から8（1000）に移動すると、4ビットすべてが変化します。つまり、異なる近い番号間で異なるビット演算数が必要となり、その結果、探索空間における結果の確率が不均一になり、特有の「確率の上昇帯」が出現し、逆に最適化されたパラメータに「盲点」が生じます。

例えば、10進数表記では1単位しか違わない2つの数値に対して算術演算をおこないたい場合、2進数表記では数ビットの変更が必要になることがあります。その結果、各ビットの変更が最終的な結果に影響するため、演算後に希望する数値が得られる確率は、別の数値の組とは異なり不均一になります。この現象は、数値表現の精度が非常に重要であり、数値の10進数表現のわずかな変化が2進表現の大きな変化につながり、その結果、計算結果が大きく変わってしまう浮動小数点計算を実行する場合に、特に問題となる可能性があります。

グレイコード2進表現（反射2進数コードとしても知られる）では、各数値はビットの集合として表現されるが、後続の各数値は、修正された1ビットだけ前の数値と異なります。これは「単位距離特性」と呼ばれる性質です。

前回、doubleの数字は有効数字16桁でしか表せないことを述べました。このことがどのような影響を及ぼすかを理解するために、例を見てみましょう。

16桁目に15個の有効数字0と1があるとします(0.0000000000000001)。この数字に1.0を足すと1.0000000000000000となります。16桁目の1が消え、小数点以下の有効数字が15桁になっていることにご注意ください。doubleの整数部分に新しい桁が追加されると、有効数字は左にシフトされます。したがって、ゼロでない整数部がある場合、小数点以下16桁までの精度を保証することはできません。

2進表現、特にグレイコードを使用する場合、そのような目標を設定するか、特定のタスクの枠内でそれが必要であれば、桁の精度が失われる問題を回避することができます。この点についてもう少し詳しく調べてみましょう。

コンピュータがプログラムや数値を2進表現で扱うのは、これが機械による情報処理にとって最も効率的で自然な方法だからです。しかし、トップレベルでの最適化アルゴリズムの理解や記述を容易にするためには、2進数、特に負数や小数部を持つ数を扱うための追加的な努力が必要となります。

プログラミングの最高レベルで2進数形式の数値を扱うために、負の数や小数部分を持つ数値の処理や表現を容易にする様々なライブラリやツールがありますが、私たちはMQL5の最適化アルゴリズムの一部としてすべてを実装します。

追加されたコードメソッドは、2進法において負の数を表現するために使用されます。これは、数値のすべてのビットを反転させ、その結果に1を加算することで、負の数値を表示することを可能にします。ただし、ここではちょっとしたトリックを使い、単に負の数を取り除くことで、負の数を扱うための追加演算を回避します。最適化されたパラメータの1つに境界があるとしましょう。

最小値＝-156.675、最大値＝456.6789

すると、最大値と最小値の距離は次のようになります。

距離 = 最大値 - 最小値 = 456.6789 - (-156.675) = 613.3539

したがって、最適化問題で求められる数値は常に正となります。数直線上の0.0の右側に位置し、最大値は613.3539に等しくなります。さて、課題は実数のエンコードを確実にすることです。そのために、この数を整数部分と小数部分に分割します。全体をグレイコードで表すと以下のようになります（括弧内は表現手法）。

613 (10進数) =1 1 0 1 0 1 0 1 1 1(グレイ2進数)

すると、分数の部分は次のようになります。

3539 (10進数) =1 0 1 1 0 0 1 1 1 0 1 0(グレイ2進数)

整数部分と分数部分を1つの文字列に格納し、両方の部分に使用される文字数を覚えておくことで、簡単に逆変換をおこなうことができます。その結果、実数は次のようになります（「:」記号は整数部分と小数部分を条件付きで区切る）。

613.3539（10進数） =1 1 0 1 0 1 0 1 1 1:  1 0 1 1 0 0 1 1 1 0 1 0（グレイ2進数）

従って、整数部では小数点以下16桁以内、倍数型では小数点以下16桁以内の任意の実数を変換することができます。さらに、これによって有効数字が16桁を超え、最大32桁以上になることもあります（整数の10進数をグレイコードに変換する関数や、その逆の関数で使用されるulong番号の長さによって制限される）。

端数部分を16桁目まで正確にするためには、9,999,999,999,999,999（可能な最大端数）という数字に変換する必要があります。

9999999999999999（10進数）=1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0（グレイ2進数）

すると、613.9999999999999999（小数点以下16桁）の最終レコードは次のようになります。

613.9999999999999999（10進数） = 1 1 0 1 0 1 0 1 1 1:  1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0（グレイ2進数）

見ての通り、ユーザーはulong型の長さの中で小数点以下の精度を自由に設定できます。

10進整数をグレイコードに変換する関数と、その逆の関数を見てみましょう。グレイコードのエンコードとデコードには、通常の2進数コードに変換するための追加関数が使用されます。

DecimalToGray関数は、decimalNumberと変換結果が格納されるarrayへのリンクをパラメータとして受け取ります。数値を10進数からグレイコードに変換します。そのために、まずdecimalNumber間のXORビット演算を使用してgrayCode値を計算し、それを1ビット右にシフトします。次に、IntegerToBinary関数を呼び出して、結果のgrayCode値を2進表現に変換し、arrayに格納します。配列には、char型による整数の保存を最も節約できるものが使用されます。

IntegerToBinary関数は、数値と、変換結果が格納される配列へのリンクをパラメータとして受け取ります。10進数から2進数に変換します。ループの中で、numberを2で割った余りをarrayに足します。そして、numberを2で割り、cntカウンターをインクリメントします。numberが0より大きい限り、ループは続きます。ループの後、配列は正しいビット順序を得るために反転されます。

GrayToDecimal関数は、配列grayCodeへのリンク、startInd初期インデックス、endInd終了インデックスをパラメータとして受け取ります。グレイコードから10進数に変換します。まず、BinaryToInteger関数を呼び出して、配列grayCodeを2進表現に変換し、変数grayCodeSに格納します。そして、変数resultをgrayCodeSの値で初期化します。そして、grayCodeSを右に1ビットシフトし、resultとビットXOR演算をおこなうループを実行します。ループは、grayCodeSが右にシフトし、ゼロより大きい限り続きます。最後に、関数はresult値を返します。

BinaryToInteger関数は、binaryStr配列へのリンク、startInd初期インデックス、endInd終了インデックスをパラメータとして受け取ります。2進数から10進数に変換します。この関数は、変数resultをゼロで初期化します。そしてループを実行し、resultを左に1ビットシフトし、binaryStr[i]の値（ビット）をresultに加算します。ループはstartIndからendIndまで続きます。最後に、関数はresult値を返します。

グレイコードから変換し直す際には、初期位置と最終位置のインデックスが使用されることにご注意ください。これにより、すべての最適化されたパラメータが格納されている行から、特定の数の最適化されたパラメータだけを抽出することができます。整数部分と分数部分を含めた文字列の全長がわかっているので、整数部分と分数部分の接合を含めて、染色体の一般的な文字列における数字の具体的な位置を決定することができます。

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4.選択法

最適化アルゴリズムにおいて、選択とは、母集団または候補の集合から最良の解を選び出し、次の世代を作成するプロセスです。これは、最適化手法において重要な役割を果たします。特定の選択オプションを選択すると、アルゴリズムの探索能力だけでなく、収束速度にも影響します。どの選択法にも長所と短所があり、アルゴリズムによってはより効果的な場合もあれば、そうでない場合もあります。それぞれの使い方は、特定の検索戦略によって異なります。

親個体を選択し、新しい世代を形成するために用いられる選択には、主にいくつかの種類があります。それぞれについて詳しく考えてみましょう。

• 一様選抜とは、各個体が等しい確率で選抜される親選抜の手法です。この手法では、集団の各個体が生殖のために選択される確率は同じです。平等淘汰の利点は、すべての個体が平等に淘汰されるチャンスを確実に得られることです。しかし、この手法は個体の適合度を考慮していないため、特にある個体が他の個体よりも著しく高い適合度を持っている場合、最適解を見つけるのに有効でない可能性があります。一様選択は、解空間の異なる領域を探索したい場合や、集団の多様性を高度に維持したい場合など、場合によっては有用です。

• 順位選択の場合、個体はその適合度に従ってランク付けされ、個体が選択される確率はそのランクに依存します。個体のランクが高ければ高いほど、選択される可能性は高くなります。順位選択には、個体を選択する確率がその順位（序数）に比例する完全比例と、非線形の法則に従って順位が高くなるにつれて個体を選択する確率が高くなる部分比例があります。順位選択には多くの利点があります。第一に、集団の多様性を維持することができます。第二に、母集団が局所最適に収束するのが早すぎるという早期収束の問題を避けることができます。順位選択は、多様性を維持し、より広い解空間を探索するのに役立ちます。順位選択は一様選択と似ていますが、最も適合した個体を選択することに重点を置き、適合していない個体が選択される可能性を残しています。
  

• トーナメント選択では、個体の小さな部分集合が無作為に選択されます（トーナメントと呼ばれる）。この部分集合から、最も適合度の高い個体が選択されます。トーナメントの規模によって、各トーナメントに参加する個体の数が決まります。トーナメント選抜は、集団の多様性を維持することができます。偶然によって、適応度の低い個体が選択される可能性もあるからです。トーナメント選択にはいくつかの利点があります。第一に、親の選択においてランダム性を考慮に入れることができるため、子孫の多様性が促進されます。第二に、最も適した個体とそれほど適していない個体の両方を含み、集団のあらゆる領域から親を選択することができます。トーナメント選択は、進化的アルゴリズムにおける主要な親選択法の1つであり、新しい子孫を作り、集団の進化を継続させるために、交叉や突然変異などの他の演算子と組み合わせて使用されることが多いです。
  

• ルーレット選択では、各個体はその適合度に比例して架空のルーレットに表されます。ルーレットが回転し、ポインタが指し示す個体が選ばれます。個体の適合度が高ければ高いほど、その個体が占めるルーレットの部分は大きくなり、選択される確率も高くなります。ルーレット選択では、親をその適合度に比例した確率で選択することができます。適合度が高い個体ほど選択される確率は高いですが、適合度が低い個体でも選択される確率はゼロではありません。これにより、集団の遺伝的多様性を維持し、解空間のさまざまな領域を探索することができます。しかし、ルーレット選択では、特に個体の適合度が大きく異なる場合、収束が早まるという問題が生じる可能性があります。高い適合度を持つ個体が選択される確率が高くなるため、遺伝的多様性が失われ、似たような解で母集団が「詰まり」、局所最適から抜け出せなくなる可能性があります。

「エリート主義」法は、追加的な措置として、あらゆる選択法と組み合わせて使用することができます。これは、現在の集団から最良の個体を保存し、そのまま次の世代に引き継ぐというものです。「エリート主義」法を用いることで、世代を超えて最良の個体を保存することができ、高い適合度を維持し、有用な情報の損失を防ぐことができます。これはアルゴリズムの収束を早め、発見された解の質を向上させるのに役立ちます。

しかし、「エリート主義」の使用は、特にエリート主義が高いレベルに設定されている場合、遺伝的多様性の喪失につながる可能性があることを考慮に入れるべきです。したがって、最適な個体の保存と解空間の探索の残高を保つために、適切なエリティズム値を選択することが重要です。

5.交叉法の種類

交叉は遺伝的アルゴリズムにおける主要な操作の1つで、自然進化における交配を模倣したものです。2つの親個体の遺伝情報を組み合わせて子孫を作り、遺伝的特徴を娘個体に移します。交叉は、情報を伝達する手段としてだけでなく、アルゴリズムの組み合わせの特質にも大きな影響を与えます。

交叉は遺伝子型レベルで働き、親個体の遺伝子を組み合わせて新しい子孫を作ることができます。

交叉法の一般的な原理は以下の通りです。

1. 親個体を選択する：ある集団から2個体または数個体を選択して交配させます。
   
2. 交叉点を決定する：交叉点は、両親の染色体を分離して子孫を作る位置を決めます。
3. 子孫を残す：親の染色体は交叉点で分離され、両親の染色体の一部が組み合わされて、子孫の新しい遺伝子型が作られます。交叉の結果、両親の遺伝子が組み合わされた1つ以上の子孫が生まれます。

図1：交叉法の一般原理

2進数交叉の主な種類を挙げてみましょう。

• 単点交叉：2つの染色体がランダムな点で分離し、その点以降で両親の染色体のセグメントを交換することで2つの子孫が生まれます。
• 多点交叉：単点交叉と似ていますが、複数の切断点があり、その切断点間で染色体セグメントが交換されます。
  
• 一様交叉：各子ビットは、等確率でその親の1つから独立して選択されます。
  
• サイクル交叉：親の間で交換されるポジションのサイクルを定義し、要素の一意性を保持します。
• PMX (Partially Mapped Crossover)：親染色体からの要素の相対的な順序と位置を保持。巡回セールスマン問題など順序が重要な問題で使用されます。
• ОX (Order Crossover)：片方の親の遺伝子の順序を保持し、もう片方の親から欠けている遺伝子を現れる順序で受け継いで子孫を作ります。
  

交叉は2進表現だけでなく、実数表現にも使用されます。交叉の主な種類は以下の通りです。

• ブレンド交叉(BLX-α)：親の値と、その範囲を拡張するαパラメータで定義される範囲内で、値がランダムに選択される子を作成します。
• 対称型ブレンド交叉(SBX)：異なる確率分布を用いて、両親の値の差の程度を考慮しながら、両親の値の中間に位置する値を持つ子を生成します。
  
• 実数値交叉：親の値の平均や加重和など、実数に算術演算を適用します。
  
• 差分交叉：例えば微分進化で使用され、2つの個体間の重み付けされた差を3番目の個体に加えることで新しいベクトルが生成されます。
  
• 補間交叉：親の値の間を補間して子を作成。線形補間または非線形補間が含まれます。
  
• 正規分布交叉：親の値を中心に正規分布を使用して子を生成し、親ポイントを中心に解空間を探索できるようにします。
  

6.突然変異法の種類

突然変異演算子は遺伝的アルゴリズムにおける主要な演算の1つで、集団内の個体の遺伝情報にランダムな変化を導入するために使用されます。新たな解決策を探り、局所最適から抜け出せなくなるのを防ぐのに役立ちます。

生物学では、突然変異は非常にまれで、通常は子孫に限定的な影響を与えます。自然界に存在する1つの種の個体数は数百万に達するため、もちろん、絶滅危惧種について話している場合を除き、個体群の遺伝物質は非常に多様です（「ボトルネック」という用語もあります。これは、その個体数がその数を下回ると種が絶滅する最小個体数です）。生きている自然とは異なり、遺伝的アルゴリズムのほとんどの実装では、突然変異も約1～2%とまれな現象です。これは遺伝的アルゴリズムでは特に重要で、一般的に母集団のサイズが小さく、近親交配が問題になることがあるため、生物学的進化よりも進化の行き詰まりが起こりやすくなります。生物学では通常、何百万もの個体からなる集団について話しますが、遺伝的アルゴリズム（および一般的な最適化アルゴリズム）では数十から数百の個体しか扱わず、突然変異が集団の遺伝子プールに新しい情報を加える唯一の方法です。

したがって、集団に遺伝情報が欠けている場合、突然変異はそれを導入する機会を提供します。

つまり、突然変異にはいくつかの重要な役割があります。

1. 新しい解を探索する：アルゴリズムが、交叉によって探索された解空間の外側にある可能性のある、問題に対する新しい潜在的な解を探索することを可能にします。突然変異は、アルゴリズムが解空間をジャンプし、新しい選択肢を発見することを可能にします。
2. 遺伝的多様性を維持する：突然変異がないと、アルゴリズムは、すべての個体が同じような遺伝情報を持つ局所最適に収束するという問題に遭遇する可能性があります。突然変異はランダムな変化を可能にし、早すぎる収束を避け、集団の多様性を維持するのに役立ちます。
3. 進化の行き詰まりを克服する：進化の過程で、遺伝的アルゴリズムは、解空間が枯渇し、より良い解に到達できない進化の行き詰まりに陥ることがあります。突然変異は、新しい可能性を開き、アルゴリズムを前進させることができるランダムな変化を導入することによって、このような行き詰まりを克服するのに役立ちます。

突然変異の確率が高すぎるとアルゴリズムがランダム探索に陥ってしまい、低すぎると収束の問題や多様性の喪失につながります。

2進表現のアルゴリズムでは、以下のような突然変異法があります。

• 単点突然変異：2進数文字列のランダムに選択された1ビットの値が反転します。例えば、101010という文字列があったとして、単点突然変異で100010に変わることがあります。
• 多点突然変異：2進数文字列のいくつかのランダムな位置が選択され、これらの位置の値が反転されます。例えば、101010という文字列があった場合、多点突然変異によって100000や001010に変えることができます。
  
• 確率に基づく（ストキャスティックな）突然変異：各ビットは、変異したときに変化する一定の確率を持っています。
  
• 完全な反転：2進数文字列のビットの完全な反転。例えば、101010という文字列があった場合、反転させると010101になります。
• Point inversion ：遺伝子配列の切断点をランダムに選び、その箇所で染色体を2つに分割し、部分を入れ替えます。 

図2：確率に基づく突然変異

実数データ表現による最適化アルゴリズムでは、次のような突然変異が区別されます。それらについて詳しく述べるつもりはありません。

• ランダム突然変異演算子
• ガウス突然変異演算子
• 算術実数クリープ演算子
• 幾何学的実数クリープ演算子
• 冪乗変異演算子
• ミハエルヴィッチの非一様演算子
• 動的突然変異演算子

一般に、すべての最適化アルゴリズムにおいて、エージェント（個体）間の情報交換がなければ、探索空間の構成要素を変化させることを目的とした操作はすべて突然変異と呼ぶことができます。それらはしばしば、アルゴリズムの特定の検索戦略に従って非常に特殊です。

7.まとめ

これは「2進数遺伝的アルゴリズム」に関する記事の前編で、このアルゴリズムだけでなく、「選択」「交叉」「突然変異」という用語が使用されていなくても、他の母集団最適化アルゴリズムで使用されている手法のほとんどすべてを見てきました。これらの手法をよく研究し理解することで、より意識的に最適化問題に取り組むことができるようになり、既知のアルゴリズムの実装や修正、また新しいアルゴリズムの創造に新しいアイデアが生まれるかもしれません。また、最適化アルゴリズムにおける情報のさまざまな表現方法、その利点と欠点についても検討しました。これは新しいアイデアや斬新なアプローチにつながる可能性があります。