ex04.cpp

遗传算法

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

#include "stdafx.h"
#include "EX04.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>

#pragma   comment(lib,"ws2_32.lib")  

// 重要常量参数
#define popsize 200   //种群的规模
#define pc 0.618        //杂交概率
#define pm 0.03        //变异概率
#define lchrom 50      //染色体长度
#define maxgen 1000     //最大进化代数

struct population
{
 unsigned int chrom[lchrom];   //染色体
 double weight;                //背包重量
 double fitness;               //适应度
 unsigned int parent1,parent2,cross;  //双亲、交叉点
};

//新生代种群、父代种群
struct population oldpop[popsize],newpop[popsize]; 

//背包问题中物体重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain; 

//种群的总适应度、最小、最大、平均适应度 
double sumfitness,minfitness,maxfitness,avgfitness;

//计算适应度时使用的 惩罚函数系数
double alpha;

//一个种群中最大和最小适应度的个体
int    minpop,maxpop; 


/* 读入背包信息,并且计算惩罚函数系数 */
void read_infor()
{
	FILE *fp;
	int j;
    
	//获取背包问题信息文件
	if ((fp=fopen("knapsack.txt","r"))==NULL)
	{   
		//读取文件失败
		AfxMessageBox("The file is not found",MB_OK,NULL);
	    return;
	}
	//读入物体收益信息
    for (j=0;j<lchrom;j++)
    {
    	fscanf(fp,"%d",&profit[j]);
    }
	//读入物体重量信息
    for (j=0;j<lchrom;j++)
    {
    	fscanf(fp,"%d",&weight[j]);
    } 
	//读入背包容量
    fscanf(fp,"%d",&contain);
    fclose(fp);
	
}

//根据计算的个体重量,判断此个体是否该留在群体中
double cal_weight(unsigned int *chr)
{
  int j;
  double pop_weight;//背包重量

  pop_weight=0;
  for (j=0;j<lchrom;j++)
  {
	pop_weight=pop_weight+(*chr)*weight[j];
	chr++;
  }
  return pop_weight;
}


/* 种群中个体适应度计算*/
double cal_fit(unsigned int *chr)
{
  int j;
  double pop_profit;//适应度

  pop_profit=0;
//  pop_weight=0;

  for (j=0;j<lchrom;j++)
  {
	pop_profit=pop_profit+(*chr)*profit[j];
//	pop_weight=pop_weight+(*chr)*weight[j];
	chr++;
  }
  
  return pop_profit;
}

/* 群体适应度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
	int i;
	double tmp_fit;

	sumfitness=pop[0].fitness;
	minfitness=pop[0].fitness;
    minpop=0;
	maxfitness=pop[0].fitness;
	maxpop=0;
	
	for (i=1;i<popsize;i++)
	{
		//计算种群的总适应度
		sumfitness=sumfitness+pop[i].fitness;
        tmp_fit=pop[i].fitness;
		//选择种群中最大适应度的个体
		if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
		{
			maxfitness=pop[i].fitness;
			maxpop=i;
		}

        //选择种群中最小适应度的个体
		if (tmp_fit<minfitness)
		{
			minfitness=pop[i].fitness;
			minpop=i;
		}
		
		//计算平均适应度
		avgfitness=sumfitness/(float)popsize;
	}
//	 printf("\nthe max pop = %d;",maxpop);
//	 printf("\nthe min pop = %d;",minpop);
//   printf("\nthe sumfitness = %f\n",sumfitness);
}

//报告种群信息
void report(struct population *pop,int gen)
{
      int j;
	  int pop_weight=0;

	  printf("the generation is %d.\n",gen); //输出种群的代数    
	  //输出种群中最大适应度个体的染色体信息
	  printf("The population's chrom is:  \n");
	  for (j=0;j<lchrom;j++)
	  { 
		if (j%5==0) 
		{  printf(" ");}
		printf("%1d",pop[maxpop].chrom[j]);
	  }
	  //输出群体中最大适应度
      printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
      printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);

}

/* 生成初始种群 */
void initpop()
{
  int i,j,ispop;
  double tmpWeight;
  //变量用于判断是否为满足条件的个体
  ispop=false;

  //生成popsize个种群个体
  for(i=0;i<popsize;i++)
  {
     while (!ispop)
	 {
	   for(j=0;j<lchrom;j++)
	   {
		  oldpop[i].chrom[j]=rand()%2;   //随机生成个体的染色体
	      oldpop[i].parent1=0;  //双亲
	      oldpop[i].parent2=0;
	      oldpop[i].cross=0;    //交叉点
	   }

	   //选择重量小于背包容量的个体,即满足条件
       tmpWeight=cal_weight(oldpop[i].chrom);
	   if (tmpWeight<=contain)
	   {
		  oldpop[i].fitness=cal_fit(oldpop[i].chrom);
		  oldpop[i].weight=tmpWeight;
		  oldpop[i].parent1=0;
		  oldpop[i].parent2=0;
		  oldpop[i].cross=0;
		  ispop=true;
	   }
	 }
	 //此个体可以加入到种群中
	 ispop=false;
  }
}

