genetic.cpp

本算法中采取了种群规模为100

#include<iostream.h>
#include<math.h>
#include <stdlib.h>
#include<time.h>

#define scale 100									//定义种群大小
#define amount 10									//定义城市数目

int * random(void);									//随机函数产生一个解序列
class citys{
private:
	int city_number;								//记录城市总数目
	double citycoordinate[amount][2];				//记录各个城市的坐标
	int father[scale][amount],son[scale][amount];   //father记录当前选取的群体.son用于在计算中暂时存储群体值
	double pc,pm;									//分别代表交配概率和变异概率
	int t;											//记录遗传代数
	int best_path[amount];							//记录最好的路径

public:
	citys(void){									//构造函数
		city_number = amount;
		pc = 1.0;
		pm = 0.1;
		t = 0;
		double temp1[amount][2] ={0.4000,0.4439,
							  0.2439,0.1463,
							  0.1707,0.2293,
							  0.2293,0.7610,
							  0.5171,0.9414,
							  0.8732,0.6536,
							  0.6878,0.5219,
							  0.8488,0.3609,
							  0.6683,0.2536,
							  0.6195,0.2634};
							/*	{5.294,1.558,
									4.286,3.622,
									4.719,2.774,
									4.185,2.230,
									0.915,3.821,
									4.771,6.041,
									1.524,2.871,
									3.447,2.111,
									3.718,3.665,
									2.649,2.556,
									4.399,1.194,
									4.660,2.949,
									1.232,6.440,
									5.036,0.244,
									2.710,3.140,
									1.072,3.454,
									5.855,6.203,
									0.194,1.862,
									1.762,2.693,
									2.682,6.097};
							*/	

		for(int i=0;i<amount;i++)
		{
			best_path[i] = 0;						//初始化最好路径
			for(int j=0;j<2;j++)					//初始化城市坐标
				citycoordinate[i][j] = temp1[i][j];
		}		

		int *temp2 = NULL;							//初始化种群，初始种群存在father和son中
		for(int j=0;j<scale;j++)
		{
			temp2 = random();
			for(int k=0;k<amount;k++)
			{
				father[j][k] = temp2[k];
				son[j][k] = temp2[k];
			}
		}
	}
	double distance(int x,int y)					 //计算两个城市之间的距离
	{
		double result = 0;
		result = sqrt( (citycoordinate[x][0] - citycoordinate[y][0]) * (citycoordinate[x][0] - citycoordinate[y][0]) + 
						(citycoordinate[x][1] - citycoordinate[y][1]) * (citycoordinate[x][1] - citycoordinate[y][1]) );
		return result;
	}
	double evaluate(int *x)							 //计算某一个序列中城市之间的距离总和
	{
		double result = 0;
	
		for(int counter=0;counter<amount-1;counter++)
		{
			result += distance(x[counter],x[counter+1]);
		}
		result += distance(x[amount-1],x[0]);

		return result;
	}

	double random0_1(void)							 //产生随机数,范围在0-1之间
	{        
		return (double)rand() / (RAND_MAX+0.0);
	}
	
	void out(int *x){
		int *temp = x;
		for(int s=0;s<amount;s++)
		{
			cout << temp[s] << " ";
		}
	}


	double Possibility(int i)						//该函数计算在当前群体中染色体xi被选中的概率。sum记录了当前群体总的适应值之和
	{
		double result = 0;
		double sum = 0;
		for (int j=0;j<scale;j++)
			sum += exp ( -evaluate(father[j]) );
		result = exp ( -evaluate(father[i]) ) / sum;
		return result;
	}

	void copy(int *x,int *y)						//将数组x[]中的值复制到数组y[]中，覆盖掉y[]原来的值
	{
		for(int j=0;j<amount;j++)
			y[j] = x[j];
	}

	void turntable(void)							//轮盘赌
	{
		double s,r;
		int i,k = 0;
		double probability[scale];

		for(i=0;i<scale;i++)
			probability[i] = Possibility(i);

		do
		{
			s = 0;
			r = random0_1();
			i = -1;
			
			while( s < r )
			{
				i++;
				i = i%(scale); 
				s += probability[i];
			}
			if(i == -1)
				i++;
			copy(father[i],son[k]);					//选中第i个染色体,存放到子代son[i]
			k++;
		}while(k < scale);							//选出新的子代
		for(i=0;i<scale;i++)
			copy(son[i],father[i]);					//将子代重新写入father当作父带进行遗传
	}
	
	void mate(int *x,int *y)						//按照常规交配法进行处理
	{
		int mateposition = 0,temp[amount];
		int i,j;
		mateposition = rand() % (amount-1);			//随机选择交配位
		for(int counter=0;counter<amount;counter++)
			temp[counter] = x[counter];
		for(j=mateposition+1;j<amount;j++)	
			{
				int k = 0;
				for(i=0;i<j;i++)
					if( (x[i] == y[k]) )
					{
						k++;
						i = -1;
					}
				x[j] = y[k];
			}										//得到子代x
		for(j=mateposition+1;j<amount;j++)	
			{
				int k = 0;
				for(i=0;i<j;i++)
					if( (y[i] == temp[k]) )
					{
						k++;
						i = -1;
					}
				y[j] = temp[k];
			}										//得到子代y
	}
	
	void mutant(int *x)								//采用基于次序的变异方法
	{
		int position1 = 0,position2 = 0;
		int temp = 0;
		double mutantchance = 0;
		mutantchance = (double)rand() / (RAND_MAX+0.0); //如果几率足够大，才发生变异
		if(mutantchance > (1.0-pm))
		{	
			do
			{
				position1 = rand() % amount;
				position2 = rand() % amount;
			}while(position1 == position2);

			temp = x[position1];
			x[position1] = x[position2];
			x[position2] = temp;				
		}
	}
	
	double bestevaluate(void)
	{
		double result = 50,save = 50;
		for(int i=0;i<scale;i++)
		{
			save = evaluate(father[i]);
			if( save < result)
			{
				result = save;
				copy(father[i],best_path);
			}
		}
		return result;
	}

	void gene(void)									//遗传算法
	{
		double prev=50,average=0,last=50;
		double best = 50;
		int time = 0;
		int temp[amount];

			best = 50;
			t = 0;									//记录遗传次数
			prev =50;
			last=50;
			do
			{
				last=prev;
				turntable();
				for(int counter=0;counter<scale;counter+=2)     //交配
					mate(father[counter],father[counter+1]);

				for(counter=0;counter<scale;counter++)			//变异
					mutant(father[counter]);		
			
				t++;
				prev = bestevaluate();							//对father代进行选择最优解，结果存在best_path中
				if(best > prev)
				{
					best = prev;
					time = t;
					copy(best_path,temp);
				}
			}while( t<20);  
			out(best_path);
			cout<<endl;
			cout << best << endl;
			
			}

};

int * random(void)
{
	int temp = 0,signal = 1,k=0;
	int *save =NULL;
	save =  new int[amount];
	for(int j=0;j<amount;j++)
		save[j] = -1;
	do
	{
		signal = 1;
		temp = rand() % amount;
		for(int i=0;i<amount;i++)
			if(save[i] == temp)
			{signal = 0;break;}
		if(signal != 0)
		{
			save[k] = temp;
			k++;
		}
	}while(signal == 0 || k != amount);
	return save;
}


void main()
{
	citys city;
	srand((unsigned)time(NULL));
    for(int i=0;i<100;i++)city.gene();

}