meditationatae

Just another WordPress.com site

newtabuzz99a.c for DIMACS graph DSJC500.5.col

The program uses the improved tabu search from:

Galinier and Hao (1999):

“Hybrid evolutionary algorithms for graph coloring” .

For maximum variability in the colorings, it starts each time with a random 500-coloring of the 500-vertex graph. Starting from a valid k-coloring, a (k-1)-coloring, not necessarily valid, is obtained by distributing the elements of one of the k color classes at random among the k-1 other color classes. This leaves one class empty, so the colors are re-labelled to be in the set: {1, 2, … k-1}.

There is a difference with Tabu Search from Galinier and Hao (1999): the tabu tenure tl is set constant to:

tl = 32;

This seems to produce 50-colorings faster, about 45 minutes.

There’s no guarantee the code follows the tabu search algorithm from Galinier and Hao (1999).

The program doesn’t have the crossover operator GPX, the strong novelty from Galinier and Hao (1999).

The algorithm does a perfunctory search for 49-colorings, but mainly 50-colorings. In 50 loops, it finds 39 different 50-colorings. This takes about 36 hours.

Moalic and Gondran have devised a variant of Galinier and Hao’s HEA named HEAD, HEA in Duet.

ref.:

“Variations on Memetic Algorithms for Graph Coloring Problems”,

https://arxiv.org/abs/1401.2184

It seems indeed that tabu search plus an evolutionary algorithm that hybridizes/combines two parent configurations/colorings to produce a child coloring , going on over up to hundreds of generations, can be very powerful: with hybrid/evolutionary methods, Galinier and Hao obtained a 48-coloring of DSJC500.5.col in their 1999 paper, and Moalic and Gondran obtain a 47-coloring, using HEAD. The papers gives experimental results for several benchmarck graphs.

 

newtabuzz99a.c source code & usage:

usage:

./newtabuzz99a.out DSJC500.5.mt 500

DSJC500.5.mt is DSJC500.5.col but in the format used by Michael Trick’s color.c , i.e. without the comments:

http://mat.gsia.cmu.edu/COLOR/solvers/trick.c

Example:

4 4
1 2
2 3
3 4
1 4

is a file for a graph with vertices {1, 2, 3, 4}, 4 edges, and the edges being: {1,2} , {2,3},  {3,4}  and {1,4}.

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

#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;
int 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;
int max_iter;
int candidate_count;
int b_candidate;
int can_number;
int num_try;
int ijk;

select = 2;

 

is_round_one = 1;

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

 

alpha = 2.00;
A = 16;
job_done = 0;

seed = 10000845109132110031ULL;

 

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

 

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 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;
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 = 100000;
}
else
{
max_iter = 200000;
}

if(num_colors <= 50)
{
max_iter = 1600000;
}

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

 

num_try = num_try +1;

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

problem_solved = 0;

 

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

printf(“select = %d\n”, 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;
}

 

cnodes = 0;

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

 

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

 

 

 

best_delta = 1000000;

 

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 = 16;
tl = tl + tabu_rand;
tl = 32;

 

 

 

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;

 

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

June 27, 2017 at 12:39 pm

Posted in History

%d bloggers like this: