scs.cpp

A Function Optimizer using Simple Genetic Algorithm developed from the Pascal SGA code

/****************************************************************************/
/*                 基本遗传学习分类系统  SCS.CPP                              */
/*        A  Simple Classifier System based on Genetic Learning             */
/*      developed from the Pascal SCS code presented by David E.Goldberg    */
/*             同济大学计算技术研究所   王小平          2000年7月           */
/****************************************************************************/

#include <stdlib.h> 
#include <fstream.h>
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <string.h>

const int wildcard=-1;                /*  通配符#   */
const long iterationsperblock=10000;
const int fmaxmating=10;
int rndcalcflag;
double rndx2;

struct classtype                     /* 分类器 */
{
  int *c;                            /*  condition */
  int a;                             /*  action */
  float strength,bid,ebid;           /* 权值, 投标，有效投标*/
  int matchflag;                     /* 匹配标志*/
  int specificity;                   /* 非#码长度 */
} ;
struct  classlist                    /* 匹配表 */
{
   int *clist;                       /* 当前与环境消息匹配的分类器表 */
   int nactive;                      /* 当前匹配数目 */
} ;
struct poptype                       /* 分类器表数据 */
{
    struct classtype *classifier;    /*  分类器表  */
    int nclassifier,nposition;       /*  分类器数目, 条件码长 */
    float pgeneral,cbid,bidsigma,bidtax,lifetax,bid1,bid2,ebid1,ebid2;  
    float sumstrength,fmaxstrength,avgstrength,fminstrength;
};
struct trecord                  /* 时间参数 */
{
   int initialiteration,initialblock,iteration,block,reportperiod;
   int gaperiod,consolereportperiod,plotreportperiod,nextplotreport;
   int nextconsolereport,nextreport,nextga;
   int reportflag,gaflag,consolereportflag,plotreportflag;
};
struct erecord                 /* 环境参数 */
{
   int laddress,ldata,lsignal,address,output,classifieroutput;
   int *signal;
};
struct crecord                /* 交易所参数 */
{
   int winner,oldwinner;
   int bucketbrigadeflag;
};
struct rrecord               /* 增强参数（得分兑现）  */
{
float reward,rewardcount,totalcount,count50,rewardcount50;
float proportionreward,proportionreward50;
int lastwinner;
};
struct mrecord               /*  交配参数  */
{
 int mate1,mate2,mort1,mort2,sitecross;
};
struct grecord              /* 遗传算法参数 */
{
float populationselect,pmutation,pcrossover;
long ncrossover,nmutation;
int crowdingfactor,crowdingsubpop,nselect;
struct mrecord *mating;
};

/* 全局变量 */
int *envmessage;                    /* 消息    */
struct poptype population;          /* 分类器表数据 */  
struct classlist matchlist;         /* 匹配表  */
struct trecord timekeeprec;         /* 时间参数  */
struct erecord environrec;          /* 环境参数 */  
struct crecord clearingrec;         /* 交易所参数  */ 
struct rrecord reinforcementrec;    /* 增强参数  */
struct grecord garec;               /* 遗传算法参数 */

struct poptype *pop=&population;
struct classlist *matchl=&matchlist;

ofstream rep("c:\\ga\\rep.txt");                        /* 结果报告文件 */
ofstream pfile("c:\\ga\\pfile.txt");                    /* 绘图数据文件 */  
ifstream tfile("c:\\ga\\tfile.txt",ios::nocreate);      /* 时间参数文件 */
ifstream efile("c:\\ga\\efile.txt",ios::nocreate);      /* 环境参数文件 */
ifstream cfile("c:\\ga\\cfile.txt",ios::nocreate);      /* 分类器参数文件 */
ifstream rfile("c:\\ga\\rfile.txt",ios::nocreate);      /* 增强参数文件 */
ifstream gfile("c:\\ga\\gfile.txt",ios::nocreate);      /* 遗传算法参数文件 */

void initrepheader();
void interactiveheader();
void initialization();  
void detectors(struct erecord *environrec,int *envmessage);  
void reportdetectors(int *envmessage,int nposition); 
void report();
void consolereport(struct rrecord *reinforcementrec);
void plotreport(struct rrecord *reinforcementrec);
int  addtime(int t,int dt,int &carryflag);
void inittimekeeper(struct trecord *timekeeprec);
void initreptimekeeper(struct trecord *timekeeprec);
void timekeeper(struct trecord *timekeeprec);
void reporttime(struct trecord *timekeeprec);
void generatesignal(struct erecord *environrec);
int  decode(int *mess,int start,int length);
void multiplexeroutput(struct erecord *environrec);
void environment(struct erecord *environrec);
void initenvironment(struct erecord *environrec);
void initrepenvironment(struct erecord *environrec);
void writesignal(int *signal,int lsignal);
void reportenvironment(struct erecord *environrec);
int  randomchar(double pgeneral);
void readcondition(int *c,float pgeneral,int nposition);
void readclassifier(struct classtype *Class,float pgeneral,int nposition);
int  counterspecificity(int *c, int nposition);
void initclassifiers(struct poptype *population);
void initrepclassifiers(struct poptype *population);
void writecondition(int c[],int nposition);
void writeclassifier(struct classtype *Class,int number,int nposition);
void reportclassifiers(struct poptype *population);
int  match(int *c,int *m, int nposition);
void matchclassifiers(struct poptype *population,int *emess,struct classlist *matchlist);
void  initaoc(struct crecord *clearingrec);
void initrepaoc(struct crecord *clearingrec);
int  auction(struct poptype *population,struct classlist *matchlist,int oldwinner);
void clearinghouse(struct poptype *population,struct crecord *clearingrec);
void taxcollector(struct poptype *population);
void reportaoc(struct crecord *clearingrec);
void aoc(struct poptype *population,struct classlist *matchlist,struct crecord *clearingrec);
void initreinforcement(struct rrecord *reinforcementrec);
void initrepreinforcement(struct rrecord *reinforcementrec);
int  criterion(struct rrecord *rrec,struct erecord *environrec);
void payreward(struct poptype *population,struct rrecord *rrec,struct crecord *clearingrec);
void reportreinforcement(struct rrecord *reinforcementrec);
void reinforcement(struct rrecord *reinforcementrec,struct poptype *population,
             struct crecord *clearingrec,struct erecord *environrec);
void advance(struct crecord *clearingrec);
void initga(struct grecord *garec,struct poptype *population);
void initrepga(struct grecord *garec);
int  select(struct poptype *population);
int  mutation(int positionvalue,float pmutation,long &nmutation );
int  bmutation(int positionvalue,float pmutation,long &nmutation );
void crossover(struct classtype *parent1,struct classtype *parent2,struct classtype *child1,struct classtype *child2,
       float pcrossover,float pmutation,int &sitecross,int nposition,long &ncrossover,long &nmutation);
int  worstofn(struct poptype *population, int n);
int  matchcount(struct classtype *classifier1,struct classtype *classifier2,int nposition);
int  crowding(struct classtype *child,struct poptype *population,int &crowdingfactor,int crowdingsubpop);
void statistics(struct poptype *population);
void ga(struct grecord *garec,struct poptype *population);
void reportga(struct grecord *garec,struct poptype *population );
float  rndreal(float lo ,float hi);
void initrandomnormaldeviate(); 
double randomnormaldeviate();
float  noise(float mu ,float sigma); 
void skip(int skipcount);
int  flip(float prob); 
int  rnd(int low,int high);
float fmax(float x,float y);
float fmin(float x,float y);
float avg(float x,float y);
int  halt();
void initmalloc(); 
void freeall();   


void initrepheader()
{
  rep<<"---------------------------------------------------------"<<endl;
  rep<<"                  基本遗传学习分类系统                   "<<endl;
  rep<<" A  Simple Classifier System based on Genetic Learning   "<<endl;
  rep<<"---------------------------------------------------------"<<endl;
 
}
void interactiveheader()
{
  cout<<"---------------------------------------------------------"<<endl;
  cout<<"                  基本遗传学习分类系统                   "<<endl;
  cout<<" A  Simple Classifier System based on Genetic Learning   "<<endl;
  cout<<"---------------------------------------------------------"<<endl;
 
}

void initialization()      /* 分类系统初始化  */
{
interactiveheader();
initrandomnormaldeviate();
initmalloc();
initrepheader();
initclassifiers(pop);
initrepclassifiers(pop);
initenvironment(&environrec);
initrepenvironment(&environrec);
initaoc(&clearingrec);
initrepaoc(&clearingrec);
initreinforcement(&reinforcementrec);
initrepreinforcement(&reinforcementrec);
inittimekeeper(&timekeeprec);
initreptimekeeper(&timekeeprec);
initga(&garec,pop);
initrepga(&garec);
}

void detectors(struct erecord *environrec,int *envmessage)    /* 检测器  */
{
int j;
for(j=0;j<=environrec->lsignal-1; j++)
 envmessage[j]=environrec->signal[j];
}

void writemessage(int *mess,int lmessage)
{
 int j;
 j=lmessage-1;
   while(j>=0)  {
          rep<<mess[j];
         j--;
   }
}

void reportdetectors(int *envmessage,int nposition)        /* 输出环境消息 */
{
 skip(1);
 rep<<" 环境消息:     ";
 writemessage(envmessage,nposition);
 skip(1);
}

void  reportheader()
{
 skip(1);
 rep<<"    详细报告 "<<endl;
 rep<<"----------------"<<endl;
 
}

void report()
{
 reportheader();
 reporttime(&timekeeprec);
 reportenvironment(&environrec);
 reportdetectors(envmessage,pop->nposition);
 reportclassifiers(pop);
 reportaoc(&clearingrec);
 reportreinforcement(&reinforcementrec);
}

void consolereport(struct rrecord *reinforcementrec)
{
  cout<<"----------------------------"<<endl;
  cout<<"      次数="<<reinforcementrec->totalcount<<endl;
  cout<<"      P  ="<<reinforcementrec->proportionreward<<endl;
  cout<<"      P50 ="<<reinforcementrec->proportionreward50<<endl;
  cout<<"----------------------------"<<endl;
}

void plotreport(struct rrecord *reinforcementrec)
{
  pfile<<setw(12)<<reinforcementrec->totalcount<<setw(12)<<reinforcementrec->proportionreward<<
                  setw(10)<<reinforcementrec->proportionreward50<<endl;
}

int addtime(int t,int dt,int &carryflag)
{
 int tempadd;
 tempadd=t+dt;
 carryflag=(tempadd>=iterationsperblock);
 if(carryflag)
    tempadd=(int)fmod((double)tempadd,(double)iterationsperblock);
 return(tempadd);
}

void inittimekeeper(struct trecord *timekeeprec)
{
 int dummyflag;
  timekeeprec->iteration=0;timekeeprec->block=0;
  tfile>>timekeeprec->initialiteration;
  tfile>>timekeeprec->initialblock;
  tfile>>timekeeprec->reportperiod;
  tfile>>timekeeprec->consolereportperiod;
  tfile>>timekeeprec->plotreportperiod;
  tfile>>timekeeprec->gaperiod;
  timekeeprec->iteration=timekeeprec->initialiteration;
  timekeeprec->block=timekeeprec->initialblock;
  timekeeprec->nextga=addtime(timekeeprec->iteration,timekeeprec->gaperiod,dummyflag);
  timekeeprec->nextreport=addtime(timekeeprec->iteration,timekeeprec->reportperiod,dummyflag);
  timekeeprec->nextconsolereport=addtime(timekeeprec->iteration,timekeeprec->consolereportperiod,dummyflag);
  timekeeprec->nextplotreport=addtime(timekeeprec->iteration,timekeeprec->plotreportperiod,dummyflag);
}

void initreptimekeeper(struct trecord *timekeeprec)
{
 skip(1);
 rep<<"       时间参数:    "<<endl;
 rep<<"------------------------------"<<endl;
 rep<<" 初始次数         = "<<timekeeprec->initialiteration<<endl;
 rep<<" 初始时间块       = "<<timekeeprec->initialblock<<endl;
 rep<<" 结果数据输出周期 = "<<timekeeprec->reportperiod<<endl;
 rep<<" 数据屏幕显示周期 = "<<timekeeprec->consolereportperiod<<endl;
 rep<<" 绘图数据输出周期 = "<<timekeeprec->plotreportperiod<<endl;
 rep<<" 遗传算法执行周期 = "<<timekeeprec->gaperiod<<endl;
}

void timekeeper(struct trecord *timekeeprec)
{
  int carryflag,dummyflag;
  timekeeprec->iteration=addtime(timekeeprec->iteration,1,carryflag);
  if(timekeeprec->iteration>=iterationsperblock) timekeeprec->block=timekeeprec->block+1;
  timekeeprec->reportflag=(timekeeprec->nextreport==timekeeprec->iteration);
  if(timekeeprec->reportflag)
  timekeeprec->nextreport=addtime(timekeeprec->iteration,timekeeprec->reportperiod,carryflag);
  timekeeprec->consolereportflag=(timekeeprec->nextconsolereport==timekeeprec->iteration);
  if(timekeeprec->consolereportflag)
  timekeeprec->nextconsolereport=addtime(timekeeprec->iteration,timekeeprec->consolereportperiod,dummyflag);
  timekeeprec->plotreportflag=(timekeeprec->nextplotreport==timekeeprec->iteration);
  if(timekeeprec->plotreportflag)
  timekeeprec->nextplotreport=addtime(timekeeprec->iteration,timekeeprec->plotreportperiod, dummyflag);
  timekeeprec->gaflag=(timekeeprec->nextga==timekeeprec->iteration);
  if(timekeeprec->gaflag)
  timekeeprec->nextga=addtime(timekeeprec->iteration,timekeeprec->gaperiod,dummyflag);
 }

void reporttime(struct trecord *timekeeprec)
{
 rep<<" [块:次数] = ["<< timekeeprec->block<<":"<<timekeeprec->iteration<<"]"<<endl;
}

void generatesignal(struct erecord *environrec)
{
int j;
for(j=0;j<=environrec->lsignal-1; j++)
 {
   if(flip(0.5))
      environrec->signal[j]=1;
   else
      environrec->signal[j]=0;
 }
}

int decode(int *mess,int start,int length)
{
int j,accum,powerof2;
accum=0;powerof2=1;
for(j=start;j<=start+length-1; j++)
 {
  accum=accum+powerof2*mess[j];
  powerof2=powerof2*2;
 }
return(accum);
}

void multiplexeroutput(struct erecord *environrec)
{

 environrec->address=decode(environrec->signal,0,environrec->laddress);
 environrec->output=environrec->signal[environrec->laddress+environrec->address];
}

void environment(struct erecord *environrec)
{
generatesignal(environrec);
multiplexeroutput(environrec);
}

void initenvironment(struct erecord *environrec)
{
int j;
efile>>environrec->laddress;
environrec->ldata=(int)ceil(pow(2.0,(double)environrec->laddress));
environrec->lsignal=environrec->laddress+environrec->ldata;
environrec->address=0;
environrec->output=0;
environrec->classifieroutput=0;
for(j=0;j<=environrec->lsignal-1; j++)
  environrec->signal[j]=1;
}

void initrepenvironment(struct erecord *environrec)
{
 skip(1);
 rep<<"  环境参数(多路复用器):    "<<endl;
 rep<<"------------------------------"<<endl;
 rep<<" 地址行数 = "<< environrec->laddress<<endl;
 rep<<" 数据行数 = "<< environrec->ldata<<endl;
 rep<<" 总行数   = "<< environrec->lsignal<<endl;
}

void writesignal(int *signal,int lsignal)
{
 int j;
 j=lsignal-1;
   while(j>=0)  {
          rep<<signal[j];
         j--;
   }
}

void reportenvironment(struct erecord *environrec)
{
 skip(1);
 rep<<"        当前多路复用器状态:    "<<endl;
 rep<<"-----------------------------------"<<endl;
 rep<<" 信号:  ";
 writesignal(environrec->signal,environrec->lsignal);  skip(1);
 rep<<" 解码地址       = "<<environrec->address<<endl;