Skip to content

Commit 29138ee

Browse files
scrappyscrappy
committed
Merge in GEQO Optimizer
From: "Martin S. Utesch" <utesch@aut.tu-freiberg.de>
1 parent 34f35a4 commit 29138ee

29 files changed

+3823
-3
lines changed

‎src/backend/optimizer/Makefile

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,13 +4,13 @@
44
# Makefile for optimizer
55
#
66
# IDENTIFICATION
7-
# $Header: /cvsroot/pgsql/src/backend/optimizer/Makefile,v 1.2 1996/11/10 03:12:38 bryanh Exp $
7+
# $Header: /cvsroot/pgsql/src/backend/optimizer/Makefile,v 1.3 1997/02/19 12:56:31 scrappy Exp $
88
#
99
#-------------------------------------------------------------------------
1010

1111
all: submake SUBSYS.o
1212

13-
OBJS = path/SUBSYS.o plan/SUBSYS.o prep/SUBSYS.o util/SUBSYS.o
13+
OBJS = path/SUBSYS.o plan/SUBSYS.o prep/SUBSYS.o util/SUBSYS.o geqo/SUBSYS.o
1414

1515
SUBSYS.o: $(OBJS)
1616
$(LD) -r -o SUBSYS.o $(OBJS)
@@ -21,16 +21,19 @@ submake:
2121
$(MAKE) -C plan SUBSYS.o
2222
$(MAKE) -C prep SUBSYS.o
2323
$(MAKE) -C util SUBSYS.o
24+
$(MAKE) -C geqo SUBSYS.o
2425

2526
clean:
2627
rm -f SUBSYS.o
2728
$(MAKE) -C path clean
2829
$(MAKE) -C plan clean
2930
$(MAKE) -C prep clean
3031
$(MAKE) -C util clean
32+
$(MAKE) -C geqo clean
3133

3234
.DEFAULT:
3335
$(MAKE) -C path $@
3436
$(MAKE) -C plan $@
3537
$(MAKE) -C prep $@
3638
$(MAKE) -C util $@
39+
$(MAKE) -C geqo $@

‎src/backend/optimizer/geqo/Makefile

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
#-------------------------------------------------------------------------
2+
#
3+
# Makefile--
4+
# Makefile for the genetic query optimizer module
5+
#
6+
# Copyright (c) 1994, Regents of the University of California
7+
#
8+
# $Id: Makefile,v 1.1 1997/02/19 12:56:38 scrappy Exp $
9+
#
10+
#-------------------------------------------------------------------------
11+
12+
SRCDIR = ../../..
13+
include ../../../Makefile.global
14+
15+
INCLUDE_OPT = -I../.. \
16+
-I../../port/$(PORTNAME) \
17+
-I../../../include
18+
19+
CFLAGS+=$(INCLUDE_OPT)
20+
21+
OBJS = geqo_copy.o geqo_eval.o geqo_main.o geqo_misc.o \
22+
geqo_params.o geqo_paths.o geqo_pool.o geqo_recombination.o \
23+
geqo_selection.o \
24+
geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.o
25+
26+
# not ready yet: geqo_ox1.o geqo_ox2.o
27+
# deprecated: minspantree.o
28+
29+
all: SUBSYS.o
30+
31+
SUBSYS.o: $(OBJS)
32+
$(LD) -r -o SUBSYS.o $(OBJS)
33+
34+
depend dep:
35+
$(CC) -MM $(INCLUDE_OPT) *.c >depend
36+
37+
clean:
38+
rm -f SUBSYS.o $(OBJS)
39+
40+
ifeq (depend,$(wildcard depend))
41+
include depend
42+
endif
43+

‎src/backend/optimizer/geqo/geqo_copy.c

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/*------------------------------------------------------------------------
2+
*
3+
* geqo_copy.c--
4+
*
5+
* Copyright (c) 1994, Regents of the University of California
6+
*
7+
* $Id: geqo_copy.c,v 1.1 1997/02/19 12:56:40 scrappy Exp $
8+
*
9+
*-------------------------------------------------------------------------
10+
*/
11+
12+
/* contributed by:
13+
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
14+
* Martin Utesch * Institute of Automatic Control *
15+
= = University of Mining and Technology =
16+
* utesch@aut.tu-freiberg.de * Freiberg, Germany *
17+
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
18+
*/
19+
20+
/* this is adopted from D. Whitley's Genitor algorithm */
21+
22+
/*************************************************************/
23+
/* */
24+
/* Copyright (c) 1990 */
25+
/* Darrell L. Whitley */
26+
/* Computer Science Department */
27+
/* Colorado State University */
28+
/* */
29+
/* Permission is hereby granted to copy all or any part of */
30+
/* this program for free distribution. The author's name */
31+
/* and this copyright notice must be included in any copy. */
32+
/* */
33+
/*************************************************************/
34+
35+
#include "postgres.h"
36+
37+
#include "nodes/pg_list.h"
38+
#include "nodes/relation.h"
39+
#include "nodes/primnodes.h"
40+
41+
#include "utils/palloc.h"
42+
#include "utils/elog.h"
43+
44+
#include "optimizer/internal.h"
45+
#include "optimizer/paths.h"
46+
#include "optimizer/pathnode.h"
47+
#include "optimizer/clauses.h"
48+
#include "optimizer/cost.h"
49+
50+
#include "optimizer/geqo_gene.h"
51+
#include "optimizer/geqo_copy.h"
52+
53+
/* geqo_copy--
54+
*
55+
* copies one gene to another
56+
*
57+
*/
58+
void
59+
geqo_copy (Chromosome *chromo1, Chromosome *chromo2, int string_length)
60+
{
61+
int i;
62+
63+
for (i=0; i<string_length; i++)
64+
chromo1->string[i] = chromo2->string[i];
65+
66+
chromo1->worth = chromo2->worth;
67+
}

‎src/backend/optimizer/geqo/geqo_cx.c

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
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+
* $Id: geqo_cx.c,v 1.1 1997/02/19 12:56:48 scrappy Exp $
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+
39+
#include "nodes/pg_list.h"
40+
#include "nodes/relation.h"
41+
#include "nodes/primnodes.h"
42+
43+
#include "utils/palloc.h"
44+
#include "utils/elog.h"
45+
46+
#include "optimizer/internal.h"
47+
#include "optimizer/paths.h"
48+
#include "optimizer/pathnode.h"
49+
#include "optimizer/clauses.h"
50+
#include "optimizer/cost.h"
51+
52+
#include "optimizer/geqo_gene.h"
53+
#include "optimizer/geqo.h"
54+
#include "optimizer/geqo_recombination.h"
55+
#include "optimizer/geqo_random.h"
56+
57+
58+
/* cx--
59+
*
60+
* cycle crossover
61+
*/
62+
int
63+
cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
64+
{
65+
66+
int i, start_pos, curr_pos;
67+
int count = 0;
68+
int num_diffs = 0;
69+
70+
/* initialize city table */
71+
for (i=1; i<=num_gene; i++) {
72+
city_table[i].used = 0;
73+
city_table[tour2[i-1]].tour2_position = i-1;
74+
city_table[tour1[i-1]].tour1_position = i-1;
75+
}
76+
77+
/* choose random cycle starting position */
78+
start_pos = geqo_randint(num_gene - 1, 0);
79+
80+
/* child inherits first city */
81+
offspring[start_pos] = tour1[start_pos];
82+
83+
/* begin cycle with tour1 */
84+
curr_pos = start_pos;
85+
city_table[(int) tour1[start_pos]].used = 1;
86+
87+
count++;
88+
89+
/* cx main part */
90+
91+
92+
/* STEP 1 */
93+
94+
while (tour2[curr_pos] != tour1[start_pos]) {
95+
city_table[(int) tour2[curr_pos]].used = 1;
96+
curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
97+
offspring[curr_pos] = tour1[curr_pos];
98+
count++;
99+
}
100+
101+
102+
/* STEP 2 */
103+
104+
/* failed to create a complete tour */
105+
if (count < num_gene) {
106+
for (i=1; i<=num_gene; i++) {
107+
if (!city_table[i].used) {
108+
offspring[city_table[i].tour2_position] =
109+
tour2[(int) city_table[i].tour2_position];
110+
count++;
111+
}
112+
}
113+
}
114+
115+
116+
/* STEP 3 */
117+
118+
/* still failed to create a complete tour */
119+
if (count < num_gene) {
120+
121+
/* count the number of differences between mom and offspring */
122+
for (i=0; i<num_gene; i++)
123+
if (tour1[i] != offspring[i]) num_diffs++;
124+
125+
}
126+
127+
return(num_diffs);
128+
}
129+

0 commit comments

Comments
 (0)