meditationatae

Just another WordPress.com site

Preparation for writing the evolutionary algorithm code

I intend to write code to implement the HEAD or HEAD’ algorithm for graph coloring of Moalic and Gondran:

“Variations on Memetic Algorithms for Graph Coloring Problems”,

https://arxiv.org/abs/1401.2184 .

There, they use the Greedy Partition Crossover or GPX crossover , and their hybrid Tabu Search + evolutionary method is inspired by Galinier and Hao’s HEA algorithm presented in a paper in 1999.

GPX takes two parent approximate solutions and constructs a child approximate solution.

Therefore, I have accumulated a collection of 50-colorings of the 500 vertex graph DSJC500.5.col produced using Tabu Search in preparation for applying the GXP crossover method to them, implementing HEAD or HEAD’ of Moalic and Gondran.

The code in the file newtabuzzu99a.c produces 48 completely unrelated 50-colorings of DSJC500.5.col, and writes them to a file. Subsequently, I checked the 48 colorings with another program to test/check that they truly are genuine 50-colorings. This check/test was passed by the 48 colorings in the file. Thus, we have 48 independent unrelated 50-colorings to which to apply the HEAD/HEAD’ algo. of Moalic and Gondran , including the addition of the GPX crossover.

My initial goal is quite modest: just to try to get a 49-coloring using the method HEAD or HEAD’ of Moalic and Gondran.

The source code of newtabuzzu99a.c will follow. On my computer, it yields one new 50-coloring approximately every 40 minutes, and it starts from “trivial” 500-colorings ( the other way is to use a randomized DSATUR to produce initial colorings with 60-65 colorings). In both cases, a valid 65-coloring is the starting point for an approximate 64-coloring, with one color class from the 65-coloring being abolished and its members redistributed at random among the remaining 64 color classes.

file newtabuzzu99a.c:

=========================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTEX 1000
#define MAX_COLORS 500

int adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int Fast_Gamma[MAX_VERTEX][MAX_COLORS];

int tabu_list[MAX_VERTEX][MAX_COLORS];
int matches_best_delta[MAX_VERTEX][MAX_COLORS];

static unsigned long long Q[2097152], carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int jm=2097151;
jm=(jm+1)&2097151;
x=Q[jm]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[jm]=t-x);
}

#define CNG ( cng=6906969069ULL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(int argc, char *argv[] )
{
FILE *in;
unsigned long long im,cng=123456789987654321ULL, xs=362436069362436069ULL;
unsigned long long mask = 2147483647ULL;
unsigned long long kiss1, kiss2, seed;
int num_colors;
int num_vertex;
int num_edges;
int num_conflicts;
int k;
int i;
int j;
int sum_adj_mat;
int ru;
int b;
int color;
int init_coloring[MAX_VERTEX];
int old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
int best_color;
long iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
int color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
int is_round_one;
int problem_solved;
int cnodes;
int select;
int temp;
long max_iter;
int candidate_count;
int b_candidate;
int can_number;
int num_try;
int ijk;

select = 2;

 

is_round_one = 1;

out = fopen(“solution707”, “w”);

 

alpha = 0.60;
A = 10;
job_done = 0;

seed = 10000845109132110031ULL;
seed = 10686169104128798711ULL;
seed = 16082481622012051572ULL;
seed = 18374146278035435545ULL;
seed = 16152130454896673086ULL;
seed = 5797258859902460576ULL;
seed = 9721747250322017459ULL;

 

 

 

 

 

num_colors = atoi(argv[2]);
printf(“num_colors = %d\n” , num_colors);

in = fopen(argv[1], “r”);

fscanf(in, “%d %d”, &num_vertex, &num_edges);

printf(“num_vertex = %d\n”, num_vertex);
printf(“num_edges = %d\n”, num_edges);

for(i = 0 ; i < MAX_VERTEX; i++)
{
for(j = 0 ; j < MAX_VERTEX; j++)
{
adj_mat[i][j] = 0;
}
}

 

for(k = 0; k < num_edges; k++)
{
fscanf(in, “%d %d”, &j, &i);
if( i != j )
{
adj_mat[i-1][j-1] = 1;
adj_mat[j-1][i-1] = 1;
}

if(i == j)
{
printf(“warning: edge %d is = %d %d\n”, k+1, i, j);
}
}

fclose(in);

sum_adj_mat = 0;

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_vertex; j++)
{
if( (adj_mat[i][j] == 1) && (i!=j) )
{
sum_adj_mat++;
}
}
}

printf(“sum_adj_mat = %d\n”, sum_adj_mat);

printf(“\n”);

 

 

for(ijk = 0; ijk < 50; ijk++)
{

job_done = 0;

printf(“ijk = %d\n”, ijk);

 

num_colors = 500;

 

num_try = 0;

 

 

while( job_done == 0)
{

 

 

 

 

 

 

 

 

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

 

printf(“\n”);

 

printf(“First select a random %d coloring of the %d vertices…\n”, num_colors, num_vertex);

b = ((int) mask)/num_colors;
b = b+1;

 

 

if(is_round_one == 1)
{

 

for(i = 0; i< num_vertex; i++)
{
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
color = ru/b;
init_coloring[i] = color ;
}

}

 

if(is_round_one == 0)
{

 

for(i = 0; i< num_vertex; i++)
{
init_coloring[i] = old_init_coloring[i];
}

select = select + 1;
select = select%num_colors;

 

 

 

for(i = 0; i< num_vertex; i++)
{
if( (init_coloring[i] == select) || (init_coloring[i] == num_colors) )
{
temp = init_coloring[i];

if(temp == select)
{
init_coloring[i]=num_colors;
}

if(temp == num_colors)
{
init_coloring[i]=select ;
}

 

}
}

 

for(i = 0; i< num_vertex; i++)
{
if( init_coloring[i] == num_colors )
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
color = ru/b;
init_coloring[i] = color ;
}
}
}

/****************************************************

if(is_round_one == 0)
{

end block

***********************************************/

 

 

 

 

 

 

 
if(num_colors > 51)
{
max_iter = 200000;
}

 

if(num_colors == 51)
{
max_iter = 1000000;
}

if(num_colors == 50)
{
max_iter = 2000000;
}

if(num_colors <= 49)
{
max_iter = 10 ;
}

 

num_try = num_try +1;

 

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

 

 

 

for(iter_counter = 1; iter_counter < max_iter ; iter_counter++)
{

problem_solved = 0;

 

if( iter_counter == 1)
{
num_conflicts = 0;

printf(“select = %d “, select);
printf(“num_try = %d\n”, num_try);

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
conflict_count = 0;

for(k = 0; k< num_vertex; k++)
{
if( (i != k) && (adj_mat[i][k] == 1) && ( j == init_coloring[k]) )
{
conflict_count++;
}
}

Gamma[i][j] = conflict_count;
Fast_Gamma[i][j] = Gamma[i][j];
}
num_conflicts = num_conflicts + Gamma[i][init_coloring[i]];
}
num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{
min_conflicts = num_conflicts;
if(num_conflicts < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}
if(num_conflicts == 0)
{
problem_solved = 1;
break;
}
}

 

 

 

best_delta = 1000000;

 

 

 

 

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{

matches_best_delta[i][j] = 0;

if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
best_delta = delta;
}
}
}
}
}

candidate_count = 0;

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] – Fast_Gamma[i][init_coloring[i]];

if( delta == best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j] >= iter_counter)&&((delta + num_conflicts+1) <= min_conflicts )))
{
matches_best_delta[i][j] = 1;
candidate_count++;
}
}
}
}
}

b_candidate = ((int) mask)/candidate_count;
b_candidate = b_candidate + 1;
ru = (int) (KISS&mask);
can_number = ru/b_candidate;

candidate_count = 0;

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
if(matches_best_delta[i][j] == 1)
{
if(candidate_count == can_number)
{
best_vertex = i;
best_color = j;
}
candidate_count++;
}
}
}

 

 

num_conflicts = num_conflicts + best_delta;

cnodes = 0;

for(i = 0; i < num_vertex; i++)
{
if( Fast_Gamma[i][init_coloring[i]] > 0)
{
cnodes++;
}
}

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
tabu_rand = ru/b_tabu_rnd;
tl = tl + tabu_rand;
tl = 30;

 

 

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

 

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == 1)
{
Fast_Gamma[i][color_tabu] = Fast_Gamma[i][color_tabu]-1;
Fast_Gamma[i][best_color] = Fast_Gamma[i][best_color]+1;
}
}

 

 

}
/*******************************************

for(iter_counter = 1; iter_counter < max_iter ; iter_counter++)
{

 

end loop …
**************************************/

 

 

 

if( (problem_solved == 1) )
{

if(num_colors == 50)
{

// fprintf(out, “solution for %d colors:\n”, num_colors);

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, “%d %d\n”, i+1, init_coloring[i]+1);
}

fprintf(out, “\n”);

fflush(out);
}

num_colors = num_colors – 1;
// printf(“num_colors = %d\n”, num_colors);

num_try = 0;

is_round_one = 0;

for(i = 0; i < num_vertex; i++ )
{
old_init_coloring[i] = init_coloring[i];
}
}

 

if( (problem_solved == 0)&& (num_colors == 50)&&(num_try >=10) )
{
job_done = 1;
}

if( (problem_solved == 0)&& (num_colors == 49)&&(num_try >=1) )
{
job_done = 1;
}

 

}

/*******************************************************

while( job_done == 0)
{

end loop …

 

********************************************************/

 

}

/********************************************

for(ijk = 0; ijk < 50; ijk++)
{

end loop …

*****************************************/

 

fclose(out);

 
return 0;

}

Advertisements

Written by meditationatae

July 4, 2017 at 10:31 pm

Posted in History

%d bloggers like this: