遗传算法.cpp

遗传算法的源码 大家可以参考

#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
int distance(int *s,int matrix[20][20]){       // 求路径的距离     
	int dis;
	int i,j,k;
	dis=0;
	for(i=0;i<19;i++){
		j=s[i];
		k=s[i+1];
        dis=dis+matrix[j][k];
	}
	j=s[19];
	k=s[0];
	dis=dis+matrix[j][k];
	return dis;
}
double fitness(int *s,int matrix[20][20]){          //适应度函数
	int n;
	n=distance(s,matrix);
	return pow(n,-1);
}
int Nature_to_Grefenstette(int nature[20],int Grefenstette[20]){//Grefenstette编码
	int j,k;
	for(j=0;j<20;j++){
		if(j==0){
			Grefenstette[j]=nature[j];
		}
		else{
            Grefenstette[j]=nature[j];
			for(k=0;k<j;k++){
				if(nature[j]>nature[k]){
					Grefenstette[j]--;
				}
			}
		}
	}
	return 0;
}
int Grefenstette_to_nature(int Grefenstette[20],int nature[20]){//Grefenstette反编码
     int i,j,k,l,m;
	 int s[20],s1[20];
	 for(i=0;i<20;i++){
		 s[i]=i;
	 }
	 for(i=0;i<20;i++){
		 if(i==0){
			 nature[i]=Grefenstette[i];
		 }
		 else{
			 m=0;
		     for(k=0;k<20;k++){
			   	l=0;
			    for(j=0;j<i;j++){
				   if(s[k]==nature[j]){
					   l++;					  
				   }
				}
			   if(l==0){
		    	  s1[m]=s[k];
				  m++;
			  }
		   } 
			l=Grefenstette[i];
			nature[i]=s1[l];
		 }
	 }
	 return 0;
}

int main(){
	double f[40],bestf,worstf;
	double sumfitness,p[40];
	int change;
	long G;
	int s1[20];
	int matrix[20][20];      //距离矩阵
	int group[40][20],Grefenstette[40][20];       //群体
	int i,j,k,l,m,n;
	char c;
	char *buffer;
	FILE *fp;
	fp=fopen("matrix.txt","rb");
	if(!fp){
		printf("Can not open this file!\n");
		printf("The file is not existed or the filename is illegal!\n");
		return 0;
	}
	i=0;
	j=0;
	k=0;
	n=0;
	while(!feof(fp)){                        //读距离矩阵，距离矩阵保存在文件中
		c=fgetc(fp);
		k++;		
    }
	rewind(fp);
	k++;
	buffer=(char*)malloc(k*sizeof(char));
	k--;	
	fread(buffer,k,1,fp);
	buffer[k]=0x0000;    
	while(i<strlen(buffer)){
		k=0;
		while(buffer[i]!='\0'&&(buffer[i]==' '||buffer[i]==0x000a||buffer[i]==0x000d)){
			while(buffer[i]==' '||buffer[i]==0x000a||buffer[i]==0x000d){
				i++;
			}
		}
		while(buffer[i]!='\0'&&buffer[i]!=' '&&buffer[i]!=0x000a&&buffer[i]!=0x000d){
			k++;
			i++;
		}
		i=i-k;
		if(j>=20){
			n++;
			j=0;
		}
		if(n>=20){
			printf("The data is wrong!");
		}
		matrix[n][j]=0;
		k=i+k;
		for(i;i<k;i++){
			matrix[n][j]=(matrix[n][j]+buffer[i]-48)*10;		
		}
		matrix[n][j]=matrix[n][j]/10;
		j++;
	}	
	for(i=0;i<20;i++){
		s1[i]=i;
	}
	for(i=0;i<40;i++){    //群体初始化
        j=rand()%20;       //产生两个0-19的随机数
	    n=rand()%20;
		if(j<n){           //"逆转中间或者逆转两端"的方式产生新解
			while(j<n){
				l=s1[n];
				s1[n]=s1[j];
				s1[j]=l;
				j++;
				n--;
			}
		}
		else if(j>n){
			m=0;
			while(m<n){
				l=s1[n];
				s1[n]=s1[m];
				s1[m]=l;
				m++;
		    	n--;
			}
			m=19;
			while(j<m){
				l=s1[m];
				s1[m]=s1[j];
				s1[j]=l;
				m--;
				j++;
			}
		}
		else{
           m=0;
		   while(m<n){
				l=s1[n];
				s1[n]=s1[m];
				s1[m]=l;
				m++;
				n--;
			}
			if(n<19){
			   	m=19;
				j++;
			   	while(j<m){
				   	l=s1[m];
				   	s1[m]=s1[j];
			    	s1[j]=l;
				   	m--;
				   	j++;
				}
			}
		}
        for(j=0;j<20;j++){
            group[i][j]=s1[j];
		}
	}
	for(i=0;i<40;i++){ 
		Nature_to_Grefenstette(group[i],Grefenstette[i]);	
	}
	for(i=0;i<40;i++){                   //求适应度数列
		f[i]=fitness(group[i],matrix);
	}
	sumfitness=0;
	for(i=0;i<20;i++){
		sumfitness=sumfitness+f[i];
	}
	for(i=0;i<40;i++){
		p[i]=f[i]*pow(sumfitness,-1);
	}
	bestf=0;
	worstf=f[0];
	for(i=0;i<40;i++){                  //求最佳适应度
		if(bestf<f[i]){
			bestf=f[i];
		}
		if(worstf>f[i]){
			worstf=f[i];
		}
	}
	for(i=0;i<40;i++){
		if(f[i]==bestf)
		break;	
	}
	for(j=0;j<40;j++){
		if(f[j]==worstf){
			for(k=0;k<20;k++){
				Grefenstette[j][k]=Grefenstette[i][k];
			}				
		}
	}
	G=0;
	while(G<4000){		
       //下面是交叉，采用单点交叉		
        n=i;
	   	m=rand()%20;
		j=rand()%20;
	   	for(j;j<20;j++){
	       	change=Grefenstette[n][j];
	       	Grefenstette[n][j]=Grefenstette[m][j];
	       	Grefenstette[m][j]=change;
		}
		
	   	//下面是变异，采用交换变异,变异的概率为0.01,且每个染色体上的基因变异概率相等
		for(i=0;i<40;i++){
			Grefenstette_to_nature(Grefenstette[i],group[i]);
		}		
    	n=rand()%20;
		m=rand()%20;			
		j=rand()%20;
		i=rand()%20;		
	  	change=group[n][j];
		group[n][j]=group[n][i];
		group[n][i]=change;	
		change=group[m][j];
		group[m][j]=group[m][i];
		group[m][i]=change;	
		for(i=0;i<40;i++){
			Nature_to_Grefenstette(group[i],Grefenstette[i]);
		}
		//计算后代中的最佳适应度
		for(i=0;i<40;i++){                
	       	f[i]=fitness(group[i],matrix);
		}	
		worstf=f[0];
		bestf=0;
        for(i=0;i<40;i++){             
	    	if(bestf<f[i]){
		    	bestf=f[i];
			}
			if(worstf>f[i]){
		    	worstf=f[i];
			}
		}
		//下面是选择,采用最优保存策略,用适应度最佳的后代淘汰适应度最差的后代
		for(i=0;i<40;i++){
			if(f[i]==bestf)
			break;	
		}
		for(j=0;j<40;j++){
			if(f[j]==worstf){
				for(k=0;k<20;k++){
					Grefenstette[j][k]=Grefenstette[i][k];
				}				
			}
		}
/*		printf("当前代数为%d,新的种群为:\n",G);
		for(k=0;k<20;k++){
			for(j=0;j<20;j++){
				printf("%d ",group[k][j]);
			}
			printf("\n");
		}*/		
		G++; 	
	}
	for(i=0;i<40;i++){
		if(f[i]==bestf)
			break;
	}
	for(j=0;j<20;j++){
		s1[j]=group[i][j];        
	}
	printf("最佳路径为:\n");
	for(i=0;i<19;i++){
		printf("%d->",s1[i]);
	}
	printf("%d\n",s1[i]);	
	printf("最小开销为:%d\n",distance(s1,matrix));
	fclose(fp);
	printf("Print any key to continue!");
	scanf("%c",c);
	return 0;
}