/*  遗传操作   */

//概率选择试验
int execise(double probability)
{
	double pp;
    //如果生成随机数大于相应的概率则返回真，否则试验不成功
	pp=(double)(rand()%20001/20000.0);
	if (pp<=probability) return 1;
	return 0;
}

// 选择进行交叉操作的个体 
int selection(int pop)
{
  double wheel_pos,rand_Number,partsum;
  int parent;

  //赌轮法选择
  rand_Number=(rand()%2001)/2000.0;
  wheel_pos=rand_Number*sumfitness;  //赌轮大小

  partsum=0;
  parent=0;
  do{
	  partsum=partsum+oldpop[parent].fitness;
	  parent=parent+1;
	} while (partsum<wheel_pos && parent<popsize);
  return parent-1;

}

/*  交叉操作  */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
	int j,cross_pos;
	if (execise(pc))
	{
		//生成交叉位置0,1,...(lchrom-2)
		cross_pos=rand()%(lchrom-1);
	}
	else cross_pos=lchrom-1;
    
	for (j=0;j<=cross_pos;j++)
	{   //保留复制；
		//包括在概率选择不成功时，父体完全保留
		newpop[i].chrom[j]=parent1[j];
	}
	for(j=cross_pos+1;j<=(lchrom-1);j++)
	{
		//从交叉点开始交叉
		newpop[i].chrom[j]=parent2[j];
	}
    
	//记录交叉位置
	newpop[i].cross=cross_pos;
	return 1;
}

/*  变异操作 */
int mutation(unsigned int alleles)
{
   if (execise(pm))
   {
	   if (alleles)
		   alleles=0;
	   else alleles=1;
   }
   //返回变异值，或者返回原值
   return alleles;
}

/* 群体更新 */
void generation()
{
  unsigned int i,j,mate1,mate2;
  double tmpWeight;
  int ispop;//记录是否是符合条件的个体
  i=0;
  while (i<popsize)
  {
	ispop=false;
    while (!ispop)
	 {
    	//选择
    	mate1=selection(i);
    	mate2=selection(i+1);

        //交叉
        crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);

	    //变异
        for (j=0;j<lchrom;j++)
		{
  	     newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
		}

	    //选择重量小于背包容量的个体,即满足条件
        tmpWeight=cal_weight(newpop[i].chrom);
	    if (tmpWeight<=contain)
		{
		  newpop[i].fitness=cal_fit(newpop[i].chrom);
		  newpop[i].weight=tmpWeight;
		  newpop[i].parent1=mate1;
		  newpop[i].parent2=mate2;
		  ispop=true;
		}
	 }
	 //此个体可以加入到种群中
    i=i+1;
  }
}


void main(int argc, char* argv[])
{
	int gen,oldmaxpop,k;
	double oldmax;
      
    read_infor();//读入背包信息
	gen=0;
	srand( (unsigned)time( NULL ) );//置随机种子
	initpop();
	memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
	statistics(newpop);//统计新生种群的信息
	report(newpop,gen);
	while(gen<maxgen)
	{
	  gen=gen+1;
	  if (gen%100==0)
	  {
	   srand( (unsigned)time( NULL ) );//置随机种子
	  }
	  oldmax=maxfitness;
	  oldmaxpop=maxpop;
	  generation();
	  statistics(newpop); //统计新生代种群信息
	  //如果新生代种群中个体的最大适应度小于老一代种群
	  //个体的最大适应度，则保存老一代种群个体的最大适应度
	  //否则报告新生代的最大适应度
	  if (maxfitness<oldmax)
	  {
		  for(k=0;k<lchrom;k++)
			  newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
		  newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
		  newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
          newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
		  newpop[minpop].cross=oldpop[oldmaxpop].cross;
		  statistics(newpop);
	  }
	  else if (maxfitness>oldmax)
		   {
		      report(newpop,gen);
	  }

	  //保存新生代种群的信息到老一代种群信息空间
	  memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
    }

	printf("It is over.");
	getch();
}