Adding upstream version 15.5.upstream/15.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 111 insertions, 0 deletions

diff --git a/src/backend/optimizer/geqo/geqo_ox2.c b/src/backend/optimizer/geqo/geqo_ox2.c
new file mode 100644
index 0000000..080dbc0
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_ox2.c
@@ -0,0 +1,111 @@
+/*------------------------------------------------------------------------
+*
+* geqo_ox2.c
+*
+*	 order crossover [OX] routines;
+*	 OX2 operator according to Syswerda
+*	 (The Genetic Algorithms Handbook, ed L Davis)
+*
+* src/backend/optimizer/geqo/geqo_ox2.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+   *  Martin Utesch				 * Institute of Automatic Control	   *
+   =							 = University of Mining and Technology =
+   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
+   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the ox 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(OX2)
+
+/* ox2
+ *
+ *	 position crossover
+ */
+void
+ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City * city_table)
+{
+	int			k,
+				j,
+				count,
+				pos,
+				select,
+				num_positions;
+
+	/* initialize city table */
+	for (k = 1; k <= num_gene; k++)
+	{
+		city_table[k].used = 0;
+		city_table[k - 1].select_list = -1;
+	}
+
+	/* determine the number of positions to be inherited from tour1  */
+	num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
+
+	/* make a list of selected cities */
+	for (k = 0; k < num_positions; k++)
+	{
+		pos = geqo_randint(root, num_gene - 1, 0);
+		city_table[pos].select_list = (int) tour1[pos];
+		city_table[(int) tour1[pos]].used = 1;	/* mark used */
+	}
+
+
+	count = 0;
+	k = 0;
+
+	/* consolidate the select list to adjacent positions */
+	while (count < num_positions)
+	{
+		if (city_table[k].select_list == -1)
+		{
+			j = k + 1;
+			while ((city_table[j].select_list == -1) && (j < num_gene))
+				j++;
+
+			city_table[k].select_list = city_table[j].select_list;
+			city_table[j].select_list = -1;
+			count++;
+		}
+		else
+			count++;
+		k++;
+	}
+
+	select = 0;
+
+	for (k = 0; k < num_gene; k++)
+	{
+		if (city_table[(int) tour2[k]].used)
+		{
+			offspring[k] = (Gene) city_table[select].select_list;
+			select++;			/* next city in  the select list   */
+		}
+		else
+			/* city isn't used yet, so inherit from tour2 */
+			offspring[k] = tour2[k];
+	}
+}
+
+#endif							/* defined(OX2) */