main.c

用C编写的部落寻优的优化算法

/*
printf("\n best_informer. Particle %i. Informers: ",part.label);
for (i=0;i<part.ig.size;i++)
{
	labelt=part.ig.label[i];
	printf(" %i",labelt);
}
*/
	for (i=0;i<part.ig.size;i++) // For each informer
	{
		labelt=part.ig.label[i];
		// Find the particle (tribe j, particle k) with this label
		for (j=0;j<TR[level].size;j++) // For each tribe ...
		{
			for (k=0;k<TR[level].tr[j].size;k++) // ... for each particle in the tribe
			{
				if (TR[level].tr[j].part[k].label==labelt) goto compare;
			}
		}
		printf("\nERROR. best_informer (default). Can't find particle with label %i",labelt);
		printf("\n Particle label %i. ig list:",part.label);
		for (k=0;k<part.ig.size;k++) printf(" %i",part.ig.label[k]);
		display_swarm(1,level);
		scanf("%c",&bid);

	compare:
        better=better_than( TR[level].tr[j].part[k].p_i.f,f0,level);
		if (better!=1) continue;
			j_best=j;
			k_best=k;
			f0=TR[level].tr[j_best].part[k_best].p_i.f;
	}
	break;
} // end switch no_best

// end:
 //printf("\n label %i, k_best %i",part.label,k_best);
return TR[level].tr[j_best].part[k_best];
}


// ----------------------------------------------------------------------------- BETTER_THAN
int	better_than(struct f f1,struct f f2, int level)
{


/* return 1 if f1 is better than f2
          0 if f2 is worse than f2
          2 if they are equivalent
Useful mainly for multiobjective problem
f1 and f2 are supposed to be the same size
*/

 int d;
 double eps;

  if(lexico>0) goto lexico;

 for( d=0;d<f1.size;d++)
 {
    if (f1.f[d]>f2.f[d]) return 0;
 }
 // All f1's f_values are <=
  for( d=0;d<f1.size;d++)
 {
      if (f1.f[d]<f2.f[d]) return 1;  // At least one is <
 }
return 2;    // They are all equal

 lexico: // Lexicographic sort

 eps=problem[level].eps/ f1.size;

   for( d=0;d<f1.size;d++)
 {
	  if (fabs(f1.f[d]-f2.f[d])+eps<MIN(f1.f[d],f2.f[d])) continue;
	  if (f1.f[d]<eps && f2.f[d]<eps) continue;
	 if (f1.f[d]<f2.f[d]-eps)   return 1;
     if (f1.f[d]>=f2.f[d]-eps)   return 0;
 }

 return 2;
}


//------------------------------------------------------------------------------ CLEAN_RUN
void clean_run(FILE *f_run,FILE *f_run_clean, int nb_f,int DD,int level)

