#include "optimizer/geqo.h"

Include dependency graph for geqo_recombination.h:

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

Data Structures
struct	Edge
struct	City
Defines
#define	DAD 1
#define	MOM 0
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)

Define Documentation

#define DAD 1

Definition at line 54 of file geqo_recombination.h.

Referenced by pmx().

#define MOM 0

Definition at line 55 of file geqo_recombination.h.

Typedef Documentation

typedef struct City City

typedef struct Edge Edge

Function Documentation

City* alloc_city_table	(	PlannerInfo *	root,
		int	num_gene
	)

Definition at line 72 of file geqo_recombination.c.

References palloc().

Referenced by geqo().

{
    City       *city_table;

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

    return city_table;
}

Edge* alloc_edge_table	(	PlannerInfo *	root,
		int	num_gene
	)

Definition at line 53 of file geqo_erx.c.

References palloc().

Referenced by geqo().

{
    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;
}

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

Definition at line 47 of file geqo_cx.c.

References geqo_randint, i, City::tour1_position, City::tour2_position, and City::used.

Referenced by bf_decrypt(), bf_encrypt(), bf_init(), geqo(), intctx_free(), rj_decrypt(), rj_encrypt(), and rj_init().

{

    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;
    }

    /* choose random cycle starting position */
    start_pos = geqo_randint(root, num_gene - 1, 0);

    /* 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;

    count++;

    /* 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++;
    }


/* 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++;
            }
        }
    }


/* STEP 3 */

    /* 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++;

    }

    return num_diffs;
}

void free_city_table	(	PlannerInfo *	root,
		City *	city_table
	)

Definition at line 90 of file geqo_recombination.c.

References pfree().

Referenced by geqo().

{
    pfree(city_table);
}

void free_edge_table	(	PlannerInfo *	root,
		Edge *	edge_table
	)

Definition at line 73 of file geqo_erx.c.

References pfree().

Referenced by geqo().

{
    pfree(edge_table);
}

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

Definition at line 92 of file geqo_erx.c.

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

Referenced by geqo().

{
    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 operaton
         * 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);
}

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

Definition at line 193 of file geqo_erx.c.

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

Referenced by geqo().

{
    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;

}

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

Definition at line 38 of file geqo_recombination.c.

References geqo_randint, i, palloc(), and pfree().

Referenced by random_init_pool().

{
    Gene       *tmp;
    int         remainder;
    int         next,
                i;

    /* Fill a temp array with the IDs of all not-yet-visited cities */
    tmp = (Gene *) palloc(num_gene * sizeof(Gene));

    for (i = 0; i < num_gene; i++)
        tmp[i] = (Gene) (i + 1);

    remainder = num_gene - 1;

    for (i = 0; i < num_gene; i++)
    {
        /* choose value between 0 and remainder inclusive */
        next = geqo_randint(root, remainder, 0);
        /* output that element of the tmp array */
        tour[i] = tmp[next];
        /* and delete it */
        tmp[next] = tmp[remainder];
        remainder--;
    }

    pfree(tmp);
}

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

Definition at line 46 of file geqo_ox1.c.

References geqo_randint, and City::used.

Referenced by geqo().

{
    int         left,
                right,
                k,
                p,
                temp;

    /* initialize city table */
    for (k = 1; k <= num_gene; k++)
        city_table[k].used = 0;

    /* select portion to copy from tour1 */
    left = geqo_randint(root, num_gene - 1, 0);
    right = geqo_randint(root, num_gene - 1, 0);

    if (left > right)
    {
        temp = left;
        left = right;
        right = temp;
    }

    /* copy portion from tour1 to offspring */
    for (k = left; k <= right; k++)
    {
        offspring[k] = tour1[k];
        city_table[(int) tour1[k]].used = 1;
    }

    k = (right + 1) % num_gene; /* index into offspring */
    p = k;                      /* index into tour2 */

    /* copy stuff from tour2 to offspring */
    while (k != left)
    {
        if (!city_table[(int) tour2[p]].used)
        {
            offspring[k] = tour2[p];
            k = (k + 1) % num_gene;
            city_table[(int) tour2[p]].used = 1;
        }
        p = (p + 1) % num_gene; /* increment tour2-index */
    }

}

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

Definition at line 46 of file geqo_ox2.c.

References geqo_randint, City::select_list, and City::used.

Referenced by geqo().

{
    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];
    }

}

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

Definition at line 46 of file geqo_pmx.c.

References DAD, geqo_randint, i, palloc(), and pfree().

Referenced by geqo().

