igka.c

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

#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <float.h>

#ifndef RAND_MAX
#define RAND_MAX 32767
#endif;

#ifndef MAX_NUMBER
#define MAX_NUMBER 0xffffff
#endif;

struct Solution{
    int *a;
    int *Z;
    int *ZDelta;
    double F;
    double **SF;
    double **SFDelta;
    double *WCV;
    double **C;
    int num;
    double TWCV;
    double TWCVDelta;
    double **d;
    double e;
    int *change;
    double *dmax;
    double *dmin;
    int *kmin;
    int *kmax;
    double *dsum;
    int used;
};

void FGKA();
void Init();
void Selection();
void Mutation();
void KMO();
void Eval(int);
void AccumulateUpdate(int, int, int, int);
void IncrementalUpdate(int);
void CopySolution(struct Solution *, struct Solution *);
double* gather(double*,int);
int Distribution(double*, int);
char* getline(FILE*);
int LoadData (const char*);
int Export(const char*);

int* match1;
int* match2;
double **X;
struct Solution *S;
struct Solution SO;

int K = 0;
int N = 0;
int D = 0;
int M = 0;
double TWCV;
double TWCVMax;

int G = 0;
float mp;
int *origin;
FILE* outputfile;

void main(int argc,char **argv)
{
    char filename[30];

    printf("\nPlease input the file name for processing: ");
    scanf("%s", filename);
    strcat(filename,"\0");
    printf("\nPlease enter the number of Clusters: ");
    scanf("%d",&K);
    printf("\nPlease enter the number of Populations: ");
    scanf("%d",&M);
    printf("\nPlease enter the number of maximum generations: ");
    scanf("%d",&G);
    printf("\nPlease enter the mutation probability: ");
    scanf("%f",&mp);

    if ( LoadData(filename) == -1 ) exit(1);

        FGKA();

    Export(filename);

    free(X);
    getch();
}

void FGKA()
{
    int tim1, tim2;
    int n, i, m;

    tim1 = time(0);

    SO.TWCV = MAX_NUMBER;
    Init();

    for(i=0; i<G; i++)
    {
        Selection();

        Mutation();

        KMO();

        for(m=0; m<M; m++)
    	{
            if(SO.TWCV > S[m].TWCV)
    		{
                SO.TWCV = S[m].TWCV;
                for(n=0; n<N; n++)
                    SO.a[n] = S[m].a[n];
    		}
    	}

        tim2 = time(0);
        printf("iteration %d\t%f\t%d\n",i, SO.TWCV, tim2 - tim1);
    }
    tim2 = time(0);
    printf("%d", tim2 - tim1);
    free(S);

}

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

    TWCVMax = 0;

    S = (struct Solution*)malloc((size_t)M*sizeof(struct Solution));
    match1 = (int*)malloc((size_t)M*sizeof(int));
    match2 = (int*)malloc((size_t)M*sizeof(int));
    srand(100);

    for(m = 0; m < M; m++)
    {
        SO.a = (int*)malloc((size_t)N*sizeof(int));
        S[m].a = (int*)malloc((size_t)N*sizeof(int));
        S[m].Z = (int*)malloc((size_t)K*sizeof(int));
        S[m].ZDelta = (int*)malloc((size_t)K*sizeof(int));
        S[m].WCV = (double*)malloc((size_t)K*sizeof(double));
        S[m].SF = (double**)malloc((size_t)K*sizeof(double*));
        S[m].SFDelta = (double**)malloc((size_t)K*sizeof(double*));
        S[m].change = (int*)malloc((size_t)K*sizeof(int));
        S[m].dsum = (double*)malloc((size_t)N*sizeof(double));
        S[m].dmax = (double*)malloc((size_t)N*sizeof(double));
        S[m].dmin = (double*)malloc((size_t)N*sizeof(double));
        S[m].kmax = (int*)malloc((size_t)N*sizeof(int));
        S[m].kmin = (int*)malloc((size_t)N*sizeof(int));
        S[m].C = (double**)malloc((size_t)K*sizeof(double*));
        S[m].d = (double**)malloc((size_t)N*sizeof(double*));
        S[m].used =0;

        for (k = 0; k < K; k++)
        {
            S[m].C[k] =(double*)malloc((size_t)D*sizeof(double));
            S[m].SF[k] = (double*)malloc((size_t)D*sizeof(double));
            S[m].SFDelta[k] = (double*)malloc((size_t)D*sizeof(double));
            S[m].change[k] = 0;
            S[m].ZDelta[k] = 0;
            for(d=0; d<D; d++)
    		{
                S[m].SFDelta[k][d] = 0;
    		}
        }

        for(n = 0; n < N; n++)
    	{
            S[m].d[n] = (double*)malloc((size_t)K*sizeof(double));
            S[m].a[n] =  (int)(((double)rand()/RAND_MAX) * K);
            if(S[m].a[n] == K) S[m].a[n] --;
    	}
        Eval(m);

        if(SO.TWCV > S[m].TWCV)
    	{
            SO.TWCV = S[m].TWCV;
            for(n=0; n<N; n++)
                SO.a[n] = S[m].a[n];
    	}


    }

}


void Selection()
{
    double Fmin = 0;
    double *psb;
    double Fsum = 0;
    int i, m, temp, count;
    int flag =0;
    struct Solution *Sprime;

    for(m=0; m<M; m++)
    {
        if (S[m].num == K)
    	{
            flag = 1;
            S[m].F = 1.5 * TWCVMax - S[m].TWCV;
            if(Fmin > S[m].F)
                Fmin = S[m].F;
            Fsum = Fsum + S[m].F;
    	}
    }

    if(flag == 0)
        Fmin =1;

    for(m=0; m<M; m++)
    {
        if (S[m].num != K)
    	{
            S[m].F = S[m].e * Fmin;
            Fsum = Fsum + S[m].F;
    	}
    }
    psb = (double*)malloc((size_t)M*sizeof(double));

    for(m=0; m<M; m++)
    {
        psb[m] = S[m].F / Fsum;
    }
    psb = gather(psb, M);

    Sprime = (struct Solution*)malloc((size_t)M*sizeof(struct Solution));

    for(m=0; m<M; m++)
        Sprime[m] = S[m];

    count = 0;
    for(m=0; m<M; m++)
    {
        temp = Distribution(psb, M);
        if(Sprime[temp].used == 0)
    	{
            S[m] = Sprime[temp];
            Sprime[temp].used = 1;
    	}
        else
    	{
            match1[count] = m;
            match2[count] = temp;
            count ++;
    	}
    }

    i = 0;
    for(m=0; m<M; m++)
    {
        if(Sprime[m].used == 0 && i<count)
    	{
            CopySolution(&Sprime[m], &Sprime[match2[i]]);
            S[match1[i]] = Sprime[m];
            S[match1[i]].used = 0;
        	i ++;
    	}
        Sprime[m].used = 0;
    }
    free(Sprime);
    free(psb);
}


void Mutation()
{
    double *p;
    int m, n, k, olda, count=0;

    p = (double*)malloc((size_t)K*sizeof(double));
    for(m=0; m<M; m++)
    {
        for(n=0; n<N; n++)
    	{
            if( (double)rand()/RAND_MAX < mp)
    		{

                for(k=0; k<K; k++ )
        		{
                    p[k] = (1.5 * S[m].dmax[n] - S[m].d[n][k] +0.5) / S[m].dsum[n];
        		}

                olda = S[m].a[n];

                p = gather(p, K);
                S[m].a[n] = Distribution(p, K);

                if(S[m].a[n] != olda)
        		{
                    AccumulateUpdate(m, n, olda, S[m].a[n]);
                	count++;
        		}
    		}
    	}

        IncrementalUpdate(m);
    }

    free(p);
}

void KMO()
{
    int m, n, olda;
    int count=0;

    for(m=0; m<M; m++)
    {
        if (S[m].num == K)
    	{
            for(n=0; n<N; n++)
    		{

                olda = S[m].a[n];
                S[m].a[n] = S[m].kmin[n];

                if(S[m].a[n] != olda)
        		{
                    AccumulateUpdate(m, n, olda, S[m].a[n]);
                	count ++;
        		}

    		}
            IncrementalUpdate(m);
    	}
    }

}


double* gather(double *psb, int distNumber)
{
    double *DistK;
    int i;

    DistK = (double*)malloc((size_t)distNumber*sizeof(double));

    DistK[0] = psb[0];
    for(i= 1; i< distNumber; i++)
    {
        DistK[i] = DistK[i-1] + psb[i];
    }
    return DistK;
}

int Distribution(double *DistK, int distNumber)
{
    double index;
    int i;

    index = ((double)rand()/RAND_MAX);

    for( i =0; i<distNumber; i++)
    {
        if ( index < DistK[i])
            return i;
    }
    return distNumber -1;
}


void CopySolution(struct Solution *t, struct Solution *f)
{
    int n,k,d;

    t->F = f->F;
    t->num = f->num;
    t->used = f->used;
    t->TWCV = f->TWCV;
    t->TWCVDelta = f->TWCVDelta;
    t->e = f->e;

    for(n=0; n<N; n++)
    {
        t->a[n] = f->a[n];
        t->dsum[n] = f->dsum[n];
        t->dmax[n] = f->dmax[n];
        t->dmin[n] = f->dmin[n];
        t->kmin[n] = f->kmin[n];
        t->kmax[n] = f->kmax[n];
        for (k=0; k<K; k++)
    	{
            t->d[n][k] = f->d[n][k];
    	}

    }

    for(k=0; k<K; k++)
    {
        t->Z[k] = f->Z[k];
        t->ZDelta[k] = f->ZDelta[k];
        t->WCV[k] = f->WCV[k];
        t->change[k] = f->change[k];

        for (d=0; d<D; d++)
    	{
            t->SF[k][d] = f->SF[k][d];
            t->SFDelta[k][d] = f->SFDelta[k][d];
            t->C[k][d] = f->C[k][d];
    	}
    }

}

void AccumulateUpdate(int m, int n, int olda, int newa)
{

    int k1, k2, d;
    S[m].change[olda] = 1;
    S[m].change[newa] = 1;
    k1 = olda;
    k2 = newa;
    S[m].ZDelta[k1]--;
    S[m].ZDelta[k2]++;
    for(d=0; d<D; d++)
    {
        S[m].SFDelta[k1][d] = S[m].SFDelta[k1][d] - X[n][d];
        S[m].SFDelta[k2][d] = S[m].SFDelta[k2][d] + X[n][d];
    }
}