meditationatae

Just another WordPress.com site

Update on Parallel Rope Team coloring algorithm

Moalic and Gondran’s Parallel Rope Team coloring algorithm is quite competitive with simulated Quantum Annealing coloring of Titiloye and Crispin, which in the hands of its inventors, broke new records in 2012 on some hard coloring problems on benchmark random graphs:

“Parameter Tuning Patterns for Random Graph Coloring with Quantum Annealing“, Olawale Titiloye and Alan Crispin,

Digital Object Identification (DOI) numbers:

https://doi.org/10.1371/journal.pone.0050060

For a random benchmark graph on 500 vertices with over 62,000 edges, both teams have found valid 47-colorings.

Using PRTcol of Moalic and Gondran ( presented at the GECCO 2017 Conference in Berlin in July 2017, with DOI numbers :

https://doi.org/10.1145/3071178.3071291 ),

I’ve tried to do the same.

Currently, I’m running a program that searches for improper 47-colorings of “the” 500-vertex , density 0.5 graph catalogued as DSJC500.5 and sometimes DSJC500.5.col when in compressed format, so improper colorings with 1 edge conflict. To do this, I have a file that contains approximately 59 improper 47-colorings each having 2 edge conflicts. I essentially use PRTcol, except for the stopping condition, which decides when to “give up” on an evolutionary run, and move on to the next run. Another difference is that I chose at random 4 distinct candidates (improper 47-colorings) from the 59 available with 2 edge conflicts, at the start of a run. I’ve obtained 2 new improper colorings with 1 conflict in 8 hours.

Previously, I had used about 33 colorings with 3 conflicts to find the 59 colorings with 2 conflicts. Along the way, I wanted to optimize the maximum number of generations in a run, before quitting and going on to another run. I estimate this optimum at roughly 720 generattions. In the case of producing colorings with 1 edge conflict, I decided to try maximum = 1500 generations at first. Empirically,

53 57 45 7 num_generation = 358 real_falls = 17 num_conflicts = 1
29 18 47 30 num_generation = 11 real_falls = 0 num_conflicts = 1

is the summary data on the two colorings with just one edge conflict found so far.

In the first solution:

Candidates number 53, 57, 45, and 7 were assembled as a 4-man rope team to in a run, with the mission to search for colorings with <= 1 edge conflicts. After 358 generations, a solution was found during the local search, which is a Tabu search. The team experienced 17 climber falls before finding the solution. The solution has one edge conflict. The terminology is explained in Moalic and Gondran’s GECCO 2017 conference paper, referenced above.

In the second solution, we see it was found after only 11 generations. I will look for the optimum maximum number of generations, but solutions arrive at a rate of one every 4 hours, roughly; so it could take 2-3 days to optimize. Also, I want to have a suitable variety of candidates, i.e. solutions with 1 edge conflict, before I attempt the search for colorings with zero edge conflicts. This number could be 30 candidates, or 5 days at 6 solutions per day.

 

December 2, 2017 insert:

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

I’m currently at 29 47-colorings with precisely one edge conflict, an edge e with both vertices of the same color. I stop a “rope team evolution” after 750 generations, at most. When I reach 30 such colorings, I’ll be ready to search for zero-conflict 47-colorings, which is the hardest of all and could take several days for just one solution.

Below, I copy screen output on the 28 first 1-edge conflict solutions (improper 47-colorings of DSJC500.5):

53 57 45 7 num_generation = 358 real_falls = 17 num_conflicts = 1
29 18 47 30 num_generation = 11 real_falls = 0 num_conflicts = 1
33 25 26 39 num_generation = 526 real_falls = 13 num_conflicts = 1
23 38 12 27 num_generation = 718 real_falls = 35 num_conflicts = 1
47 25 8 46 num_generation = 439 real_falls = 13 num_conflicts = 1
50 18 44 42 num_generation = 574 real_falls = 21 num_conflicts = 1
9 46 42 56 num_generation = 625 real_falls = 18 num_conflicts = 1
32 36 43 29 num_generation = 481 real_falls = 10 num_conflicts = 1
29 21 46 31 num_generation = 267 real_falls = 10 num_conflicts = 1
6 28 51 8 num_generation = 590 real_falls = 28 num_conflicts = 1
39 29 28 45 num_generation = 182 real_falls = 0 num_conflicts = 1
3 0 40 30 num_generation = 190 real_falls = 3 num_conflicts = 1
31 53 50 0 num_generation = 57 real_falls = 0 num_conflicts = 1
29 50 12 40 num_generation = 765 real_falls = 24 num_conflicts = 1
36 56 50 45 num_generation = 2608 real_falls = 35 num_conflicts = 1
40 28 52 9 num_generation = 1047 real_falls = 17 num_conflicts = 1
5 52 22 0 num_generation = 220 real_falls = 1 num_conflicts = 1
7 35 49 39 num_generation = 545 real_falls = 18 num_conflicts = 1
34 9 58 48 num_generation = 428 real_falls = 18 num_conflicts = 1
42 47 35 44 num_generation = 725 real_falls = 26 num_conflicts = 1
4 23 46 10 num_generation = 450 real_falls = 9 num_conflicts = 1
6 54 50 13 num_generation = 243 real_falls = 24 num_conflicts = 1
17 41 1 40 num_generation = 391 real_falls = 8 num_conflicts = 1
28 38 45 43 num_generation = 170 real_falls = 4 num_conflicts = 1
33 11 53 37 num_generation = 345 real_falls = 22 num_conflicts = 1
3 10 54 16 num_generation = 329 real_falls = 11 num_conflicts = 1
57 47 25 41 num_generation = 194 real_falls = 1 num_conflicts = 1
4 50 18 39 num_generation = 495 real_falls = 27 num_conflicts = 1

_________________ END DEC 2ND INSERT _____________________

 

 

 

Below is the source code file, the_powzoomuzzjo97a68.c :

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

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

A C implementation of Parallel Rope Team Coloring of

Moalic and Gondran

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

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

#define MAX_VERTEX 600
#define MAX_COLORS 60

unsigned char adj_mat[MAX_VERTEX][MAX_VERTEX];

int 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;
char color;
char init_coloring[MAX_VERTEX];
char init_population[59][MAX_VERTEX];
char old_init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
char best_color;
long iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
char color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;
FILE *out2;
int is_round_one;
int problem_solved;
int cnodes;
int select;
int temp;
int candidate_count;
int b_candidate;
int can_number;
int num_try;
int ijk;
int answer;
FILE *insol;
int junk;
char initparent1[MAX_VERTEX];
char initparent2[MAX_VERTEX];
char parent1[MAX_VERTEX];
char parent2[MAX_VERTEX];
int count_classes[MAX_COLORS];
int count;
int maxcount;
int is_maxcount[MAX_COLORS];
int total_maxcount;
int b_total_maxcount;
char random_color_choice;
char index_maxcolor;
char chosen_partition;
char gp;
int taken[MAX_VERTEX];
int total_taken;
char child[MAX_VERTEX];
int b_color_classes;
char child1[MAX_VERTEX];
char child2[MAX_VERTEX];
char best_coloring1[MAX_VERTEX];
char best_coloring2[MAX_VERTEX];
int num_generation;
int j1;
int j2;
int ps1[MAX_COLORS];
int ps2[MAX_COLORS];
int diff;
int tmatch;
int is_perfectmatch;
int itmatch[47];
int oksofar;
int quit_do;
int b_sol;
int j3;
int j4;
int ps1b[MAX_COLORS];
int ps2b[MAX_COLORS];
char initparent1b[MAX_VERTEX];
char initparent2b[MAX_VERTEX];
char parent1b[MAX_VERTEX];
char parent2b[MAX_VERTEX];
char child3[MAX_VERTEX];
char child4[MAX_VERTEX];
int itmatchb[47];
char best_coloring1b[MAX_VERTEX];
char best_coloring2b[MAX_VERTEX];
int realfall;

int tmatchark;
int arkdup;
int tark;
int runs;
unsigned char one;
unsigned char zero;
int clg;
int iter_Tcol;
int reponse;

 

one = (unsigned char) 1;

zero = (unsigned char) 0;

 

select = 2;

 

is_round_one = 1;

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

out2 = fopen(“newnovember17at1545A”, “w”);

 

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

 

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

 

seed = 17100878265236724972ULL;
seed = 14607519818599557672ULL;
seed = 16573800653132675660ULL;
seed = 12519423405243906132ULL;
seed = 17354323623922913637ULL;
seed = 13879391473350592641ULL;
seed = 16523780796786991467ULL;
seed = 11750700245178463264ULL;

 

 

 

 

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] = zero;
}
}

 

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

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] == one) && (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< 59 ; 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”);

 

