A Hard(?) Problem
 
I am interested in how the number of dimensions affects GA and other
search methods. Also, because I am interested in engineering design,
I am interested in how methods cope with optima that occur hard up
against constraint boundaries. While looking at this problem I have
developed a test function that is easy to code with arbitrary numbers
of dimensions but hard to solve. The function is (in eqn speak!)
 
maximize
 
      { abs ( sum from i=1 to n { cos sup 4 ( x sub i ) }
            - 2 prod from i=1 to n { cos sup 2 ( x sub i ) } ) }
      over { sqrt { sum from i=1 to n { i x sub i sup 2 } } }
 
for
 
      0 < x sub i < 10 , i=1 , ... , n
 
subject to
 
      prod from i=1 to n { x sub i } > 0.75
and
      sum from i=1 to n { x sub i } < 15 n /2
 
starting from
 
      x sub i = 5, i=1 , ... , n
 
where the x sub i are the variables (expressed in
radians) and n is the number of dimensions.
 
This function gives a highly bumpy surface (try n=2 and contour the function
to see what I mean) where the true global optimum is usually defined
by the product constraint.
 
I am currently using a parallel GA with 12bit binary encoding, crossover,
inversion, mutation, niche forming and a modified Fiacco-McCormick constraint
penalty function to tackle this. For n=20 I get values
like 0.76 after 20,000 evaluations, while for n=50 I need around 50,000 to get
this far. However I can get to 0.65 in about 5,000 and 12,000, respectively.
The absolute maximum for the n=50 problem would seem to be about 0.82 but I
do not know this to be the case (150,000 trials is a long way !).
 
I would be interested to know how others get on with this problem
and to see if there are any dramatically faster methods that work well
across a range of n (this problem is not trivial even for low n as many
methods fail to find the global optimum - again try plotting the n=2
version to see what I mean).

Appended to this message is a snipit of C code to set up a trial vector
for the n=20 version and then to evaluate the function and constraint.
 
Andy Keane
School of Engineering Sciences,
Southampton University,
Highfield, Southampton, SO17 1BJ, U.K.
Tel +44-2380-592944
FAX +44-2380-593230
http://www.soton.ac.uk/~ajk/welcome.html

June 1994

#include <math.h>

#define NVARS 20

main(argc,  argv)

int argc;
char *argv[];
 
{
	int ii;
	double x[NVARS], obj, con1, con2;

	for (ii = 0; ii<NVARS; ii++) {
		x[ii] = 5.0;
	}

	x[0] = 9.42;
	x[1] = 3.15;
	x[2] = 3.14;
	x[3] = 3.19;
	x[4] = 3.12;
	x[5] = 3.10;
	x[6] = 3.13;
	x[7] = 3.09;
	x[8] = 3.08;
	x[9] = 0.39;
	x[10] = 3.05;
	x[11] = 0.25;
	x[12] = 0.41;
	x[13] = 0.26;
	x[14] = 0.25;
	x[15] = 0.22;
	x[16] = 0.40;
	x[17] = 0.22;
	x[18] = 0.27;
	x[19] = 0.21;

	obj = 0.0;
	con1 = 0.0;
	con2 = 0.0;
	optfun(x, &obj);
	printf("obj  =  %10g\n", obj);
	optcon(x, &con1, &con2);
	printf("con1  =  %10g , con2  =  %10g\n", con1, con2);

}

optfun(x, obj)
 	double x[], *obj;
{
	int ii;
	double sumc4, prodc2, sumsq;
 
	sumc4 = 0.0;
	prodc2 = 1.0;
	sumsq = 0.0;
	for (ii = 0; ii<NVARS; ii++) {
		sumc4 = sumc4 + cos(x[ii]) * cos(x[ii]) * cos(x[ii]) * cos(x[ii]);
		prodc2 = prodc2 * cos(x[ii]) * cos(x[ii]);
		sumsq = sumsq + (double)(ii+1) * x[ii] * x[ii];
	}
	sumsq = sqrt(sumsq);
 	*obj = (sumc4 - 2.0 * prodc2)/sumsq;
	if(*obj<0.0) *obj = - *obj;
	return;
}
 
optcon(x, con1, con2)
	double x[], *con1, *con2;
{
	int ii;
 
	*con1 = 1.0;
	*con2 = 0.0;
	for (ii = 0; ii<NVARS; ii++) {
		*con1 = *con1 * x[ii];
		*con2 = *con2 + x[ii];
	}
	return;
}