apple_trees.c

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

//  ================================================================== APPLE_TREES
double	apple_trees(struct position pos)
{
/*
This subroutine compute the objective function value for the position "pos"
for the "Apple trees" problem. It uses homogeneous coordinates relatively
to the three points A, B, C.

Aplle trees problem

Let ABC be a triangular field, with N apple trees. 
Let P be a point inside ABC
Let n1 be the number of apple trees in the triangle ABP
Let n2 be the number of apple trees in the triangle BCP
Let n3 be the number of apple trees in the triangle CAP

We are looking for a point P so that, if possible, n1=n2=n3.

 */

// Apple trees positions
/*  Each apple tree T is defined by three coordinates  t_1,t_2,t_3, relatively to ABC, so that
vector(O,T)=t_1*vector(O,A)+t_2*vector(0,B)+t_3*vector(0,C)
all t_i >0
t_1+t_2+t_3=1
*/

int				n_tree=20;
static double 	tree[50][3] =
{
{	0.639746245434385	,	0.307960237012273	,	0.0522935175533428	},
{	0.280835889852243	,	0.184333225280322	,	0.534830884867435	},
{	0.575508514977293	,	0.00530679182224588	,	0.419184693200461	},
{	0.337022637565724	,	0.248818720916488	,	0.414158641517789	},
{	0.654984026189228	,	0.209193769471434	,	0.135822204339338	},
{	0.179847117950272	,	0.286577885055583	,	0.533574996994145	},
{	0.292280717417545	,	0.323323895201444	,	0.384395387381011	},
{	0.375839583560393	,	0.606641949045372	,	0.0175184673942345	},
{	0.0106627446441443	,	0.408368043142947	,	0.580969212212908	},
{	0.420019455329547	,	0.368852171804188	,	0.211128372866265	},
{	0.320420524422852	,	0.300388234989245	,	0.379191240587904	},
{	0.521538476092585	,	0.249147824713397	,	0.229313699194018	},
{	0.0466619003870333	,	0.556636387982314	,	0.396701711630652	},
{	0.469594665050065	,	0.43863280703249	,	0.0917725279174454	},
{	0.403710900991078	,	0.21148010467317	,	0.384808994335753	},
{	0.0957751288301681	,	0.390565384942256	,	0.513659486227576	},
{	0.319946311478094	,	0.443173313759304	,	0.236880374762602	},
{	0.211891909772366	,	0.230220193305707	,	0.557887896921926	},
{	0.364576066012892	,	0.117348019516671	,	0.518075914470437	},
{	0.00483274321514129	,	0.434234851031356	,	0.560932405753503	},
{	0.450550375456143	,	0.0706334161177079	,	0.478816208426149	},
{	0.195080908994269	,	0.387469308086217	,	0.417449782919513	},
{	0.118365087468346	,	0.302020973067528	,	0.579613939464126	},
{	0.246937044423816	,	0.509741148266069	,	0.243321807310115	},
{	0.433361778344894	,	0.236759234881219	,	0.329878986773887	},
{	0.175390339737958	,	0.540541266799226	,	0.284068393462816	},
{	0.0524723816221108	,	0.596680280219583	,	0.350847338158307	},
{	0.325685598250723	,	0.133777439612362	,	0.540536962136914	},
{	0.413882646539365	,	0.537670230305588	,	0.0484471231550477	},
{	0.129582146969157	,	0.589282661507827	,	0.281135191523017	},
{	0.106500984429014	,	0.24473964804488	,	0.648759367526106	},
{	0.276126966657802	,	0.133472318580804	,	0.590400714761394	},
{	0.503417516885091	,	0.0348880568407504	,	0.461694426274158	},



{	0.213132263763455	,	0.36607163318592	,	0.420796103050625	},
{	0.867481208833211	,	0.122410251326314	,	0.0101085398404746	},
{	0.285817691403412	,	0.418691818789608	,	0.295490489806981	},
{	0.346829674181994	,	0.364534229826083	,	0.288636095991924	},
{	0.0409054010992303	,	0.316701770622011	,	0.642392828278759	},
{	0.206064075600438	,	0.167191503612828	,	0.626744420786733	},
{	0.0671101933458943	,	0.573385048000581	,	0.359504758653525	},
{	0.258577852288686	,	0.249352207901994	,	0.492069939809321	},
{	0.534948117455922	,	0.343928702250002	,	0.121123180294077	},
{	0.452238586314534	,	0.276508930537038	,	0.271252483148428	},
{	0.0595981411060292	,	0.469456059539192	,	0.470945799354778	},
{	0.357229100199135	,	0.218143949404633	,	0.424626950396232	},
{	0.354970313516061	,	0.444961247148121	,	0.200068439335818	},
{	0.456781869495123	,	0.253613485935699	,	0.289604644569178	},
{	0.455231658700055	,	0.389480806207741	,	0.155287535092204	},
{	0.237295169350416	,	0.501289987226391	,	0.261414843423193	},
{	0.330045125110048	,	0.347612229297512	,	0.32234264559244	}
};

double	comp1,comp2;
int		n1,n2,n3; // Numbers of trees in each sub-triangle ABP, BCP, CAP
double	p_1,p_2,p_3;
double	s;
double 	total;
int		i_tree;

n1=0;n2=0;n3=0;

/* As the apple trees, P is also defined by (p_1,p_2,p_3), 
  relatively to ABC
*/
s=pos.p.x[0]+pos.p.x[1]+pos.p.x[2];
if (fabs(s)>0)
	{
	p_1=pos.p.x[0]/s;
	p_2=pos.p.x[1]/s;
	p_3=pos.p.x[2]/s;
	}
else // Arbitrarily set to the gravity center
	{
	p_1=1/3;
	p_2=1/3;
	p_3=1/3;
	}

/* For a given tree, we compute the coordinates: 
- relatively to  ABP. If they are all >0, the tree is inside ABP
	if not, relatively to  BPC, if they are all >0, the tree is inside BCP
		if not, it is inside CAP
(Note: we do'nt take into account the case when a tree is just on the frontier of a triangle
*/

for (i_tree=0;i_tree<n_tree;i_tree++) // For each tree ...
	{
	comp1=(float)(tree[i_tree][0]*p_3-tree[i_tree][2]*p_1); // For ABP
	if (comp1<0) goto BCP;
		comp2=(float)(tree[i_tree][1]*p_3-tree[i_tree][2]*p_2);
		if(comp2<0) goto BCP;
			n1=n1+1;
			continue;

	BCP:
	comp1=(float)(tree[i_tree][1]*p_1-tree[i_tree][0]*p_2); // For BCP
	if (comp1<0) goto CAP;
		comp2=(float)(tree[i_tree][2]*p_1-tree[i_tree][0]*p_3);
		if(comp2<0) goto CAP;
			n2=n2+1;
			continue;

	CAP:
	n3=n3+1;
	}

//if (print_level>2) 
fprintf(f_trace,"\n Number of trees in each sub-triangle: %i %i %i ",n1,n2,n3);

total=(float)((n1-n2)*(n1-n2)+(n2-n3)*(n2-n3)); // Objective function to minimize

return total;
}