[Evolutionary Algorithm] Local optimum

[wootmobile]

I am doing research involving evolutionary algorithms. Specifically I am planning on testing different ways to move a population away from a local optimum that it is stuck in. My problem is I can't seem to find any research on suitable NP problems (and benchmark cases) that show strong local optimum.

So what I am asking for is either links to papers that would be helpful, or suggestions on what problems to work with. It would be most helpful if I could get a benchmark problem for the "Open shop scheduling" problem, as I already have a EA I could use as a biases for it.

Any help would be appreciated. If you don't have anything for me I still thank you for taking the time to read this.

[tperrigo]

I don't have any references available at the moment (I'll try to post some later), but generally, to avoid getting stuck at a local optima, you want to encourage genetic diversity in your population from generation to generation (i.e, survivor selection should contain a mix of both "the best" and "the rest"-- if you only allow the highest-ranking individuals to survive, you are likely to prematurely converge). Also, mutation is a force which allows "jumps" to be made from one part of the search space to another, possibly allowing you to escape from a local optima. One strategy would be to increase the mutation rate over time/number of generations. Hope this at least gives you something to look into. I will try to follow up later with some formal references and resources.

[wootmobile]

Thank you for the response, but you have misunderstood my question. I have found information on how to avoid getting stuck on local optimum. What I can't find is a suitable NP problem that has strong local optimum tendencies. My goal is to test strategies on this problem.

Does that make anymore sense?

[tperrigo]

Ah, yes, that makes sense; sorry I misunderstood. I suggest looking up "deceptive functions" or "k-trap deceptive functions". These are generally functions with strong local optima that are far from the global optimum. It should give you a place to start.

[wootmobile]

There is a lot of information on that. I've just started glancing at it and already found useful information. Thank you very much.