# 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