遺伝的アルゴリズム

遺伝的アルゴリズムをCで組み、Cygwinのgccコマンドでコンパイルしたのですが、実行するとエラーが出てしまいます。
gsb内で実行しwhereコマンドで異常箇所を探した場合のメッセージは以下の通りです。
#0 0x61016525 in stack_info::walk () from /usr/bin/cygwin1.dll
#1 0x7c859dcc in OutputDebugStringsA ()
from /cygdrive/c/WINDOWS/system32/kernel32.dll
#2 0x40010006 in ?? ()
#3 0x00000000 in ?? ()

プログラムは長いので載せられませんが、アルゴリズム中の染色体は二次元配列の遺伝子を含む構造体です。
遺伝子の配列に関わるノード数（chromo[timeslot][NODE]←このNODEです。プログラム冒頭で値をdefineで宣言しています）が30位なら世代数が比較的多くても動くのですが、これが50あたりになると世代数が低くてもエラーが出てしまいます。

printf関数で交叉や突然変異の結果を表示しているのですがちゃんと動作しているようです。
二台のパソコンどちらでやってもこのようなメッセージが出るので困っています。何が起こっているか見当がつく方、いらっしゃいましたら助言願います。

よろしくお願いいたします。

No.3 ベストアンサー 回答者： ibe_tattsu 回答日時： 2007/07/12 19:35

わざわざソースを載せていただきありがとうございます。

こちらでも、足りない関数はありましたが、一応Cygwinで確認させていただきました。

こちらの、動作環境や足りない関数を適当に補ったため、
そちらでの結果を保証することはできませんが、一応気がついた点を伝えておきます。

１．
if(random < MUTATE){
....
next_p++;
}
if(...){
...
}
else{
next[next_p] = chromo[k];
...
}
上の文ですが、最初のif内でnext_pが増加されますが、
その後で、else内でnext[next_p]で配列を超えて参照する可能性がありました。
実際に、next[next_p]...の前に、
if(next_p >= POPULATION){
fprintf(stderr,"Overflow!\n");
}
などとやってみましたら、「Overflow!」が出力されました。

２．
for(k=0;k<POPULATION;k++);
　chromo[k] = next[k];
の部分ですが、forの後に；が記述されておりました。

１はelseのみでなく、その前のifでもcrossoverで使われているようですね。
それと、２は直接は関係ないですが、気になったので。

あくまで、こちらの仮想的なソースの補足、および環境での動作ですので、
そちらでも同様に直るかどうか分かりませんが、参考までに。

ちなみに、ソースが完成されていないので、アルゴリズムの確認はしておりません。

この回答へのお礼

ご指摘感謝致します。
どうやら1番の問題のせいだったようです。修正し関数等を調べた結果、ちゃんと交叉や突然変異も行われ、指定された世代数動くようになりました。
本当にありがとうございました。これでやっと試行段階に進めそうです。

お礼日時：2007/07/12 22:13

No.2 回答者： ibe_tattsu 回答日時： 2007/07/12 17:23

もう１つ可能性があったので、追記させていただきます。

もしかして、その配列は自動変数(関数内で宣言)ではないでしょうか？
自動変数ですと、変数領域がスタック領域に確保されます。

しかし、スタック領域というものは比較的小さなものなので、
あまり多くの変数を使おうとしてしまうと、領域が確保できなくなることがあります。

今回、配列の大きさを変えてエラーが発生するとのことなので、これかもしれません。
一度、alloc系統でヒープ領域に変数を確保し、実行してみてください。
もしかしたら、これで上手くいくかもしれません。

それでも上手くいかない場合は、できればソースの一部で良いので見せてもらえればと思います。
回答のお礼の補足欄ですと、いくらか制限字数が多くなるようですし。
もちろん、載せたくないのであれば、かまいませんので＾＾；

この回答への補足

ソースを載せてみます。だいぶ省いていますが…
無線ネットワークの送信をTDMAスケジューリングする問題です。
C・Dmatrixは送信干渉を設定した行列の読み込み・生成の格納場所です。初期集団生成・突然変異(乱数で決定された遺伝子の1/0を逆手)も省略。…しても制限字数以上なのでmain関数も切りました…

/* ノード数 */
#define NODE 20
/* 世代数 */
#define GENERATION 10000
/* 現世代個体数 */
#define POPULATION 100
/* エリート選択個数 */
#define ELITE 2
/* 交叉率 */
#define CROSS 0.8
/* 突然変異率 */
#define MUTATE 0.02
/* timeslot最大値 */
#define TIME 60 /* 20node */
/* ペナルティ */
#define COST 100

/* Connectivity matrix */
int C[NODE][NODE];
/* Compatibility matrix */
int D[NODE][NODE];
/* Traffic demand vector */
int R[NODE] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4};

/* 染色体 */
struct chromosome{
int slot[TIME][NODE];
int cost; //コスト
int timeslot; //全タイムスロット数
}chromo[POPULATION], next[POPULATION];

/* 評価 */
int evaluate()
{
int time_num;
int flag1[NODE];
int hantei[POPULATION];
int i, j, k;
struct chromosome tmp; //コピー用

/* コスト計算 */
for(i = 0; i < POPULATION; i++){
time_num = 0;
for(j= 0; j < NODE; j++)
flag1[j] = 0;

/* timeslot loop */
for(time_num = 0; time_num < chromo[i].timeslot+1; time_num++){
/* 同時送信できないものが混ざっていたら+COST */
for(j = 0; j < NODE; j++){
if(chromo[i].slot[time_num][j] == 1){
for(k = 0; k < NODE; k++){
if(chromo[i].slot[time_num][k] & D[j][k] == 1)
chromo[i].cost += COST;
}
/* 送信回数調査 */
flag1[j]++;
}
}
}

/* 必要送信回数を満たしていなかったら+COST */
for(j = 0; j < NODE; j++){
if(R[j] != flag1[j])
chromo[i].cost += COST;
}

/* 最終タイムスロット分を足す */
chromo[i].cost += chromo[i].timeslot;
}
/* ソート */
for(i = 0; i < POPULATION-1; i++)
for(j = POPULATION-1; j > i ; j--)
if(chromo[i].cost > chromo[j].cost){
tmp = chromo[i];
chromo[i] = chromo[j];
chromo[j] = tmp;
}
}

/* 交叉 */
int crossover(int i, int next_p, int flag[])
{
int random2, random3; //乱数格納
int time_num, time_num2; //タイムスロット調べ
int j, k;

/* 出来た子供はNEXTPOPULATIONに格納 */
while(1){
select = (int)(rand() % POPULATION);
if(flag[select] == 0)
break;
}
/* 交叉点決定 */
/* 列(timeslot) */
if(chromo[i].timeslot <= chromo[select].timeslot){
random2 = (int)(rand() % chromo[i].timeslot);
time_num = chromo[i].timeslot;
}
else if(chromo[i].timeslot > chromo[select].timeslot){
random2 = (int)(rand() % chromo[select].timeslot);
time_num = chromo[select].timeslot;
}
/* 行(node) */
random3 = (int)(rand() % NODE);
/* 二次元一点交叉 */
next[next_p] = chromo[i];
next[next_p+1] = chromo[select];
for(j = time_num; j > random2; j--)
for(k = NODE-1; k > random3; k--){
next[next_p].slot[j][k] = chromo[select].slot[j][k];
next[next_p+1].slot[j][k] = chromo[i].slot[j][k];
}
return select;
}

補足日時：2007/07/12 17:56

この回答へのお礼

main関数です。

/* main関数 */
int main(int argc, char *argv[])
{
double random;//乱数格納

int i, j, k;
int next_p, select;
int flag[POPULATION];

/* マトリクスファイル(connect)読み込み */
i = read_c(argv[1]);
if(i == -1)
return 1;
/* Dマトリクス作成 */
make_d();

/* 初期集団生成 */
srand((unsigned) time(NULL));
first();
//print();

i = 0;
while(1){
/* 設定された世代数を超えたら終了 */
if(i > GENERATION)
break;

/* POPULATION */
for(j = 0; j < POPULATION; j++)
flag[j] = 0;

/* 評価＆ソート */
evaluate();

/* 遺伝的操作 */
for(k = 0, next_p = 0; next_p < POPULATION; k++){
/* エリート選択 */
if(k < ELITE){
next[next_p] = chromo[k];
flag[k]++;
next_p++;
}

else if(flag[k] == 0){
random = (double)rand() / RAND_MAX;
/* 突然変異 */
if(random < MUTATE){
mutation(k, next_p, chromo[k].timeslot);
flag[k] = 1;
next_p++;
}
/* 交叉 */
if(MUTATE <= random && random < CROSS+MUTATE && next_p != POPULATION-1){
flag[k] = 1;
select = crossover(k, next_p, flag);
flag[select] = 1;
next_p += 2;
}
/* 次世代へ持ち越し */
else{
next[next_p] = chromo[k];
flag[k] = 1;
next_p++;
}
}
}

/* 次世代→現世代 */
for(k = 0; k < POPULATION; k++);
chromo[k] = next[k];
i++;
}

printf("chromo 0 : %d\nchromo %d : %d\n", chromo[0].timeslot, POPULATION-1, chromo[POPULATION-1].timeslot);

return 0;
}

お礼日時：2007/07/12 18:23

No.1 回答者： ibe_tattsu 回答日時： 2007/07/12 13:04

スタック領域のメモリが壊されているかもしれません。

その場合は、おそらく、配列の領域を超えて書き込み等をしている可能性があります。

できれば、ソースを載せてもらうほうが早く解決するかと思います。

拙い意見ですが、参考になればと思います。

この回答へのお礼

ソースを載せるのは字数制限に引っかかって不可能でした。

自分で確認したのですが領域を超えての書き込みはないように思います。もちろん見落としもあるかもしれませんが…

お礼日時：2007/07/12 15:41