Does someone has a hard-to-solve task for GA with known global optima.

This topic is 4650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm testing a algorithm which has its roots growing from genetic algorithm and by now i'm looking at face of next problem: i can't find (bored inventing my own) a tasks with quite complex fitness functions (non linear) with known global optimum I have just achieved a global optimum for: f(x) = sum(x*sin(sqrt(abs(x))), i = 1..n); x = [-500.0 .. 500.0] where n = 300 The amount of local extremas for this function is 14^(300) = 68930384886645998099980586833154610877542496355613188203815387416246616955296951264276229574297559287437335159210584213571292078030867197684119272414354927403310155953577048773747604426442940728403693781654245716519841230786783237728897680001696984541558002263204361832900820678168113145192966533409135339551410225142051162816350167161295077376 it took me about two and a half hours to achieve a global optima; But the problem is that x do not corelate with each-others. So if someone has a interesting optimization task with known global optima for me to test this algorithm, i would appreciate it. Thanks.

Share on other sites
Quote:
 Original post by _Tank_I'm testing a algorithm which has its roots growing from genetic algorithm and by now i'm looking at face of next problem: i can't find (bored inventing my own) a task with quite complex fitness function (non linear) with known global optimum
I think you need to be more specific. For instance, a needle-in-a-haystack problem satisfies your request
       { 1, if x = k, for some random single k of a large input domainf(x) = {       { 0, otherwise
but I doubt that's the function you're after!

When I was working with GAs some 15 years ago, the De Jong test suite was what was typically used for testing GAs. De Jong suggested these problems already back in 1975. For a description of them, eee e.g.:

http://home.ku.edu.tr/~dyuret/pub/aitr1569/node19.html

You may want to play with these.

However, for some perspective, you may also want to read De Jong's paper

http://cs.gmu.edu/~eclab/papers/foga2_opt.ps

for his view on GAs as function optimizers.

Share on other sites
It's been 10 years since I did any meaningful research using De Jong's suite, but I seem to recall there being a second test suite that fixed some flaws in the first. You might want to hunt it down.

Cheers,

Timkin

Share on other sites
Quote:
  { 1, if x = k, for some random single k of a large input domainf(x) = { { 0, otherwise

Yeap thats the function, lots of work, no aim and perspective.

Share on other sites
Quote:
Original post by _Tank_
Quote:
  { 1, if x = k, for some random single k of a large input domainf(x) = { { 0, otherwise

Yeap thats the function, lots of work, no aim and perspective.
For this type of function, you cannot do better than:

best = 0;for (i = 1; i < domain_size; i++)    if (f(i) > f(best)) best = i;return best;

Running a genetic algorithm (or any other type of search algorithm) on a needle-in-the-haystack problem would be folly.

Share on other sites
:))))))

I was not looking for a function that this algorithm or any other is not able to optimize. Right now i'm working on algorithm that produces algorithms to solve problems.
Although i was not like 'look at me i've developed an algorithm ...' so please do hesitate to do the following:

Quote:
 { 1, if x = k, for some random single k of a large input domainf(x) = { { 0, otherwise

P.S:

Have just finished testing the 0-1 multidimensional knapsack optimizator. Just have to tell you that it works unexpectedly well. Unexpectedly becouse the search is done via the {0,1}^|n| space which is not very well for such algorithm.

[Edited by - _Tank_ on March 9, 2006 11:34:38 AM]

Share on other sites
I found that the sorting network problem is an interresting area of GA exploration.

Go from a small problem space (optimal solutions can be brute forced) to an immensely large one (brute force is not feasable) just by making a small change in the size of the input space.

There are several types of usefull fitness evaluations within this problem space that are usefull in real life terms.

Minimizing "length" and/or "depth" are obvious choices.

Not so obvious is factoring in a level of error tolerance which is relevent to manufacturing issues. Ie, a significantly low depth 256-sorter that can survive 2 manufacturing defects is probably of some value.

Share on other sites
Agree with Christer Ericson, the needle in a haystack function has no intermediate firness-value, it's either one or zero, therefor ga's do nothing more than random parallel search, it's has been proven (in prime factorization problems) that random search is less efficient than exhaustive search (as suggested by CE).

One thing to try your teeth on though are (but it's in the same arena as knapsack) is the travelling salesmen-problem, it can easily be made huge and has a fitness-value related to each tentative solution.

Plenty of problems with solutions:

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

1. 1
2. 2
Rutin
19
3. 3
khawk
15
4. 4
A4L
13
5. 5

• 13
• 26
• 10
• 11
• 44
• Forum Statistics

• Total Topics
633744
• Total Posts
3013657
×