ga_similarity.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

    if (a[i] == b[i]) count++;

  return count;
  }


/**********************************************************************
  ga_similarity_bitstring_tanimoto()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Tanimoto similarity coefficient.
  last updated:	16 May 2002
 **********************************************************************/

double ga_similarity_bitstring_tanimoto(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i;              /* Loop variable over all chromosomes. */
  int		a=0, b=0;	/* Number of ones in the individual entities' chromosomes. */
  int		n=0;		/* Number of ones both entities' chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    n += ga_similarity_bitstring_count_and_alleles( pop, alpha, beta, i );
    a += ga_similarity_bitstring_count_1_alleles( pop, alpha, i );
    b += ga_similarity_bitstring_count_1_alleles( pop, beta, i );
    }

  return (double) n/(a+b-n);
  }


/**********************************************************************
  ga_similarity_bitstring_dice()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Dice similarity coefficient.
  last updated:	16 May 2002
 **********************************************************************/

double ga_similarity_bitstring_dice(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i;              /* Loop variable over all chromosomes. */
  int		a=0, b=0;	/* Number of ones in the individual entities' chromosomes. */
  int		n=0;		/* Number of ones both entities' chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    n += ga_similarity_bitstring_count_and_alleles( pop, alpha, beta, i );
    a += ga_similarity_bitstring_count_1_alleles( pop, alpha, i );
    b += ga_similarity_bitstring_count_1_alleles( pop, beta, i );
    }

  return (double) 2*n/(a+b);
  }


/**********************************************************************
  ga_similarity_bitstring_euclidean()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Euclidean similarity coefficient.
  last updated:	16 May 2002
 **********************************************************************/

double ga_similarity_bitstring_euclidean(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i;              /* Loop variable over all chromosomes. */
  int		a=0, b=0;	/* Number of ones in the individual entities' chromosomes. */
  int		n=0;		/* Number of ones both entities' chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    n += ga_similarity_bitstring_count_and_alleles( pop, alpha, beta, i );
    a += ga_similarity_bitstring_count_1_alleles( pop, alpha, i );
    b += ga_similarity_bitstring_count_1_alleles( pop, beta, i );
    }

  return 1.0 - sqrt((double)(a+b-2*n))/pop->len_chromosomes;
  }


/**********************************************************************
  ga_similarity_bitstring_hamming()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Hamming similarity coefficient.
  last updated:	16 May 2002
 **********************************************************************/

double ga_similarity_bitstring_hamming(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i;              /* Loop variable over all chromosomes. */
  int		a=0, b=0;	/* Number of ones in the individual entities' chromosomes. */
  int		n=0;		/* Number of ones both entities' chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    n += ga_similarity_bitstring_count_and_alleles( pop, alpha, beta, i );
    a += ga_similarity_bitstring_count_1_alleles( pop, alpha, i );
    b += ga_similarity_bitstring_count_1_alleles( pop, beta, i );
    }

  return 1.0 - (a+b-2*n)/pop->len_chromosomes;
  }


/**********************************************************************
  ga_similarity_bitstring_cosine()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Cosine similarity coefficient.
  last updated:	16 May 2002
 **********************************************************************/

double ga_similarity_bitstring_cosine(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i;              /* Loop variable over all chromosomes. */
  int		a=0, b=0;	/* Number of ones in the individual entities' chromosomes. */
  int		n=0;		/* Number of ones both entities' chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    n += ga_similarity_bitstring_count_and_alleles( pop, alpha, beta, i );
    a += ga_similarity_bitstring_count_1_alleles( pop, alpha, i );
    b += ga_similarity_bitstring_count_1_alleles( pop, beta, i );
    }

  if (a==0 || b==0) return 0;

  return n/sqrt((double)(a*b));
  }


/**********************************************************************
  ga_similarity_double_count_match_alleles()
  synopsis:	Compares two "double" chromosomes and counts matching
		alleles.  A match is defined to be when
		x+GA_TINY_DOUBLE>y>x-GA_TINY_DOUBLE
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
		const int chromosomeid	Index of chromosome to consider.
  return:	Returns number of matching alleles.
  last updated:	23 May 2002
 **********************************************************************/

int ga_similarity_double_count_match_alleles( const population *pop,
                                      const entity *alpha, const entity *beta,
                                      const int chromosomeid )
  {
  int		i;		/* Loop variable over all alleles. */
  int		count=0;	/* Number of matching alleles. */
  double	*a, *b;		/* Comparison chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");
  if (chromosomeid<0 || chromosomeid>=pop->num_chromosomes) die("Invalid chromosome index passed");

  a = (double*)(alpha->chromosome[chromosomeid]);
  b = (double*)(beta->chromosome[chromosomeid]);

  for ( i=0; i<pop->len_chromosomes; i++ )
    {
    if (a[i]+GA_TINY_DOUBLE>b[i] && b[i]>a[i]-GA_TINY_DOUBLE) count++;
    }

  return count;
  }


/**********************************************************************
  ga_similarity_double_tanimoto()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Tanimoto similarity coefficient.
		Range: -1/3 to +1
  last updated:	01 Apr 2004
 **********************************************************************/

double ga_similarity_double_tanimoto(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i, j;			/* Loop variable over all chromosomes, alleles. */
  double	ab=0.0, aa=0.0, bb=0.0;	/* Components of the similarity equation. */
  double	*a, *b;		/* Comparison chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    a = (double*)(alpha->chromosome[i]);
    b = (double*)(beta->chromosome[i]);

    for (j=0; j<pop->len_chromosomes; j++)
       {
       aa += a[j]*a[j];
       ab += a[j]*b[j];
       bb += b[j]*b[j];
       }
    }

  return ab/(aa+bb-ab);
  }


/**********************************************************************
  ga_similarity_double_dice()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Dice similarity coefficient.
		Range: -1 to +1
  last updated:	01 Apr 2004
 **********************************************************************/

double ga_similarity_double_dice(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i, j;			/* Loop variable over all chromosomes, alleles. */
  double	ab=0.0, aa=0.0, bb=0.0;	/* Components of the similarity equation. */
  double	*a, *b;			/* Comparison chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    a = (double*)(alpha->chromosome[i]);
    b = (double*)(beta->chromosome[i]);

    for (j=0; j<pop->len_chromosomes; j++)
       {
       aa += a[j]*a[j];
       ab += a[j]*b[j];
       bb += b[j]*b[j];
       }
    }

  return (2*ab)/(aa+bb);
  }


/**********************************************************************
  ga_similarity_double_cosine()
  synopsis:	Compares the chromosomes of two entities.
  parameters:	const population *pop	Population.
		const entity *alpha	entity containing alpha chromosome.
		const entity *beta	entity containing beta chromosome.
  return:	Returns Cosine similarity coefficient.
		Range: -1 to +1
  last updated:	01 Apr 2004
 **********************************************************************/

double ga_similarity_double_cosine(const population *pop,
                                      const entity *alpha, const entity *beta)
  {
  int           i, j;			/* Loop variable over all chromosomes, alleles. */
  double	ab=0.0, aa=0.0, bb=0.0;	/* Components of the similarity equation. */
  double	*a, *b;			/* Comparison chromosomes. */

  /* Checks. */
  if (!pop) die("Null pointer to population structure passed");
  if (!alpha || !beta) die("Null pointer to entity structure passed");

  for (i=0; i<pop->num_chromosomes; i++)
    {
    a = (double*)(alpha->chromosome[i]);
    b = (double*)(beta->chromosome[i]);

    for (j=0; j<pop->len_chromosomes; j++)
       {
       aa += a[j]*a[j];
       ab += a[j]*b[j];
       bb += b[j]*b[j];
       }
    }

  return ab/sqrt(aa+bb);
  }