1 /*------------------------------------------------------------------------ 2 * 3 * geqo_cx.c 4 * 5 * cycle crossover [CX] routines; 6 * CX operator according to Oliver et al 7 * (Proc 2nd Int'l Conf on GA's) 8 * 9 * src/backend/optimizer/geqo/geqo_cx.c 10 * 11 *------------------------------------------------------------------------- 12 */ 13 14 /* contributed by: 15 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= 16 * Martin Utesch * Institute of Automatic Control * 17 = = University of Mining and Technology = 18 * utesch@aut.tu-freiberg.de * Freiberg, Germany * 19 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= 20 */ 21 22 /* the cx algorithm is adopted from Genitor : */ 23 /*************************************************************/ 24 /* */ 25 /* Copyright (c) 1990 */ 26 /* Darrell L. Whitley */ 27 /* Computer Science Department */ 28 /* Colorado State University */ 29 /* */ 30 /* Permission is hereby granted to copy all or any part of */ 31 /* this program for free distribution. The author's name */ 32 /* and this copyright notice must be included in any copy. */ 33 /* */ 34 /*************************************************************/ 35 36 37 #include "postgres.h" 38 #include "optimizer/geqo_random.h" 39 #include "optimizer/geqo_recombination.h" 40 41 #if defined(CX) 42 43 /* cx 44 * 45 * cycle crossover 46 */ 47 int 48 cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, 49 int num_gene, City * city_table) 50 { 51 int i, 52 start_pos, 53 curr_pos; 54 int count = 0; 55 int num_diffs = 0; 56 57 /* initialize city table */ 58 for (i = 1; i <= num_gene; i++) 59 { 60 city_table[i].used = 0; 61 city_table[tour2[i - 1]].tour2_position = i - 1; 62 city_table[tour1[i - 1]].tour1_position = i - 1; 63 } 64 65 /* choose random cycle starting position */ 66 start_pos = geqo_randint(root, num_gene - 1, 0); 67 68 /* child inherits first city */ 69 offspring[start_pos] = tour1[start_pos]; 70 71 /* begin cycle with tour1 */ 72 curr_pos = start_pos; 73 city_table[(int) tour1[start_pos]].used = 1; 74 75 count++; 76 77 /* cx main part */ 78 79 80 /* STEP 1 */ 81 82 while (tour2[curr_pos] != tour1[start_pos]) 83 { 84 city_table[(int) tour2[curr_pos]].used = 1; 85 curr_pos = city_table[(int) tour2[curr_pos]].tour1_position; 86 offspring[curr_pos] = tour1[curr_pos]; 87 count++; 88 } 89 90 91 /* STEP 2 */ 92 93 /* failed to create a complete tour */ 94 if (count < num_gene) 95 { 96 for (i = 1; i <= num_gene; i++) 97 { 98 if (!city_table[i].used) 99 { 100 offspring[city_table[i].tour2_position] = 101 tour2[(int) city_table[i].tour2_position]; 102 count++; 103 } 104 } 105 } 106 107 108 /* STEP 3 */ 109 110 /* still failed to create a complete tour */ 111 if (count < num_gene) 112 { 113 114 /* count the number of differences between mom and offspring */ 115 for (i = 0; i < num_gene; i++) 116 if (tour1[i] != offspring[i]) 117 num_diffs++; 118 119 } 120 121 return num_diffs; 122 } 123 124 #endif /* defined(CX) */ 125