color_kit.c

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

				if (coin==4) {d1=0;d2=-1;}
			}
			if (c1>c2) // (1,0) or (0,-1)
			{
				coin=alea(0,1);
				d1=(float)coin;
				d2=(float)coin-1;
			}
			
			if (c1<c2) // (-1,0) or (0,1)
			{
				coin=alea(0,1);
				d2=(float)coin;
				d1=(float)coin-1;
			}
			d1=-d1; // (because diff is <0)
			d2=-d2;
		}
//printf("\n node %i diff=%f, d1= %f, d2= %f",node,diff,d1,d2);
			
			delta[node]=delta[node]+d1*diff;
			delta[j]=delta[j]+d2*diff;	
	}//next neighbour
	//delta[node]=delta[node]-f2*c1;// Try to be as small as possible
	//delta[node]=delta[node]-f2;// Try to be as small as possible
//printf("\n reduce node %i d= %.2f",node,-f2*c1); 
	}// next node
		

//printf("\n %i unconsistencies", uncons);

//if (uncons<=uncons_max) printf("\n CONSISTENT");


// Change the colors
for (node=0;node<dim;node++) 
	{
/*
	if (delta[node]>0) {d=1;}
	if (delta[node]<0) {d=-1;}
	if (delta[node]==0) d=0;
*/
	d=delta[node];
//printf("\n node %i, color %.2f. ",node, colort.x[node]);
	colort.x[node]=colort.x[node]+d*step;
//printf(" delta %.2f, delta*step %.2f => color %.2f",delta[node],d*step,colort.x[node]);
	}
E0=E1;
E1=E2;	
E2=energy_color(colort,M,dplus,f0,f1);	
 if (trace>2) printf("\n E0 E2 %f %f",E0,E2);
// "parapet" criterion: the same energy from a too long time

if (E2>=E0) 
{
	if (trace>1) printf("\n /  Stop by no improvement");
	goto end;
}

// Normal stop criterion: energy small enough
if (E2>Emin)
{
	goto loop;
}

//--------------------
end:

if (trace >1) 
{
	display_position(colort);
	printf("\nDistance between color0 and colort: %f",distance(color0,colort));
}

uncons=check_color(convert_position_to_color(colort),M,dplus);
//Admissible ?
if (uncons==0) colort.adm=1; else colort.adm=0;

if (trace>1)
	{
	if (colort.adm==0) printf("\n color_6. (non admissible)");
	}
return colort;
}


// ----------------------------------------------------------------------------- COLOR_8
struct position	color_8(struct position color,struct matrix M, struct dplus dplus,int trace)
{
/*
Try to improve a coloring:

Built the list of the "bad" nodes (using the max color)
Try to modify the color of at least one of the bad nodes

First, try to decrease just the color of the node.
	If it works, keep this coloring, and try to improve again.
	
	If it doesn't work, try for pairs of nodes: 
	For each neighbour i, look if it has several possibilities
	all better than colort.max. For each pair of these possibilities (c,c'),
 	try to put c on i and c' on max_node.
	If it works, keep this coloring, and try to improve again.
	
	If it doesn't work, try with three nodes at a time



  If it still doesn't work, well, give up!

NOTE: valid only with granularity = 1  (colors are integers)

*/

int				c,c1,c2;
int				cmax;

struct position	colort;

int				colort_max;

int				colort_max0;
int				i;
int				improv;
int				j,j1,j2;
int				k,k1,k2;
int				maxcolor;
int				n_not;
int				neighbour1,neighbour2;

int				OK;


int				worst;
struct vector_int	worst_node;


if (trace>0)

