meditationatae

Just another WordPress.com site

Source code of July 14 to test HEA in Duet, version HEAD’

The source code file, pnewtbuza75a.c , can be compiled using the GCC compiler as follows:

gcc -lm -O2 -o pnewtbuza75a.out pnewtbuza75a.c

To run the program, at the Unix shell prompt, I type:

./pnewtbuza75a.out DSJC500.5.mt 500

DSJC500.5.mt is a file containing a description of the 500-vertex DSJC500.5 graph created by David Johnson. In substance, it can be found here:

http://mat.gsia.cmu.edu/COLOR04/INSTANCES/DSJC500.5.col

The format in DSJC500.5.mt removes from the above the header comment lines with a “c” in them, removes “p edge” from the line:

p edge 500 62624

and finally removes all the e’s from the ~= 60,000 lines listing the edges.

Additionally, the program reads in a file of 14 improper 48-olorings, whose name is “againrndsolution202”. This will be in the next post.

From the previous post, should someone verify or find errors in the claimed 48-colorings of the graph DSJC500.5, from the Second DIMACS challenge, I’d be very interested in finding out, either way. My email address is david250 (at) videotron (dot) ca  .

The July 14 source code file is copied below.

 

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

HEAD’ graph coloring algorithm

implementation from HEA in Duet

by Moalic and Gondran, France.

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

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

#define MAX_VERTEX 600
#define MAX_COLORS 60
#define TABUL 28

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 init_population[14][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;
int answer;
FILE *insol;
int junk;
int initparent1[MAX_VERTEX];
int initparent2[MAX_VERTEX];
int parent1[MAX_VERTEX];
int parent2[MAX_VERTEX];
int count_classes[MAX_COLORS];
int count;
int maxcount;
int is_maxcount[MAX_COLORS];
int total_maxcount;
int b_total_maxcount;
int random_color_choice;
int index_maxcolor;
int chosen_partition;
int gp;
int taken[MAX_VERTEX];
int total_taken;
int child[MAX_VERTEX];
int total_vertices_added;
int b_color_classes;
int child1[MAX_VERTEX];
int child2[MAX_VERTEX];
int best_coloring1[MAX_VERTEX];
int best_coloring2[MAX_VERTEX];
int num_generation;
int num_pair;

 

 

 

select = 2;

 

is_round_one = 1;

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

insol = fopen(“againrndsolution202”, “r”);

 

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

seed = 10000845109132110031ULL;
seed = 10686169104128798711ULL;
seed = 16082481622012051572ULL;
seed = 18374146278035435545ULL;

 

 

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”);

 

printf(“now, read in initial population …\n\n”);

printf(“ok?\n”);

for(k = 0; k< 14 ; k++)
{
for(i = 0 ; i < num_vertex; i++)
{
fscanf(insol, “%d”, &junk);
fscanf(insol, “%d”, &color);
init_population[k][i] = color-1;
}
}

fclose(insol);

 

 

printf(“initial population read in …\n\n”);

printf(“ok?\n”);

 

 

 

printf(“now, select the two initial parents from 48…\n”);

printf(“ok?\n”);

 

 

 

for( num_pair = 0; num_pair < 7; num_pair++)
{

 

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1[i] = init_population[0+2*num_pair][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2[i] = init_population[1+2*num_pair][i];
}

 

printf(“selection of the two initial parents done…\n”);

printf(“ok?\n”);

 
printf(“set parent1 and parent2 and prepare for GPX algorithm…\n”);

 

printf(“ok?\n”);

 

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = initparent1[i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = initparent2[i];
}

 

 

printf(“parent1 and parent2 set.\n”);

 

 

for( num_generation = 1; num_generation <= 1000; num_generation++)
{

 

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

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

 

 

total_vertices_added = 0;

 

 

for( gp = 0; gp < 48; gp++)
{

 

 

if( 0 == (gp%2) )
{

for(i = 0; i < 48; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 48; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == i)&&(taken[j] == 0) )
{
count = count + 1;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 48; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 48; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

total_maxcount = 0;

for( i=0; i<48; i++)
{
total_maxcount = total_maxcount + is_maxcount[i];
}

 

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_total_maxcount;
random_color_choice++;

 

 

index_maxcolor = 0;

 

for( i =0; i < 48; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
total_vertices_added++;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

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

if( 0 == (gp%2) )
{

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

 

 

if( 1 == (gp%2) )
{
for(i = 0; i < 48; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 48; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == i) &&(taken[j] == 0) )
{
count = count + 1;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 48; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 48; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

 

total_maxcount = 0;

for( i=0; i<48; i++)
{
total_maxcount = total_maxcount + is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_total_maxcount;
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 48; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = i;
}
}

}

 

 

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
total_vertices_added++;
}
}

 

 

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

 

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

 

 

total_taken = 0;

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 1)
{
total_taken++;
}
}

 

b_color_classes = ((int) mask)/48;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_color_classes;
child[i] = random_color_choice;
}
}

 

for(j=0; j < num_vertex; j++)
{
child1[j] = child[j] ;
}

 

/*** child2 below … ***/

 

 

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

 

for(i = 0; i< num_vertex; i++)
{
child[i] = -1;
}

 

 

 

total_vertices_added = 0;

 

 

for( gp = 0; gp < 48; gp++)
{

 

 

if( 0 == (gp%2) )
{

for(i = 0; i < 48; i++)
{
count_classes[i] = 0;
}

 

for( i =0; i < 48; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == i)&&(taken[j] == 0) )
{
count = count + 1;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 48; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

for( i =0; i < 48; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

 

total_maxcount = 0;

for( i=0; i<48; i++)
{
total_maxcount = total_maxcount + is_maxcount[i];
}

 

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_total_maxcount;
random_color_choice++;

 

 

index_maxcolor = 0;

 

for( i =0; i < 48; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = i;
}
}

 

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent2[j] == chosen_partition) && ( taken[j] == 0) )
{
child[j] = gp;
total_vertices_added++;
}
}

for(j = 0; j< num_vertex; j++)
{
if( parent2[j] == chosen_partition )
{
taken[j] = 1;
}
}

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

if( 0 == (gp%2) )
{

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

 

 

if( 1 == (gp%2) )
{
for(i = 0; i < 48; i++)
{
count_classes[i] = 0;
}

for( i =0; i < 48; i++)
{
count = 0;

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == i) &&(taken[j] == 0) )
{
count = count + 1;
}
}
count_classes[i] = count;
}

 

maxcount = 0;

for( i =0; i < 48; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

for( i =0; i < 48; i++)
{
if(count_classes[i] == maxcount)
{
is_maxcount[i] = 1;
}
else
{
is_maxcount[i] = 0;
}
}

 

 

total_maxcount = 0;

for( i=0; i<48; i++)
{
total_maxcount = total_maxcount + is_maxcount[i];
}

 

b_total_maxcount = ((int) mask)/total_maxcount;
b_total_maxcount = b_total_maxcount + 1;

 

kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_total_maxcount;
random_color_choice++;

 

index_maxcolor = 0;

for( i =0; i < 48; i++)
{
if( is_maxcount[i] == 1 )
{
index_maxcolor++;
}

if( is_maxcount[i] == 1 )
{
if(index_maxcolor == random_color_choice)
{
chosen_partition = i;
}
}

}

 

for(j = 0; j< num_vertex; j++)
{
if( (parent1[j] == chosen_partition)&&(taken[j] == 0) )
{
child[j] = gp;
total_vertices_added++;
}
}

 

 

for(j = 0; j< num_vertex; j++)
{
if( parent1[j] == chosen_partition )
{
taken[j] = 1;
}
}

 

}
/*************************************
if( 1 == (gp%2) )
{
end of loop…
*************************************/

 

 

}
/*************************************
for( gp = 0; gp < 49; gp++)
{
end of loop…
*************************************/

 

 

 

total_taken = 0;

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 1)
{
total_taken++;
}
}

 

b_color_classes = ((int) mask)/48;
b_color_classes = b_color_classes + 1;

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
kiss1 = KISS;
kiss2 = kiss1^seed;
ru = (int) (kiss2&mask);
random_color_choice = ru/b_color_classes;
child[i] = random_color_choice;
}
}

 

 

 

for(j=0; j < num_vertex; j++)
{
child2[j] = child[j] ;
}

 

 

num_colors = 48;

max_iter = 8000 ;

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

 

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 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;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
Fast_Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_vertex; k++)
{
if(adj_mat[i][k] == 1)
{
Gamma[i][init_coloring[k]]++;
Fast_Gamma[i][init_coloring[k]]++;
}
}
}

 

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

num_conflicts = num_conflicts/2;
}

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

 

if(num_conflicts < 15)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

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

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

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

printf(“\n”);

fprintf(out, “num_pair = %d\n”, num_pair);
fprintf(out, “num_generation = %d\n”, num_generation);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

 

 

best_delta = 1000000;

 

 

 

 

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

 

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++)
{
if(Fast_Gamma[i][init_coloring[i]] > 0)
{

 

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++)
{
if(Fast_Gamma[i][init_coloring[i]] > 0)
{

 

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;

 

 

 

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)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}
else
{
printf(“the problem is not solved\n”);
}

 

/*** run tabu search on child2 ***/

 

if( problem_solved == 0 )
{

num_colors = 48;

max_iter = 8000 ;

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

 

 

min_conflicts = 1000000;

 

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 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;

 

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_colors; k++)
{
Gamma[i][k] = 0;
Fast_Gamma[i][k] = 0;
}
}

for(i = 0; i < num_vertex; i++)
{
for(k = 0; k< num_vertex; k++)
{
if(adj_mat[i][k] == 1)
{
Gamma[i][init_coloring[k]]++;
Fast_Gamma[i][init_coloring[k]]++;
}
}
}

 

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

num_conflicts = num_conflicts/2;
}

 

 

if( num_conflicts < min_conflicts )
{

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

 

min_conflicts = num_conflicts;

if(num_conflicts < 15)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

 

 

 

 

 

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

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

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

printf(“\n”);

fprintf(out, “num_pair = %d\n”, num_pair);
fprintf(out, “num_generation = %d\n”, num_generation);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

 

best_delta = 1000000;

 

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

 

 

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++)
{
if( Fast_Gamma[i][init_coloring[i]] > 0)
{

 

 

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++)
{
if( Fast_Gamma[i][init_coloring[i]] > 0)
{

 

 

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;

 

 

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)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}
else
{
printf(“the problem is not solved\n”);
}

 

/*** run tabu search on child2 done ***/

 

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

if( problem_solved == 0 )
{

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

 

for(i = 0 ; i < num_vertex; i++)
{
parent1[i] = best_coloring1[i];
}

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = best_coloring2[i];
}

 

printf(“generation %d done … \n”, num_generation);

 

printf(“\n”);

if( problem_solved == 1)
{
break;
}

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

for( num_generation = 1; num_generation <= 10000; num_generation++)
{

end of loop …

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

 

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

for( num_pair = 0; num_pair < 24; num_pair++)
{

end of loop ….

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

 

 

fclose(out);

 
return 0;

}

Advertisements

Written by meditationatae

July 14, 2017 at 6:22 am

Posted in History

%d bloggers like this: