ga-1.cpp

清华大学不确定规划教材中的用遗传算法训练神经元网络的混合智能算法1

// 装箱问题遗传算法
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static void  initialization(void);
static void  evaluation(int gen);
static void  selection(void);
static void  crossover(void);
static void  mutation(void);
static void  objective_function(void);
static int   constraint_check(int x[]);

#define M 10  // 需要进行装箱的物品个数
#define N 10  // 箱子个数
#define W 5  // 物品平均重量
  
#define G_MAX 400 // 最大种群代数
#define POP_SIZE 10 //种群大小
#define P_MUTATION 0.2 //变异概率
#define P_CROSSOVER 0.2 //交叉概率

int  CHROMOSOME[POP_SIZE+1][M+1]; //染色体数组，即整个种群
int  OBJECTIVE[POP_SIZE+1]; //目标函数数组，存放每个染色体的函数值
int x[N+1][M+1] = {0}; //表示第j个物品是否放入第i个箱子
int y[N+1] = {0}; //表示第i个箱子是否空着
double w[N+1];//物品重量数组
double c[N+1];//箱子重量限制




//初始化
static void initialization(void)
{
  printf("\n Initializing");
  int CH[M+1];
  int p,i,j;
  for(p=1; p<=POP_SIZE; p++){
	  mark:
	  for(j=1; j<=M; j++) {
	  CH[j]=(int)floor(myu(1,N)); //取1到N内的整数
      w[j]=myn(W,2);//初始化物品重量，取期望为物品均值W，标准差为1.2的正态分布
	  }
	  if(constraint_check(CH)==0) goto mark;
	  for(j=1; j<=M; j++) CHROMOSOME[p][j]=CH[j];

  }
  for(i=1;i<=N;i++)
	  c[i]=myn(W*M/N,2);//初始化物品重量，取期望为物品均值W，标准差为1.2的正态分布
	
}

//产生均匀分布随机数
double myu(double a, double b)
{
  srand((int)time(0)); 
  double y;
  if(a>b) {
	printf("\nThe first parameter should be less than the second!");
	exit(1);
  }
  y = (double)rand()/(RAND_MAX);
  return (a+(b-a)*y); 
}

//产生整台分布随机数
double myn(double mu, double sigma2)
{
  double mu1, mu2, z;
  do {
    mu1 = myu(0,1);
    mu2 = myu(0,1);
  } while (mu1<=0||mu1>=1);
  z = sqrt(-2*log(mu1))*sin(2*3.14159*mu2);
  return (mu+sqrt(sigma2)*z);
}

//目标函数计算
static void objective_function(void)
{
	int i,j;

	for(i = 1; i <= POP_SIZE; i++) {
		for(j=1;j<=M;j++){
			if(CHROMOSOME[i][j]<=N) y[CHROMOSOME[i][j]]=1; //如果有物品放入，置1
		}

		for(j=1;j<=N;j++){
			OBJECTIVE[i] += y[j]; //计算目标函数，总共使用的箱子数量
		}
	}
}

//约束条件检验
static int constraint_check(int CH[])
{
	
	int i,j; 
	for(j=1;j<=M;j++){
		if(CH[j]<0 || CH[j]>N) return 0;
		x[CH[j]][j]=1;
	}
	for(i=1;i<=N;i++){
		double sum_weight;
		for(j=1;j<=M;j++){
			sum_weight+=x[i][j]*c[j];
		}
		if(sum_weight>c[i]) return 0;
	}
	return 1;
}



main()
{
  int g, i;

  initialization();
  evaluation(0);
  for(g=1; g<=G_MAX; g++) {
	  selection();
	  crossover();
	  mutation();
	  evaluation(g);
	  printf("\nGeneration NO.%d\n", g);
	  printf("x=(");
	  for(i=1; i<=N; i++) {
		  if(i<N) printf("%d,",CHROMOSOME[0][i]);
		  else printf("%d",CHROMOSOME[0][i]);
	  }
	  printf(")\nf=%d\n", OBJECTIVE[0]);
  }
  printf("\n");
  return 1;
}

static void evaluation(int gen)
{
  double a;
  int   i, j, k, label;
  objective_function();
  if(gen==0){
	 for(j = 1; j <= N; j++) CHROMOSOME[0][j]=CHROMOSOME[1][j];
  }
  for(i=0; i<POP_SIZE; i++){
	  label=0;  a=OBJECTIVE[i][0];
	  for(j=i+1; j<=POP_SIZE; j++)
		 if((TYPE*a)<(TYPE*OBJECTIVE[j][0])) {
			 a=OBJECTIVE[j][0];
			 label=j;
		 }
	  if(label!=0) {
		 for(k=0; k<=M; k++) {
			 a=OBJECTIVE[i][k];
			 OBJECTIVE[i][k]=OBJECTIVE[label][k];
			 OBJECTIVE[label][k]=a;
		 }
		 for(j=1; j<=N; j++) {
			 a=CHROMOSOME[i][j];
			 CHROMOSOME[i][j]=CHROMOSOME[label][j];
			 CHROMOSOME[label][j]=a;
		 }
	  }
  }
}

static void selection()
{
  double r, temp[POP_SIZE+1][N+1];
  int   i, j, k;
  for(i=1; i<=POP_SIZE; i++) {
	  r=myu(0, q[POP_SIZE]);
	  for(j=0; j<=POP_SIZE; j++) {
		  if(r<=q[j]) {
			  for(k=1; k<=N; k++) temp[i][k]=CHROMOSOME[j][k];
			  break;
		  }
	  }
  }
  for(i=1; i<=POP_SIZE; i++)
	 for(k=1; k<=N; k++)
		 CHROMOSOME[i][k]=temp[i][k];
}

static void crossover()
{
  int   i, j, jj, k, pop;
  double r, x[N+1], y[N+1];
  pop=POP_SIZE/2;
  for(i=1; i<=pop; i++) {
	 if(myu(0,1)>P_CROSSOVER) continue;
	 j=(int)myu(1,POP_SIZE);
	 jj=(int)myu(1,POP_SIZE);
	 r=myu(0,1);
	 for(k=1; k<=N; k++) {
		 x[k]=r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k];
		 y[k]=r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k];
	 }
	 if(constraint_check(x)==1)
		 for(k=1; k<=N; k++) CHROMOSOME[j][k]=x[k];
	 if(constraint_check(y)==1)
		 for(k=1; k<=N; k++) CHROMOSOME[jj][k]=y[k];
  }
}

static void mutation(void)
{
  int i, j, k;
  double x[N+1], y[N+1], infty, direction[N+1];
  double INFTY=10, precision=0.0001;
  for(i=1; i<=POP_SIZE; i++) {
	  if(myu(0,1)>P_MUTATION) continue;
	  for(k=1; k<=N; k++) x[k] = CHROMOSOME[i][k];
	  for(k=1; k<=N; k++)
		  if(myu(0,1)<0.5) direction[k]=myu(-1,1);
		  else direction[k]=0;
	  infty=myu(0,INFTY);
	  while(infty>precision) {
		  for(j=1; j<=N; j++) y[j]=x[j]+infty*direction[j];
		  if(constraint_check(y)==1) {
			 for(k=1; k<=N; k++) CHROMOSOME[i][k]=y[k];
			 break;
		  }
		  infty=myu(0,infty);
	  }
  }
}