遺伝的アルゴリズムを使った山登り法の課題です

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
村長
記事: 3
登録日時: 6年前

遺伝的アルゴリズムを使った山登り法の課題です

#1

投稿記事 by 村長 » 6年前

遺伝的アルゴリズムを使った山登り法の問題をC言語で作成したいです。
授業で、使う関数はそれぞれ作成したのですが、何を表示させればこの山登り法で解が求められたか、また局所解に陥っているのかを見極められるかがわかりません。

自分で高さが把握できるような、以下の画像のような山をプログラム上に作成したいのですが、どのようにすれば良いか教えていただきたいです。


画像


また、もしよければ、以下のプログラムにどのように組み込めばよいかもお教え願いたいです。

コード:

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

#define TRUE 1
#define FALSE 0
#define Halfstring 8 //8ビット
#define Maxstring 2*Halfstring //16ビット
#define Maxpopulation 500    //最大世代数

#define ID_FuncA 200  //山の曲面を決める関数番号
#define ID_FuncB 201
#define ID_FuncC 202
#define ID_FuncD 203
#define ID_FuncE 204
#define ID_FuncF 205
#define ID_FuncG 206

#define M_Peaks 30 //山の頂点の数

int gen;  //世代数
int nPopulation = Maxpopulation;
int nGeneration = 100; //最大世代数

int chrom_size = Maxstring;
double pc = 0.6;  //交配確率
double pm = 0.2;  //突然変異確率

struct Individual{      //遺伝子数とそれぞれの適合度
		int chrom[Maxstring];
		double fitness;
};


struct Individual oldpop[Maxpopulation],newpop[Maxpopulation];
int numTable[] = {1,2,4,8,16,32,64,128,256,512};  //2進数に変換

double biasY, normF;  //適合度の値の調整用
int kindofHill =203; //使用する山の曲面関数を決める番号
int funcSeed =1;    //シード値
double sum_fitness; 
int best_chrom[Maxstring];
double max_fitness,min_fitness,old_fitness,ave_fitness,best_fitness;
int max_Individual;
struct {double a,b,h,t;}mCoef[M_Peaks];



double random()
{
	double r;
	int i;
	i = rand(); if(i!=0) i--;
	r = ((double)i)/(0x7fff);
	//printf("r:%f")
	return(r);
}


flip(double probability)
{
	if(probability == 1,0) return(TRUE);
	else if(random() <= probability)
		return(TRUE);
	else return(FALSE);
}

double range_rand(double min, double max)
{
	return((max-min)*random()+min);
}

gen_chrom(int chrom[], int chrom_size)
{
	int i;
	for(i=0; i<chrom_size; i++)
	{
		if(flip(0.5)) chrom[i] = 1;
		else		  chrom[i] = 0;
	}
}


double mpeaks(int iniflag,double x ,double z)
{
	double val, xx, zz;
	int i;
	if(iniflag)
	{
		srand(funcSeed);
		for(i = 0; i<M_Peaks; i++)
		{
			mCoef[i].a = range_rand(-120, 120);
			mCoef[i].b = range_rand(-120, 120);
			mCoef[i].h = range_rand(0, 100);
			val = range_rand(0,25);
			mCoef[i].t = 0.5/(val*val);
		}
		return(0.0);
	}
	
	val = 0;
	for(i=0; i<M_Peaks; i++)
	{
		xx = (x - mCoef[i].a)*(x - mCoef[i].a);
		zz = (z - mCoef[i].b)*(z - mCoef[i].b);
		val += mCoef[i].h * exp(-1*mCoef[i].t*(xx+zz));
	}
	return(val);
}




