Bump
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.835 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).
A snipit of C code
is available 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
see also my WWW pages
June 1994