遺伝的アルゴリズム

遺伝的アルゴリズムのプログラムを作っているのですがサンプルソースの下の関数のやってこるこがよく意味がわかりません。よかったら解説
お願いします。


// 一点交叉
void one_point_crossover(struct genotype *ind) {
int i, ia, ib; // 個体インデックス
int j; // 遺伝子座インデックス
int c; // 交叉点
int test[M]; // 個体の利用フラグ
int temp[N]; // 遺伝子を入れ替えるための仮変数 // 4/24修正
int r; // 乱数値

for(i=0; i<M; i++) test[i] = 0;

ia = ib = 0;
for(i=0; i<M/2; i++) {
// 個体をランダムにペアリング
for(; test[ia]==1; ia=(ia+1)%M);
test[ia] = 1;

r = random() % (M-2*i) + 1;

while(r>0) {
ib=(ib+1)%M;
for(; test[ib]==1; ib=(ib+1)%M);
r--;
}
test[ib] = 1;
// 個体iaとibを交叉
if(flip(Pc)) {
c = random() % N;

for(j=0; j<c; j++) {
temp[j] = ind[ia].gene[j];
ind[ia].gene[j] = ind[ib].gene[j];
ind[ib].gene[j] = temp[j];
}
}
}
} // End of one_point_crossover()

No.1 回答者： sgwjn 回答日時： 2007/07/05 00:58

一点交叉は、２つの個体の遺伝情報をある一点の後で置換するアルゴリズムだったと思います。

それを踏まえて解説を入れると、

for(i=0; i<M; i++)
{
　　test[i] = 0;　　　// ペアで使用済みの個体を識別するフラグの初期化
}

ia = ib = 0;
for(i=0; i<M/2; i++) 　　　　　　　　// 全個体に対し、一点交叉を実行
{
　　// 個体をランダムにペアリング
　　for(; test[ia]==1; ia=(ia+1)%M);　 // 未使用の個体を１つ選択し
　　　　test[ia] = 1;　　　　　　　　　　　// その個体の使用済みフラグを立てる

　　r = random() % (M-2*i) + 1;　　　　// ２つ目の個体決定用の乱数生成

　　while(r>0)
　　{
　　　　ib=(ib+1)%M;　　　　　　　　　　　　// ２つ目の個体を決定
　　　　for(; test[ib]==1; ib=(ib+1)%M);
　　　　　　r--;
　　}

　　test[ib] = 1;　　　　　　　　　　　　// ２つ目の個体の使用済みフラグを立てる

　　// 個体iaとibを交叉
　　if(flip(Pc))
　　{
　　　　c = random() % N;　　　　　　　　　　　// ランダムに交叉位置を決定

　　　　for(j=0; j<c; j++)
　　　　{
　　　　　　temp[j] = ind[ia].gene[j];　　　　　　// 交叉位置の前後で遺伝情報を置換
　　　　　　ind[ia].gene[j] = ind[ib].gene[j];
　　　　　　ind[ib].gene[j] = temp[j];
　　　　}
　　}
}


プログラムで見ると分かりにくいですが、要するに交叉させる個体ia、ibを選択して、交叉位置をランダムに決定し、その位置の後で遺伝情報を入れ替えて個体ia'、ib'を作成しているだけです。

例）
個体ia [1, 2, 3, 4, 5]
個体ib [6, 7, 8, 9, 10] []内が遺伝情報
　　　　　↓
　　　　　↓交叉位置を3とすると（先頭1始まり）
　　　　　↓
個体ia' [1, 2, 3, 9, 10]
個体ib' [6, 7, 8, 4, 5]　 （交叉位置を含めるかはプログラムによる）

後、このプログラムはネストが深いので、書き込む際にはインデントを入れた方が見やすいですよ。