２次関数の最小値をＣ言語と遺伝的アルゴリズム（ＧＡ）を用いて求める

niji.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define ITEM_NUM  5  

#define IND_NUM   8  /* 個体の数 */
#define MUTATE_RATE  0.1  /* 突然変異する確率（10%）*/

int indGeneration;              /* 個体の世代 */
int indGene[ IND_NUM ][ ITEM_NUM ]; /* 個体の遺伝子 */
int indWeight[ IND_NUM ];         /* 個体の重量 */
int indValue[ IND_NUM ];          /* 個体の価値 */
int indFitness[ IND_NUM ];        /* 個体の適応度 */

int minx, maxx, a, p, q;

/* 個体をランダムに生成する関数 */
void createIndividual() {
	int ind, item;  /* ループカウンタ */

					/* 0か1をランダムに格納する */
	for( ind = 0; ind < IND_NUM; ind++ ) {
		for( item = 0; item < ITEM_NUM; item++ ) {
			indGene[ ind ][ item ] = rand() % 2;
		}
	}
}

int getDeci( int ind ) {
	int t = 1;
	int v = 0;
	for( int i = 0; i < ITEM_NUM - 1 ; i++ ) {
		t = pow( 2.0, i );
		v += indGene[ ind ][ i ] == 1 ? t : 0;
		
	}
	v *= indGene[ ind ][ ITEM_NUM - 1 ] == 1 ? -1 : 1;
	return v;
}

/* 個体の重量、価値、適応度を計算する関数 */
void calcIndividual() {
	int ind, item;  /* ループカウンタ */

	for( ind = 0; ind < IND_NUM; ind++ ) {
		indWeight[ ind ] = getDeci(ind);
		if( indWeight[ ind ] < minx || maxx < indWeight[ ind ] ) {
			indValue[ ind ] = 0;
			indFitness[ ind ] = INT_MIN;
		}else{
			indValue[ ind ] = a * pow((indWeight[ ind ] + p ), 2.0) + q;
			indFitness[ ind ] = -10000 - indValue[ ind ];
		}
	}
}

/* 個体の情報を表示する関数 */
void showIndividual() {
	int ind, item;  /* ループカウンタ */
					/* 世代を表示する */
	printf( "\n＜第%d世代＞\n", indGeneration );
	/* 遺伝子、重量、価値、適応度を表示する */
	printf( "遺伝子\t\t   x\t   y\t適応度\n" );
	for( ind = 0; ind < IND_NUM; ind++ ) {
		for( item = 0; item < ITEM_NUM; item++ ) {
			printf( "[%d]", indGene[ ind ][ item ] );
		}
		printf( "\t%2d  \t%4d  \t%4d\n",
			indWeight[ ind ], indValue[ ind ], indFitness[ ind ] );
	}
	printf( "\n" );
}

/* 個体を適応度の大きい順にソートする */
void sortIndividual() {
	int pos;  /* 挿入する要素 */
	int ins;  /* 挿入する位置 */
	int item; /* ループカウンタ */
	int tmp;  /* 一時的に値を逃がす変数 */

			  /* 挿入法でソートする */
	for( pos = 1; pos < IND_NUM; pos++ ) {
		ins = pos;
		while( ins >= 1 && indFitness[ ins - 1 ] < indFitness[ ins ] ) {
			for( item = 0; item < ITEM_NUM; item++ ) {
				tmp = indGene[ ins - 1 ][ item ];
				indGene[ ins - 1 ][ item ] = indGene[ ins ][ item ];
				indGene[ ins ][ item ] = tmp;
			}

			tmp = indWeight[ ins - 1 ];
			indWeight[ ins - 1 ] = indWeight[ ins ];
			indWeight[ ins ] = tmp;

			tmp = indValue[ ins - 1 ];
			indValue[ ins - 1 ] = indValue[ ins ];
			indValue[ ins ] = tmp;

			tmp = indFitness[ ins - 1 ];
			indFitness[ ins - 1 ] = indFitness[ ins ];
			indFitness[ ins ] = tmp;

			ins--;
		}
	}
}

