Header And Logo

PostgreSQL
| The world's most advanced open source database.

geqo_pmx.c

Go to the documentation of this file.
00001 /*------------------------------------------------------------------------
00002 *
00003 * geqo_pmx.c
00004 *
00005 *    partially matched crossover [PMX] routines;
00006 *    PMX operator according to Goldberg & Lingle
00007 *    (Proc Int'l Conf on GA's)
00008 *
00009 * src/backend/optimizer/geqo/geqo_pmx.c
00010 *
00011 *-------------------------------------------------------------------------
00012 */
00013 
00014 /* contributed by:
00015    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00016    *  Martin Utesch              * Institute of Automatic Control      *
00017    =                             = University of Mining and Technology =
00018    *  [email protected]  * Freiberg, Germany                   *
00019    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00020  */
00021 
00022 /* the pmx algorithm is adopted from Genitor : */
00023 /*************************************************************/
00024 /*                                                           */
00025 /*  Copyright (c) 1990                                       */
00026 /*  Darrell L. Whitley                                       */
00027 /*  Computer Science Department                              */
00028 /*  Colorado State University                                */
00029 /*                                                           */
00030 /*  Permission is hereby granted to copy all or any part of  */
00031 /*  this program for free distribution.   The author's name  */
00032 /*  and this copyright notice must be included in any copy.  */
00033 /*                                                           */
00034 /*************************************************************/
00035 
00036 #include "postgres.h"
00037 #include "optimizer/geqo_random.h"
00038 #include "optimizer/geqo_recombination.h"
00039 
00040 
00041 /* pmx
00042  *
00043  *   partially matched crossover
00044  */
00045 void
00046 pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
00047 {
00048     int        *failed = (int *) palloc((num_gene + 1) * sizeof(int));
00049     int        *from = (int *) palloc((num_gene + 1) * sizeof(int));
00050     int        *indx = (int *) palloc((num_gene + 1) * sizeof(int));
00051     int        *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
00052 
00053     int         left,
00054                 right,
00055                 temp,
00056                 i,
00057                 j,
00058                 k;
00059     int         mx_fail,
00060                 found,
00061                 mx_hold;
00062 
00063 
00064 /* no mutation so start up the pmx replacement algorithm */
00065 /* initialize failed[], from[], check_list[] */
00066     for (k = 0; k < num_gene; k++)
00067     {
00068         failed[k] = -1;
00069         from[k] = -1;
00070         check_list[k + 1] = 0;
00071     }
00072 
00073 /* locate crossover points */
00074     left = geqo_randint(root, num_gene - 1, 0);
00075     right = geqo_randint(root, num_gene - 1, 0);
00076 
00077     if (left > right)
00078     {
00079         temp = left;
00080         left = right;
00081         right = temp;
00082     }
00083 
00084 
00085 /* copy tour2 into offspring */
00086     for (k = 0; k < num_gene; k++)
00087     {
00088         offspring[k] = tour2[k];
00089         from[k] = DAD;
00090         check_list[tour2[k]]++;
00091     }
00092 
00093 /* copy tour1 into offspring */
00094     for (k = left; k <= right; k++)
00095     {
00096         check_list[offspring[k]]--;
00097         offspring[k] = tour1[k];
00098         from[k] = MOM;
00099         check_list[tour1[k]]++;
00100     }
00101 
00102 
00103 /* pmx main part */
00104 
00105     mx_fail = 0;
00106 
00107 /* STEP 1 */
00108 
00109     for (k = left; k <= right; k++)
00110     {                           /* for all elements in the tour1-2 */
00111 
00112         if (tour1[k] == tour2[k])
00113             found = 1;          /* find match in tour2 */
00114 
00115         else
00116         {
00117             found = 0;          /* substitute elements */
00118 
00119             j = 0;
00120             while (!(found) && (j < num_gene))
00121             {
00122                 if ((offspring[j] == tour1[k]) && (from[j] == DAD))
00123                 {
00124 
00125                     check_list[offspring[j]]--;
00126                     offspring[j] = tour2[k];
00127                     found = 1;
00128                     check_list[tour2[k]]++;
00129                 }
00130 
00131                 j++;
00132             }
00133 
00134         }
00135 
00136         if (!(found))
00137         {                       /* failed to replace gene */
00138             failed[mx_fail] = (int) tour1[k];
00139             indx[mx_fail] = k;
00140             mx_fail++;
00141         }
00142 
00143     }                           /* ... for */
00144 
00145 
00146 /* STEP 2 */
00147 
00148     /* see if any genes could not be replaced */
00149     if (mx_fail > 0)
00150     {
00151         mx_hold = mx_fail;
00152 
00153         for (k = 0; k < mx_hold; k++)
00154         {
00155             found = 0;
00156 
00157             j = 0;
00158             while (!(found) && (j < num_gene))
00159             {
00160 
00161                 if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
00162                 {
00163                     check_list[offspring[j]]--;
00164                     offspring[j] = tour2[indx[k]];
00165                     check_list[tour2[indx[k]]]++;
00166 
00167                     found = 1;
00168                     failed[k] = -1;
00169                     mx_fail--;
00170                 }
00171 
00172                 j++;
00173             }
00174 
00175         }                       /* ... for   */
00176 
00177     }                           /* ... if    */
00178 
00179 
00180 /* STEP 3 */
00181 
00182     for (k = 1; k <= num_gene; k++)
00183     {
00184 
00185         if (check_list[k] > 1)
00186         {
00187             i = 0;
00188 
00189             while (i < num_gene)
00190             {
00191                 if ((offspring[i] == (Gene) k) && (from[i] == DAD))
00192                 {
00193                     j = 1;
00194 
00195                     while (j <= num_gene)
00196                     {
00197                         if (check_list[j] == 0)
00198                         {
00199                             offspring[i] = (Gene) j;
00200                             check_list[k]--;
00201                             check_list[j]++;
00202                             i = num_gene + 1;
00203                             j = i;
00204                         }
00205 
00206                         j++;
00207                     }
00208 
00209                 }               /* ... if    */
00210 
00211                 i++;
00212             }                   /* end while */
00213 
00214         }
00215     }                           /* ... for   */
00216 
00217     pfree(failed);
00218     pfree(from);
00219     pfree(indx);
00220     pfree(check_list);
00221 }