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!) 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