diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_cx.c')
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_cx.c | 132 |
1 files changed, 70 insertions, 62 deletions
diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c index a3aa6fce4f4..dfde1bdc530 100644 --- a/src/backend/optimizer/geqo/geqo_cx.c +++ b/src/backend/optimizer/geqo/geqo_cx.c @@ -2,35 +2,35 @@ * * geqo_cx.c-- * -* cycle crossover [CX] routines; -* CX operator according to Oliver et al -* (Proc 2nd Int'l Conf on GA's) +* cycle crossover [CX] routines; +* CX operator according to Oliver et al +* (Proc 2nd Int'l Conf on GA's) * -* $Id: geqo_cx.c,v 1.1 1997/02/19 12:56:48 scrappy Exp $ +* $Id: geqo_cx.c,v 1.2 1997/09/07 04:43:02 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* the cx 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. */ -/* */ +/* */ +/* 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. */ +/* */ /*************************************************************/ @@ -57,73 +57,81 @@ /* cx-- * - * cycle crossover + * cycle crossover */ int -cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table) +cx(Gene * tour1, Gene * tour2, Gene * offspring, int num_gene, City * city_table) { - int i, start_pos, curr_pos; - int count = 0; - int num_diffs = 0; + int i, + start_pos, + curr_pos; + int count = 0; + int num_diffs = 0; - /* initialize city table */ - for (i=1; i<=num_gene; i++) { - city_table[i].used = 0; - city_table[tour2[i-1]].tour2_position = i-1; - city_table[tour1[i-1]].tour1_position = i-1; - } + /* initialize city table */ + for (i = 1; i <= num_gene; i++) + { + city_table[i].used = 0; + city_table[tour2[i - 1]].tour2_position = i - 1; + city_table[tour1[i - 1]].tour1_position = i - 1; + } - /* choose random cycle starting position */ - start_pos = geqo_randint(num_gene - 1, 0); + /* choose random cycle starting position */ + start_pos = geqo_randint(num_gene - 1, 0); - /* child inherits first city */ - offspring[start_pos] = tour1[start_pos]; + /* child inherits first city */ + offspring[start_pos] = tour1[start_pos]; - /* begin cycle with tour1 */ - curr_pos = start_pos; - city_table[(int) tour1[start_pos]].used = 1; + /* begin cycle with tour1 */ + curr_pos = start_pos; + city_table[(int) tour1[start_pos]].used = 1; - count++; + count++; - /* cx main part */ + /* cx main part */ /* STEP 1 */ - while (tour2[curr_pos] != tour1[start_pos]) { - city_table[(int) tour2[curr_pos]].used = 1; - curr_pos = city_table[(int) tour2[curr_pos]].tour1_position; - offspring[curr_pos] = tour1[curr_pos]; - count++; - } + while (tour2[curr_pos] != tour1[start_pos]) + { + city_table[(int) tour2[curr_pos]].used = 1; + curr_pos = city_table[(int) tour2[curr_pos]].tour1_position; + offspring[curr_pos] = tour1[curr_pos]; + count++; + } /* STEP 2 */ - /* failed to create a complete tour */ - if (count < num_gene) { - for (i=1; i<=num_gene; i++) { - if (!city_table[i].used) { - offspring[city_table[i].tour2_position] = - tour2[(int) city_table[i].tour2_position]; - count++; - } - } - } + /* failed to create a complete tour */ + if (count < num_gene) + { + for (i = 1; i <= num_gene; i++) + { + if (!city_table[i].used) + { + offspring[city_table[i].tour2_position] = + tour2[(int) city_table[i].tour2_position]; + count++; + } + } + } /* STEP 3 */ - /* still failed to create a complete tour */ - if (count < num_gene) { + /* still failed to create a complete tour */ + if (count < num_gene) + { - /* count the number of differences between mom and offspring */ - for (i=0; i<num_gene; i++) - if (tour1[i] != offspring[i]) num_diffs++; + /* count the number of differences between mom and offspring */ + for (i = 0; i < num_gene; i++) + if (tour1[i] != offspring[i]) + num_diffs++; - } - - return(num_diffs); - } + } + return (num_diffs); +} |