遺伝的アルゴリズムのプログラム

質問

はじめての投稿になります．これからよろしくお願いします．

先日、大学でＧＡを使って
あるxの関数(例えば，f(x)=x^2-2=0のxにあてはまる解を導き出す)を解いてくるようにと課題がありました。
しかし、ＧＡに関しては交叉や突然変異など基本的な用語を
教わったのみでプログラムが全然分かりません。
自分でも色々調べてみたのですが、全く参考になりそうなものが
見つかりませんでした。
そこで、もしご存知の方がいらっしゃるなら教えていただけないでしょうか？
プログラムを組む場合にはＣ言語を使うことになるのですが、どなたかＣ言語でよろしくお願いいたします！

回答No.4

precog

アルゴリズムがわかればプログラムは組めますので、まずはアルゴリズムを考えてください。

大学では全てを知識として与えてくれることはありません。自分で調べるのも課題の一部。

>自分でも色々調べてみたのですが、全く参考になりそうなものが見つかりませんでした。

そんなはずはないです。人工知能は古い分野だしGAは良く知られた考え方です。調べればわかるはずです。まさかネットで検索して見つからなかったから質問してるとかじゃないですよね?

学生なら文献を調べましょう。図書館もあるしその手の教科書もあるはずです。

回答No.3

kettachin

あ、バグあった…。ソースの66行目、
誤）for(j=i; j<100; j++)
正）for(j=i+1; j<100; j++)
です。

回答No.2

kettachin

昔大学でGAをちょっとかじってた者です。アドバイスしようと思って
実際に組んでみたら意外とてこずってショック…。ソースだけ貼って
去ります。ちなみにGAっぽいけど微妙にGAじゃないエセGAです。ソー
スの解読はそちらでお願いします。
/*==============================================================================
* ESE-GA PROGRAM by kettachin
* compiler: gcc version 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
*==============================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SCALE 1.0e+10 /* スケール */
#define MAX_GENERATION 1000 /* 最大世代数 */
#define ABS(n) ( ((n) > 0) ? (n) : -(n) ) /* nの絶対値取得用マクロ*/

/* #define DEBUG */

int main(void)
{
int i, j, number_of_generation; /* ループカウンタ */
int random_value; /* 乱数 */
double present_generation[100]; /* 現世代の個体群 */
double child, coming_generation[100]; /* 次世代の個体、個体群 */
double accommodating[100]; /* 各個体の適合度 */
double max_acc, min_acc, average_acc; /* 最大、最小、平均適合度 */
double x; /* 解 */

/* 現在時刻から乱数シードをセット */
srand((unsigned) time(NULL));

/* 第一世代の個体群を生成する */
for(i=0; i<100; i++)
{
random_value = rand();
if (random_value % 2 == 0) /* 偶数なら正の実数 */
present_generation[i] = random_value / SCALE;
else /* 奇数なら負の実数 */
present_generation[i] = -random_value / SCALE;
}

/* イテレーション開始 */
for(number_of_generation=0; number_of_generation<MAX_GENERATION; number_of_generation++)
{
/* 適合度を計算 */
for(i=0; i<100; i++)
{
accommodating[i] = -ABS( present_generation[i] * present_generation[i] - 2.0 );
}

/* 平均適合度を計算 */
max_acc = min_acc = accommodating[0];
for(i=1; i<100; i++)
{
if (accommodating[i] > max_acc)
max_acc = accommodating[i];
if (accommodating[i] < min_acc)
min_acc = accommodating[i];
}
average_acc = (max_acc + min_acc) / 2 ;

/* 現世代から次世代を生成 */
child = present_generation[0];
for(i=0; i<100; i++)
{
/* 選択 */
if (accommodating[i] > average_acc )
{
/* 交配 */
for(j=i; j<100; j++)
{
if (accommodating[j] > average_acc)
{
child = (present_generation[i] + present_generation[j]) / 2;
break;
}
else if ( j == 99 ) /* 交配相手が居ない場合自己複製 */
child = present_generation[i];
}
}
if (i == 0 || i == 99)
{
/* 突然変異 */
random_value = rand() % (unsigned long)SCALE;
if (random_value % 2 == 0) /* 偶数なら1より小さい小数を足す */
child += random_value / SCALE;
else /* 奇数なら1より小さい小数を引く */
child -= random_value / SCALE;
}
coming_generation[i] = child;
}

/* 世代交代 */
for(i=0; i<100; i++)
present_generation[i] = coming_generation[i];
}

/* 適合度を計算 */
for(i=0; i<100; i++)
{
accommodating[i] = -ABS( present_generation[i] * present_generation[i] - 2.0 );
}

/* 最も適合度の高い個体を表示 */
max_acc = accommodating[0];
x = present_generation[0];
for(i=1; i<100; i++)
{
if (accommodating[i] > max_acc)
{
max_acc = accommodating[i];
x = present_generation[i];
}

#if defined DEBUG
printf("%2d acc:%.10f x:%.10f\n",i,accommodating[i],present_generation[i]);
#endif
}
printf ("解:%f, 適合度:%f\n", x, max_acc);

return 0;
}

回答No.1

neKo_deux

Cのプログラムならまず入っている「include main stdio.h」などのキーワード、
遺伝的アルゴリズムなら関数名になりがちな「mutation crossover」などのキーワードで情報収集するとか。

google「ga mutation crossover stdio.h include」検索結果
http://www.google.co.jp/search?hl=ja&lr=&safe=off&num=100&ei=IIPBSrQPn_bqA4aslIwE&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=ga+mutation+crossover+stdio.h+include&spell=1