Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit71fd8d4

Browse files
committed
> There are some minor fixes to the GEQO.
> Please apply them to the direcory "backend/optimizer/geqo".> Two new files with different crossover techniques are included.> Standard procedure is optimization by means of "geqo_erx.c"> (Edge Recombination Crossover).From: "Martin S. Utesch" <utesch@aut.tu-freiberg.de>
1 parentf749fe4 commit71fd8d4

File tree

4 files changed

+223
-8
lines changed

4 files changed

+223
-8
lines changed

‎src/backend/optimizer/geqo/Makefile

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
#
66
# Copyright (c) 1994, Regents of the University of California
77
#
8-
# $Id: Makefile,v 1.2 1997/02/19 14:51:55 scrappy Exp $
8+
# $Id: Makefile,v 1.3 1997/03/14 16:02:40 scrappy Exp $
99
#
1010
#-------------------------------------------------------------------------
1111

@@ -21,9 +21,8 @@ CFLAGS+=$(INCLUDE_OPT) -Wno-error
2121
OBJS =geqo_copy.o geqo_eval.o geqo_main.o geqo_misc.o\
2222
geqo_params.o geqo_paths.o geqo_pool.o geqo_recombination.o\
2323
geqo_selection.o\
24-
geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.o
24+
geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.ogeqo_ox1.o geqo_ox2.o
2525

26-
# not ready yet: geqo_ox1.o geqo_ox2.o
2726
# deprecated: minspantree.o
2827

2928
all: SUBSYS.o

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

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
*
77
* Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Id: geqo_main.c,v 1.2 1997/02/19 14:51:59 scrappy Exp $
9+
* $Id: geqo_main.c,v 1.3 1997/03/14 16:02:51 scrappy Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -71,22 +71,22 @@ geqo(Query *root)
7171
Chromosome*daddy;
7272
Chromosome*kid;
7373

74+
#if defined(ERX)
7475
Edge*edge_table;/* list of edges */
7576
intedge_failures=0;
7677
floatdifference;
78+
#endif
7779

78-
#if defined(CX)|| defined(PX)|| defined(QX1)|| defined(QX2)
80+
#if defined(CX)|| defined(PX)|| defined(OX1)|| defined(OX2)
7981
City*city_table;/* list of cities */
8082
#endif
8183

8284
#if defined(CX)
8385
intcycle_diffs=0;
84-
#endif
85-
86-
#if defined(CX)&& defined(GEQO_DEBUG)
8786
intmutations=0;
8887
#endif
8988

89+
9090
intnumber_of_rels;
9191

9292
Pool*pool;

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

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
/*------------------------------------------------------------------------
2+
*
3+
* geqo_ox1.c--
4+
*
5+
* order crossover [OX] routines;
6+
* OX1 operator according to Davis
7+
* (Proc Int'l Joint Conf on AI)
8+
*
9+
* $Id: geqo_ox1.c,v 1.1 1997/03/14 16:02:58 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 ox 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+
#include"postgres.h"
37+
38+
#include"nodes/pg_list.h"
39+
#include"nodes/relation.h"
40+
#include"nodes/primnodes.h"
41+
42+
#include"utils/palloc.h"
43+
#include"utils/elog.h"
44+
45+
#include"optimizer/internal.h"
46+
#include"optimizer/paths.h"
47+
#include"optimizer/pathnode.h"
48+
#include"optimizer/clauses.h"
49+
#include"optimizer/cost.h"
50+
51+
#include"optimizer/geqo_gene.h"
52+
#include"optimizer/geqo.h"
53+
#include"optimizer/geqo_recombination.h"
54+
#include"optimizer/geqo_random.h"
55+
56+
57+
/* ox1--
58+
*
59+
* position crossover
60+
*/
61+
void
62+
ox1(Gene*tour1,Gene*tour2,Gene*offspring,intnum_gene,City*city_table)
63+
{
64+
intleft,right,k,p,temp;
65+
66+
/* initialize city table */
67+
for (k=1;k <=num_gene;k++)
68+
city_table[k].used=0;
69+
70+
/* select portion to copy from tour1 */
71+
left=geqo_randint (num_gene-1,0);
72+
right=geqo_randint (num_gene-1,0);
73+
74+
if (left>right)
75+
{
76+
temp=left;
77+
left=right;
78+
right=temp;
79+
}
80+
81+
/* copy portion from tour1 to offspring */
82+
for (k=left;k <=right;k++)
83+
{
84+
offspring[k]=tour1[k];
85+
city_table[(int)tour1[k]].used=1;
86+
}
87+
88+
k= (right+1) %num_gene;/* index into offspring */
89+
p=k;/* index into tour2 */
90+
91+
/* copy stuff from tour2 to offspring */
92+
while (k!=left)
93+
{
94+
if (!city_table[(int)tour2[p]].used)
95+
{
96+
offspring[k]=tour2[p];
97+
k= (k+1) %num_gene;
98+
city_table[(int)tour2[p]].used=1;
99+
}
100+
p= (p+1) %num_gene;/* increment tour2-index */
101+
}
102+
103+
}

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

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
/*------------------------------------------------------------------------
2+
*
3+
* geqo_ox2.c--
4+
*
5+
* order crossover [OX] routines;
6+
* OX2 operator according to Syswerda
7+
* (The Genetic Algorithms Handbook, ed L Davis)
8+
*
9+
* $Id: geqo_ox2.c,v 1.1 1997/03/14 16:03:02 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 ox 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+
#include"postgres.h"
37+
38+
#include"nodes/pg_list.h"
39+
#include"nodes/relation.h"
40+
#include"nodes/primnodes.h"
41+
42+
#include"utils/palloc.h"
43+
#include"utils/elog.h"
44+
45+
#include"optimizer/internal.h"
46+
#include"optimizer/paths.h"
47+
#include"optimizer/pathnode.h"
48+
#include"optimizer/clauses.h"
49+
#include"optimizer/cost.h"
50+
51+
#include"optimizer/geqo_gene.h"
52+
#include"optimizer/geqo.h"
53+
#include"optimizer/geqo_recombination.h"
54+
#include"optimizer/geqo_random.h"
55+
56+
57+
/* ox2--
58+
*
59+
* position crossover
60+
*/
61+
void
62+
ox2(Gene*tour1,Gene*tour2,Gene*offspring,intnum_gene,City*city_table)
63+
{
64+
intk,j,count,pos,select,num_positions;
65+
66+
/* initialize city table */
67+
for (k=1;k <=num_gene;k++) {
68+
city_table[k].used=0;
69+
city_table[k-1].select_list=-1;
70+
}
71+
72+
/* determine the number of positions to be inherited from tour1 */
73+
num_positions=geqo_randint (2*num_gene/3,num_gene/3);
74+
75+
/* make a list of selected cities */
76+
for (k=0;k<num_positions;k++) {
77+
pos=geqo_randint (num_gene-1,0);
78+
city_table[pos].select_list= (int)tour1[pos];
79+
city_table[(int)tour1[pos]].used=1;/* mark used */
80+
}
81+
82+
83+
count=0;
84+
k=0;
85+
86+
/* consolidate the select list to adjacent positions */
87+
while (count<num_positions) {
88+
if (city_table[k].select_list==-1) {
89+
j=k+1;
90+
while ((city_table[j].select_list==-1)&& (j<num_gene))
91+
j++;
92+
93+
city_table[k].select_list=city_table[j].select_list;
94+
city_table[j].select_list=-1;
95+
count++;
96+
}
97+
else
98+
count++;
99+
k++;
100+
}
101+
102+
select=0;
103+
104+
for (k=0;k<num_gene;k++) {
105+
if (city_table[(int)tour2[k]].used) {
106+
offspring[k]= (Gene)city_table[select].select_list;
107+
select++;/* next city in the select list */
108+
}
109+
else/* city isn't used yet, so inherit from tour2 */
110+
offspring[k]=tour2[k];
111+
}
112+
113+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp