Quelle  geqo_pmx.c

/*------------------------------------------------------------------------
*
* geqo_pmx.c
*
*  partially matched crossover [PMX] routines;
*  PMX operator according to Goldberg & Lingle
*  (Proc Int'l Conf on GA's)
*
* src/backend/optimizer/geqo/geqo_pmx.c
*
*-------------------------------------------------------------------------
*/

/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch     * Institute of Automatic Control    *
   =        = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany       *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* the pmx algorithm is adopted from Genitor : */
/*************************************************************/
/*  */
/* Copyright (c) 1990  */
/* Darrell L. Whitley  */
/* Computer Science Department  */
/* Colorado State University  */
/*  */
/* Permission is hereby granted to copy all or any part of  */
/* this program for free distribution.   The author's name  */
/* and this copyright notice must be included in any copy.  */
/*  */
/*************************************************************/

#include "postgres.h"
#include "optimizer/geqo.h"

#if defined(PMX)

#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

/* pmx
 *
 *  partially matched crossover
 */
void
pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
{
 int     *failed = (int *) palloc((num_gene + 1) * sizeof(int));
 int     *from = (int *) palloc((num_gene + 1) * sizeof(int));
 int     *indx = (int *) palloc((num_gene + 1) * sizeof(int));
 int     *check_list = (int *) palloc((num_gene + 1) * sizeof(int));

 int   left,
    right,
    temp,
    i,
    j,
    k;
 int   mx_fail,
    found,
    mx_hold;


/* no mutation so start up the pmx replacement algorithm */
/* initialize failed[], from[], check_list[] */
 for (k = 0; k < num_gene; k++)
 {
  failed[k] = -1;
  from[k] = -1;
  check_list[k + 1] = 0;
 }

/* locate crossover points */
 left = geqo_randint(root, num_gene - 1, 0);
 right = geqo_randint(root, num_gene - 1, 0);

 if (left > right)
 {
  temp = left;
  left = right;
  right = temp;
 }


/* copy tour2 into offspring */
 for (k = 0; k < num_gene; k++)
 {
  offspring[k] = tour2[k];
  from[k] = DAD;
  check_list[tour2[k]]++;
 }

/* copy tour1 into offspring */
 for (k = left; k <= right; k++)
 {
  check_list[offspring[k]]--;
  offspring[k] = tour1[k];
  from[k] = MOM;
  check_list[tour1[k]]++;
 }


/* pmx main part */

 mx_fail = 0;

/* STEP 1 */

 for (k = left; k <= right; k++)
 {       /* for all elements in the tour1-2 */

  if (tour1[k] == tour2[k])
   found = 1;   /* find match in tour2 */

  else
  {
   found = 0;   /* substitute elements */

   j = 0;
   while (!(found) && (j < num_gene))
   {
    if ((offspring[j] == tour1[k]) && (from[j] == DAD))
    {

     check_list[offspring[j]]--;
     offspring[j] = tour2[k];
     found = 1;
     check_list[tour2[k]]++;
    }

    j++;
   }
  }

  if (!(found))
  {      /* failed to replace gene */
   failed[mx_fail] = (int) tour1[k];
   indx[mx_fail] = k;
   mx_fail++;
  }
 }       /* ... for */


/* STEP 2 */

 /* see if any genes could not be replaced */
 if (mx_fail > 0)
 {
  mx_hold = mx_fail;

  for (k = 0; k < mx_hold; k++)
  {
   found = 0;

   j = 0;
   while (!(found) && (j < num_gene))
   {

    if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
    {
     check_list[offspring[j]]--;
     offspring[j] = tour2[indx[k]];
     check_list[tour2[indx[k]]]++;

     found = 1;
     failed[k] = -1;
     mx_fail--;
    }

    j++;
   }
  }      /* ... for  */
 }       /* ... if  */


/* STEP 3 */

 for (k = 1; k <= num_gene; k++)
 {

  if (check_list[k] > 1)
  {
   i = 0;

   while (i < num_gene)
   {
    if ((offspring[i] == (Gene) k) && (from[i] == DAD))
    {
     j = 1;

     while (j <= num_gene)
     {
      if (check_list[j] == 0)
      {
       offspring[i] = (Gene) j;
       check_list[k]--;
       check_list[j]++;
       i = num_gene + 1;
       j = i;
      }

      j++;
     }
    }    /* ... if  */

    i++;
   }     /* end while */
  }
 }       /* ... for  */

 pfree(failed);
 pfree(from);
 pfree(indx);
 pfree(check_list);
}

#endif       /* defined(PMX) */