meditationatae

Just another WordPress.com site

HEA in Duet update (49 colors, DSJC500.5.col )

generation 600 done …

14 conflicts at 18 iterations
13 conflicts at 19 iterations
12 conflicts at 20 iterations
11 conflicts at 22 iterations
10 conflicts at 28 iterations
9 conflicts at 29 iterations
8 conflicts at 33 iterations
7 conflicts at 42 iterations
6 conflicts at 84 iterations
5 conflicts at 248 iterations
4 conflicts at 337 iterations
3 conflicts at 2266 iterations
2 conflicts at 3138 iterations
1 conflicts at 3774 iterations
the problem is not solved
14 conflicts at 18 iterations
13 conflicts at 20 iterations
12 conflicts at 21 iterations
11 conflicts at 22 iterations
10 conflicts at 23 iterations
9 conflicts at 24 iterations
8 conflicts at 33 iterations
7 conflicts at 38 iterations
6 conflicts at 67 iterations
5 conflicts at 119 iterations
4 conflicts at 204 iterations
3 conflicts at 510 iterations
2 conflicts at 2702 iterations
1 conflicts at 3016 iterations
0 conflicts at 3158 iterations
the problem is solved
what now?

===========

Based on :

[1] Laurent Moalic, Alexandre Gondran:

“Variations on Memetic Algorithms for Graph Coloring Problems” ,

https://arxiv.org/abs/1401.2184

and

[2] Philippe Galinier , Jin-Kao Hao:

Hybrid Evolutionary Algorithms for Graph Coloring

The GPX crossover algorithm is discussed in terms of color classes of the child or offspring on page 385 of Galinier and Hao.

Below, source code of file newtabuzzzzzl99a.c, using the method HEAD’ of Moalic and Gondran cited above, to build 49-colorings from 24 given pairs of 50-colorings:

 

#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 init_population[48][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(“solution707”, “w”);

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

 

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

 

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

printf(“ok?\n”);

for(k = 0; k< 48 ; 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 < 24; 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 <= 2000; 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 < 49; gp++)
{

 

 

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

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

 

for( i =0; i < 49; 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 < 49; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

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

 

total_maxcount = 0;

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

for( i =0; i < 49; 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 < 49; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

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

 

 

total_maxcount = 0;

for( i=0; i<49; 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 < 49; 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)/49;
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 < 49; gp++)
{

 

 

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

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

 

for( i =0; i < 49; 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 < 49; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

 

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

 

 

total_maxcount = 0;

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

for( i =0; i < 49; 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 < 49; i++)
{
if( count_classes[i] > maxcount)
{
maxcount = count_classes[i];
}
}

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

 

 

total_maxcount = 0;

for( i=0; i<49; 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 < 49; 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)/49;
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 = 49;

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

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

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

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++)
{
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 = 32;

 

 

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

 

 

num_colors = 49;

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

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

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

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++)
{
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 = 32;

 

 

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

 

 

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 11, 2017 at 1:34 am

Posted in History

%d bloggers like this: