lan11.cpp

用遗传算法求借最短路径的程序

// Lan11.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "iostream.h"
#include "iomanip.h"
#include "math.h"

#define  MAX   1
#define  MIN   2
#define  CHROMLENGTH  13       //染色体长度，注意编码变化时，要随时修改
#define  MAXNUM       1000
#define  Cmax  30
#define  Cmin  0

int      PopSize = 150;   
int      FunctionMode = MIN;
double   m_fPc = 0.9;                   //交叉概率
double   m_fPm = 0.009;                 //变异概率
int      MaxGeneration = 20;
int      d[150][13];
int      s[150][13];
int      generation;
int      Best_Index;
int      Worst_Index;

struct individual      //定义染色体
{
	double chrom[CHROMLENGTH+1];
	double value;
	double fitness;	
};

struct individual
          BestIndividual;
struct individual
          WorstIndividual;
struct individual 
          Group[150];

double Random(double Low, double High)//本函数实现随机产生Low-High之间的实数 
{  
	return((double)rand()/RAND_MAX)*(High-Low)+Low;
}

double Max(double a, double b)
{
	if(a>=b) return a;
	else return b;
}


void GenerateInitialPopulation()//二进制编码初始化其中'1'表示路径顶点在最短路径中,'0'则反之
{
	int i,j;
    
	for(i = 0; i < PopSize; i++)
	{
		for(j = 1; j < CHROMLENGTH-2; j++)
		{    
			Group[i].chrom[j] = (int)(Random(1,10)<6)?'\0':'\1';
		}
		Group[i].chrom[CHROMLENGTH-1] = '\1';
		Group[i].chrom[0] = '\1';
	}
}

void CalculateObjectValue()//计算个体值
{
	int i,j,l;
  
	int a[13][13]={{0,     3,    5,     4,     MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,0,     MAXNUM,MAXNUM,9,     5,     MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,0,     MAXNUM,4,     3,     5,     MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,1,     7,     MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,MAXNUM,1,     5,     MAXNUM,MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,8,     4,     6,     MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     4,     4,     2,     MAXNUM,MAXNUM,MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,MAXNUM,4,     2,     MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,6,     9,     MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     7,     5,     MAXNUM},
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     MAXNUM,1     },
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0,     2     },
	{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0     },};
	for(i=0; i < PopSize; i++)
	{
	   for(l=0; l<CHROMLENGTH; l++)
	   {
	      if(Group[i].chrom[l]!=0)
		  {
		    d[i][l]=a[0][l];
		    s[i][l]=0;
		  }
	   }
	   d[i][0]=0;
	   s[i][0]=1;
	}
	
	
	for(i=0; i < PopSize; i++)
	{
	
		for(l=0; l<CHROMLENGTH-1; l++)
		{
	       int u=0;
		   for(j=0; j<CHROMLENGTH; j++)
		   {
			   if(!s[i][j]&&Group[i].chrom[j]=='\1')
			   {
				  u=j;
			   }
			   s[i][u]=1;
			   for(int w=0; w<CHROMLENGTH; w++)
			   if(!s[i][w]&&Group[i].chrom[w]=='\1')
			   {
                 d[i][w]=d[i][u]+a[u][w];
			   }
		   }
		}	
	Group[i].value = d[i][12];		
	}
}

void CalculateFitnessValue()//根据优化函数值计算出个体适应度
{
	int     i;
	double  temp;

	for(i=0; i<PopSize; i++)
	{
		if(FunctionMode==MAX)
		{
			if((Group[i].value + Cmin) > 0.0)
			{
				temp=Cmin + Group[i].value;
			}
			else
			{
				temp=0.0;
			}
		}
		else if(FunctionMode==MIN)
		{
			if(Group[i].value<Cmax)
			{
				temp=Cmax-Group[i].value;
			}
			else
			{
				temp=0.0;
			}
		}
		Group[i].fitness=temp;
	}
}
			

void FindBestAndWorstIndividual()//从当前群体中找出适应度最好和最差个体
{
	int i;
	double sum = 0.0;

	Best_Index = 0;
	Worst_Index = 0;
	BestIndividual = Group[0];
	WorstIndividual = Group[0];
	
	for(i = 1; i < PopSize; i++)
	{
		if(Group[i].fitness > BestIndividual.fitness)
		{
			BestIndividual = Group[i];
			Best_Index = i;
		}
		else if(Group[i].fitness < WorstIndividual.fitness)
		{
			WorstIndividual = Group[i];
			Worst_Index = i;
		}
		sum += Group[i].fitness;
	}
}			   

void SelectionOperator()//采用比例选择算子产生新群体
{
	int i, index;
	double p,sum = 0.0;
	
	struct individual *NewGroup = new struct individual[PopSize];
	double *cfitness = new double[PopSize];   
	
	for(i = 0; i < PopSize; i++)
	{
		sum += Group[i].fitness ;
	}
	
	for(i = 0; i < PopSize; i++)
	{
		cfitness[i] = Group[i].fitness/sum;
	}
	
	for(i = 1; i < PopSize; i++)
	{
		cfitness[i] = cfitness[i-1] + cfitness[i];
	}

    int temp=0;
	for(i = 1; i < PopSize; i++)
	{ 
		if(cfitness[temp] > cfitness[i])  
			temp = i;
	}
	
 	for(i = 0; i < PopSize; i++)
	{
	    p = (double)(rand()%1000)/1000.0;
		index = 0;
		while(p > cfitness[index])
		{
			index++;
		}
		if(index >= 10)
		{
			NewGroup[i] = Group[temp];		
		}
		else
		{
			NewGroup[i] = Group[index];
		}
	}

	//将最好个体复制下来,不参与进化
    Group[Best_Index] = Group[Best_Index];
	for(i = 0; i < PopSize; i++)
	{
		if(i != Best_Index)
			Group[i] = NewGroup[i];
	}	

	delete []cfitness;
	delete []NewGroup;
}

void CrossoverOperator()//采用单点交叉方法产生新群体
{
	int i,j;
	int index;
	int point, temp;
	double p;
	char   ch;

	for(i=0; i<PopSize; i++)
	{	
		index=i;
	}
	for(i=0; i<PopSize; i++)
	{	
		point = (int)Random(0,PopSize-i);
		temp=index;
		index = point+i;
		index = temp;
	}

	for(i=0; i<PopSize-1; i+=2)
	{	
		p=rand()%1000/1000.0;
		if(p < m_fPc)
		{	
			point = (int)Random(0,CHROMLENGTH-1)+1;
			for(j = point; j<CHROMLENGTH; j++)
			{
			    if(Group[index].value<MAXNUM&&Group[index+1].value<MAXNUM)
				{
				  ch = (int)Group[index].chrom[j];
				  Group[index].chrom[j]=Group[index+1].chrom[j];
				  Group[index+1].chrom[j] = ch;
				}
			}
		}
	}
}



void MutationOperator()//随机产生变异位，进行染色体基因位的变异
{	
	int i,j;
	double p;

	for(i = 0; i < PopSize; i++)
	{
		if(i != Best_Index) //保证当前最优个体不参与进化
		{
			for(j = 0;j < CHROMLENGTH; j++)
			{
				p = rand()%1000/1000.0;
				if(p < m_fPm)
				{
				   if(Group[i].value<MAXNUM)
				   {
                      Group[i].chrom[j] = (Group[i].chrom[j]==0)?1:0;		
				   }	 	
				}
			}
		}
	}
}

void PerformEvolution()//用当前最好个体代替最差个体
{
	Group[Worst_Index] = BestIndividual;	
}

void OutPut()//输出计算结果
{
    cout<<"路径顶点:";
	for(int k=0;k<CHROMLENGTH;k++)
	{
		cout<<setw(3)<<k;
	}
	cout<<endl;
	cout<<"-------------------------------------------------------------------------------"<<endl;
	cout<<"路径顶点:";
    for(int j=0; j<CHROMLENGTH; j++)
	 {
	      
		cout<<setw(3)<<BestIndividual.chrom[j];
	 }    
	 cout<<endl;
     cout<<"最短路径:";
 
	 cout<<setw(3)<<BestIndividual.value;
	 cout<<endl;
}


void main(void)
{

   generation = 0;

   GenerateInitialPopulation();
   CalculateObjectValue();//计算优化函数值
   
   CalculateFitnessValue(); 
   FindBestAndWorstIndividual(); 
   while(generation < MaxGeneration)
   {
	   generation++;
	   SelectionOperator(); 
	   CrossoverOperator();
	   MutationOperator();

	   CalculateObjectValue();
	   CalculateFitnessValue();           
	   FindBestAndWorstIndividual();		 
	   PerformEvolution();
   
   }
   OutPut();

}