Sign in to follow this  

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

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

If you intended to correct an error in the post then please contact us.

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[i]*sin(sqrt(abs(x[i]))), i = 1..n); x[i] = [-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[i] 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 this post


Link to post
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 domain
f(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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:


{ 1, if x = k, for some random single k of a large input domain
f(x) = {
{ 0, otherwise



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

Share this post


Link to post
Share on other sites
Quote:
Original post by _Tank_
Quote:


{ 1, if x = k, for some random single k of a large input domain
f(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 this post


Link to post
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 domain
f(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 this post


Link to post
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 this post


Link to post
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/

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this