double uFunction(double x, double z)
{
	double rd = 3.1415927/180;
	double y,yy,wk;

	switch(kindofHill){
		case ID_FuncA:
			wk = sqrt(x*x + z*z)*rd;
			y= 30*(cos(wk)+cos(3*wk));
			biasY = 60; normF = 120;
			break;
		
		case ID_FuncB:
			y = (-1*(x*x+z*z)/200)+120;
			biasY = 400; normF = 600;
			break;
			
		case ID_FuncC:
			wk = sqrt(x*x+z*z)*rd;
			yy = 30*(cos(wk)+cos(3*wk));
			x = x-200; z = z-300;
			wk = sqrt(x*x+z*z)*rd;
			y = 20*(cos(wk) + cos(3*wk))+yy;
			biasY = 60; normF = 120;
			break;
		
		case ID_FuncD:
			y = mpeaks(FALSE, x,z);
			biasY = -60; normF = 100;
			break;
			
		case ID_FuncE:
			y = floor(0.02*x)+floor(0.02*z);
			y = 12.0*y;
			biasY = 0.0; normF = 120;
			break;
			
		case ID_FuncF:
			
			y=cos(rd);
			biasY = 0; normF = 1;
			break;
	}
	return(y);
}



double hfitness(int chrom[])
{
	int i;
	double x,z,r;
	x=z=0;
	for(i = 0; i<Halfstring; i++)
	{
		if(chrom[i]) x=x+numTable[i];
		if(chrom[i+Halfstring]) z = z+numTable[i];
	}
	
	if(x > numTable[Halfstring])
		x = x-numTable[Halfstring];
		
	if(z > numTable[Halfstring])
		z = z-numTable[Halfstring];
	
	r = (uFunction(x,z)+biasY)/normF;
	return(r);
}

crossover(int parent1[], int parent2[], int child1[], int child2[], int chrom_size)
{
	//printf("%d\n",gen);
	int i, i1, i2;
	if(flip(pc))
	{
		i1 = chrom_size * random();
		i2 = chrom_size * random();
		
		if(i1>i2){
			i = i1; i1=i2; i2=i;
		}
		
		for(i=0; i<i1; i++)
		{
			child1[i] = parent1[i];
			child2[i] = parent2[i];
		}
		
		for(i = i1; i<i2; i++)
		{
			child2[i] = parent1[i];
			child1[i] = parent2[i];
		}

		for(i = i2; i<chrom_size; i++)
		{
			child1[i] = parent1[i];
			child2[i] = parent2[i];
		}
	}
	else {
		for(i=0; i<chrom_size; i++)
		{
			child1[i]=parent1[i];
			child2[i]=parent2[i];
		}
	}
}

mutation(int chrom[], int chrom_size)
{
	int i;
	if(flip(pm))
	{
		i = chrom_size * random();
		chrom[i] = 1-chrom[i];
	}
}




copy_population()
{
	int i,j;
	for(i=0; i<Maxpopulation; i++)
	{
		for(j=0; j<Maxstring; j++)
		oldpop[i].chrom[j]= newpop[i].chrom[j];
	oldpop[i].fitness = newpop[i].fitness;
	}
}

select(struct Individual pop[])
{
	double r,sum;
	int i;
	sum = 0.0; i=0;
	r = random() * sum_fitness;
	do{
		sum+=pop[i].fitness; i++;
	}while(sum < r && i<nPopulation);
	return(i-1);
}

next_generation()
{
	int i,mate1,mate2;
	i = 0;
	do{
		mate1 = select(oldpop);
		mate2 = select(oldpop);
		crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[i].chrom,newpop[i+1].chrom,Maxstring);
		
		mutation(newpop[i].chrom, Maxstring);
		mutation(newpop[i+1].chrom, Maxstring);

		newpop[i].fitness = hfitness(newpop[i].chrom);
		newpop[i+1].fitness = hfitness(newpop[i+1].chrom);

//printf("newpop[].fitness::: %f\nnewpop[i+1].fitness::%f\n\n",newpop[i].fitness,newpop[i+1].fitness);
		i+=2;
	}while(i < nPopulation);
}


statistic(struct Individual pop[])
{
	int imax, imin, i;
	sum_fitness = max_fitness = min_fitness = pop[0].fitness;
	
	imax = 0;
	for(i = 1; i < nPopulation; i++)
	{
		sum_fitness += pop[i].fitness;
		if(pop[i].fitness >= max_fitness)
		{
			max_fitness = pop[i].fitness; imax = i;
		}
		
		if(pop[i].fitness < min_fitness)
		{
			min_fitness = pop[i].fitness; imin = i;
		}
	}
	
	ave_fitness = sum_fitness/nPopulation;
	max_Individual = imax;
	
	//printf("maxfitness %f\n\nbestfitness%f\n",max_fitness,best_fitness);
	if(best_fitness < max_fitness)
	{
		for(i = 0; i<chrom_size; i++)
			best_chrom[i] = pop[imax].chrom[i];
		best_fitness= max_fitness;
		//printf("best::%f\n\nmax::%f",best_fitness,max_fitness);
	}
}

initialize_population()
{
	int i;
	i=0;
	while(i<nPopulation)
	{
		gen_chrom(oldpop[i].chrom,Maxstring);
		oldpop[i].fitness = hfitness(oldpop[i].chrom);
		i++;
	}
}

App_Exceute()
{
	int cycles;
	int n=0 ;
	cycles = 1;
	printf("n:%d\ncycles:%d\ngen:%d\nnGeneration:%d\n",n,cycles,gen,nGeneration);
	for(n = 0; n < cycles && gen < nGeneration; n++)
	{
		gen++;
		next_generation();
		copy_population();
		statistic(oldpop);
	}
	if(gen >= nGeneration) {
		return (1);
	}
	else
		return (0);
}

void App_Initialize()
{
	mpeaks(TRUE, 0.0, 0.0);
	best_fitness = 0.0;
	initialize_population();
	gen = 0;
	statistic(oldpop);
}










int main(void){
	
	//printf("maxfitness %f\n\nminfitness %f\n\n",max_fitness, min_fitness);
	App_Initialize();
	App_Exceute();
	
	//printf("maxfitness %f\n\nminfitness %f\n\nbestfitness%f\n",max_fitness, min_fitness,best_fitness);
	
	return 0;
}
よろしくお願い致します。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#2

投稿記事 by たいちう » 6年前

ちょっと質問が理解できないのですが、、、


まず、添付しているプログラムを理解していますか?
質問内容から村長さんが自分で作ったものとは思えず、
課題の参考として渡されたものでは?

だとすると、まずはこのプログラムを理解することが第一歩でしょう。
何をするプログラムですか?
完成していますか?
課題に必要な機能で、何が足りないですか?


> 授業で、使う関数はそれぞれ作成したのですが、
> 何を表示させればこの山登り法で解が求められたか、
> また局所解に陥っているのかを見極められるかがわかりません。

局所解でないことを示す一般的な方法はありません。
特殊な条件がある場合は教えてください。

解の有効範囲を細かいメッシュで区切って、
遺伝的アルゴリズムで求めた解よりも高い値が存在しないことで、
一応の検証をするのが精いっぱいではないでしょうか。
つまり、2つのアルゴリズムで求めた結果が一致していることで、
よしとしましょう。


> 自分で高さが把握できるような、
> 以下の画像のような山をプログラム上に作成したいのですが、
> どのようにすれば良いか教えていただきたいです。

与えられた地形データを添付画像のように表示する
プログラムを作りたいということでしょうか。
以下が参考になるでしょうか。

gnuplotの初歩
3次元でグラフをプロット
http://graph.pc-physics.com/threedimensions.html

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#3

投稿記事 by みけCAT » 6年前

村長 さんが書きました:自分で高さが把握できるような、以下の画像のような山をプログラム上に作成したいのですが、どのようにすれば良いか教えていただきたいです。


画像
山(の各座標での高さ)を関数で表すといいでしょう。
この画像でググると、peaksというサンプル関数のようですね。
colorbar
GLG410/598--Computers in Geology, Spring, 2009 Lecture 9

