diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_pmx.c')
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_pmx.c | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/geqo_pmx.c b/src/backend/optimizer/geqo/geqo_pmx.c new file mode 100644 index 0000000..e44fd0b --- /dev/null +++ b/src/backend/optimizer/geqo/geqo_pmx.c @@ -0,0 +1,218 @@ +/*------------------------------------------------------------------------ +* +* geqo_pmx.c +* +* partially matched crossover [PMX] routines; +* PMX operator according to Goldberg & Lingle +* (Proc Int'l Conf on GA's) +* +* src/backend/optimizer/geqo/geqo_pmx.c +* +*------------------------------------------------------------------------- +*/ + +/* contributed by: + =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= + * Martin Utesch * Institute of Automatic Control * + = = University of Mining and Technology = + * utesch@aut.tu-freiberg.de * Freiberg, Germany * + =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= + */ + +/* the pmx algorithm is adopted from Genitor : */ +/*************************************************************/ +/* */ +/* Copyright (c) 1990 */ +/* Darrell L. Whitley */ +/* Computer Science Department */ +/* Colorado State University */ +/* */ +/* Permission is hereby granted to copy all or any part of */ +/* this program for free distribution. The author's name */ +/* and this copyright notice must be included in any copy. */ +/* */ +/*************************************************************/ + +#include "postgres.h" +#include "optimizer/geqo_random.h" +#include "optimizer/geqo_recombination.h" + +#if defined(PMX) + +/* pmx + * + * partially matched crossover + */ +void +pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene) +{ + int *failed = (int *) palloc((num_gene + 1) * sizeof(int)); + int *from = (int *) palloc((num_gene + 1) * sizeof(int)); + int *indx = (int *) palloc((num_gene + 1) * sizeof(int)); + int *check_list = (int *) palloc((num_gene + 1) * sizeof(int)); + + int left, + right, + temp, + i, + j, + k; + int mx_fail, + found, + mx_hold; + + +/* no mutation so start up the pmx replacement algorithm */ +/* initialize failed[], from[], check_list[] */ + for (k = 0; k < num_gene; k++) + { + failed[k] = -1; + from[k] = -1; + check_list[k + 1] = 0; + } + +/* locate crossover points */ + left = geqo_randint(root, num_gene - 1, 0); + right = geqo_randint(root, num_gene - 1, 0); + + if (left > right) + { + temp = left; + left = right; + right = temp; + } + + +/* copy tour2 into offspring */ + for (k = 0; k < num_gene; k++) + { + offspring[k] = tour2[k]; + from[k] = DAD; + check_list[tour2[k]]++; + } + +/* copy tour1 into offspring */ + for (k = left; k <= right; k++) + { + check_list[offspring[k]]--; + offspring[k] = tour1[k]; + from[k] = MOM; + check_list[tour1[k]]++; + } + + +/* pmx main part */ + + mx_fail = 0; + +/* STEP 1 */ + + for (k = left; k <= right; k++) + { /* for all elements in the tour1-2 */ + + if (tour1[k] == tour2[k]) + found = 1; /* find match in tour2 */ + + else + { + found = 0; /* substitute elements */ + + j = 0; + while (!(found) && (j < num_gene)) + { + if ((offspring[j] == tour1[k]) && (from[j] == DAD)) + { + + check_list[offspring[j]]--; + offspring[j] = tour2[k]; + found = 1; + check_list[tour2[k]]++; + } + + j++; + } + } + + if (!(found)) + { /* failed to replace gene */ + failed[mx_fail] = (int) tour1[k]; + indx[mx_fail] = k; + mx_fail++; + } + } /* ... for */ + + +/* STEP 2 */ + + /* see if any genes could not be replaced */ + if (mx_fail > 0) + { + mx_hold = mx_fail; + + for (k = 0; k < mx_hold; k++) + { + found = 0; + + j = 0; + while (!(found) && (j < num_gene)) + { + + if ((failed[k] == (int) offspring[j]) && (from[j] == DAD)) + { + check_list[offspring[j]]--; + offspring[j] = tour2[indx[k]]; + check_list[tour2[indx[k]]]++; + + found = 1; + failed[k] = -1; + mx_fail--; + } + + j++; + } + } /* ... for */ + } /* ... if */ + + +/* STEP 3 */ + + for (k = 1; k <= num_gene; k++) + { + + if (check_list[k] > 1) + { + i = 0; + + while (i < num_gene) + { + if ((offspring[i] == (Gene) k) && (from[i] == DAD)) + { + j = 1; + + while (j <= num_gene) + { + if (check_list[j] == 0) + { + offspring[i] = (Gene) j; + check_list[k]--; + check_list[j]++; + i = num_gene + 1; + j = i; + } + + j++; + } + } /* ... if */ + + i++; + } /* end while */ + } + } /* ... for */ + + pfree(failed); + pfree(from); + pfree(indx); + pfree(check_list); +} + +#endif /* defined(PMX) */ |