b_sol = ((int) mask)/59;
b_sol = b_sol + 1;

 

 

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

printf(“ok?\n”);

for(runs = 0; runs < 10000; runs++)
{

 

ru = (int) ((KISS^seed)&mask);
j1 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j2 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j3 = ru/b_sol;

ru = (int) ((KISS^seed)&mask);
j4 = ru/b_sol;

 

 

if( (j1!=j2)&&(j1!=j3)&&(j1!=j4)&&(j2!=j3)&&(j2!=j4)&&(j3!=j4) )
{

clg = 1000000;

 

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

 

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

 

for(i = 0 ; i < num_vertex; i++)
{
initparent1b[i] = init_population[j3][i];
}

 

for(i = 0 ; i < num_vertex; i++)
{
initparent2b[i] = init_population[j4][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];
}

 

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

 

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

 

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

quit_do = 0;

realfall = 0;

 

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

 

 

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

if( realfall > 30 )
{
quit_do = 1 ;
}

 

 

if( quit_do == 1)
{
break;
}

 

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

 

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

 

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

 

 

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

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

 

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

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

 

maxcount = 0;

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

 

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

 

total_maxcount = 0;

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

 

 

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

 

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

 

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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 < 47; i++)
{
count_classes[i] = 0;
}

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

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

 

maxcount = 0;

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

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

 

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

 

 

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

 

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

 

 

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

 

for(i = 0; i< num_vertex; i++)
{
if( taken[i] == 0)
{
ru = (int) ((KISS^seed)&mask);
random_color_choice = (char) (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;
}

 

 

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

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

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

 

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

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

maxcount = 0;

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

 

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

total_maxcount = 0;

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

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

 

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

index_maxcolor = 0;

 

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

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

 

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

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 < 47; i++)
{
count_classes[i] = 0;
}

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

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

 

maxcount = 0;

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

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

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

 

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

 

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

 

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

 

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

 

/*** child 3 ***/

 

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

 

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

 

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

 

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

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

 

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

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

maxcount = 0;

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

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

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

 

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

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

 

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

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

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

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

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

 

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

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

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

 

maxcount = 0;

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

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

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

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

 

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

 

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

 

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

 

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

 

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

/*** child 3 done ***/

 

 

/*** child 4 ***/

 

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

 

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

 

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

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

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

 

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

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

 

maxcount = 0;

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

 

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

 

total_maxcount = 0;

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

 

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

 

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

 

index_maxcolor = 0;

 

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

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

 

}

 

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

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

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

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

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

 

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

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

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

 

maxcount = 0;

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

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

total_maxcount = 0;

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

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

 

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

 

index_maxcolor = 0;

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

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

}

 

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

 

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

 

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

 

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

 

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

 

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

 

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

