utility.cpp

一个遗传算法（GA）的实现。command line 的结构。输入输出格式请见命令行

/*----------------------------------------------------------------------------*/
/* utility.c - utility routines, contains copyright,  repchar, skip           */
/*----------------------------------------------------------------------------*/

#include "utility.h"

#include "external.h"
#include <stdlib.h>

void copyright()
{
//    void repchar(), skip();
    int iskip;
    int ll = 62;

    iskip = (LINELENGTH - ll)/2;
    skip(outfp,1);
    repchar(outfp," ",iskip); repchar(outfp,"-",ll); skip(outfp,1); 
    repchar(outfp," ",iskip);  
    fprintf(outfp,"|         SGA-C (v1.1) - A Simple Genetic Algorithm          |\n"); 
    repchar(outfp," ",iskip);  
    fprintf(outfp,"|      (c) David E. Goldberg 1986, All Rights Reserved       |\n"); 
    repchar(outfp," ",iskip);  
    fprintf(outfp,"|         C version by Robert E. Smith, U. of Alabama        |\n"); 
    repchar(outfp," ",iskip);  
    fprintf(outfp,"|     v1.1 modifications by Jeff Earickson, Boeing Company   |\n"); 
    repchar(outfp," ",iskip);  
    fprintf(outfp,"|  V2.0 Modified for Feature-Selection by Xiaohan, MSR China |\n"); 
    repchar(outfp," ",iskip); repchar(outfp,"-",ll); skip(outfp,2); 
}


/* Repeatedly write a character to stdout */
void repchar (FILE *outfp,char *ch,int repcount)
{
    int j;

    for (j = 1; j <= repcount; j++) fprintf(outfp,"%s", ch);
}


/* Skip skipcount lines */
void skip(FILE *outfp,int skipcount)
{
    int j;

    for (j = 1; j <= skipcount; j++) fprintf(outfp,"\n");
}


/* interpret bits i thru j of a individual as an integer      */ 
/* j MUST BE greater than or equal to i AND j-i < UINTSIZE-1  */
/* from is a chromosome, represented as an array of unsigneds */
int ithruj2int(int i,int j,unsigned *from)
{
    unsigned mask, temp;
    int bound_flag;
    int iisin, jisin;
    int i1, j1, out;
  
    if(j < i)
    {
        fprintf(stderr,"Error in ithruj2int: j < i\n");
        exit(-1);
    }
    if(j-i+1 > UINTSIZE)
    {
        fprintf(stderr,"Error in ithruj2int: j-i+1 > UINTSIZE\n");
        exit(-1);
    }
  
    iisin = i/UINTSIZE;
    jisin = j/UINTSIZE;

    i1 = i - (iisin*UINTSIZE);
    j1 = j - (jisin*UINTSIZE);

	if(i1 == 0)
 	{
  		iisin = iisin-1;
  		i1 = i - (iisin*UINTSIZE);
 	};

	if(j1 == 0)
 	{ 
  		jisin = jisin-1;
  		j1 = j - (jisin*UINTSIZE);
 	};

    /* check if bits fall across a word boundary */    
    if(iisin == jisin)
        bound_flag = 0;
    else
        bound_flag = 1;

    if(bound_flag == 0)
    {
        mask = 1;
        mask = (mask<<(j1-i1+1))-1;
        mask = mask<<(i1-1);
        out = (from[iisin]&mask)>>(i1-1);
        return(out);
    }
    else
    {
        mask = 1;
        mask = (mask<<j1)-1;
        temp = from[jisin]&mask;
        mask = 1;
        mask = (mask<<(UINTSIZE-i1+1))-1;
        mask = mask<<(i1-1);
        out = ((from[iisin]&mask)>>(i1-1)) | (temp<<(UINTSIZE-i1+1));
        return(out);
    }
}


/*============================================
快速排序子函数，供qsort调用。
dbuff: 数据缓冲指针
============================================*/
int partition(float* array,int l,int r,float pivot)
{
	float dtmp;
	do {
		while(array[++l]<pivot);
		while(r&&(array[--r])>pivot);
		dtmp=array[l];
		array[l]=array[r];
		array[r]=dtmp;
	}while(l<r);
	dtmp=array[l];
	array[l]=array[r];
	array[r]=dtmp;
	return l;
}

/*============================================
快速排序子函数，递归调用
dbuff: 数据缓冲指针
i,j	:  缓冲区中的数据范围，一般为0,n-1;
============================================*/
void qsort(float *array,int i,int j)
{
	float dtmp;
	int k,pivotindex=(i+j)/2;
	dtmp=array[pivotindex];
	array[pivotindex]=array[j];
	array[j]=dtmp;
	k=partition(array,i-1,j,array[j]);
	dtmp=array[k];
	array[k]=array[j];
	array[j]=dtmp;
	if ((k-i)>1) qsort(array,i,k-1);
	if ((j-k)>1) qsort(array,k+1,j);
}

/*============================================
快速排序子函数，供外部调用(外部调用函数不允许递归)
dbuff: 数据缓冲指针
i,j	:  缓冲区中的数据范围，一般为0,n-1;
============================================*/
void fastsort(float *array,int i,int j)
{
	qsort(array,i,j);
}

float CalcFAFR(float *fuserscore,int iu,float *fimpscore,int ii)
{
	/*--------------------------------
	Declaration
	--------------------------------*/
	int ij,ipu,ipi,ilength=iu+ii;
	float fmax = 1e+10;
	float *pC,*pI,ffab,ffrb;
	//--------------------------------
	// Claculate FA & FR 数组
	//--------------------------------
	// assuming minimum of fimpscore < minimum of fuserscore
	if (fuserscore[0]<fimpscore[0])
		printf(" ### Warning! Minimum of Impostor Score is larger than Minimum of Claiment Score !!\nThe FA & FR may be not accurate !");
	
	ipi = ipu = 0;
	pC = fuserscore;
	pI = fimpscore;
	for (ij=0;ij<ilength;ij++)
	{
		if (*pI < *pC) 
		{
			ffab = (float)(ii-ipi)/ii;
			ffrb = (float)ipu/iu;
			if (ffab<=ffrb)
				return (ffab+ffrb)/2;
			if (ipi < ii-1)
			{
				ipi++;
				pI = fimpscore+ipi;
			}else
			{
				ipi = ii;
				pI = &fmax;
			}
		}else{
			ffab = (float)(ii-ipi)/ii;
			ffrb = (float)ipu/iu;
			if (ffab<=ffrb)
				return (ffab+ffrb)/2;
			if (ipu < iu-1)
			{
				ipu++;
				pC = fuserscore+ipu;
			}else
			{
				ipu = iu;
				pC = &fmax;
			}
		}
	}
	return 0;
}

float CalcFOMArea(float *fuserscore,int iu,float *fimpscore,int ii,float frthreshold)
{
	/*--------------------------------
	Declaration
	--------------------------------*/
	int ij,ipu,ipi,ilength=iu+ii;
	float fmax = 1e+10;
	float *pC,*pI,eer;
	bool flag = 1;
	//--------------------------------
	// Claculate FA & FR 数组
	//--------------------------------
	// assuming minimum of fimpscore < minimum of fuserscore
	if (fuserscore[0]<fimpscore[0])
		printf(" ### Minimum of Impostor Score is larger than Minimum of Claiment Score !!\nThe FA & FR may be not accurate !","Warning!");
	
	ipi=0;ipu=0;
	pC = fuserscore;
	pI = fimpscore;
	for (ij=0;ij<ilength;ij++)
	{
		if (*pI < *pC) 
		{
			Ffa[ij] = (float)(ii-ipi)/ii;
			Ffr[ij] = (float)ipu/iu;
//			if ((Ffa[ij]<=Ffr[ij]) && flag)//~
//			{
//				eer = (Ffa[ij]+Ffr[ij])/2;
//				flag = 0;
//				return eer;
//			}//~
			if (ipi < ii-1)
			{
				ipi++;
				pI = fimpscore+ipi;
			}else
			{
				ipi = ii;
				pI = &fmax;
			}
		}else{
			Ffa[ij] = (float)(ii-ipi)/ii;
			Ffr[ij] = (float)ipu/iu;
//			if ((Ffa[ij]<=Ffr[ij]) && flag)//~
//			{
//				eer = (Ffa[ij]+Ffr[ij])/2;
//				flag = 0;
//				return eer;
//			}//~
			if (ipu < iu-1)
			{
				ipu++;
				pC = fuserscore+ipu;
			}else
			{
				ipu = iu;
				pC = &fmax;
			}
		}
	}
/*
#define FAC 100
	for (ij=0;ij<ilength;ij++)
	{
		Ffr[ij] = log(1+FAC*Ffr[ij]);
		Ffa[ij] = log(1+FAC*Ffa[ij]);
	}*/
/*	FILE *fp = fopen("d:\\log","w");
	for (ij=0;ij<ilength;ij++)
	{
		fprintf(fp,"Fr[%d] = %f    Fa[%d] = %f\n",ij,Ffr[ij],ij,Ffa[ij]);
	}
	fclose(fp);*/
	float ftmp,area = 0;
	for (ij=1;(Ffr[ij]<frthreshold)&&(ij<ilength);ij++)
	{
//		ftmp = Ffa[ij] > 0.2 ? 0.2:Ffa[ij];
//		area += (Ffr[ij]-Ffr[ij-1])*Ffa[ij];
		area += (Ffr[ij]-Ffr[ij-1])*(1-Ffa[ij]);
	}
//	return 1/(0.01+area);
	return area;
}