color_kit.c

C语言开发的微粒群优化算法源程序

	
for (d=0;d<post.size;d++)
	{
	if (post.x[d]<=NA) continue;
		post.x[d]=pos.x[d]-c_min;
	}

return post;
}


// ----------------------------------------------------------------------------- CONVERT_COLOR_TO_POSITION
struct position	convert_color_to_position(struct color color)
{
/*
struct color		{int size;int val[Max_DD];int max;int adm;};
struct position		{int size;float x[Max_DD];float f;float ep;float prev_f[10];};


WARNING: you need to use complete_part() after that, or, at least
to evaluate pos.f
*/
int				i;
struct position pos;

for (i=0;i<color.size;i++)
{
	pos.x[i]=(float)color.val[i];

}
pos.size=color.size;
return pos;

}


// ----------------------------------------------------------------------------- CONVERT_POSITION
struct position	convert_position(struct position pos)
{
/*
Conversion before to display/result.
FAP/LCP particular case (the internal representation of a position is not
directly the coloring)
*/
float			DD;
struct position post;


post=pos;
DD=(float)pos.size;

	
// Shift

post=color_shift(pos);
	

/*
// Scale 

for (d=0;d<pos.size;d++)
	{
	post.x[d]=post.x[d]/DD;
	}
*/

return post;
}

// ----------------------------------------------------------------------------- CONVERT_POSITION_TO COLOR
struct color	convert_position_to_color(struct position pos)
{
/*
struct position		{int size;float x[Max_DD];float f;float ep;float prev_f[10];};
struct color		{int size;int val[Max_DD];int max;int adm;};

WARNING: after that, you need to use diff_color() and to evaluate if it is admissible or not 
*/
int				i;
struct color 	color;

for (i=0;i<pos.size;i++)
{
	color.val[i]=(int)pos.x[i];

}
color.size=pos.size;
return color;

}

// ----------------------------------------------------------------------------- DIFF_COLOR
int diff_color(struct position color)
{
// Count how many different colors are used
// WARNING: global variable NA must be <0 and abs(NA) must be greater than any possible color. NA means non assigned
int					c;
int					i0,i,j;
int					n_color;
int					times[1001];


for (i0=0;i0<color.size;i0++)
{
	c=(int)color.x[i0];
	if (c<=NA) continue;
		times[i0]=c;
		n_color=1;
		goto diff;	
}
return 0;


diff:
if (i0==color.size-1) return n_color;

for (i=i0+1;i<color.size;i++)
{
	c=(int)color.x[i];
	if (c<=NA) continue;


	for (j=0;j<n_color;j++)
	{
		if (c==times[j]) goto next_i;
	}
	times[n_color]=c;
	n_color=n_color+1;

next_i:;
}

return n_color;

}


// ----------------------------------------------------------------------------- DIFF_COLOR_LIST
struct vector diff_color_list(struct position color)
{
// Find the list of different colors used
// WARNING: global variable NA must be <0 and abs(NA) must be greater than any possible color. NA means non assigned
float					c;

struct vector		color_list;
int					i0,i,j;


color_list.size=0;
for (i0=0;i0<color.size;i0++)
{
	c=color.x[i0];
	if (c<=NA) continue;
		color_list.x[color_list.size]=c;
		color_list.size=1;
		goto diff;	
}
return color_list; // No assigned colors at all


diff:
if (i0==color.size-1) return color_list; // Just one color

for (i=i0+1;i<color.size;i++)
{
	c=color.x[i];
	if (c<=NA) continue;


	for (j=0;j<color_list.size;j++) // Check if already counted
	{
		if (c==color_list.x[j]) goto next_i;
	}
	color_list.x[color_list.size]=c;
	color_list.size=color_list.size+1;

next_i:;
}

return color_list;


}

// ----------------------------------------------------------------------------- DISPLAY_MATRIX
void display_matrix(struct matrix M)
{
int	i,j;

printf("\n\n Matrix, size %i \n",M.size);

for (i=0;i<M.size;i++)
{
	for (j=0;j<M.size;j++)
		printf("%i ",M.val[i][j]);
	printf("\n");
}
}

// ----------------------------------------------------------------------------- ENERGY_COLOR
float energy_color (struct position color,struct matrix M,struct dplus dplus,float f0,float f1)
{
int i,j,k;
float d;
float e=0;

for (i=0;i<M.size;i++)
	{
	for (j=0;j<dplus.dplus[i].size;j++)
		{
		k=dplus.dplus[i].val[j];
		if (k<=i) continue; // Symmetric matrix
		
		d=(float)fabs(color.x[i]-color.x[k])-M.val[i][k];
		if (d>0) d=f1*d; // Too satisfied constraint
		if (d<0) d=-f0*d; // Unsatisfied constraint
		e=e+d;
//printf("\n (%i,%i) d_energy %f",i,k,d);	
		}
	}

return e;
}

// ----------------------------------------------------------------------------- GENER_PARTICLE_COLOR
struct particle	gener_particle_color(struct swarm sw,int part_rank,struct param param,struct model model)
{
/* Generate a new particle, according to the particle of rank part_rank (supposed to be a good one)

*/
int				g;
struct subswarm	hood;
int				i;
struct particle part0,part1,part;


//printf("\n gener_particle_color");


part0=sw.part[part_rank];

// Find another good particle, as far as possible

i=part_rank+sw.size/2;
if (i>=sw.size) i=i-sw.size;

 //  ... find neighborhood best (sequential)
hood=hood_swarm(sw,i,param.eps);
g=hood.rank[hood.best];

part1=sw.part[g];

// Combine part1 and part2

part=part0;

/*
for (i=0;i<part0.pos.size;i++)
{
	r=alea_float(0,1);
	if (r<0.5)
	{
		part.pos.x[i]=part1.pos.x[i];
		part.vel.v[i]=part1.vel.v[i];
	}
}
*/

i=alea(0,part0.pos.size-1);

part.pos.x[i]=alea_float(param.H.min[i],param.H.max[i]); // Partial cloning
part.vel.v[i]=0;


part.pos.label=label[level];

label[level]=label[level]+1;
part.prev_best.label=label[level];
part=complete_part(part,param, model);


//printf("  %f => %f",part0.pos.f,part.pos.f);
//display_position(part0.pos);
//display_position(part.pos);
return part;
}


// ----------------------------------------------------------------------------- INIT_COLOR_1
struct position init_color_1(struct matrix M, struct dplus dplus,int cmin, int cmax)
{
/*
while there is a non colored node
	choose at random a non colored node i
	assign to i a randomly chosen consistent color
end while
*/
int					c;
struct position 	color;
struct vector_int	colored_nodes;
struct vector_int	color_values;
struct vector_int	non_colored_nodes;
int					i;
int					j;
int					k;

int					node;
int					rank;


color.size=M.size;

//printf("\n Random coloring 1");

non_colored_nodes.size=M.size; // At the beginning, all nodes are not colored
for (i=0;i<M.size;i++)
	non_colored_nodes.val[i]=i;
	
colored_nodes.size=0; // No colored nodes at all

// Set color to NA (arbitrary negative value for "not colored")

for (i=0;i<color.size;i++) 
	color.x[i]=(float)NA;


next_node:

// Choose at random a non colored node

rank=alea(0,non_colored_nodes.size-1);
node=non_colored_nodes.val[rank];

//printf("\n rank, size, node, %i %i %i",rank,non_colored_nodes.size,node);

// Build a list of consistent colors for the current node
// according to the nodes already colored

color_values.size=0;
c=cmin; 

try_c:
if (colored_nodes.size>0)
{
	check_color:
	
	for (i=0;i<dplus.dplus[node].size;i++) // For each neighbour
	{
		j=(int)dplus.dplus[node].val[i];
		k=(int)color.x[j]; // ... check the color
		if (k<=NA) continue; // ... not colored => consistent
			if (fabs(c-k)<M.val[node][j]) // If color c is not admissible ...
			{
				c=c+1; // ... increase it ...
				goto check_color; // ... and try again.
			}
	}
}
	
color_values.val[color_values.size]=c;
color_values.size=color_values.size+1;
if (c<cmax && color_values.size<Max_DD)
{
	c=c+1;
	goto try_c;
}
	
// Choose one at random

c=color_values.val[alea(0,color_values.size-1)];
	
//printf("\n  coloring node %i",node+1);
//printf(" with color %i",c);

colored_nodes.val[colored_nodes.size]=node; // Save which node has been colored
colored_nodes.size=colored_nodes.size+1; 
color.x[node]=(float)c; // Save the color of the node
if (colored_nodes.size>=color.size) goto end;

// Compact the list of non colored nodes

if (rank<non_colored_nodes.size-1)
{
	for (i=rank;i<non_colored_nodes.size-1;i++)
	{
		non_colored_nodes.val[i]=non_colored_nodes.val[i+1];
	}
	non_colored_nodes.size=non_colored_nodes.size-1;
}

// Loop as long as some nodes are still not colored
goto next_node;

end:
//display_position(color);

return color;
}


// ----------------------------------------------------------------------------- INIT_PARTICLE_COLOR
struct particle	init_particle_color(struct param param,struct model model, struct matrix M, struct dplus dplus,int type)
{ // Special initialization of a particle for Coloring/Frequency assignment problem
int				cmax;
int				d;
struct particle part;
int				xmin,xmax;


//printf("\n init_particle_color, type %i. H = %i",type,H);


part.pos.size=param.DD;
part.vel.size=param.DD;
part.H=H; // Useful for model.H=3
H=3-H; // Switch projection space

xmin=(int)param.H.min[0];
xmax=(int)param.H.max[0]; // Maximum possible color

cmax=(int)param.max_fr; // Max number of colors wanted

if (param.combin==0)
{
	for( d = 0;d<param.DD;d++)  //for each dimension
	{
		part.vel.v[d] = 0;

		//part.vel.v[d] = alea_float(param.H.min[d],param.H.max[d]);
	}
}
else
{
part.vel=alea_velocity (param.DD,param); // Cf combinatorial kit
}
part.vel.ek=0; // Kinetic energy



if (type==-1) // Generate a "null" particle
{
	for( d = 0;d<param.DD;d++)  //for each dimension
	{
		part.pos.x[d] = 0; 
	}

	return part;
}

if (type==-2) // Generate a special particle
{
	for( d = 0;d<param.DD;d++)  //for each dimension
	{
		  part.pos.x[d] = (float)dplus.dplus[d].size; 
	}

	return part;
}


if (model.init_type==0) // Random
{
	for( d = 0;d<param.DD;d++)  //for each dimension
	{
		part.pos.x[d] = (float)alea((int)param.H.min[d],(int)param.H.max[d]);   //x(i,d) in [xmin, xmax]
	}

}
		

if (model.init_type==1) // Use init method 1
{
	part.pos=init_color_1( M, dplus,xmin,xmax);
}



return part;
}

// ----------------------------------------------------------------------------- MAX_COLOR_RANK
int	max_color_rank(struct position pos)
{
// Give the rank of a node with the max color
float	cmax;
int	i;
int	max;
struct vector_int	rank;

// Find the max color
max=0;
cmax=pos.x[0];

for (i=1;i<pos.size;i++)
{
	if (pos.x[i]<=cmax) continue;
		cmax=pos.x[i];
		max=i;
}

// Build the list of "bad" nodes
rank.size=0;
for (i=0;i<pos.size;i++)
{
	if (pos.x[i]<cmax) continue;
		rank.val[rank.size]=i;
		rank.size=rank.size+1;
}

// Choose one at random
i=alea(0,rank.size-1);
max=rank.val[i];

return max;
}

// ----------------------------------------------------------------------------- MINIMIZE_COLOR
struct particle minimize_color(struct particle part,int cmax)
{
/*
Try to find the nearest position with just cmax colors, even if some constraints are not satisfied


while there is too many different colors
	choose the color which is involved in the fewest number of constraints
	replace it by the nearest different color already used
	

*/

float			c;
int				i;
float			new_color;
int				node;
struct particle	partt;
struct vector	color_list;
float			total;
float			tot_min;
float			worst_color;

//printf("\n minimize_color");
partt=part;

check:

color_list=diff_color_list(partt.pos);


//printf("\n minimize_color %i / ",color_list.size);

/*
for (i=0;i<color_list.size;i++)
	printf(" %.0f",color_list.x[i]);
*/


	
if (color_list.size<=cmax) 

{

//printf("\n end of minimize_color");	

	return partt;

}

//display_position(partt.pos);
// Find the worst color
tot_min=(float)dplus.dtot+1; 

for (i=0;i<color_list.size;i++)
{
	c=color_list.x[i]; // color to check
	
	total=0;
	for (node=0;node<M.size;node++)
	{
		if (partt.pos.x[node]!=c) continue;
			total=total+dplus.dplus[node].size;
	}
	if (total<tot_min)
	{
		worst_color=c;