/*** child 4 done ***/

 

num_colors = 47;

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

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; 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;
}
}

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

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
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 < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

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

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
printf(“num_generation = %d\n”, num_generation);

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

 

printf(“\n”);

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

best_delta = 1000000;

 

for(i = 0; i < num_vertex; i++)
{
if(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 = Gamma[i][j] – 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(Gamma[i][init_coloring[i]] > 0)
{
for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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(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 = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

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

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&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] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color] ++ ;
}
}

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

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

 

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

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

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

 

if( problem_solved == 0 )
{

num_colors = 47;

 

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

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; 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;
}
}

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

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
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 < 10)
{
printf(“%d conflicts at %d iterations\n”, num_conflicts, iter_counter);
}

 

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

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
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”);

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

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

best_delta = 1000000;

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

 

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

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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( Gamma[i][init_coloring[i]] > 0)
{

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

for(i = 0; i < num_vertex; i++)
{
if( 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 = (char) j;
}
candidate_count++;
}
}

}
}

 

num_conflicts+= best_delta;

cnodes = 0;

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

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&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] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

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

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

 

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

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

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

 

if( problem_solved == 0)
{

/*** tabu on child 3 ***/

num_colors = 47;

 

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child3[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;
}
}

 

 

iter_Tcol = 9000;

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; 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;
}
}

 

 

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

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
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_coloring1b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

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

 

 

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

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
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”);

 

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

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

 

