Header And Logo

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

geqo_ox1.c

Go to the documentation of this file.
00001 /*------------------------------------------------------------------------
00002 *
00003 * geqo_ox1.c
00004 *
00005 *    order crossover [OX] routines;
00006 *    OX1 operator according to Davis
00007 *    (Proc Int'l Joint Conf on AI)
00008 *
00009 * src/backend/optimizer/geqo/geqo_ox1.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 ox 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 /* ox1
00042  *
00043  *   position crossover
00044  */
00045 void
00046 ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
00047     City *city_table)
00048 {
00049     int         left,
00050                 right,
00051                 k,
00052                 p,
00053                 temp;
00054 
00055     /* initialize city table */
00056     for (k = 1; k <= num_gene; k++)
00057         city_table[k].used = 0;
00058 
00059     /* select portion to copy from tour1 */
00060     left = geqo_randint(root, num_gene - 1, 0);
00061     right = geqo_randint(root, num_gene - 1, 0);
00062 
00063     if (left > right)
00064     {
00065         temp = left;
00066         left = right;
00067         right = temp;
00068     }
00069 
00070     /* copy portion from tour1 to offspring */
00071     for (k = left; k <= right; k++)
00072     {
00073         offspring[k] = tour1[k];
00074         city_table[(int) tour1[k]].used = 1;
00075     }
00076 
00077     k = (right + 1) % num_gene; /* index into offspring */
00078     p = k;                      /* index into tour2 */
00079 
00080     /* copy stuff from tour2 to offspring */
00081     while (k != left)
00082     {
00083         if (!city_table[(int) tour2[p]].used)
00084         {
00085             offspring[k] = tour2[p];
00086             k = (k + 1) % num_gene;
00087             city_table[(int) tour2[p]].used = 1;
00088         }
00089         p = (p + 1) % num_gene; /* increment tour2-index */
00090     }
00091 
00092 }