igka.c

遗传算法

	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];
	}
}


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; //used for fig2data.txt

  	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 - 4; //used for fig2data.txt
	D = Columns - 2; // used for chodata

  	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 */
    	{

			//skip first 4 columns
			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;
}