inherit.cpp

人智经典算法的实现

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <ctime>
#include <cmath>

using namespace std;

const int N=500;  
double pc=1.0;                                                       
double pm=0.01;														 

int cityNum=0;														
double  * xCoor;													
double  * yCoor;														
char     * cityName;														

struct aUnit{
		int * path;   
		double  f; 
};

vector<aUnit>  colony ;  
vector<aUnit>  newColony ;  
double *p=new double[N];  


//用于从文件中读入的函数
void input(){    
	char FileName[50];
	cin>>FileName;
	ifstream in=ifstream(FileName);
	if(!in)
	{
		cout<<"文件打开失败"<<endl;
		return ;
	}
	in>>cityNum;
	xCoor=new double[cityNum];  
	yCoor=new double[cityNum];
	cityName=new char[cityNum];
    int index=0;  
	  while(in>>cityName[index]){
	   double dis;
		in>>dis;
		xCoor[index]=dis;
		in>>dis;
		yCoor[index]=dis;
		index++;
   }
}

//计算路径长度的函数
double distance(int* arr,int num){
	 double  *newX=new double[num];	
	 double  *newY=new double[num];
	 for(int i=0;i<cityNum;i++){
		 newX[i]=xCoor[arr[i]];
		 newY[i]=yCoor[arr[i]];
	 }
	double dis=0.0;
	for(int i=0;i<num-1;i++)
	{
		dis+=sqrt(pow( newX[i+1]- newX[i],2)+pow( newY[i+1]- newY[i],2));
	}
	dis+=sqrt(pow(newX[num-1]-newX[0],2)+pow( newY[num-1]- newY[0],2));
	return dis;
}


//交换两个位置上的整数基因，以产生变异，得到不同与祖先的后代
void changeTwo(int * & Array) {
         	int  index1=rand()%cityNum;   //随机产生两个交换位置
			int  index2 =rand()%cityNum;
	         int temp=Array[index1];
			Array[index1]=Array[index2];
			Array[index2]=temp;
}


void copy(int *& w1,int * w2, int num)
{
	for(int i=0;i<num;i++)
	{
		w1[i]=w2[i];
	}
}

//计算每一个个体被选择的概率
void getP()
{
	double all=0.0;
	for(vector<int>::size_type i=0;i<N;i++){
		all+=colony[i].f;
	}
	//cout<<"all  "<<all<<endl;
	for(vector<int>::size_type i=0;i<N;i++){
		p[i]=colony[i].f/all;
		//cout<<"p[i]  "<<p[i]<<endl;
	}
}

bool exist(int a,int *arr,int pos){
	for(int i=0;i<pos;i++)
	{
		if(a==arr[i])
			return true;
	}
	return false;
}

//得到初始群体的函数
void getStart()
{
	for(int i=0;i<N;i++)
	{
		bool *show;
		show=new bool[cityNum];
		for(int i=0;i<cityNum;i++)
			show[i]=false;
		aUnit u;
		u.path=new int[cityNum];
		for(int j=0;j<cityNum;j++)    //******************个体的编码方案为整数编码，以城市在数组中的下标为基因
		{
			int init=rand()%cityNum;
				while(show[init])
				{
					 init=rand()%cityNum;
				}
				u.path[j]=init;
				show[init]=true;
		}
		u.f=100-distance(u.path,cityNum);
		colony.push_back(u); 
	}
	getP();
}

// 用于选择的函数，实现方法为“轮盘赌”
/*void choose(){
	cout<<"轮盘赌之前的种群情况"<<endl;
	for(int i=0;i<N;i++)
	{
		cout<<i<<"  : ";
		for(int j=0;j<cityNum;j++)
			cout<<colony[i].path[j]<<" ";
			cout<<endl;
			cout<<10-colony[i].f<<endl;
	}
	newColony.clear();
   for(int k=0;k<N;k++){        //做N次轮盘赌，产生N个个体
		double r=(double)rand()/RAND_MAX;
		double s=0.0;
		int i=0;
		while(r>=s&&i<N){    
			s+=p[i];
			i++;  
		}
		cout<<" 轮盘赌选出的个体:  "<<i-1<<endl;
		newColony.push_back(colony[i-1]);
	}
	for(int i=0;i<N;i++)
	{
		copy(colony[i].path,newColony[i].path,cityNum);
		colony[i].f=newColony[i].f;
	}
	cout<<"轮盘赌之后的种群情况"<<endl;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<cityNum;j++)
			cout<<colony[i].path[j]<<" ";
			cout<<endl;
			cout<<10-colony[i].f<<endl;
	}
	cout<<"end"<<endl;
	getP();
}*/

void choose(){
	newColony.clear();
	int n=0;
	double *Num;
	Num=new double[N];
	double *left;
	left=new double[N];
	for(int i=0;i<N;i++)
	{
		Num[i]=p[i]*N;
		//cout<<"num  "<<Num[i]<<endl;
		left[i]=Num[i]-(int)Num[i];
		//cout<<left[i]<<endl;
		//cout<<"left[i]"<<left[i]<<endl;
		if((int)Num[i]>0)
		{
			for(int j=1;j<=(int)Num[i];j++)
			{
				newColony.push_back(colony[i]);    
				n++;
			}
			/*if(left[i]>0.005){
			   newColony.push_back(colony[i]);
		       n++;
			   if(n>=N) break;
			}*/
		}
	}
	while(n<N){
		int m=0;
		double max=0.0;
		for(int k=0;k<N;k++)
		{
			if(max<left[k])
			{
				max=left[k];
				m=k;
			}
		}
		left[m]=0.0;
		newColony.push_back(colony[m]);
		n++;
	}
	for(int i=0;i<N;i++)
	{
		copy(colony[i].path,newColony[i].path,cityNum);
		colony[i].f=newColony[i].f;
	}
	getP();
}

//*****************************实现交配过程,实现为两两交配，如0，1交配，2，3交配，交配方法为常规交配
void transmit(){
	int i=0;
	if(N<=1) return;
	while(i<N&&i+1<N)
	{
		//得到交配位置
		int  pos=rand()%cityNum;
		int * newUnit=new int[cityNum];
	    copy(newUnit,colony[i].path,cityNum);
		int k=pos;
		for(vector<int>::size_type j=0;j<cityNum;j++)
		{
			if(!exist(colony[i+1].path[j],  colony[i].path, pos)){
				colony[i].path[k]=colony[i+1].path[j];
				k++;
				if(k==cityNum)break;
			}
		}
		int m=pos;
		for(vector<int>::size_type j=0;j<cityNum;j++)
		{
			if(!exist(newUnit[j],  colony[i+1].path,pos)){
				colony[i+1].path[m]=newUnit[j];
			    m++;
				if(m==cityNum)break;
			}
		}
		colony[i].f=100-distance(colony[i].path,cityNum);
		colony[i+1].f=100-distance(colony[i+1].path,cityNum);
		i+=2;
	}
	getP();
}

//********************用于变异的函数，其实现方法为交换两个位置上的整数编码
void vari(){
	for(int i=0;i<N;i++)                        //每一个个体都有一定的变异概率
	{
		double d=(double)rand()/RAND_MAX;
		if(d<pm){
			changeTwo(colony[i].path);
			colony[i].f=100-distance(colony[i].path,cityNum);
		}
	}
	getP();
}

//主函数
int main(){
	srand((unsigned int) time(NULL));     //种种子
	
	input();  
	for(int loop=0;loop<5;loop++){
		cout<<"总共做5次遗传算法，第 "<<loop+1<<" 次结果如下:"<<endl;
	int t=0;  
	getStart();	
    while(t<200){          //***************************算法结束条件为进化200代之后结束
		choose();                           //用于选择的函数
		transmit();                          //用于交配的函数
		vari();                                 //用于变异的函数*************新种群为交配变异之后的种群
		t++;
    }
	double max=0.0;
	int rem=0;
	for(int i=0;i<N;i++)
	{
		if(max<colony[i].f)
		{
			max=colony[i].f;
			rem=i;
		}
	}
	for(int i =0;i<cityNum;i++){
		cout<<cityName[colony[rem].path[i]]<<" ";
	}
	cout<<endl;
	cout<<"得到的最短路径为 :"<<100-max<<endl;
	colony.clear();
	}
	return 0;
}