/* 淘汰する関数 */
void selectIndividual() {
	int ind, item;  /* ループカウンタ */
					/* 適応度の上位50%を下位50%にコピーする（下位50％を淘汰する） */
	for( ind = 0; ind < IND_NUM / 2; ind++ ) {
		for( item = 0; item < ITEM_NUM; item++ ) {
			indGene[ ind + IND_NUM / 2 ][ item ] = indGene[ ind ][ item ];
		}
	}
	printf( "下位50%%を淘汰しました。\n" );
}

/* 交叉する関数 */
void crossoverIndividual() {
	int ind, item;       /* ループカウンタ */
	int crossoverPoint;  /* 交叉する位置 */
	int tmp;             /* 一時的に値を逃がす変数 */

						 /* 下位50%にコピーした個体を対象とする */
	for( ind = IND_NUM / 2; ind < ( IND_NUM - 1 ); ind += 2 ) {
		/* 交叉する位置をランダムに決める */
		crossoverPoint = rand() % ( ITEM_NUM - 1 ) + 1;
		for( item = crossoverPoint; item < ITEM_NUM; item++ ) {
			/* 隣の個体と交差する */
			tmp = indGene[ ind ][ item ];
			indGene[ ind ][ item ] = indGene[ ind + 1 ][ item ];
			indGene[ ind + 1 ][ item ] = tmp;
		}
		printf( "個体%dと個体%dを%dの位置で交叉しました。\n",
			ind, ind + 1, crossoverPoint );
	}
}

/* 突然変異する関数 */
void mutateIndividual() {
	int ind, item;  /* ループカウンタ */
					/* 下位50%にコピーした個体を対象とする */
	for( ind = IND_NUM / 2; ind < IND_NUM; ind++ ) {
		for( item = 0; item < ITEM_NUM; item++ ) {
			/* あらかじめ決められた確率で突然変異する */
			if( rand() / ( double )RAND_MAX <= MUTATE_RATE ) {
				/* 反転する */
				indGene[ ind ][ item ] ^= 1;
				printf( "個体%dの%dの位置で突然変異しました。\n", ind, item );
			}
		}
	}
}

/* main関数 */
int main() {
	int genMax;  /* 最大の世代 */
	int item;    /* ループカウンタ */
				 /* 乱数の種を設定する */
	srand( ( unsigned int )time( NULL ) );
	/* 最大の世代をキー入力する */
	printf( "最大の世代 = " );
	scanf( "%d", &genMax );
	printf( "minx=" ); scanf( "%d", &minx );
	printf( "maxx=" ); scanf( "%d", &maxx );
	printf( "a=" ); scanf( "%d", &a );
	printf( "p=" ); scanf( "%d", &p );
	printf( "q=" ); scanf( "%d", &q );
	/* 第1世代の個体を生成する */
	indGeneration = 1;
	createIndividual();
	/* 適応度を計算する */
	calcIndividual();
	/* 適応度が大きい順にソートする */
	sortIndividual();
	/* 個体を表示する */
	showIndividual();
	/* 1世代ずつ進化させる */
	indGeneration++;
	while( indGeneration <= genMax ) {
		/* 適応度が大きい順にソートする */
		sortIndividual();
		/* 淘汰する */
		selectIndividual();
		/* 交叉する */
		crossoverIndividual();
		/* 突然変異する */
		mutateIndividual();
		/* 適応度を計算する */
		calcIndividual();
		/* 適応度が大きい順にソートする */
		sortIndividual();
		/* 個体を表示する */
		showIndividual();
		/* 世代を進める */
		indGeneration++;
	}

	/* 最も適応度の高い個体を解として表示する */
	printf( "＜遺伝的アルゴリズムで得られた解＞\n" );
	printf( "x = %d\n", indWeight[ 0 ] );
	printf( "y = %d\n", indValue[ 0 ] );
	return 0;
}