head.h

hws01:野人和传教士问题 hws02:用Romberg外推法求积分近似值 hws03:八数码问题 hws04:模拟退火算法 hws05:遗传算法解决旅行商问题

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N=388;	                //种群数量
const double Pc = 1.00;	            //交配概率
const double Pm = 0.0388;	        //变异概率
const int Generation=10;     //对于每次遗传算法，达到 Generation代停止

struct City                         //定义城市的类
{            
	string name;                    //城市的名称
	double x;                       //城市的x坐标
	double y;                       //城市的y坐标
};

struct Path                         //定义一条路径的类
{
	vector<int> road;               //保存一个城市序列
	double F;                       //适应值
	double Ex;                      //期望次数
	Path&  operator = (Path& p)     //重载赋值符号=，用于两条路径的复制
	{
		this->road = p.road;
		this->F = p.F;
		this->Ex = p.Ex;
		return *this;
	}
	void change(int pos1,int pos2){ //用于基于次序的变异，交换两个城市
		int temp;
        temp=road[pos1];
		road[pos1]=road[pos2];
		road[pos2]=temp;
	}
};

Path Group[N];                      //定义N个个体的种群
vector<City> city;               //定义存储城市的容器
vector<int>  index;                 //定义存储城市的下标
Path thebest;                       //种群中的最佳路径

double **matrix;                    //二维数组，保存城市间的距离的距离矩阵
int Num;                            //城市数目
void BuildCity(ifstream & fin){    //从文本中读入建立城市
	int size;
	fin>>size;
	Num=size;
	for(int i=0;i<size;i++){
		City c;
		string name;
		fin>>name;
		c.name=name;
		double pos;
		fin>>pos;
	    c.x=pos;
		fin>>pos;
		c.y=pos;
		city.push_back(c);
		index.push_back(i);
	}
}

double distance(int i,int j)     //计算两个城市间的距离
{ 
	return sqrt(pow(city.at(i).x-city.at(j).x,2.0)+pow((city.at(i).y-city.at(j).y),2.0));
}

void BuildMatrix(){              //建立城市的距离矩阵
	matrix = new double*[Num];
	for(int j=0;j<Num;j++)
	{
	    matrix[j]=new double[Num];
		for(int k=0;k<Num;k++)
		{
			matrix[j][k]=distance(j,k);
		}
	}
}

double length(vector<int>& Path)          //计算路径的长度
{         
	double length=0;
	for(int i=0;i<Num-1;i++)
	{
		length+=matrix[Path.at(i)][Path.at(i+1)];
	}
	length+=matrix[Path.at(Num-1)][Path.at(0)];
	return length;
}
void randomPath(int n,Path* p)         //随机产生新的路径
{       
	p[n].road.reserve(Num);
	int *random = new int[Num];
	for(int i=0; i<Num; i++)
		random[i]=0;
		
	int index = 0;
	while(index<Num)
	{
		int temp =rand()%Num;
		int i;
		for( i=0; i<index; i++)
		{
			if(temp==random[i])
				break;
			
		}
		if(i==index)
		{
			random[i] = temp;
			index++;
		}
		
	}
	if(p[n].road.size()>0)
		p[n].road.clear();
	for(int i=0;i<Num;i++){
        p[n].road.push_back(random[i]);
	}
}

void GenGroup(Path* p)             //生成新的种群
{           
	for(int i=0;i<N;i++){
		randomPath(i,p);
	}
}

void figure()                      //计算种群每个路径的适应值和期望值
{                   
	double sum=0.0;                //算适应值的总和
    double best=0.0;               //最大适应值
	int bestpos=0;                 //最佳路径的标号
    for (int i=0;i<N;i++)
    {
        Group[i].F=100-length(Group[i].road);
        if(Group[i].F>best)
		{
			bestpos=i; 
			best=Group[i].F;       //记录当前种群的最好值
		}
		sum+=Group[i].F;
    }
	for(int i=0; i<N; i++)
	{
		Group[i].Ex=N*Group[i].F/sum;//计算期望次数
	}
	if(thebest.F<Group[bestpos].F)
	{
		thebest=Group[bestpos];
	}
}



void newGroup(Path *g)              //根据所得概率选取N个染色体，得到种群
{
	Path *temp = new Path[N];
	for(int i=0;i < N; i++)
	{
		temp[i] = g[i];
	}
	int index =0;
	for(int i=0;i < N; i++)
	{
		if( temp[i].Ex >=1 )
		{
			int count=2*(int)temp[i].Ex;
			while(count>0)
			{
				if(index<N)
				{
					g[index]=temp[i];
					index++;
					count--;
				}
				else
					break;
			}
			temp[i].Ex = temp[i].Ex-(int)temp[i].Ex;//修改期望值
		}
	}

	double max = 0.0;
	int pos=0;
	while(index<N)                            //新的种群的染色体的数量还不够,按照从大到小的顺序在未选的中选择
	{   
		for(int i=0; i<N; i++)                //每次选择出最大者
		{  
			if(max<temp[i].Ex){
				max = temp[i].Ex;
				pos = i;
			}
		}
		g[index]= temp[pos];
		index++;
		temp[pos].Ex=0.0;
		max =0.0;
		
	}
}
void Genson(int* temp1,int* temp2,vector<int>& father,vector<int>& mather)//由双亲father和mather产生两个子代temp1和temp2
{
	//首先产生一半的交配位
	int* random=new int[Num/2];
	for(int i=0;i<Num/2;i++)
		random[i]=0;
	int index=0;
	while(index<Num/2)
	{
		int temp=rand()%Num;
		int i;
		for(i=0; i<index; i++)
		{
			if(temp==random[i])
			break;
		}
		if(i==index)
		{
			random[i] = temp;
			index++;
		}
	}

	for(int i=0;i<Num;i++)
		temp1[i]=temp2[i]=-1;
		
	for(int i=0;i<Num/2;i++)           //子代的相关位上的基因来自mather/father
	{    
		temp1[random[i]]=mather[random[i]];
		temp2[random[i]]=father[random[i]];
	}
	
	for(int i=0;i<Num;i++)
	{
		bool flag1=false;bool flag2=false;
		for(int j=0;j<Num/2;j++)
		{
			if(father[i]==mather[random[j]])
			{
				flag1=true;
				break;
			}
		}
		if(!flag1)                     //father[i]还未被选择
		{
			for(int k=0;k<Num;k++)
			{
				if(temp1[k]==-1)      //该位空缺
				{      
					temp1[k]=father[i];
					break;
				}
			}
		}
		for(int j=0;j<Num/2;j++)
		{
			if(mather[i]==father[random[j]])
			{
				flag2=true;
				break;
			}
		}
		if(!flag2)
		{
			for(int k=0;k<Num;k++)
			{
				if(temp2[k]==-1)     //该位空缺
				{   
					temp2[k]=mather[i];
					break;
				}
			}
		}
	}
}

void Mating(Path * p)              //基于位置的交配法
{ 
	for(int n=0;n<N/2;n++){
		vector<int> father=p[n].road;
		vector<int> mather=p[N-n-1].road;
		vector<int> son,daught;
		son.reserve(Num);
        daught.reserve(Num);
		int *temp1=new int[Num];  //产生两个子代
		int *temp2=new int[Num];
		Genson(temp1,temp2,father,mather);
		for(int i=0;i<Num;i++){
			son.push_back(temp1[i]);
			daught.push_back(temp2[i]);
		}
		p[n].road=son;
		p[N-n-1].road=daught;
	}
}

void Variation(Path* p)           //基于次序的变异函数
{    
    int num=Pm*N;                 //变异的个体个数
	for(int i=0;i<num;i++){
		int position=rand()%Num;  //变异个体的下标值
		int pos1=rand()%Num;      //产生变异个体的两个交换位置
		int pos2=rand()%Num;
		p[position].change(pos1,pos2);
	}

}