yichuan.cpp

本遗传算法是保留大量状态种群的随机爬山搜索算法

// YiChuan.cpp: implementation of the CYiChuan class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "yichuansuanfa.h"
#include "YiChuan.h"
#include "stdlib.h"
#include <stdio.h>
#include <time.h>
#include "math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////



CYiChuan::~CYiChuan()
{
 delete []population;
 delete []parater;
}

 
extern int num;
//srand( (unsigned)time( NULL ) );
  
void CYiChuan::InisialPopulation()
{
  population=new individual[Popsize];
   for(int i=0;i<Popsize;i++)
	{
	  for(int j=0;j<chromlength;j++)
	  {
		 //srand( (unsigned)time( NULL ) );
         //double b=(double)(rand()%10)/10;
         double b=shuijihanshu();
		// double b=rand()/(double)RAND_MAX;
		//  float b=rand()%10/10.0;
		 if((b*10)<=5)
		 population[i].chrom[j]='0';
		else
          population[i].chrom[j]='1';	
		}
	}
}
	
    
double CYiChuan::JieMa(char*chrom,int point,int length)
{
 double sum=0;
 int j=length-1;

 for(int i=point;i<point+length;i++)
 {
	 CString str=chrom[i];
    //CString str='0';
    sum=sum+atoi(str)*pow(2,j);
   j--;
 }
 return sum;
}

void CYiChuan::JinHuaComputer()
{
	MuBiaoComputer();
    ShiYingComputer();
    ZhuiIdividual();
}

void CYiChuan::MuBiaoComputer()
{
    
 double*x=new double[num];
	
 for(int i=0;i<Popsize;i++)
 {
    int point=0;
	int length=lengthi[0];
	for(int k=0;k<num;k++)
	{   
	 int temp=JieMa(population[i].chrom,point,length);
     x[k]=leftlimit[k]+temp*(rightlimit[k]-leftlimit[k])/(pow(2,lengthi[k])-1);
    
	point=point+length;
	length=lengthi[k+1];
	}
    m_formular.SetFormula(string.GetBuffer(string.GetLength()));
    population[i].value=m_formular.computer(x,num);
 }
 delete []x;
}


void CYiChuan::ShiYingComputer()
{
  double temp=0.0;
  for(int i=0;i<Popsize;i++)
  {
    if(population[i].value<Cmax)
	  temp=Cmax-population[i].value;
    else
	{
	 temp=0.0;
	}
  population[i].fitness=temp;
  }

}


void CYiChuan::ZhuiIdividual()
{
   bestindividual=population[0];
  individual worstindividual=population[0];
  for(int i=0;i<Popsize;i++)
  {
	if(bestindividual.fitness<population[i].fitness)
	{
		bestindividual=population[i];
     BestIndex=i;
	}
    if(worstindividual.fitness>population[i].fitness)
	{
		worstindividual=population[i];
     WorstIndex=i;
	}
  }
  if(generation==0)
	  Currentbest = bestindividual;
  if(bestindividual.fitness >Currentbest.fitness) 
	 Currentbest = bestindividual;
  if(worstindividual.fitness <Currentworst.fitness) 
	 Currentworst = worstindividual;
}


void CYiChuan::NextPopulation()
{
  SelectionOperator();
  CrossoverOperator();
  MutationOperation();

}
void CYiChuan::SelectionOperator()
{
 double Sum=0.0;
 double*cfitness=new double[Popsize];
 double p=0.0;
 individual*newpopulation=new individual[Popsize];
 for(int i=0;i<Popsize;i++)
 {
    Sum = Sum + population[i].fitness;
 }
 for( i=0;i<Popsize;i++)
 {
    cfitness[i] = population[i].fitness / Sum;
 }
 for( i=1;i<Popsize;i++)
 {
   cfitness[i] = cfitness[i - 1] + cfitness[i];

 }
 int Index=0;
 for(i=0;i<Popsize;i++)
 {
	int n=0;
   // srand( (unsigned)time( NULL ) );
    // p=(double)(rand()%10)/10;
	p=shuijihanshu();
	//p=rand()/(double)RAND_MAX;
	while( p > cfitness[Index])
	{
	    Index++;
	     if (Index>=Popsize)
		 {	
	       Index=0;
	      // p=srand( (unsigned)time( NULL ) );
           p=shuijihanshu();
		   //p=rand()/(double)RAND_MAX;
           n++;
		}
		 if(n>1000)
		 {
		  AfxMessageBox("Can't find the best indivialar");
		  exit(1);
		 }
	}
  newpopulation[i] = population[Index];
 }
 for(i=0;i<Popsize;i++)
 {
  population[i]=newpopulation[i];
 }
 delete[]newpopulation;
 delete[]cfitness;

}

     


void CYiChuan::CrossoverOperator()
{

  int *Index=new int[Popsize];
  for(int i=0;i<Popsize;i++)
  {
    Index[i]=i;
  }
  for(int j=0;j<Popsize;j++)
  {
    //srand( (unsigned)time( NULL ) );
    //double q=(double)(rand()%10)/10;
	//double q=shuijihanshu();
	int point=(int)shuijihanshu()*(Popsize-j);
	int temp=Index[j];
	Index[j]=Index[point+j];
	Index[point+j]=temp;
  }

  for( i=0;i<Popsize;i+=2)
  {
    //srand( (unsigned)time( NULL ) );
    //double p=(double)(rand()%10)/10;
	  double p=shuijihanshu();
	  //double p=rand()/(double)RAND_MAX;
	  if(p<pc)
	  {
		  //double p1=(double)(rand()%10)/10;
		int point1=(int)shuijihanshu()*chromlength;
		for(int j=point1;j<chromlength;j++)
		{
			char ch=population[Index[i]].chrom[j];
			population[Index[i]].chrom[j]=population[Index[i+1]].chrom[j];
			population[Index[i+1]].chrom[j]=ch;
		}
	  }
  }
  delete[]Index;
}

double CYiChuan::shuijihanshu()
{
  //srand( (unsigned)time( NULL ) );
  double shuijizhi=rand()%10/10.0;
  return shuijizhi;
}
  


void CYiChuan::MutationOperation()    	
{
	for(int i=0;i<Popsize;i++)
	{
		for(int j=0;j<chromlength;j++)
		{
          //srand( (unsigned)time( NULL ) );
          //double p=(double)(rand()%10)/10;
			double p=shuijihanshu();
			//double p=rand()/(double)RAND_MAX;
             if(p<pm)
			 {
			  if(population[i].chrom[j]='1')
				  population[i].chrom[j]='0';
			  else
				  population[i].chrom[j]='1';
			 }
		}
	}

}
	
void CYiChuan::ZhiXingOperation()
{
	if(bestindividual.fitness >Currentbest.fitness )
		 Currentbest=population[BestIndex];
    else
         population[WorstIndex]=Currentbest;

}
void CYiChuan::ShowResult()
{
 double sum=0.0;
 for(int i=0;i<Popsize;i++)
 {
   sum=sum+population[i].value;
 }
 average=sum/Popsize;
 
   parater=new double[num];
   int point=0;
   int length=lengthi[0];
   for(int k=0;k<num;k++)
	{   
	 int temp=JieMa(Currentbest.chrom,point,length);
     parater[k]=leftlimit[k]+temp*(rightlimit[k]-leftlimit[k])/(pow(2,lengthi[k])-1);
    
	point=point+length;
	length=lengthi[k+1];
	}
}