igka.c

GA遗传算法的C语言版改进实现

void IncrementalUpdate(int m)
{

    int j, d, k, n, oldZ;
    double oldWCV, oldDist;

    S[m].TWCVDelta = 0;

    for (k=0; k<K; k++)
    {
        if (S[m].change[k] != 1 ) continue;

            oldZ = S[m].Z[k];
            S[m].Z[k] = S[m].Z[k] + S[m].ZDelta[k];

            for (d=0; d<D; d++)
    		{
                S[m].SF[k][d] = S[m].SF[k][d] + S[m].SFDelta[k][d];
                S[m].SFDelta[k][d] = 0;
                if(S[m].Z[k] > 0 )
                    S[m].C[k][d] = S[m].SF[k][d] / S[m].Z[k];
    		}
            S[m].change[k] = 0;
            S[m].ZDelta[k] = 0;

            if(oldZ == 0 && S[m].Z[k] >0 )
                S[m].num ++;
        	else
                if(oldZ>0 && S[m].Z[k]==0)
                    S[m].num --;

            oldWCV = S[m].WCV[k];
            S[m].WCV[k] = 0;

            for(n=0; n<N; n++)
    		{
                if(S[m].a[n] == k)
        		{
                    for(d=0; d<D; d++)
                        S[m].WCV[k] = S[m].WCV[k] + (X[n][d] - S[m].C[k][d])*(X[n][d] - S[m].C[k][d]);
        		}
    		}
            S[m].TWCVDelta = S[m].TWCVDelta + S[m].WCV[k] - oldWCV;

            for(n=0; n<N; n++)
    		{
                oldDist = S[m].d[n][k];
                S[m].d[n][k] = 0;
                for(d=0; d<D; d++)
                    S[m].d[n][k] = S[m].d[n][k] + (X[n][d] - S[m].C[k][d])*(X[n][d] - S[m].C[k][d]);

                if (S[m].d[n][k]> S[m].dmax[n])
        		{
                    S[m].dmax[n] = S[m].d[n][k];
                    S[m].kmax[n] = k;
        		}
                if (S[m].d[n][k] < S[m].dmin[n])
        		{
                    S[m].dmin[n] = S[m].d[n][k];
                    S[m].kmin[n] = k;
        		}

                if(S[m].d[n][k] < oldDist && S[m].kmax[n] == k)
        		{
                    S[m].dmax[n] = 0;
                    for(j=0; j<K; j++)
                        if(S[m].dmax[n] < S[m].d[n][j])
        				{
                            S[m].dmax[n] = S[m].d[n][j];
                        	S[m].kmax[n] = j;
        				}
        		}

                if(S[m].d[n][k] > oldDist && S[m].kmin[n] == k)
        		{
                    S[m].dmin[n] = MAX_NUMBER;
                    for(j=0; j<K; j++)
                        if(S[m].dmin[n] > S[m].d[n][j])
        				{
                            S[m].dmin[n] = S[m].d[n][j];
                        	S[m].kmin[n] = j;
        				}
        		}

                S[m].dsum[n] = S[m].dsum[n] - oldDist + S[m].d[n][k];
    		}
    }

    S[m].e = S[m].num/K;
    S[m].TWCV = S[m].TWCV + S[m].TWCVDelta;

    if(TWCVMax < S[m].TWCV)
        TWCVMax = S[m].TWCV;
}

/*
double Twcv(int *PN)
{
    double twcv;
    double center;
    int i,j,k;
    int ClusterName;

    for(i=0; i<K; i++) num[i]=0;

    for(i=0; i<K; i++) wcv[i]=0;

    for(i=0; i<K; i++)
        for(j=0; j<D;j++)
            Sum[i][j]=0;

    twcv = 0;

    for(i=0; i<N; i++)
    {
        ClusterName = PN[i];
        num[ClusterName] ++;
        for(j=0; j<D;j++)
    	{
            wcv[ClusterName] += X[i][j] * X[i][j];
            Sum[ClusterName][j] += X[i][j];
    	}
    }

    for(k=0; k<K; k++)
    {
        for(j=0; j<D;j++)
    	{
            if (num[k] != 0)
                center =  Sum[k][j] / num[k];
        	else
                center = 0;
            wcv[k] = wcv[k] + num[k]*center*center - 2*Sum[k][j]*center;
    	}
        twcv += wcv[k];
    }
    return twcv;
}
*/

void Eval(int m)
{
    int d, n, k;

    for(k = 0; k < K; k++)
    {
        S[m].Z[k] = 0;
        S[m].WCV[k] = 0;
        for(d=0; d<D; d++)
    	{
            S[m].SF[k][d] = 0;
    	}
    }
    S[m].num = 0;

    for(n=0; n<N; n++)
    {
        k = S[m].a[n];
        S[m].Z[k] = S[m].Z[k] + 1;
        for(d=0; d<D; d++)
    	{
            S[m].SF[k][d] += X[n][d];
    	}
    }

    for(k = 0; k < K; k++)
    {
        if (S[m].Z[k] >0)
    	{
            S[m].num ++;
            for(d=0; d<D; d++)
    		{
                S[m].C[k][d] = S[m].SF[k][d] / S[m].Z[k];
    		}
    	}
    }

    for(n=0; n<N; n++)
    {
        k = S[m].a[n];
        for(d=0; d<D; d++)
            S[m].WCV[k] = S[m].WCV[k] + (X[n][d] - S[m].C[k][d]) * (X[n][d] - S[m].C[k][d]);
    }

    S[m].e = S[m].num/K;
    S[m].TWCV = 0;
    for(k=0; k<K; k++)
        S[m].TWCV = S[m].TWCV + S[m].WCV[k];

    if ( TWCVMax < S[m].TWCV )
        TWCVMax = S[m].TWCV;

    for( n=0; n<N; n++)
    {
        S[m].dmax[n] = 0;
        S[m].dmin[n] = MAX_NUMBER;
        S[m].dsum[n] = 0;

        for(k=0; k<K; k++)
    	{
            S[m].d[n][k] = 0;
    	}
    }

    for( n=0; n<N; n++)
    {
        for(k=0; k<K; k++)
    	{
            for(d=0; d<D; d++)
    		{
                S[m].d[n][k] = S[m].d[n][k] + (X[n][d] -S[m].C[k][d])* (X[n][d] -S[m].C[k][d]);
    		}
            S[m].dsum[n] = S[m].dsum[n] + S[m].d[n][k];
            if(S[m].d[n][k] > S[m].dmax[n])
    		{
                S[m].dmax[n] = S[m].d[n][k];
                S[m].kmax[n] = k;
    		}

            if(S[m].d[n][k] < S[m].dmin[n])
    		{
                S[m].dmin[n] = S[m].d[n][k];
                S[m].kmin[n] = k;
    		}
    	}
    }

}


char* getline(FILE* inputfile)
{
    int c;
    char* newline;
    int n = 0;
    int size = 1023;
    char* line = (char*)malloc((size_t)(size+1)*sizeof(char));
    while ((c = getc(inputfile))!='\n' && c != EOF)
    {
        if (c!='\r')
        {
            if (n == size)
            {
                size *= 2;
                newline = (char*)malloc((size_t)(size+1)*sizeof(char));
                strncpy (newline, line, n);
                free (line);
                line = newline;
            }
            line[n] = c;
            n++;
        }
    }

    if (n==0)
    {
        free (line);
        return 0;
    }

    line[n] = '\0';
    newline = (char*)malloc((size_t)(n+1)*sizeof(char));
    strcpy (newline, line);
    free(line);
    return newline;
}

int Export(const char *filename)
{
    FILE *outputfile, *inputfile;
    int i,c,Columns,row;
    char *line;
    char *word;
    char *error;
    double number;

    inputfile = fopen(filename,"rt");
    if (!inputfile){
        printf("Error opening file");
        return -1;
    }

    outputfile = fopen("result.out","w");
    if (!outputfile){
        printf("Error opening file");
        return -1;
    }

    fseek (inputfile, 0, SEEK_SET);

    /* Count the number of columns in the first row */
    Columns = 1; /* One more column than tabs */
    while ((c = getc(inputfile)) && (c!='\n') && (c!='\r'))
    {
        if (c == '\t') Columns++;
    }


    while ((line = getline(inputfile)))
    {
        if (strlen(line) > 1) /* Ignore completely empty lines */
        	N ++;
        free(line);
    }


    D = Columns;

    if (D < 1)
    {
        printf("Error: less than six columns found in the file");
        return -1;
    }

    fseek (inputfile, 0, SEEK_SET);
    getline(inputfile);  /* Skip header line and empty lines*/
    row = 0;

    while ((line=getline(inputfile)))
    {
        if (strlen(line) > 1) /* Ignore completely empty lines */
        {

            word = strtok(line,"\t");

            number = strtod(word, &error);
            fprintf(outputfile, "%d \t", SO.a[row]);

            for(i=0; i<D-1; i++)
    		{
                word = strtok(NULL,"\t");
                if (!(*error)) fprintf(outputfile, "%s\t", word);
                else fprintf(outputfile, "%f\t", 0);
            }
        }
        fprintf(outputfile, "\n");
        free(line);
        row++;
    }

    fclose(inputfile);
    fclose(outputfile);
    return 0;

}

int LoadData (const char* filename)
{
    FILE* inputfile;
    int i,c,Columns;
    int row;
    char *line;
    char *word;
    char *error;
    double number;

    inputfile = fopen(filename,"rt");
    if (!inputfile){
        printf("Error opening file");
        return -1;
    }

    fseek (inputfile, 0, SEEK_SET);

    /* Count the number of columns in the first row */
    Columns = 1; /* One more column than tabs */
    while ((c = getc(inputfile)) && (c!='\n') && (c!='\r'))
    {
        if (c == '\t') Columns++;
    }


    while ((line = getline(inputfile)))
    {
        if (strlen(line) > 1) /* Ignore completely empty lines */
        	N ++;
        free(line);
    }



    D = Columns - 2;

    if (D < 1)
    {
        printf("Error: less than six columns found in the file");
        return -1;
    }

    /* Allocate space for data */
    X = (double**)malloc((size_t)N*sizeof(double*));
    for (row = 0; row < N; row++)
    {
        X[row] =(double*)malloc((size_t)D*sizeof(double));
    }
    origin = (int*)malloc((size_t)N*sizeof(int));

    row = 0;
    fseek (inputfile, 0, SEEK_SET);
    getline(inputfile);  /* Skip header line and empty lines*/

    while ((line=getline(inputfile)))
    {
        if (strlen(line) > 1) /* Ignore completely empty lines */
        {


            word = strtok(line,"\t");

            number = strtod(word, &error);
            origin[row] = number;
/*
            for(i=0; i<3; i++ )
                word = strtok( NULL, "\t");
*/
            for(i=0; i<D; i++)
    		{
                word = strtok(NULL,"\t");
                number = strtod(word, &error);
                if (!(*error)) X[row][i] = number;
                else X[row][i]  = 0;
            }
            row++;
        }
        free(line);
    }

    fclose(inputfile);
    return 0;
}