cls.cpp

机器学习中一个重要的方法——概念学习系统。

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <conio.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>
#include <dos.h>
#include "scs2.h"
int        maxrule;
int        chromnum;
float      pcross = 0.6,pmutation = 0.033,sumfitness;
float      avg,max,min;
Chromosome *chrom,*newchrom;
FILE	   *fp,*fpd;
int		   gen = 0,maxgen;
const int rulelen = 17;
const int attrnum = 4;
const int attrlen[attrnum] = {4,4,4,4};

void checkvalid(Chromosome * checkchrom,int index);

int main(int argc,char *argv[])
{
	char filename[12];
	srand(time(NULL));
	if (argc == 2)
	{strcpy(filename,argv[1]);
	 do{
		cout<<"Input number of chroms(1.."<<MAXCHROM<<"):";
		cin>>chromnum;
		}while(chromnum>MAXCHROM);
	}
	else if (argc == 3)
	{strcpy(filename,argv[1]);
	 chromnum = atoi(argv[2]);
	}
	else
	{
		cout<<"Input a string like nDmC,such as 1d1c"<<endl;
		cout<<"n & m is a integer between 1 and 4"<<endl;
		cin>>filename;
		do{
			cout<<"Input number of chroms(1.."<<MAXCHROM<<"):";
			cin>>chromnum;
		}while(chromnum>MAXCHROM);
	}
	assert(strlen(filename) == 4);
	if (!isdigit(filename[0])||!isdigit(filename[2])||
		(filename[1] != 'd' && filename[1] != 'D')||
		(filename[3] != 'c' && filename[3] != 'C'))
		{
		cout<<"Usage:prein[ndmc][chromnum]"<<endl;
		cout<<"such as:prein 1D1C 10"<<endl;
		cout<<"n&m is a integer between 1 and 4"<<endl;
		return 1;
		}
	if(!(fp = fopen(filename,"rt")))
		{
		 cout<<"file"<<filename<<"doesn't exists"<<endl;
		return 1;
		}
	strcat(filename,".DAT");
//	strcat(filename,".txt");
	if (!(fpd = fopen(filename,"wt")))
	{
		 cout<<"file"<<filename<<"append error"<<endl;
		 return 1;
	}
	cout.setf(ios::left,ios::adjustfield);
	cout<<"input maximum generation"<<endl;
	cin>>maxgen;
	assert(maxgen>0);
	initdata();
	objfunc(chrom);
	statistics(chrom);
	while(gen < maxgen)
	{
		gen++;
		report();
		generation();
		objfunc(newchrom);
		replace();
		objfunc(chrom);
		statistics(chrom);
	}
	report();
	fprintf(fpd,"\n");
	delete[]chrom;
	delete[]newchrom;
	fclose(fp);
	fclose(fpd);
	return 0;
}


/*初始化群体*/
void initdata(void)
{
	int i,j,len;
	maxrule = MAXLEN / rulelen;//maxrule number in a chromosome
	chrom = new Chromosome[chromnum];
	newchrom = new Chromosome[chromnum];
	if (!chrom || !newchrom)
	{
	cout<<"no enough memory to run this program"<<endl;
	fclose(fp);
	fclose(fpd);
	exit(1);
	}
	for(i=0;i<chromnum;i++)
	{
		chrom[i].Rulenum = rand()%maxrule + 1;//at least 1 rule
		chrom[i].Parent1 = chrom[i].Parent2 = 0;
		len = chrom[i].Rulenum * rulelen;
		for(j=0;j<len;j++)chrom[i].String[j] = (Allele)(rand()%2);
		checkvalid(chrom,i);//check valid of string,prevent all zero attribute
	}
}

/*检查染色体的有效性*/
void checkvalid(Chromosome * checkchrom,int index)
{
	Boolean flag;
	int curbit = 0,changebit;
	int i,j,k;
	for(i=0;i<checkchrom[index].Rulenum;i++)
	{
		for(j=0;j<attrnum;j++)
		{
			flag = T;
			for(k=0;k<attrlen[j];k++)
				if (checkchrom[index].String[curbit+k] == T)
				{
					flag = F;
					break;
				}
				if (flag == T)
				{
					changebit = curbit + rand()%attrlen[j];
					checkchrom[index].String[changebit] = T;
				}
				curbit +=  attrlen[j];
		}
		curbit ++;
	}
}

/*从染色体中抽取实例*/
void extractstr(char *str,int curbit,int length,int index)
{
	int i;
	for(i=0;i<length;i++)
	{
		if (chrom[index].String[curbit+i] == F)
			*str = '0';
		else
			*str = '1';
			str ++;
	}
	*str = '\0';
}

/*显示染色体及其适应度*/
void report(void)
{
	int i,j,k;
	int curbit;
	char str[20];
	cout<<endl;
	for(i=0;i<chromnum;i++)
	{
		curbit = 0;
		for(j=0;j<chrom[i].Rulenum;j++)
		{
			for(k=0;k<attrnum;k++)
			cout<<"F"<<setw(attrlen[k])<<k+1;
			cout<<"class";
		}
		cout<<"fitness"<<endl;	
		for(j=0;j<chrom[i].Rulenum;j++)
		{
			for(k=0;k<attrnum;k++)
			{
				extractstr(str,curbit,attrlen[k],i);
				curbit += attrlen[k];
				cout<<setw(attrlen[k]+1)<<str;
			}
			extractstr(str,curbit,1,i);
			curbit ++;
			cout<<""<<setw(6)<<str;
		}
		cout<<""<<chrom[i].Fitness;
		cout<<endl<<endl;
	}
	 cout<<"max = "<<max<<endl;
	 cout<<"avg = "<<avg<<endl;
	 cout<<"min = "<<min<<endl;
	 cout<<endl<<endl;
}

/*统计群体的最大、最小、平均适应度*/
void statistics(Chromosome *pop)
{
	int j,maxfindex = 0;
	min = max = sumfitness = pop[0].Fitness;
	for(j=1;j<chromnum;j++)//Loop for max,min,sumfitness
	{sumfitness += pop[j].Fitness;
		if (pop[j].Fitness>max)
		{max = pop[j].Fitness;
		 maxfindex = j;
		}
		if (pop[j].Fitness<min)min = pop[j].Fitness;
	}
	avg = sumfitness/chromnum;
	fprintf(fpd,"%f\n",chrom[maxfindex].Fitness);
}

/*生成随机数0，1*/
inline float random01(void)
{
	return rnd(0,1);
}

/*生成范围在low与high之间的一个随机数*/
float rnd(int low,int high)
{
	int i;
	float j;
	i=rand();
	j=low+(high - low)* float(i)/float(RAND_MAX);
	return j;
}

Boolean flip(float val)
{
	float j=rnd(0,1);
	if (j<=val) return T;
	else return F;
}

/*生成下一代群体*/
void generation(void)
{
	//Creat a new generation through; select, crossover,and mutation
	int j,mate1,mate2;
	int even_number =(chromnum%2)?(chromnum-1):chromnum;
	//If chrom number is a odd number,then the last don't crossover
	j = 0;
	while (j<even_number)
	{mate1=select();//Pick pair of mates
	 mate2=select();
	 crossover(mate1,mate2,j);
	 j += 2;
	}
	if (even_number != chromnum)
	{
		for(mate1=0;mate1 < chrom[j].Rulenum * rulelen;mate1++)
		newchrom[j].String[mate1]=mutation(chrom[j].String[mate1]);
		newchrom[j].Rulenum=chrom[j].Rulenum;
		newchrom[j].Parent1=newchrom[j].Parent2=j;
		checkvalid(newchrom,j);
	}
}

int select (void)
{
	float rand,partsum=0.0;
	int j=-1;
	rand=random01()*sumfitness;
	do {
		j++;
		partsum+=chrom[j].Fitness;
		}while((partsum<rand)&&(j!=chromnum-1));
	return j;//Return individual number
}

Allele mutation(Allele alleleval)
{
	//Mutate an allele w/[pmuatation, count number of mutations
	Boolean mutate;
	mutate=flip(pmutation);
	if (mutate == T)
		return (Allele)(!alleleval);
	else
		return alleleval;
}

void crossover(int parent1,int parent2,int child)
{
	//Cross 2 parent strings,place in 2 child strings
	int r1,r2,b,i;
	int len1,len2;
	Boolean flag = T;
	r1 = rand()%chrom[parent1].Rulenum;
	r2 = rand()%chrom[parent2].Rulenum;
	b = rand()%rulelen;
	len1 = r1 + chrom[parent2].Rulenum - r2;
	len2 = r2 + chrom[parent1].Rulenum - r1;
	if (len1>maxrule||len2>maxrule)
		flag=F;
	if ((flag == T)&&flip(pcross))
	{
		newchrom[child].Rulenum=len1;
		newchrom[child+1].Rulenum=len2;
		newchrom[child].Parent1=newchrom[child+1].Parent1=parent1;
		newchrom[child].Parent2=newchrom[child+1].Parent2=parent2;
		len1 = r1*rulelen + b;
		len2 = chrom[parent2].Rulenum*rulelen - r2*rulelen - b;
		for (i=0;i<len1;i++)
			newchrom[child].String[i]=mutation(chrom[parent1].String[i]);
		for(i=0;i<len2;i++)
			newchrom[child].String[len1+i]=
			mutation(chrom[parent2].String[r2*rulelen+b+i]);
			len1 = r2*rulelen + b;
			len2 = chrom[parent1].Rulenum*rulelen - r1*rulelen - b;
		 for(i=0;i<len1;i++)
			newchrom[child+1].String[i]=mutation(chrom[parent2].String[i]);
		for (i=0;i<len2;i++)
			newchrom[child+1].String[len1+i]=
		      mutation(chrom[parent1].String[r1*rulelen+b+i]);
	}
	else
	{
		newchrom[child].Rulenum=chrom[parent1].Rulenum;
		newchrom[child+1].Rulenum=chrom[parent2].Rulenum;
		newchrom[child].Parent1=newchrom[child].Parent2=parent1;
		newchrom[child+1].Parent1=newchrom[child+1].Parent2=parent2;
	for (i=0;i<chrom[parent1].Rulenum*rulelen;i++)
		newchrom[child].String[i]=mutation(chrom[parent1].String[i]);
	for(i=0;i<chrom[parent2].Rulenum*rulelen;i++)
		newchrom[child+1].String[i]=mutation(chrom[parent2].String[i]);
	}
	checkvalid(newchrom,child);
	checkvalid(newchrom,child+1);
}

/*适应度=正确分类数、实例总数（=256）*/
void objfunc(Chromosome *pop)
{
	const int len =rulelen + 1;
	char str[len];
	int fi[MAXCHROM];
	int  i=0,j,k;
	Allele flag;
	int bitoftrue;
	for(;i<chromnum;i++)  fi[i] = 0;
	while (fread(str,sizeof(char),len,fp) == len)
	{
		for (i=0;i<chromnum;i++)
		{
			for(j=0;j<pop[i].Rulenum;j++)
			{
				bitoftrue = 0;
				flag = T;
				for(k=0;k<attrnum;k++)
				{
				  while(str[bitoftrue] =='0')
					  bitoftrue++;
					  if(pop[i].String[j*rulelen + bitoftrue] == F)
					  {
						  flag=F;
						  break;
					  }
						  else bitoftrue++;
				}
				if((flag == T)&&(str[rulelen-1]-'0')==
						(int)(pop[i].String[j*rulelen+rulelen-1]))
				{
					 fi[i] ++;
					 break;
				 }/*if*/
			}/*j,Rulenum*/
		}/*i,chromnum*/
	}/*fread*/
			  for(i=0;i<chromnum;i++)
				  pop[i].Fitness=float(fi[i])/256.0;//total examples
			  rewind(fp);
}

/*若两个父代染色体通过遗传操作生成的两个子代中有一个染色体
的适应度高于父代中较差的，则用子代中适应度高的去代替父代中较差的染色体*/
void replace(void)
{
	int even_number=(chromnum%2)?(chromnum-1):chromnum;
	int i = 0;
//	Boolean flag;
	int maxofchild,minofparent;
	while(i<even_number)
	{
		maxofchild = (newchrom[i].Fitness > newchrom[i+1].Fitness)?i:i+1;
		minofparent = (chrom[newchrom[i].Parent1].Fitness < chrom[newchrom[i].Parent2].Fitness) ?newchrom[i].Parent1:newchrom[i].Parent2;
		if (newchrom[maxofchild].Fitness > chrom[minofparent].Fitness)
		{
			chrom[minofparent].Rulenum =newchrom[maxofchild].Rulenum;
			for(int j=0;j<newchrom[maxofchild].Rulenum*rulelen;j++)
			chrom[minofparent].String[j] = newchrom[maxofchild].String[j];

		}
		i += 2;
	}
	if(even_number!=chromnum)
	{
		if (newchrom[i].Fitness>chrom[newchrom[i].Parent1].Fitness)
		{
			chrom[newchrom[i].Parent1].Rulenum = newchrom[i].Rulenum;
			for(int j=0;j<newchrom[i].Rulenum*rulelen;j++)
				chrom[newchrom[i].Parent1].String[j] = newchrom[i].String[j];
		}
	}
}