(JS) 進化計算における遺伝子的アルゴリズムでbitを用いて子を生成する方法の速度検証

やったこと

遺伝子的進化計算において、親から子を作成する(交叉する)ときに2つのやり方のうちどちらが早いのかを計算した備忘録。

具体的に、遺伝子長列(NUM_OF_GENE)に対して親が2体(NUM_OF_PARENT)、子を30対(NUM_OF_CHILD)作るときに、親の遺伝子から30種類の子の遺伝子を作る。このときに30+2 = 2⁵なので、5-1個の交叉位置を用いる。このときに、bit配列を生成せずに書くか、bit配列を生成して書くかの速さについて検証する。なお以下にコードを示すが、bit配列を用いる方がシンプルである。

前提

const NUM_OF_PARENT = 2;  // 親の数
const NUM_OF_CHILD = 32;  // 子の数(30+2であり、2は親と同じものが生成される)
const NUM_OF_GENE = 1000; // 遺伝子の長さ
const N =10;           // 計測用の繰り返し回数(10,100,1000で検証する)
const NUM_OF_SEPARATOR = Math.log(NUM_OF_CHILD) / Math.log(2)-1; // 交叉位置の数、log2(NUM_OF_CHILD)-1
const LENGTH_OF_BITBOX = Math.log(NUM_OF_CHILD) / Math.log(2); // 何桁のbit配列を必要とするのか

//--親の生成--//
var parent = new Array(NUM_OF_PARENT);
for(var i=0;i<NUM_OF_PARENT ;i++){
  parent[i] = new Array(NUM_OF_GENE);
  for(var j=0;j<NUM_OF_GENE ;j++){
    parent[i][j] = i;
  }
}
//--生成された親の確認--//
console.log(parent[0]); // 全て0の遺伝子
console.log(parent[1]); // 全て1の遺伝子

//--子の遺伝子を入れる配列の生成--//
var child = new Array(NUM_OF_CHILD);
for(var i=0;i<NUM_OF_CHILD ;i++){
  child[i] = new Array(NUM_OF_GENE);
}

//--交叉位置の設定--//
var rand = new Array(NUM_OF_SEPARATOR);
for(var i=0;i<NUM_OF_SEPARATOR;i++){
  //--重複のない乱数を生成する--//
  while(true){
    tmp = Math.floor(Math.random()*NUM_OF_GENE);
    if(!rand.includes(tmp)){
      rand[i] = tmp;
      break;
    }
  }
}
rand.sort(); // 交叉位置を昇順に
console.log(rand); // 交叉位置の確認

パターン1(bit配列を生成しない)

const startTime1 = performance.now(); // 開始時間
for(var i=0;i<N;i++){
  pattern1(); // 計測する処理
}
const endTime1 = performance.now(); // 終了時間

console.log("パターン1の計測時間::"+(endTime1 - startTime1)); // 何ミリ秒かかったかを表示する
function pattern1(){
  var rand_position =0; // 交差位置を入れる
  var choiced_parent =0; // どちらの親を選択しているのか
  var count=0; // どの点で親を交代するのか
  //--遺伝子1つ1つに対してのループ--//
  for(var c=0;c<NUM_OF_GENE;c++){
    // 交差位置を変更する
    if(c>=rand[rand_position]){
      rand_position++;
    }
    // どの子供の遺伝子を親を同じにするのか
    for(var i=0;i<NUM_OF_CHILD;i++){
      child[i][c] = parent[choiced_parent][c];
      count++; // 親と同じにした子の数を取得(どこで親を切り替えるのか)
      // 交差位置においてどのタイミングで親を切り替えるのかを選択する。
      // 初め(30この親を生成する場合)は16個の子が親0と同じで残りの16個の子が親1と同じであるが、交差位置が最後になるとiが変わるループ内で交互に親が入れ替わる。bit配列を書くとわかりやすい。
      if(count>=2**(NUM_OF_SEPARATOR-rand_position)){ 
        count=0;
        choiced_parent = choiced_parent ^ 1;
      }
    }
  }
}

パターン1(bit配列を生成する。)

const startTime2 = performance.now(); // 開始時間
//--bit配列の生成--//
var bitBox = [];
for(let i = 0; i < (1 << LENGTH_OF_BITBOX); i++){
  bitBox.push(i.toString(2).padStart(LENGTH_OF_BITBOX, '0'));
}
for(var i=0;i<N;i++){
  pattern2(); // 計測する処理
}
const endTime2 = performance.now(); // 終了時間

console.log("パターン2の計測時間::"+(endTime2 - startTime2)); // 何ミリ秒かかったかを表示する


function pattern2(){
  var rand_position =0;
  //--遺伝子1つ1つに対してのループ--//
  for(var c=0;c<NUM_OF_GENE;c++){
    // 交差位置を変更する
    if(c>=rand[rand_position]){
      rand_position++;
    }
    // 各bitが0,1によって親を変える。
    for(var i=0;i<NUM_OF_CHILD;i++){
      child[i][c] = parent[bitBox[i][rand_position]][c]
    }
  }
}

bitについての補足

結果

# N=10
パターン1の計測時間::9.599999994039536
パターン2の計測時間::6.0999999940395355

# N = 100
パターン1の計測時間::33.900000005960464
パターン2の計測時間::35.400000005960464

# N = 1000
パターン1の計測時間::250.59999999403954
パターン2の計測時間::328.59999999403954

Nが大きくなるとbit配列の方が大きくなる。bit配列を用いる方は配列の番地を指定する際に配列を用いているため処理速度の低下が伺える。

参照回数が多いときにはパターン1が有効であり、コードの短さが必ずしも早いとは限らない。