	{
	printf("\n Color_8 (improvement) ");	
	}

colort=color;
colort_max=diff_color(colort);// Max number of different colors
improv=0; // No improvement, to begin!

improve:
OK=0;


// Built the list of the "bad" nodes (using the max color)
maxcolor=0;
for (i=0;i<colort.size;i++) // Find the max color
	if (colort.x[i]>maxcolor) maxcolor=(int) colort.x[i];


	
worst_node.size=0; // Built the list
for (i=0;i<colort.size;i++)
	{
	if (colort.x[i]<maxcolor) continue;
		worst_node.val[worst_node.size]=i;
		worst_node.size=worst_node.size+1;
	}



// Try to modify the color of at least one of the worst nodes

for (i=0;i<worst_node.size;i++)
	{
	worst=worst_node.val[i];

	cmax=(int) color.x[worst];
	if (cmax<maxcolor) continue; // (it may already have been improved as a neighbour)
	
	for (c=0;c<cmax;c++) // try a new color for "worst"
		{
		n_not=0;
		for (j=0;j<dplus.dplus[worst].size;j++) // try each neighbour
			{
			k=dplus.dplus[worst].val[j]; // (k is the neighbour of "worst")
			if (fabs(c-colort.x[k])<M.val[worst][k])   // not consistent
				{
				n_not=n_not+1;
				if (n_not>2) 
					{
					goto next_c ; // We admit just two not consistent neighbours
					}
				if (n_not==1) neighbour1=k;
				if (n_not==2) neighbour2=k;
				}		
			}

		
		if (n_not==0) // super lucky, just one color to change!
			{
			OK=OK+1;
			colort.x[worst]=(float)c;

			//colort_max=diff_color(colort);// Max number of different colors
			goto next_worst;
			}
			
		if (n_not==1)// just one non consistent neighbour
		{


			for (c1=0;c1<cmax;c1++) // try a new color for the neighbour
			{
				if (fabs(c-c1)<M.val[worst][neighbour1]) goto next_c1; // not consistent
			
				for (j=0;j<dplus.dplus[neighbour1].size;j++) // check each neighbour of the neighbour
				{
					k=dplus.dplus[neighbour1].val[j]; // (k is the neighbour of the neighbour)
					if (k==worst) continue; // (already checked: for this pair of node, we try (c1,c))
						if (fabs(colort.x[k]-c1)<M.val[neighbour1][k]) goto next_c1; // not consistent
				}			
				// colors (c,c1) are OK for nodes (worst,neighbour1)
				OK=OK+1;
				colort.x[worst]=(float)c;
				colort.x[neighbour1]=(float)c1;


				goto next_worst;	
				
				next_c1:; // next color for the neighbour of the worst node
			}
		} // end of the case "one unconsistent neighbour"
			
		if (n_not==2) // just two non consistent neighbours
			{


			for (c1=0;c1<cmax;c1++)
				{
				if (fabs(c-c1)<M.val[worst][neighbour1]) goto next_c1_2; // not consistent
						
				// Check the neighbours of neighbour1
				
				for (j1=0;j1<dplus.dplus[neighbour1].size;j1++)
					{
					k1=dplus.dplus[neighbour1].val[j1]; // k1 is a neighbour of neigbour1
					if (k1==worst) continue;
					if (k1==neighbour2) continue;


					if (fabs(colort.x[k1]-c1)<M.val[neighbour1][k1]) goto next_c1_2; // not consistent
					}
				
				for (c2=0;c2<cmax;c2++)
					{
					if (fabs(c-c2)<M.val[worst][neighbour2]) goto next_c2; // not consistent
					if (fabs (c1-c2)<M.val[neighbour1][neighbour2]) goto next_c2; // not consistent	
						
						// Check the neighbours of neighbour2
				
					for (j2=0;j2<dplus.dplus[neighbour2].size;j2++)
						{
						k2=dplus.dplus[neighbour2].val[j2]; // k2 is a neighbour of neigbour1
						if (k2==worst) continue;
						if (k2==neighbour1) continue;
						if (fabs(colort.x[k2]-c2)<M.val[neighbour2][k2]) goto next_c2; // not consistent
						}
						
					// colors (c,c1,c2) are OK for nodes (worst,neighbour1,neighbour2)
					OK=OK+1;
		//printf("\n 	%i/%i %i/%i %i/%i",worst,c,neighbour1,c1,neighbour2,c2);
					colort.x[worst]=(float)c;
					colort.x[neighbour1]=(float)c1;
					colort.x[neighbour2]=(float)c2;
					
					goto next_worst;	
					next_c2:;	
					}	
				next_c1_2:;
				}
			}// end of the case "two unconsistent neighbours"
				
		next_c:; // next color for a worst node
		}
	next_worst:;
	} // next worst node


colort_max0=colort_max;
colort_max=diff_color(colort);// Max number of different colors


if (colort_max>=colort_max0)	// Noimprovement
	{
	return colort;
	}
else
	{
	goto improve; 
	}

}

// ----------------------------------------------------------------------------- COLOR_8_1
struct position	color_8_1(struct position color,struct matrix M, struct dplus dplus,int trace,struct param param,struct model model)
{
/*
Try to improve a coloring:

Built the list of the "bad" nodes (using the max color)
For each one, build a subgraph, and try to improv its coloring

for model.local_search >= 2

*/

int					backtrack;
struct vector_int	bad_node;
float				c,c1;
struct position		color0;
struct position		color1;
struct position		color3;
struct position		color_best;
float				d;
int					i;
int					j;
int					k;
int					l,l1;
int					m,m1;
float				max_unsat;
int					node;
int					parallel;
int					search;
float				total;
float				unsat;

parallel=1;
backtrack=0;


if (trace>0)
{
	printf("\n COLOR_8_1");
}

//printf("\n  %f ",color.f);
search=model.local_search;

color_best=color;

//printf("\n color_8_1 ici1 %i",color.size);
// Built the list of the "bad" nodes 

// Bad node = generating the greatest unsatisfaction

// Find the max
max_unsat=(float)NA;
for (node=0;node<color.size;node++)
{ 
	unsat=0;
	c=color.x[node];
	for (j=0;j<dplus.dplus[node].size;j++) // Neighbours
	{
		k=dplus.dplus[node].val[j];
		c1=color.x[k];
		d=(float)M.val[node][k]-(float) fabs(c-c1);
		if (d>0) unsat=unsat+d;
	}
	if (unsat>max_unsat) max_unsat=unsat;
}

// Build the list
bad_node.size=0;
for (node=0;node<color.size;node++)
{ 
	unsat=0;
	c=color.x[node];
	for (j=0;j<dplus.dplus[node].size;j++) // Neighbours
	{
		k=dplus.dplus[node].val[j];
		c1=color.x[k];
		d=(float)M.val[node][k]-(float)fabs(c-c1);
		if (d>0) unsat=unsat+d;
	}
	if (unsat<max_unsat) continue;
		bad_node.val[bad_node.size]=node;
		bad_node.size=bad_node.size+1;
}

if(trace>1)
{
	printf("\n max_unsat %f. Bad nodes",max_unsat);
	for (node=0;node<bad_node.size;node++) printf( " %i",bad_node.val[node]);
}

/*  OLD METHOD-----------
// Bad node = using the max color
maxcolor=NA;
for (i=0;i<color.size;i++) // Find the max color
	if (color.x[i]>maxcolor) maxcolor=color.x[i];
	
bad_node.size=0; // Build the list
for (i=0;i<color.size;i++)
	{
	if (color.x[i]<maxcolor) continue;
		bad_node.val[bad_node.size]=i;
		bad_node.size=bad_node.size+1;
	}
 --------------- */

erase:
color1=color;

for (i=0;i<bad_node.size;i++)
{
	// Set the subgraph
	node=bad_node.val[i]; // First node
	color1.x[node]=(float)NA;
	if (search<3) continue;
	
//printf("\n node %i",node);	
	for (j=0;j<dplus.dplus[node].size;j++) // Neighbours
	{
		k=dplus.dplus[node].val[j];
		color1.x[k]=(float)NA;
//printf("\n level 1 %i",k);
		if (search<4) continue;
	
			for (l=0;l<dplus.dplus[k].size;l++) // Neighbours of neighbours
			{
				m=dplus.dplus[k].val[l];
				color1.x[m]=(float)NA;

//printf("\n level 2 %i",m);

				if (search>=4)
				{
					for (l1=0;l1<dplus.dplus[m].size;l1++) // Neighbours of neighbours
					{
						m1=dplus.dplus[m].val[l1];
						color1.x[m1]=(float)NA;
//printf("\n level 3 %i",m1);
					}
				}
			}
	
	}


	if(parallel==0) // Try for each small subgraph at a time

	{
		// Find a coloring for the subgraph 
		if (backtrack>0)

		{
			color0=color_0(M,dplus,color1,param); // Try local backtrack 

			total=tot(color0, param, model);       //evaluation of the position
			color0.f=eval(total,param.target);

			if (color0.f<color_best.f)
			{
				color_best=color0;
				goto next_bad_node;
			}
		}
	
// Check if there is still something colored

for (i=0;i<color.size;i++)
{
	if (color1.x[i]>NA) goto recolor;
}
search=search-1;
if (search>1) goto erase;

//----------	
recolor:		
		color3=color_3(M,dplus,color1,param);
	
		// Check if better. If so, keep it
	
		total=tot(color3, param, model);       //evaluation of the position
		color3.f=eval(total,param.target);

		if (color3.f<color_best.f)
		{
			color_best=color3;
			goto next_bad_node;
		}
	}
next_bad_node:;
}




if(parallel>0) // Try just once, but for the union of the subgraphs

{

//printf("\n color_8_1. before backtrack");	

	// Find a coloring for the subgraph 
	if (backtrack>0)
	{
		color0=color_0(M,dplus,color1,param); // Try local backtrack 

		// Check if better. If so, keep it

		total=tot(color0, param, model);       //evaluation of the position
		color0.f=eval(total,param.target);
		if (color0.f<color_best.f)
			{
				color_best=color0;
			}
	}

//printf("\n color_8_1. after backtrack");
//printf("\n color_8_1. before greedy");

	// Try a greedy algo for approximate solution
	color3=color_3(M,dplus,color1,param);
	total=tot(color3, param, model);       //evaluation of the position
	color3.f=eval(total,param.target);
	if (color3.f<color_best.f)
	{
		color_best=color3;
	}
//printf("\n color_8_1. after greedy");
}

return color_best;
}

// ----------------------------------------------------------------------------- COLOR_LOCAL_SEARCH
struct position color_local_search(struct position pos,struct param param,struct model model)
{
int				type;
struct position post;

type=model.local_search;


switch (type)
{
	case 1:
	post=color_8(pos,M,  dplus,0);
	break;

	default:
	post=color_8_1(pos,M,dplus,0,param,model);
	break;

}


if (post.f<pos.f && param.printlevel>1)

//if (post.f<pos.f)

{ 
	printf("\n color_local_search %f => %f",pos.f,post.f);
}

return post;
}

// ----------------------------------------------------------------------------- COLOR_SHIFT
struct position color_shift (struct position pos)
{
// Change all colors/frequencies so that the min one is zero
// It does NOT change the f value of the position (see tot_color)
//Global variable  NA is big negative number. Means "non assigned"

int				d;
float			c_min;
struct position post;

c_min=min_comp(pos);
//printf("\n color_shift. min %f",c_min);
//display_position(pos);

if (c_min==0) return pos;

post=pos;