2 変数のサンプル関数 - MATLAB peaks - MathWorks 日本
R: Peaks Function (Matlab Style)
Rのページにある式をC言語にすると、

コード:

3.0 * (1.0-x)*(1.0-x) * exp(-(x*x) - (y+1.0)*(y+1.0)) - 10.0 * (x/5.0 - x*x*x - y*y*y*y*y) * exp(-x*x - y*y) - 1.0/3.0 * exp(-(x+1.0)*(x+1.0) - y*y)
となるはずです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

村長
記事: 3
登録日時: 6年前

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#4

投稿記事 by 村長 » 6年前

わかりにくい質問申し訳ありません。。。
おっしゃるとおり先生にとりあえずこれを作ってみろとソースをほぼ丸写ししたものです。

必要な機能についてはそろってはいるはずです。
基本的には遺伝子プールから二点交差法を用いて100世代までに山の頂上を求めたいというプログラムになります。
x座標とz座標からy座標を求め、y座標が高いものを優良な遺伝子として扱うプログラムになります。


自分で山の形状がわかっている場合に頂上でない解が導かれたときに、局所解に陥っているということにはならないのでしょうか?
二つのアルゴリズムで求める必要はありますか?

また、表示するわけではなく、あくまでも探索する山を自作するというものになります。

村長
記事: 3
登録日時: 6年前

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#5

投稿記事 by 村長 » 6年前

わざわざこの画像の通りの山をつくるプログラムをありがとうございます。
この山を元に、実際にプログラムが正常に動くか確かめたいと思います。


みけCAT さんが書きました:
村長 さんが書きました:自分で高さが把握できるような、以下の画像のような山をプログラム上に作成したいのですが、どのようにすれば良いか教えていただきたいです。


画像
山(の各座標での高さ)を関数で表すといいでしょう。
この画像でググると、peaksというサンプル関数のようですね。
colorbar
GLG410/598--Computers in Geology, Spring, 2009 Lecture 9

2 変数のサンプル関数 - MATLAB peaks - MathWorks 日本
R: Peaks Function (Matlab Style)
Rのページにある式をC言語にすると、

コード:

3.0 * (1.0-x)*(1.0-x) * exp(-(x*x) - (y+1.0)*(y+1.0)) - 10.0 * (x/5.0 - x*x*x - y*y*y*y*y) * exp(-x*x - y*y) - 1.0/3.0 * exp(-(x+1.0)*(x+1.0) - y*y)
となるはずです。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#6

投稿記事 by usao » 6年前

(GAについては素人なので,変なことを言っているかもしれませんが…)

> 自分で山の形状がわかっている場合に頂上でない解が導かれたときに、局所解に陥っているということにはならないのでしょうか?
> 二つのアルゴリズムで求める必要はありますか?

探索処理が十分に収束している状態では,
解が既知であればそこから「十分に近い」みたいな判定方法でも良いのではないでしょうか.
(どの程度が「十分」なのかについては,関数形状についての知識から決める)

> 100世代までに
100世代目の時点ではまだ絶賛探索途上状態で,
その時点での結果では真の解(山の頂上)からめちゃくちゃ遠い! なんてことが起こり得そうな気もしますが…

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムを使った山登り法の課題です

#7

投稿記事 by たいちう » 6年前

> 自分で山の形状がわかっている場合に頂上でない解が導かれたときに、
> 局所解に陥っているということにはならないのでしょうか?
> 二つのアルゴリズムで求める必要はありますか?

一般的には、どこが頂上なのか判らない問題を解く必要があると思いました。
その場合、局所解かどうかを判定することが困難なので、
検証方法を提案しました。

すでに頂上が判っている場合ならば、
局所解か頂上なのか人間が判断することができますので、
他のアルゴリズムでの検証は必要ないでしょう。

返信

“C言語何でも質問掲示板” へ戻る