Header And Logo

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

geqo_ox2.c

Go to the documentation of this file.
00001 /*------------------------------------------------------------------------
00002 *
00003 * geqo_ox2.c
00004 *
00005 *    order crossover [OX] routines;
00006 *    OX2 operator according to Syswerda
00007 *    (The Genetic Algorithms Handbook, ed L Davis)
00008 *
00009 * src/backend/optimizer/geqo/geqo_ox2.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 /* ox2
00042  *
00043  *   position crossover
00044  */
00045 void
00046 ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
00047 {
00048     int         k,
00049                 j,
00050                 count,
00051                 pos,
00052                 select,
00053                 num_positions;
00054 
00055     /* initialize city table */
00056     for (k = 1; k <= num_gene; k++)
00057     {
00058         city_table[k].used = 0;
00059         city_table[k - 1].select_list = -1;
00060     }
00061 
00062     /* determine the number of positions to be inherited from tour1  */
00063     num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
00064 
00065     /* make a list of selected cities */
00066     for (k = 0; k < num_positions; k++)
00067     {
00068         pos = geqo_randint(root, num_gene - 1, 0);
00069         city_table[pos].select_list = (int) tour1[pos];
00070         city_table[(int) tour1[pos]].used = 1;  /* mark used */
00071     }
00072 
00073 
00074     count = 0;
00075     k = 0;
00076 
00077     /* consolidate the select list to adjacent positions */
00078     while (count < num_positions)
00079     {
00080         if (city_table[k].select_list == -1)
00081         {
00082             j = k + 1;
00083             while ((city_table[j].select_list == -1) && (j < num_gene))
00084                 j++;
00085 
00086             city_table[k].select_list = city_table[j].select_list;
00087             city_table[j].select_list = -1;
00088             count++;
00089         }
00090         else
00091             count++;
00092         k++;
00093     }
00094 
00095     select = 0;
00096 
00097     for (k = 0; k < num_gene; k++)
00098     {
00099         if (city_table[(int) tour2[k]].used)
00100         {
00101             offspring[k] = (Gene) city_table[select].select_list;
00102             select++;           /* next city in  the select list   */
00103         }
00104         else
00105             /* city isn't used yet, so inherit from tour2 */
00106             offspring[k] = tour2[k];
00107     }
00108 
00109 }