{

 /*
   For multiobjective problem, keep only the non dominated points
  f_run: 3 numbers, nb_f values, 4 numbers, position (DD values)
  EOF = -1
 */
 int     better;
 float bid;
 int     d;

  int eof;
  int    i,j,k;
  int    ibid;
  char line[400];
  int    n_clean;
  int    n_pos;
  struct position pos[Max_run];
int      clean[Max_run];


  printf("\nMultiobjective. A moment, please, I clean up the result file");

if (nb_pb_max>1)
{
	printf("\n WARNING. I can clean up the run file for you are running");
	printf("\n           the program on several problems");

}

// Shunt the title line
fgets( line,400,f_run);

// Read the positions
   n_pos=0;
read_pos:
        fscanf(f_run,"%i",&eof);

        if(eof==-1) goto clean_up;

        fscanf(f_run,"%i %f",&ibid,&bid);

        for (d=0;d<nb_f;d++)
        {
           fscanf(f_run," %f",&bid);
           pos[n_pos].f.f[d]=bid;
        }

        fscanf(f_run,"%f %f %f %f",&bid,&bid, &bid,&bid);

        for (d=0;d<DD;d++)
        {

           fscanf(f_run," %f",&bid);
            pos[n_pos].p.x[d]=bid;
        }
        pos[n_pos].f.size=nb_f;
        pos[n_pos].p.size=DD;

         n_pos=n_pos+1;
         goto read_pos;

clean_up:
// Write the titles
for(d=0;d<nb_f;d++)    fprintf(f_run_clean," f%i", d+1);
for(d=0;d<DD;d++)    fprintf(f_run_clean," x%i", d+1);

 n_clean=0;
 // For each result, look if it is dominated by another one
 // If not, write it in the f_run_clean file


 for (i=0;i<n_pos;i++)
 {
       if (i==n_pos-1) goto already;

       // Compare to not already checked positions
       for (j=i+1;j<n_pos;j++)
       {
         better=better_than(pos[j].f,pos[i].f,level);
         if (better==1) goto next_i; // pos(j) is better. Don't keep pos(i)
       }

 already:
         // Compare to already saved positions
        for (j=0;j<n_clean;j++)
        {
           k=clean[j];
           better=better_than(pos[k].f,pos[i].f,level);

           if (better!=0) goto next_i;  // pos(k) is better or equal. Don't keep pos(i)
         }

         clean[n_clean]=i;
         n_clean=n_clean+1;
 next_i:;

 }

 // Write the cleaned result

 for (i=0;i<n_clean;i++)
 {
    j=clean[i];
    fprintf(f_run_clean,"\n");
      for(d=0;d<nb_f;d++)    fprintf(f_run_clean," %f", pos[j].f.f[d]);
      for(d=0;d<DD;d++)    fprintf(f_run_clean," %.12f", pos[j].p.x[d]);
 }
 printf("\n OK, finished. I keep %i non dominated positions. See file run_cleaned.txt",n_clean);
}



// ----------------------------------------------------------------------------- COMPLETE_PART
struct particle complete_part(struct particle par, int option,int level)
 // WARNING: position must be already initialized. Complete the particle
{
struct particle	part;

part=par;

if (option==0) // Completely new particle
{
	part.label=label[level];
	label[level]=label[level]+1;
}

//part.ig.size=1;
//part.ig.label[0]=part.label;

part.x.p.size=problem[level].DD;

part=constrain(part,level); // Keep in the search space

part.x.f.size=problem[level].nb_f;
part.x.f=MyFunction(part.x,problem[level].funct,problem[level].target,level); //evaluation of the position
part.p_i=part.x; // previous best = current position
part.status=0; // no improvement
part.prev_x=part.x;
return part;

}

// ----------------------------------------------------------------------------- HOMOGEN_TO_CARTE
struct position	homogen_to_carte(struct position pos)
{
/* Convert a position given by its homogeneous coordinates into
the same position given by its cartesian coordinates. The homogeneous coordinates
are supposed to be given relatively to the unit points:
(0, ... 0), (1,0,...0) (0,1,0...,0) ... (0,...,0,1)

See, for example, Apple Trees problem

*/
int				d;

struct position post;
double			s;

post.p.size=pos.p.size-1;

s=0;
for (d=0;d<pos.p.size;d++)
{
		s=s+pos.p.x[d];
	}
if (fabs (s)<almostzero)
{
	printf("\n WARNING. Incorrect homogeneous coordinates. Return null point");
	for (d=0;d<post.p.size;d++)

		post.p.x[d]=0;
	return post;
}

for (d=0;d<post.p.size;d++)
	post.p.x[d]=pos.p.x[d+1]/s;

return post;
}




// ----------------------------------------------------------------------------- INIT_PARTICLE
struct particle	init_particle(int option,int level,struct particle part0)
{ // Initialisation of a particle
int				d;
double			dist_min;
int				loop;
int				loop_max;

int				random; // See below the different kinds of random generation

int				place;
int				rank;
struct particle part={0};

//random=alea(0,3);  // 0,1,2,3
random=alea(0,2);
//if (problem[level].nb_f>1)
//   random=2*alea(0,1); // 0 or 2    (mainly useful for multiobjective problem)
//else
 //  random=0;
//random=alea(0,1); if(random==1) random=2;

part.x.p.size=problem[level].DD;

if(option>0) part=part0; // Re-init position, but no the links
if (option==2) goto complete; // Just recompute the position

dist_min=0;
loop=0;
loop_max=problem[level].DD;

switch (random)
{
case 0:	// Random generation anywhere in the search space
for( d = 0;d<problem[level].DD;d++)  //for each dimension
{
	part.x.p.x[d] = alea_float(problem[level].H.min[d],problem[level].H.max[d]);
}


break;

case 1: // Random generation on an edge of the search space

for( d = 0;d<problem[level].DD;d++)
{

	place=alea(0,2);

	switch (place)
	{
	case 0:
		part.x.p.x[d] = problem[level].H.min[d];
		break;
	case 1:
		part.x.p.x[d] = problem[level].H.max[d];
		break;
	case 2:
		part.x.p.x[d] = (problem[level].H.min[d]+problem[level].H.max[d])/2;
		break;
	}
}
break;

case 2: // On the frontier
	for( d = 0;d<problem[level].DD;d++)
	{
		part.x.p.x[d] = alea_float(problem[level].H.min[d],problem[level].H.max[d]);
	}
	rank=alea(0,part.x.p.size-1);
	place=alea(0,1);
	if (place==0) 	part.x.p.x[rank]=problem[level].H.min[d];
	else part.x.p.x[rank]=problem[level].H.max[d];
	break;

case 3: // Inside the memory swarm
//printf("\n init_particle %f %f",Xmin.x[0],Xmax.x[0]);

for( d = 0;d<problem[level].DD;d++)  //for each dimension
{
	part.x.p.x[d] = alea_float(Xmin.x[d],Xmax.x[d]);
}

}

complete:
part=complete_part(part,option,level);
//display_position(part.x);

if (problem[level].printlevel>1)
   printf("\n init => %f",total_error(part.x.f));

// For some strategies, more features are needed
for( d = 0;d<problem[level].DD;d++)  //for each dimension
{
     part.mod[d]=0; // Has not been modified (for Taboo option)
     part.v[d]=0; // Or random, if you want
  }
return part;
}

// ----------------------------------------------------------------------------- LINK_REORG
void link_reorg(int level)
{

/* Reorganise information links between tribes
The tribe list TR[level] is a global variable

Note 1: symmetry of the information graph is not garanteed
Note 2: connectivity of the information graph is not garanteed
Note 3:  this is just a "research" option. Does not seem to be very efficient
*/
int					better;
struct	particle	best;
double				dist;
double				dist_far;
double				dist_near;
struct	particle	farest;
int					far_ig_rank;
int					i,i2,i3,i4;
int					i_best;
int					i_near;
int					inform;
int					label;
struct	particle	nearest;
int					not_inform;
struct	particle	part;
int					t,t2,t3;
int					t_near;


for(t=0;t<TR[level].size;t++) // For each tribe
{
// ... find the best particle B
	best=TR[level].tr[t].part[0]; i_best=0;

	for (i=1;i<TR[level].tr[t].size;i++)
	{
		better=	better_than(TR[level].tr[t].part[i].p_i.f,best.p_i.f,level);
		if(better==1) {best=TR[level].tr[t].part[i]; i_best=i;}
	}

	// Find a particle that is not an informer
	for(t2=0;t2<TR[level].size;t2++)
	{
		if (t2==t) continue; // All particles of the tribe t are informers for best

		label=TR[level].tr[t].part[i].label;


		for (i=0;i<best.ig.size;i++)
		{
			if (best.ig.label[i]!=label)
			{nearest=TR[level].tr[t].part[i];goto loop_swarm;}
		}

		printf("\nWARNING.link_reorg. Can't find a non informer for particle label %i",best.label);

		goto end;

	}

loop_swarm:
// ... loop on all particles of the swarm
	farest=best; far_ig_rank=-1;
	dist_far=0; // Distance farest informer<->best
	dist_near=infinite; // Dist