diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_pool.c')
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_pool.c | 301 |
1 files changed, 158 insertions, 143 deletions
diff --git a/src/backend/optimizer/geqo/geqo_pool.c b/src/backend/optimizer/geqo/geqo_pool.c index 98a1a6e2a06..89c945d4ef4 100644 --- a/src/backend/optimizer/geqo/geqo_pool.c +++ b/src/backend/optimizer/geqo/geqo_pool.c @@ -1,20 +1,20 @@ /*------------------------------------------------------------------------ * * geqo_pool.c-- - * Genetic Algorithm (GA) pool stuff + * Genetic Algorithm (GA) pool stuff * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_pool.c,v 1.1 1997/02/19 12:57:31 scrappy Exp $ + * $Id: geqo_pool.c,v 1.2 1997/09/07 04:43:19 momjian Exp $ * *------------------------------------------------------------------------- */ /* contributed by: =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= - * Martin Utesch * Institute of Automatic Control * - = = University of Mining and Technology = - * utesch@aut.tu-freiberg.de * Freiberg, Germany * + * Martin Utesch * Institute of Automatic Control * + = = University of Mining and Technology = + * utesch@aut.tu-freiberg.de * Freiberg, Germany * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -44,205 +44,220 @@ #include "optimizer/geqo_recombination.h" -static int compare(void *arg1, void *arg2); +static int compare(void *arg1, void *arg2); /* * alloc-pool-- - * allocates memory for GA pool + * allocates memory for GA pool */ -Pool * +Pool * alloc_pool(int pool_size, int string_length) { - Pool *new_pool; - Chromosome *chromo; - int i; - - /* pool */ - new_pool = (Pool *) palloc (sizeof(Pool)); - new_pool->size = (int) pool_size; - new_pool->string_length = (int) string_length; - - /* all chromosome */ - new_pool->data = (Chromosome *) palloc (pool_size * sizeof(Chromosome)); - - /* all gene */ - chromo = (Chromosome *) new_pool->data; /* vector of all chromos */ - for (i=0; i<pool_size; i++) { - chromo[i].string = palloc((string_length+1)*sizeof(Gene)); + Pool *new_pool; + Chromosome *chromo; + int i; + + /* pool */ + new_pool = (Pool *) palloc(sizeof(Pool)); + new_pool->size = (int) pool_size; + new_pool->string_length = (int) string_length; + + /* all chromosome */ + new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome)); + + /* all gene */ + chromo = (Chromosome *) new_pool->data; /* vector of all chromos */ + for (i = 0; i < pool_size; i++) + { + chromo[i].string = palloc((string_length + 1) * sizeof(Gene)); } - return (new_pool); + return (new_pool); } /* * free-pool-- - * deallocates memory for GA pool + * deallocates memory for GA pool */ void -free_pool (Pool *pool) +free_pool(Pool * pool) { - Chromosome *chromo; - int i; + Chromosome *chromo; + int i; - /* all gene */ - chromo = (Chromosome *) pool->data; /* vector of all chromos */ - for (i=0; i<pool->size; i++) pfree(chromo[i].string); + /* all gene */ + chromo = (Chromosome *) pool->data; /* vector of all chromos */ + for (i = 0; i < pool->size; i++) + pfree(chromo[i].string); - /* all chromosome */ - pfree (pool->data); + /* all chromosome */ + pfree(pool->data); - /* pool */ - pfree (pool); + /* pool */ + pfree(pool); } /* * random-init-pool-- - * initialize genetic pool + * initialize genetic pool */ void -random_init_pool (Query *root, Pool *pool, int strt, int stp) +random_init_pool(Query * root, Pool * pool, int strt, int stp) { - Chromosome *chromo = (Chromosome *) pool->data; - int i; + Chromosome *chromo = (Chromosome *) pool->data; + int i; - for (i=strt; i<stp; i++) { - init_tour(chromo[i].string, pool->string_length); /* from "geqo_recombination.c" */ + for (i = strt; i < stp; i++) + { + init_tour(chromo[i].string, pool->string_length); /* from + * "geqo_recombination.c" + * */ - pool->data[i].worth = - geqo_eval(root, chromo[i].string, pool->string_length); /* "from geqo_eval.c" */ + pool->data[i].worth = + geqo_eval(root, chromo[i].string, pool->string_length); /* "from geqo_eval.c" */ } } /* * sort-pool-- - * sorts input pool according to worth, from smallest to largest + * sorts input pool according to worth, from smallest to largest * - * maybe you have to change compare() for different ordering ... + * maybe you have to change compare() for different ordering ... */ void -sort_pool(Pool *pool) -{ - pg_qsort(pool->data, pool->size, sizeof(Chromosome), compare); +sort_pool(Pool * pool) +{ + pg_qsort(pool->data, pool->size, sizeof(Chromosome), compare); } /* * compare-- - * static input function for pg_sort + * static input function for pg_sort * - * return values for sort from smallest to largest are prooved! - * don't change them! + * return values for sort from smallest to largest are prooved! + * don't change them! */ static int compare(void *arg1, void *arg2) { - Chromosome chromo1 = *(Chromosome *) arg1; - Chromosome chromo2 = *(Chromosome *) arg2; - - if (chromo1.worth == chromo2.worth) - return(0); - else if (chromo1.worth > chromo2.worth) - return(1); - else - return(-1); + Chromosome chromo1 = *(Chromosome *) arg1; + Chromosome chromo2 = *(Chromosome *) arg2; + + if (chromo1.worth == chromo2.worth) + return (0); + else if (chromo1.worth > chromo2.worth) + return (1); + else + return (-1); } /* alloc_chromo-- - * allocates a chromosome and string space + * allocates a chromosome and string space */ -Chromosome * -alloc_chromo (int string_length) +Chromosome * +alloc_chromo(int string_length) { - Chromosome *chromo; + Chromosome *chromo; + + chromo = (Chromosome *) palloc(sizeof(Chromosome)); + chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene)); - chromo = (Chromosome *) palloc (sizeof(Chromosome)); - chromo->string = (Gene *) palloc ((string_length+1)*sizeof(Gene)); - - return (chromo); + return (chromo); } /* free_chromo-- - * deallocates a chromosome and string space + * deallocates a chromosome and string space */ void -free_chromo (Chromosome *chromo) +free_chromo(Chromosome * chromo) { - pfree(chromo->string); - pfree(chromo); + pfree(chromo->string); + pfree(chromo); } /* spread_chromo-- - * inserts a new chromosome into the pool, displacing worst gene in pool - * assumes best->worst = smallest->largest + * inserts a new chromosome into the pool, displacing worst gene in pool + * assumes best->worst = smallest->largest */ void -spread_chromo (Chromosome *chromo, Pool *pool) +spread_chromo(Chromosome * chromo, Pool * pool) { - int top, mid, bot; - int i, index; - Chromosome swap_chromo, tmp_chromo; - - /* new chromo is so bad we can't use it */ - if (chromo->worth > pool->data[pool->size-1].worth) return; - - /* do a binary search to find the index of the new chromo */ - - top = 0; - mid = pool->size/2; - bot = pool->size-1; - index = -1; - - while (index == -1) { - /* these 4 cases find a new location */ - - if (chromo->worth <= pool->data[top].worth) - index = top; - else - if (chromo->worth == pool->data[mid].worth) - index = mid; - else - if (chromo->worth == pool->data[bot].worth) - index = bot; - else - if (bot-top <=1) - index = bot; - - - /* these 2 cases move the search indices since - a new location has not yet been found. */ - - else - if (chromo->worth < pool->data[mid].worth) { - bot = mid; - mid = top + ( (bot-top)/2 ); - } - else { /* (chromo->worth > pool->data[mid].worth) */ - top = mid; - mid = top + ( (bot-top)/2 ); - } - } /* ... while */ - - /* now we have index for chromo */ - - /* move every gene from index on down - one position to make room for chromo */ - - /* copy new gene into pool storage; - always replace worst gene in pool */ - - geqo_copy (&pool->data[pool->size-1], chromo, pool->string_length); - - swap_chromo.string = pool->data[pool->size-1].string; - swap_chromo.worth = pool->data[pool->size-1].worth; - - for (i=index; i<pool->size; i++) { - tmp_chromo.string = pool->data[i].string; - tmp_chromo.worth = pool->data[i].worth; - - pool->data[i].string = swap_chromo.string; - pool->data[i].worth = swap_chromo.worth; - - swap_chromo.string = tmp_chromo.string; - swap_chromo.worth = tmp_chromo.worth; - } + int top, + mid, + bot; + int i, + index; + Chromosome swap_chromo, + tmp_chromo; + + /* new chromo is so bad we can't use it */ + if (chromo->worth > pool->data[pool->size - 1].worth) + return; + + /* do a binary search to find the index of the new chromo */ + + top = 0; + mid = pool->size / 2; + bot = pool->size - 1; + index = -1; + + while (index == -1) + { + /* these 4 cases find a new location */ + + if (chromo->worth <= pool->data[top].worth) + index = top; + else if (chromo->worth == pool->data[mid].worth) + index = mid; + else if (chromo->worth == pool->data[bot].worth) + index = bot; + else if (bot - top <= 1) + index = bot; + + + /* + * these 2 cases move the search indices since a new location has + * not yet been found. + */ + + else if (chromo->worth < pool->data[mid].worth) + { + bot = mid; + mid = top + ((bot - top) / 2); + } + else + { /* (chromo->worth > pool->data[mid].worth) */ + top = mid; + mid = top + ((bot - top) / 2); + } + } /* ... while */ + + /* now we have index for chromo */ + + /* + * move every gene from index on down one position to make room for + * chromo + */ + + /* + * copy new gene into pool storage; always replace worst gene in pool + */ + + geqo_copy(&pool->data[pool->size - 1], chromo, pool->string_length); + + swap_chromo.string = pool->data[pool->size - 1].string; + swap_chromo.worth = pool->data[pool->size - 1].worth; + + for (i = index; i < pool->size; i++) + { + tmp_chromo.string = pool->data[i].string; + tmp_chromo.worth = pool->data[i].worth; + + pool->data[i].string = swap_chromo.string; + pool->data[i].worth = swap_chromo.worth; + + swap_chromo.string = tmp_chromo.string; + swap_chromo.worth = tmp_chromo.worth; + } } |