geqo_recombination.h File Reference

#include "optimizer/geqo.h"

Include dependency graph for geqo_recombination.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	Edge
struct	City

Macros
#define	DAD   1 /* indicator for gene from dad */
#define	MOM   0 /* indicator for gene from mom */

Typedefs
typedef struct Edge	Edge
typedef struct City	City

Functions
void	init_tour (PlannerInfo *root, Gene *tour, int num_gene)
Edge *	alloc_edge_table (PlannerInfo *root, int num_gene)
void	free_edge_table (PlannerInfo *root, Edge *edge_table)
float	gimme_edge_table (PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
int	gimme_tour (PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
void	pmx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
City *	alloc_city_table (PlannerInfo *root, int num_gene)
void	free_city_table (PlannerInfo *root, City *city_table)
int	cx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
void	px (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
void	ox1 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
void	ox2 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)

Macro Definition Documentation

DAD

#define DAD   1 /* indicator for gene from dad */

Definition at line 54 of file geqo_recombination.h.

MOM

#define MOM   0 /* indicator for gene from mom */

Definition at line 55 of file geqo_recombination.h.

Typedef Documentation

City

typedef struct City City

Edge

typedef struct Edge Edge

Function Documentation

alloc_city_table()

City* alloc_city_table	(	PlannerInfo *	root,
		int	num_gene
	)

Referenced by geqo().

alloc_edge_table()

Edge* alloc_edge_table	(	PlannerInfo *	root,
		int	num_gene
	)

Definition at line 56 of file geqo_erx.c.

{
    Edge       *edge_table;
 
    /*
     * palloc one extra location so that nodes numbered 1..n can be indexed
     * directly; 0 will not be used
     */
 
    edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
 
    return edge_table;
}

References palloc().

Referenced by geqo().

cx()

int cx	(	PlannerInfo *	root,
		Gene *	tour1,
		Gene *	tour2,
		Gene *	offspring,
		int	num_gene,
		City *	city_table
	)

Referenced by combo_decrypt(), combo_encrypt(), combo_free(), combo_init(), geqo(), and px_find_combo().

free_city_table()

void free_city_table	(	PlannerInfo *	root,
		City *	city_table
	)

Referenced by geqo().

free_edge_table()

void free_edge_table	(	PlannerInfo *	root,
		Edge *	edge_table
	)

Definition at line 76 of file geqo_erx.c.

{
    pfree(edge_table);
}

References pfree().

Referenced by geqo().

gimme_edge_table()

float gimme_edge_table	(	PlannerInfo *	root,
		Gene *	tour1,
		Gene *	tour2,
		int	num_gene,
		Edge *	edge_table
	)

Definition at line 95 of file geqo_erx.c.

{
    int         i,
                index1,
                index2;
    int         edge_total;     /* total number of unique edges in two genes */
 
    /* at first clear the edge table's old data */
    for (i = 1; i <= num_gene; i++)
    {
        edge_table[i].total_edges = 0;
        edge_table[i].unused_edges = 0;
    }
 
    /* fill edge table with new data */
 
    edge_total = 0;
 
    for (index1 = 0; index1 < num_gene; index1++)
    {
        /*
         * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
         * maps n back to 1
         */
 
        index2 = (index1 + 1) % num_gene;
 
        /*
         * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
         * twice per edge
         */
 
        edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
        gimme_edge(root, tour1[index2], tour1[index1], edge_table);
 
        edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
        gimme_edge(root, tour2[index2], tour2[index1], edge_table);
    }
 
    /* return average number of edges per index */
    return ((float) (edge_total * 2) / (float) num_gene);
}

References gimme_edge(), i, root, Edge::total_edges, and Edge::unused_edges.

Referenced by geqo().

gimme_tour()

int gimme_tour	(	PlannerInfo *	root,
		Edge *	edge_table,
		Gene *	new_gene,
		int	num_gene
	)

Definition at line 196 of file geqo_erx.c.

{
    int         i;
    int         edge_failures = 0;
 
    /* choose int between 1 and num_gene */
    new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
 
    for (i = 1; i < num_gene; i++)
    {
        /*
         * as each point is entered into the tour, remove it from the edge
         * table
         */
 
        remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
 
        /* find destination for the newly entered point */
 
        if (edge_table[new_gene[i - 1]].unused_edges > 0)
            new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
 
        else
        {                       /* cope with fault */
            edge_failures++;
 
            new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
        }
 
        /* mark this node as incorporated */
        edge_table[(int) new_gene[i - 1]].unused_edges = -1;
    }                           /* for (i=1; i<num_gene; i++) */
 
    return edge_failures;
}

References edge_failure(), geqo_randint(), gimme_gene(), i, remove_gene(), and root.

Referenced by geqo().

init_tour()

void init_tour	(	PlannerInfo *	root,
		Gene *	tour,
		int	num_gene
	)

Definition at line 34 of file geqo_recombination.c.

{
    int         i,
                j;
 
    /*
     * We must fill the tour[] array with a random permutation of the numbers
     * 1 .. num_gene.  We can do that in one pass using the "inside-out"
     * variant of the Fisher-Yates shuffle algorithm.  Notionally, we append
     * each new value to the array and then swap it with a randomly-chosen
     * array element (possibly including itself, else we fail to generate
     * permutations with the last city last).  The swap step can be optimized
     * by combining it with the insertion.
     */
    if (num_gene > 0)
        tour[0] = (Gene) 1;
 
    for (i = 1; i < num_gene; i++)
    {
        j = geqo_randint(root, i, 0);
        /* i != j check avoids fetching uninitialized array element */
        if (i != j)
            tour[i] = tour[j];
        tour[j] = (Gene) (i + 1);
    }
}

References geqo_randint(), i, j, and root.

Referenced by random_init_pool().

ox1()

void ox1	(	PlannerInfo *	root,
		Gene *	mom,
		Gene *	dad,
		Gene *	offspring,
		int	num_gene,
		City *	city_table
	)

Referenced by geqo().

ox2()

void ox2	(	PlannerInfo *	root,
		Gene *	mom,
		Gene *	dad,
		Gene *	offspring,
		int	num_gene,
		City *	city_table
	)

Referenced by geqo().

pmx()

void pmx	(	PlannerInfo *	root,
		Gene *	tour1,
		Gene *	tour2,
		Gene *	offspring,
		int	num_gene
	)

Referenced by geqo().

px()

void px	(	PlannerInfo *	root,
		Gene *	tour1,
		Gene *	tour2,
		Gene *	offspring,
		int	num_gene,
		City *	city_table
	)

Referenced by byteapos(), geqo(), and interpret_function_parameter_list().