1
$\begingroup$

For my programming project I need to implement a local search algorithm. The generic local search algorithm is easy to understand but the thing I am most struggling with is how to deal with the neighbourhood.

It seems that when you implement such an algorithm, you don't explicitly state the neighbourhood but you declare a neighbourhood relation which tells you what you are allowed to modify in your present solution to get a "neighbour" or how two neighbours differ.

So lets say I have such a neighbourhood relation and a starting solution. What I first thought about was to make this purely random. Take the starting solution S. I would then call something like neighbour(S) which randomly chooses a neighbour and then you would start comparing...

How common is it to choose the neighbour systematically? I thought about the option to choose my neighbour systematically but so I had somehow to keep track about the neighbours I already visited which seemed more complicated than to just choose them randomly. What is your opinion on that?

$\endgroup$
1
$\begingroup$

I expect choosing a single neighbor systematically will work poorly. Typical local search algorithms either look at multiple neighbors and choose the best (in which case you need more than one...) or repeatedly choose a random neighbor and decide whether to move there or stay where you are (in which case if you always choose the same neighbor, then you will quickly get stuck at a local optimum). But you can do anything that works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.