# 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