best_delta = 1000000;

 

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

 

 

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

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

for(i = 0; i < num_vertex; i++)
{
if( 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 = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts+= best_delta;

cnodes = 0;

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

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&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] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

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

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

 

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

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 3 done ***/

/*** run tabu search on child 4 ***/

 

 

 

 

if( problem_solved == 0 )
{

 

/*** tabu on child 4 ***/

num_colors = 47;

 

for(i = 0; i < num_vertex; i++)
{
init_coloring[i] = child4[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;
}
}

 

 

iter_Tcol = 9000;

 

 

 

for(iter_counter = 1; iter_counter < iter_Tcol ; 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;
}
}

 

 

 

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

}
}
}

 

for(i = 0; i < num_vertex; i++)
{
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_coloring2b[i] = init_coloring[i];
}

 

min_conflicts = num_conflicts;

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

 

 

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

printf(“%d %d %d %d\n”, j1, j2, j3, j4);
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”);

 

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

 

 

fprintf(out, “%d %d %d %d “, j1, j2, j3, j4);
fprintf(out, “num_generation = %d “, num_generation);
fprintf(out, “real_falls = %d “, realfall);
fprintf(out, “num_conflicts = %d\n”, num_conflicts);

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

fprintf(out, “\n”);

fflush(out);

 

break;
}
}

 

if( min_conflicts < clg)
{
clg = min_conflicts;
}

 

 

best_delta = 1000000;

 

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

 

 

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

matches_best_delta[i][j] = 0;

if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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( Gamma[i][init_coloring[i]] > 0)
{

 

 

for(j = 0; j < num_colors; j++)
{
if( ((char)j) != init_coloring[i])
{
delta = Gamma[i][j] – 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^seed)&mask);
can_number = ru/b_candidate;

candidate_count = 0;

 

 

for(i = 0; i < num_vertex; i++)
{
if( 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 = (char) j;
}
candidate_count++;
}
}

}
}

 

 

num_conflicts = num_conflicts + best_delta;

cnodes = 0;

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

 

tl = (int) (floor( alpha*((float) cnodes ) + 0.5));
ru = (int) ((KISS^seed)&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] == one)
{
Gamma[i][color_tabu]– ;
Gamma[i][best_color]++ ;
}
}

 

 

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

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

 

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

 

 

if( problem_solved == 1)
{
printf(“the problem is solved\n”);
printf(“what now?\n”);
}

 

/*** run tabu search on child 4 done ***/

 

 

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

if( problem_solved == 0 )
{

 

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

 

 

 

 

 

 

}
/********************************
if( problem_solved == 0)
{

end loop …

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

 

 

 

 

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

if( problem_solved == 0 )
{

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

 

 

 

 

 

 

 

 

 

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

 

int fall_archives_size[47];

 

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

 

 

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

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

 

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

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

 

 

 

for(i = 0; i < 47; i++)
{
ps1[i] = 0;
ps2[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1[parent1[j]]++;
ps2[parent2[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1[i-1]< ps1[i] )
{
temp = ps1[i];
ps1[i] = ps1[i-1];
ps1[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2[i-1]< ps2[i] )
{
temp = ps2[i];
ps2[i] = ps2[i-1];
ps2[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1[i]-ps2[i]);
}

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

 

if( diff == 0 )
{

for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1[i] == ps2[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1[k] == ((char)i) )&&(parent2[k] == ((char)j) )) || ((parent1[k] != ((char)i) )&&(parent2[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatch[i] = 1;
}
else
{
itmatch[i] = 0;
}
}

if( itmatch[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatch[i];
}

if( tmatch >= 45 )
{
realfall++;
}

printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
printf(“perfect match\n”);

/*** compare to archives for size ***/

 

 

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}

 

tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}
}
}

 

 

printf(“%d matches\n”, tmatch);

for(i = 0 ; i < num_vertex; i++)
{
parent2[i] = parent2b[i];
}
}
else
{
printf(“no perfect match\n”);
}
}
/************************************
if( diff == 0 )
{
block of code
**************************************/

 

 

/*** check n = 2 ***/

for(i = 0; i < 47; i++)
{
ps1b[i] = 0;
ps2b[i] = 0;
}

 

for(j = 0; j < num_vertex; j++)
{
ps1b[parent1b[j]]++;
ps2b[parent2b[j]]++;
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps1b[i-1]< ps1b[i] )
{
temp = ps1b[i];
ps1b[i] = ps1b[i-1];
ps1b[i-1] = temp;
}
}
}

 

 

for(j = 0; j < 46; j++)
{
for(i = 1; i < 47-j; i++)
{
if( ps2b[i-1]< ps2b[i] )
{
temp = ps2[i];
ps2b[i] = ps2b[i-1];
ps2b[i-1] = temp;
}
}
}

 

 

diff = 0;

for(i = 0; i< 47; i++)
{
diff = diff + abs(ps1b[i]-ps2b[i]);
}

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

 

if( diff == 0 )
{

 

for(i = 0; i< 47; i++)
{
itmatchb[i] = 0;
}

 

for(i = 0; i< 47; i++)
{
for(j = 0; j<47; j++)
{
if( ps1b[i] == ps2b[j] )
{
is_perfectmatch = 1;

for(k = 0; k< num_vertex; k++)
{
if( ((parent1b[k] == ((char)i) )&&(parent2b[k] == ((char)j) )) || ((parent1b[k] != ((char)i) )&&(parent2b[k] != ((char)j) )) )
{
oksofar = 1;
}
else
{
is_perfectmatch = 0;
break;
}
}

if( is_perfectmatch == 1 )
{
itmatchb[i] = 1;
}
else
{
itmatchb[i] = 0;
}
}

if( itmatchb[i] == 1 )
{
break;
}
}
}

tmatch = 0;

for(i = 0; i< 47; i++)
{
tmatch = tmatch + itmatchb[i];
}

if( tmatch >= 45 )
{
realfall++;

 

 

}

 

printf(“%d matches\n”, tmatch);

if(tmatch >= 45)
{
printf(“perfect match\n”);

 

/**** insert ***/

arkdup = 0;

for(tark = 0; tark< realfall-1; tark++)
{
diff = 0;

if( diff == 0)
{
for(i = 0; i< 47; i++)
{
itmatch[i] = 0;
}
tmatchark = 0;

for(i = 0; i< 47; i++)
{
tmatchark = tmatchark + itmatch[i];
}

// if( tmatchark >= 47 )
// {
// arkdup = 1;
// quit_do = 1;
// }
}
}

for(i = 0 ; i < num_vertex; i++)
{
parent1b[i] = parent1[i];
}
}
else
{
printf(“no perfect match\n”);
}
}
/************************************
if( diff == 0 )
{
block of code
**************************************/
printf(“%d real falls\n”, realfall);

 

 

 

if( 0 == (num_generation%29) )
{

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

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

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 …

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

 

 

}

/*********************
if( j1 != j2)
{
loop end
***********************/

 

 

}

 

fclose(out);
return 0;

}

Advertisements

Written by meditationatae

November 18, 2017 at 7:34 am

Posted in History

%d bloggers like this: