diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_px.c')
-rw-r--r-- | src/backend/optimizer/geqo/geqo_px.c | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/geqo_px.c b/src/backend/optimizer/geqo/geqo_px.c new file mode 100644 index 0000000..914296b --- /dev/null +++ b/src/backend/optimizer/geqo/geqo_px.c @@ -0,0 +1,107 @@ +/*------------------------------------------------------------------------ +* +* geqo_px.c +* +* position crossover [PX] routines; +* PX operator according to Syswerda +* (The Genetic Algorithms Handbook, L Davis, ed) +* +* src/backend/optimizer/geqo/geqo_px.c +* +*------------------------------------------------------------------------- +*/ + +/* contributed by: + =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= + * Martin Utesch * Institute of Automatic Control * + = = University of Mining and Technology = + * utesch@aut.tu-freiberg.de * Freiberg, Germany * + =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= + */ + +/* the px 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(PX) + +/* px + * + * position crossover + */ +void +px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, + City * city_table) +{ + int num_positions; + int i, + pos, + tour2_index, + offspring_index; + + /* initialize city table */ + for (i = 1; i <= num_gene; i++) + city_table[i].used = 0; + + /* choose random positions that will be inherited directly from parent */ + num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3); + + /* choose random position */ + for (i = 0; i < num_positions; i++) + { + pos = geqo_randint(root, num_gene - 1, 0); + + offspring[pos] = tour1[pos]; /* transfer cities to child */ + city_table[(int) tour1[pos]].used = 1; /* mark city used */ + } + + tour2_index = 0; + offspring_index = 0; + + + /* px main part */ + + while (offspring_index < num_gene) + { + + /* next position in offspring filled */ + if (!city_table[(int) tour1[offspring_index]].used) + { + + /* next city in tour1 not used */ + if (!city_table[(int) tour2[tour2_index]].used) + { + + /* inherit from tour1 */ + offspring[offspring_index] = tour2[tour2_index]; + + tour2_index++; + offspring_index++; + } + else + { /* next city in tour2 has been used */ + tour2_index++; + } + } + else + { /* next position in offspring is filled */ + offspring_index++; + } + } +} + +#endif /* defined(PX) */ |