{
    int        *failed = (int *) palloc((num_gene + 1) * sizeof(int));
    int        *from = (int *) palloc((num_gene + 1) * sizeof(int));
    int        *indx = (int *) palloc((num_gene + 1) * sizeof(int));
    int        *check_list = (int *) palloc((num_gene + 1) * sizeof(int));

    int         left,
                right,
                temp,
                i,
                j,
                k;
    int         mx_fail,
                found,
                mx_hold;


/* no mutation so start up the pmx replacement algorithm */
/* initialize failed[], from[], check_list[] */
    for (k = 0; k < num_gene; k++)
    {
        failed[k] = -1;
        from[k] = -1;
        check_list[k + 1] = 0;
    }

/* locate crossover points */
    left = geqo_randint(root, num_gene - 1, 0);
    right = geqo_randint(root, num_gene - 1, 0);

    if (left > right)
    {
        temp = left;
        left = right;
        right = temp;
    }


/* copy tour2 into offspring */
    for (k = 0; k < num_gene; k++)
    {
        offspring[k] = tour2[k];
        from[k] = DAD;
        check_list[tour2[k]]++;
    }

/* copy tour1 into offspring */
    for (k = left; k <= right; k++)
    {
        check_list[offspring[k]]--;
        offspring[k] = tour1[k];
        from[k] = MOM;
        check_list[tour1[k]]++;
    }


/* pmx main part */

    mx_fail = 0;

/* STEP 1 */

    for (k = left; k <= right; k++)
    {                           /* for all elements in the tour1-2 */

        if (tour1[k] == tour2[k])
            found = 1;          /* find match in tour2 */

        else
        {
            found = 0;          /* substitute elements */

            j = 0;
            while (!(found) && (j < num_gene))
            {
                if ((offspring[j] == tour1[k]) && (from[j] == DAD))
                {

                    check_list[offspring[j]]--;
                    offspring[j] = tour2[k];
                    found = 1;
                    check_list[tour2[k]]++;
                }

                j++;
            }

        }

        if (!(found))
        {                       /* failed to replace gene */
            failed[mx_fail] = (int) tour1[k];
            indx[mx_fail] = k;
            mx_fail++;
        }

    }                           /* ... for */


/* STEP 2 */

    /* see if any genes could not be replaced */
    if (mx_fail > 0)
    {
        mx_hold = mx_fail;

        for (k = 0; k < mx_hold; k++)
        {
            found = 0;

            j = 0;
            while (!(found) && (j < num_gene))
            {

                if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
                {
                    check_list[offspring[j]]--;
                    offspring[j] = tour2[indx[k]];
                    check_list[tour2[indx[k]]]++;

                    found = 1;
                    failed[k] = -1;
                    mx_fail--;
                }

                j++;
            }

        }                       /* ... for   */

    }                           /* ... if    */


/* STEP 3 */

    for (k = 1; k <= num_gene; k++)
    {

        if (check_list[k] > 1)
        {
            i = 0;

            while (i < num_gene)
            {
                if ((offspring[i] == (Gene) k) && (from[i] == DAD))
                {
                    j = 1;

                    while (j <= num_gene)
                    {
                        if (check_list[j] == 0)
                        {
                            offspring[i] = (Gene) j;
                            check_list[k]--;
                            check_list[j]++;
                            i = num_gene + 1;
                            j = i;
                        }

                        j++;
                    }

                }               /* ... if    */

                i++;
            }                   /* end while */

        }
    }                           /* ... for   */

    pfree(failed);
    pfree(from);
    pfree(indx);
    pfree(check_list);
}

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

Definition at line 46 of file geqo_px.c.

References geqo_randint, i, and City::used.

Referenced by geqo().

{

    int         num_positions;
    int         i,
                pos,
                tour2_index,
                offspring_index;

    /* initialize city table */
    for (i = 1; i <= num_gene; i++)
        city_table[i].used = 0;

    /* choose random positions that will be inherited directly from parent */
    num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);

    /* choose random position */
    for (i = 0; i < num_positions; i++)
    {
        pos = geqo_randint(root, num_gene - 1, 0);

        offspring[pos] = tour1[pos];    /* transfer cities to child */
        city_table[(int) tour1[pos]].used = 1;  /* mark city used */
    }

    tour2_index = 0;
    offspring_index = 0;


    /* px main part */

    while (offspring_index < num_gene)
    {

        /* next position in offspring filled */
        if (!city_table[(int) tour1[offspring_index]].used)
        {

            /* next city in tour1 not used */
            if (!city_table[(int) tour2[tour2_index]].used)
            {

                /* inherit from tour1 */
                offspring[offspring_index] = tour2[tour2_index];

                tour2_index++;
                offspring_index++;
            }
            else
            {                   /* next city in tour2 has been used */
                tour2_index++;
            }

        }
        else
        {                       /* next position in offspring is filled */
            offspring_index++;
        }

    }

}

Header And Logo

geqo_recombination.h File Reference

Data Structures

Defines

Typedefs

Functions

Define Documentation

Typedef Documentation

Function Documentation