小弟第一次发帖，在网上看了一篇遗传算法入门的文章（http://blog.csdn.net/zzwu/article/details/561577）
觉得很有意思，于是想自己练习一下
解释：
程序中先提供一张地图，设置好入口和出口，随机生成100条染色体，每个染色体有40个节点
每个节点可能出现的数据为0、1、2、3（0代表向上↑，1代表向下↓，2代表向左←，3代表向右→），从出发点出发，依次读取染色体的节点，如果碰到墙壁（地图中的1）或者入口（地图中的8）就跳过该节点，继续读取下一节点，当所在方位是出口时，给予此染色体1分（满分），若走完一条染色体之后却没有到达出口，则给予此染色体一个适应性评分（为此染色体离出口最近的横向距离与纵向距离的绝对值只和）
使用单点交叉的杂交方法，和单点取反的变异方法
初学编程 编程水平有限 请各位指点
疑问：
在实验中，程序出现过几次很久都没有跑出结果的情况。请各位说一下我哪里出问题了
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "iostream.h"
#include "windows.h"
#include "math.h"
#define GENE_COUNT 100 //染色体的数量
#define GENE_LENG 40 //每个染色体所具有的节点个数
#define MAP_WIDTH 15 //地图的宽
#define MAP_HEIGHT 10 //地图的高
#define CROSSOVER_RATE 0.7 //杂交率
#define MUTATION_RATE 0.001 //变异率
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;
}
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
