granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_erx.c

   1 /*------------------------------------------------------------------------
   2 *
   3 * geqo_erx.c
   4 *        edge recombination crossover [ER]
   5 *
   6 * $Id: geqo_erx.c,v 1.17 2002/03/02 21:39:26 momjian Exp $
   7 *
   8 *-------------------------------------------------------------------------
   9 */
  10
  11 /* contributed by:
  12    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  13    *  Martin Utesch                              * Institute of Automatic Control          *
  14    =                                                     = University of Mining and Technology =
  15    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                               *
  16    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  17  */
  18
  19 /* the edge recombination algorithm is adopted from Genitor : */
  20 /*************************************************************/
  21 /*                                                                                                                       */
  22 /*      Copyright (c) 1990                                                                               */
  23 /*      Darrell L. Whitley                                                                               */
  24 /*      Computer Science Department                                                              */
  25 /*      Colorado State University                                                                */
  26 /*                                                                                                                       */
  27 /*      Permission is hereby granted to copy all or any part of  */
  28 /*      this program for free distribution.   The author's name  */
  29 /*      and this copyright notice must be included in any copy.  */
  30 /*                                                                                                                       */
  31 /*************************************************************/
  32
  33
  34 #include "postgres.h"
  35 #include "optimizer/geqo_recombination.h"
  36 #include "optimizer/geqo_random.h"
  37
  38
  39 static int      gimme_edge(Gene gene1, Gene gene2, Edge *edge_table);
  40 static void remove_gene(Gene gene, Edge edge, Edge *edge_table);
  41 static Gene gimme_gene(Edge edge, Edge *edge_table);
  42
  43 static Gene edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene);
  44
  45
  46 /* alloc_edge_table
  47  *
  48  *       allocate memory for edge table
  49  *
  50  */
  51
  52 Edge *
  53 alloc_edge_table(int num_gene)
  54 {
  55         Edge       *edge_table;
  56
  57         /*
  58          * palloc one extra location so that nodes numbered 1..n can be
  59          * indexed directly; 0 will not be used
  60          */
  61
  62         edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
  63
  64         return edge_table;
  65 }
  66
  67 /* free_edge_table
  68  *
  69  *        deallocate memory of edge table
  70  *
  71  */
  72 void
  73 free_edge_table(Edge *edge_table)
  74 {
  75         pfree(edge_table);
  76 }
  77
  78 /* gimme_edge_table
  79  *
  80  *       fills a data structure which represents the set of explicit
  81  *       edges between points in the (2) input genes
  82  *
  83  *       assumes circular tours and bidirectional edges
  84  *
  85  *       gimme_edge() will set "shared" edges to negative values
  86  *
  87  *       returns average number edges/city in range 2.0 - 4.0
  88  *       where 2.0=homogeneous; 4.0=diverse
  89  *
  90  */
  91 float
  92 gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
  93 {
  94         int                     i,
  95                                 index1,
  96                                 index2;
  97         int                     edge_total;             /* total number of unique edges in two
  98                                                                  * genes */
  99
 100         /* at first clear the edge table's old data */
 101         for (i = 1; i <= num_gene; i++)
 102         {
 103                 edge_table[i].total_edges = 0;
 104                 edge_table[i].unused_edges = 0;
 105         }
 106
 107         /* fill edge table with new data */
 108
 109         edge_total = 0;
 110
 111         for (index1 = 0; index1 < num_gene; index1++)
 112         {
 113                 /*
 114                  * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this
 115                  * operaton maps n back to 1
 116                  */
 117
 118                 index2 = (index1 + 1) % num_gene;
 119
 120                 /*
 121                  * edges are bidirectional, i.e. 1->2 is same as 2->1 call
 122                  * gimme_edge twice per edge
 123                  */
 124
 125                 edge_total += gimme_edge(tour1[index1], tour1[index2], edge_table);
 126                 gimme_edge(tour1[index2], tour1[index1], edge_table);
 127
 128                 edge_total += gimme_edge(tour2[index1], tour2[index2], edge_table);
 129                 gimme_edge(tour2[index2], tour2[index1], edge_table);
 130         }
 131
 132         /* return average number of edges per index */
 133         return ((float) (edge_total * 2) / (float) num_gene);
 134 }
 135
 136 /* gimme_edge
 137  *
 138  *        registers edge from city1 to city2 in input edge table
 139  *
 140  *        no assumptions about directionality are made;
 141  *        therefor it is up to the calling routine to
 142  *        call gimme_edge twice to make a bi-directional edge
 143  *        between city1 and city2;
 144  *        uni-directional edges are possible as well (just call gimme_edge
 145  *        once with the direction from city1 to city2)
 146  *
 147  *        returns 1 if edge was not already registered and was just added;
 148  *                        0 if edge was already registered and edge_table is unchanged
 149  */
 150 static int
 151 gimme_edge(Gene gene1, Gene gene2, Edge *edge_table)
 152 {
 153         int                     i;
 154         int                     edges;
 155         int                     city1 = (int) gene1;
 156         int                     city2 = (int) gene2;
 157
 158
 159         /* check whether edge city1->city2 already exists */
 160         edges = edge_table[city1].total_edges;
 161
 162         for (i = 0; i < edges; i++)
 163         {
 164                 if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
 165                 {
 166
 167                         /* mark shared edges as negative */
 168                         edge_table[city1].edge_list[i] = 0 - city2;
 169
 170                         return 0;
 171                 }
 172         }
 173
 174         /* add city1->city2; */
 175         edge_table[city1].edge_list[edges] = city2;
 176
 177         /* increment the number of edges from city1 */
 178         edge_table[city1].total_edges++;
 179         edge_table[city1].unused_edges++;
 180
 181         return 1;
 182 }
 183
 184 /* gimme_tour
 185  *
 186  *        creates a new tour using edges from the edge table.
 187  *        priority is given to "shared" edges (i.e. edges which
 188  *        all parent genes possess and are marked as negative
 189  *        in the edge table.)
 190  *
 191  */
 192 int
 193 gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
 194 {
 195         int                     i;
 196         int                     edge_failures = 0;
 197
 198         new_gene[0] = (Gene) geqo_randint(num_gene, 1);         /* choose int between 1
 199                                                                                                                  * and num_gene */
 200
 201         for (i = 1; i < num_gene; i++)
 202         {
 203                 /*
 204                  * as each point is entered into the tour, remove it from the edge
 205                  * table
 206                  */
 207
 208                 remove_gene(new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
 209
 210                 /* find destination for the newly entered point */
 211
 212                 if (edge_table[new_gene[i - 1]].unused_edges > 0)
 213                         new_gene[i] = gimme_gene(edge_table[(int) new_gene[i - 1]], edge_table);
 214
 215                 else
 216                 {                                               /* cope with fault */
 217                         edge_failures++;
 218
 219                         new_gene[i] = edge_failure(new_gene, i - 1, edge_table, num_gene);
 220                 }
 221
 222                 /* mark this node as incorporated */
 223                 edge_table[(int) new_gene[i - 1]].unused_edges = -1;
 224
 225         }                                                       /* for (i=1; i<num_gene; i++) */
 226
 227         return edge_failures;
 228
 229 }
 230
 231 /* remove_gene
 232  *
 233  *       removes input gene from edge_table.
 234  *       input edge is used
 235  *       to identify deletion locations within edge table.
 236  *
 237  */
 238 static void
 239 remove_gene(Gene gene, Edge edge, Edge *edge_table)
 240 {
 241         int                     i,
 242                                 j;
 243         int                     possess_edge;
 244         int                     genes_remaining;
 245
 246         /*
 247          * do for every gene known to have an edge to input gene (i.e. in
 248          * edge_list for input edge)
 249          */
 250
 251         for (i = 0; i < edge.unused_edges; i++)
 252         {
 253                 possess_edge = (int) Abs(edge.edge_list[i]);
 254                 genes_remaining = edge_table[possess_edge].unused_edges;
 255
 256                 /* find the input gene in all edge_lists and delete it */
 257                 for (j = 0; j < genes_remaining; j++)
 258                 {
 259
 260                         if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
 261                         {
 262
 263                                 edge_table[possess_edge].unused_edges--;
 264
 265                                 edge_table[possess_edge].edge_list[j] =
 266                                         edge_table[possess_edge].edge_list[genes_remaining - 1];
 267
 268                                 break;
 269                         }
 270                 }
 271         }
 272 }
 273
 274 /* gimme_gene
 275  *
 276  *        priority is given to "shared" edges
 277  *        (i.e. edges which both genes possess)
 278  *
 279  */
 280 static Gene
 281 gimme_gene(Edge edge, Edge *edge_table)
 282 {
 283         int                     i;
 284         Gene            friend;
 285         int                     minimum_edges;
 286         int                     minimum_count = -1;
 287         int                     rand_decision;
 288
 289         /*
 290          * no point has edges to more than 4 other points thus, this contrived
 291          * minimum will be replaced
 292          */
 293
 294         minimum_edges = 5;
 295
 296         /* consider candidate destination points in edge list */
 297
 298         for (i = 0; i < edge.unused_edges; i++)
 299         {
 300                 friend = (Gene) edge.edge_list[i];
 301
 302                 /*
 303                  * give priority to shared edges that are negative; so return 'em
 304                  */
 305
 306                 /*
 307                  * negative values are caught here so we need not worry about
 308                  * converting to absolute values
 309                  */
 310                 if (friend < 0)
 311                         return (Gene) Abs(friend);
 312
 313
 314                 /*
 315                  * give priority to candidates with fewest remaining unused edges;
 316                  * find out what the minimum number of unused edges is
 317                  * (minimum_edges); if there is more than one cadidate with the
 318                  * minimum number of unused edges keep count of this number
 319                  * (minimum_count);
 320                  */
 321
 322                 /*
 323                  * The test for minimum_count can probably be removed at some
 324                  * point but comments should probably indicate exactly why it is
 325                  * guaranteed that the test will always succeed the first time
 326                  * around.      If it can fail then the code is in error
 327                  */
 328
 329
 330                 if (edge_table[(int) friend].unused_edges < minimum_edges)
 331                 {
 332                         minimum_edges = edge_table[(int) friend].unused_edges;
 333                         minimum_count = 1;
 334                 }
 335                 else if (minimum_count == -1)
 336                         elog(ERROR, "gimme_gene: Internal error - minimum_count not set");
 337                 else if (edge_table[(int) friend].unused_edges == minimum_edges)
 338                         minimum_count++;
 339
 340         }                                                       /* for (i=0; i<edge.unused_edges; i++) */
 341
 342
 343         /* random decision of the possible candidates to use */
 344         rand_decision = (int) geqo_randint(minimum_count - 1, 0);
 345
 346
 347         for (i = 0; i < edge.unused_edges; i++)
 348         {
 349                 friend = (Gene) edge.edge_list[i];
 350
 351                 /* return the chosen candidate point */
 352                 if (edge_table[(int) friend].unused_edges == minimum_edges)
 353                 {
 354                         minimum_count--;
 355
 356                         if (minimum_count == rand_decision)
 357                                 return friend;
 358                 }
 359         }
 360
 361         /* ... should never be reached */
 362         elog(ERROR, "gimme_gene: neither shared nor minimum number nor random edge found");
 363         return 0;                                       /* to keep the compiler quiet */
 364 }
 365
 366 /* edge_failure
 367  *
 368  *        routine for handling edge failure
 369  *
 370  */
 371 static Gene
 372 edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
 373 {
 374         int                     i;
 375         Gene            fail_gene = gene[index];
 376         int                     remaining_edges = 0;
 377         int                     four_count = 0;
 378         int                     rand_decision;
 379
 380
 381         /*
 382          * how many edges remain? how many gene with four total (initial)
 383          * edges remain?
 384          */
 385
 386         for (i = 1; i <= num_gene; i++)
 387         {
 388                 if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
 389                 {
 390                         remaining_edges++;
 391
 392                         if (edge_table[i].total_edges == 4)
 393                                 four_count++;
 394                 }
 395         }
 396
 397         /*
 398          * random decision of the gene with remaining edges and whose
 399          * total_edges == 4
 400          */
 401
 402         if (four_count != 0)
 403         {
 404
 405                 rand_decision = (int) geqo_randint(four_count - 1, 0);
 406
 407                 for (i = 1; i <= num_gene; i++)
 408                 {
 409
 410                         if ((Gene) i != fail_gene &&
 411                                 edge_table[i].unused_edges != -1 &&
 412                                 edge_table[i].total_edges == 4)
 413                         {
 414
 415                                 four_count--;
 416
 417                                 if (rand_decision == four_count)
 418                                         return (Gene) i;
 419                         }
 420                 }
 421
 422                 elog(LOG, "edge_failure(1): no edge found via random decision and total_edges == 4");
 423         }
 424
 425         else
 426 /* random decision of the gene with remaining edges */
 427
 428         if (remaining_edges != 0)
 429         {
 430
 431                 rand_decision = (int) geqo_randint(remaining_edges - 1, 0);
 432
 433                 for (i = 1; i <= num_gene; i++)
 434                 {
 435
 436                         if ((Gene) i != fail_gene &&
 437                                 edge_table[i].unused_edges != -1)
 438                         {
 439
 440                                 remaining_edges--;
 441
 442                                 if (rand_decision == remaining_edges)
 443                                         return i;
 444                         }
 445                 }
 446
 447                 elog(LOG, "edge_failure(2): no edge found via random decision and remainig edges");
 448         }
 449
 450         /*
 451          * edge table seems to be empty; this happens sometimes on the last
 452          * point due to the fact that the first point is removed from the
 453          * table even though only one of its edges has been determined
 454          */
 455
 456         else
 457         {                                                       /* occurs only at the last point in the
 458                                                                  * tour; simply look for the point which
 459                                                                  * is not yet used */
 460
 461                 for (i = 1; i <= num_gene; i++)
 462                         if (edge_table[i].unused_edges >= 0)
 463                                 return (Gene) i;
 464
 465                 elog(LOG, "edge_failure(3): no edge found via looking for the last ununsed point");
 466         }
 467
 468
 469 /* ... should never be reached */
 470         elog(ERROR, "edge_failure: no edge detected");
 471         return 0;                                       /* to keep the compiler quiet */
 472 }