inline int RandInt(int x,int y) {return rand()%(y-x+1)+x;}
inline double RandFloat() {return (rand())/(RAND_MAX+1.0);}
const int map[MAP_HEIGHT][MAP_WIDTH] =
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1,
1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5,
1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
class GeneticAlgorithm
{
private:
char Gene[GENE_COUNT][GENE_LENG];
char GeneBuffer[GENE_COUNT][GENE_LENG];
double GeneScore[GENE_COUNT];
int Top;
public:
GeneticAlgorithm::GeneticAlgorithm();
MakeScore();
int WheelRoulette();
Hybr();
Hybr_main();
Show();
Variation(char *);
int CheckScore();
};
GeneticAlgorithm::Show()
{
for(int i=0;i<GENE_COUNT;i++)
{
cout<<"the gene is:";
for(int j =0;j<GENE_LENG;j++)
{
printf(" %d",Gene[i][j]);
//cout<<" "<<Gene[i][j];
}
printf("\n");
cout<<endl<<"the score is:"<<GeneScore[i]<<endl;
}
}
GeneticAlgorithm::GeneticAlgorithm()
{
Top =0;
srand((unsigned) time(NULL));
for(int k = 0;k <GENE_COUNT; k ++)
{
for(int i = 0;i < GENE_LENG;i ++)
{
Gene[k][i] =(char)RandInt(0,3);
}
}
for(int j = 0;j <GENE_COUNT ;j ++)
{
GeneScore[j] = 0;
}
}
GeneticAlgorithm::MakeScore()
{
int x,y,m,n;
m =0;
n =2;
double adaptiveScores,t,temp;
temp = 0;
for(int i =0;i<GENE_COUNT;i++)
{
x = 0;
y = 2;
adaptiveScores = 0;
for(int j = 0;j< GENE_LENG;j++)
{
temp = abs(14-m)+abs(7-n)+1;
t = 1/temp;
m = x;
n = y;
if(Gene[i][j]==0)
y--;
if(Gene[i][j]==1)
y++;
if(Gene[i][j]==2)
x--;
if(Gene[i][j]==3)
x++;
if(map[y][x]==1||map[y][x]==8||(x<0)||(y<0))
{
x = m;
y = n;
continue;
}
if(map[y][x]==5)
{
adaptiveScores = 1;
break;
}
if(map[y][x]==0)
{
temp = abs(14-m)+abs(7-n)+1;
t = 1/temp;
}
if(adaptiveScores<t)
adaptiveScores = t;
}
GeneScore[i] = adaptiveScores;
}
}
int GeneticAlgorithm::WheelRoulette()
{
double sum = 0;
for(int i= 0;i<GENE_COUNT;i++)
{
sum = sum +GeneScore[i];
}
back:
double p = RandFloat()*sum;
sum=0;
for(int j = 0;j<GENE_COUNT;j++)
{
sum = sum+GeneScore[j];
if(sum > p)
{
if(GeneScore[j]==0)
goto back;
return j;
}
}
}
GeneticAlgorithm::Hybr()
{
char gene1[GENE_LENG];
char gene2[GENE_LENG];
int temp;
int a,b;
a = 0;
b = 0;
double pro= RandFloat();
while(a==b)
{
a = WheelRoulette();
b = WheelRoulette();
}
temp = RandInt(0,GENE_LENG-1);
if(pro < CROSSOVER_RATE)
{
for(int k = 0;k<temp;k++)
{
gene1[k] = Gene[a][k];
}
for(int l = temp;l <GENE_LENG;l++)
{
gene1[l] = Gene[b][l];
}
for(int m = 0;m<temp;m++)
{
gene2[m] = Gene[b][m];
}
for(int n = temp;n <GENE_LENG;n++)
{
gene2[n] = Gene[a][n];
}
}
else
{
for(int o = 0;o <GENE_LENG;o++)
{
gene1[o] = Gene[b][o];
}
for(int p = 0;p <GENE_LENG;p++)
{
gene2[p] = Gene[a][p];
}
}
Variation(gene1);
Variation(gene2);
for(int j = 0;j<GENE_LENG;j++)
{
GeneBuffer[Top][j] =gene1[j];
}
Top++;
for(int i = 0;i<GENE_LENG;i++)
{
GeneBuffer[Top][i] =gene2[i];
}
Top++;
//printf("Hybr is finished\n");
}
GeneticAlgorithm::Hybr_main()
{
for(int i = 0;i<50;i++)
{
Hybr();
// printf("this is Hybr_main()\n");
// cout<<i<<endl;
}
Top = 0 ;
memcpy(Gene,GeneBuffer,GENE_COUNT*GENE_LENG*sizeof(char));
}
GeneticAlgorithm::Variation(char *gene)
{
double p = MUTATION_RATE;
int point = RandInt(1,GENE_LENG*2-1);
if(RandFloat() < p)
{
if(point%2==0)
{
if(gene[point/2]==0)
gene[point/2] =2;
if(gene[point/2]==1)
gene[point/2] =3;
if(gene[point/2]==2)
gene[point/2] = 0;
if(gene[point/2]==3)
gene[point/2]= 1;
}
else
{
if(gene[point/2]==0)
gene[point/2] =1;
if(gene[point/2]==1)
gene[point/2] =0;
if(gene[point/2]==2)
gene[point/2] = 3;
if(gene[point/2]==3)
gene[point/2]= 2;
}
}
}
int GeneticAlgorithm::CheckScore()
{
for(int i=0;i<GENE_COUNT;i++)
{
if(GeneScore[i]==1)
{
for(int m =0;m<GENE_LENG;m++)
{
printf(" %d",Gene[i][m]);
}
return 1;
}
}
return 0;
}
int main()
{
GeneticAlgorithm temp;
for(int i= 0;i<MAP_HEIGHT;i++)
{
for(int j =0;j<MAP_WIDTH;j++)
{
printf(" %d",map[i][j]);
}
printf("\n");
}
printf("\n");
for(int n=1;;n++)
{
temp.MakeScore();
if(temp.CheckScore()==1)
{
cout<<"the generation is :"<<n<<endl;
break;
}
temp.Hybr_main();
}
cout<<endl<<"Congratulation!!!!"<<endl;
return 1;
}
