Describe the basic algorithm for performing local search. Give an example of a search problem for which it is an appropriate solution. When would an algorithm such as A* search be preferred?

  • 4
    $\begingroup$ This looks to me like a course work question. You should really answer that question yourself, rather than getting other people to do it for you. Otherwise you won't learn anything from it. $\endgroup$ – Oliver Mason Nov 21 '18 at 9:06

Before a robot can move on a line, a plan must be generated first. A plan is a sequence of steps to reach a goal. Generating plans is called search&planning. The idea is to traverse the existing search space to fulfill constraints. The term “local search” is used to make clear, that it's impossible to generate all plans but only a limited set which is in the neighborhood. The neighborhood is located in the error map of the objective function. The first question is, why only a local search is possible but not a global one in the complete state space? In case of pathplanning this can be answered by algorithmic needs. If we want to create a graph from the start to the goal, we can only add new nodes, step by step by executing a for loop. That means, the graph starts with zero nodes, then we add one, then another and so forth. That means, we have to wait a long time until the complete graph is generated and we are always searching nearby the start node.

The local search algorithm has an interesting capability, which is called grammatical evolution. The idea is not to search in the lowlevel statespace, which is the 2d map in a pathplanning problem, but to search in the state space of grammars. Like in the example from the introduction it is only possible to traverse nodes nearby the original one, but this time we are not searching for spatial points on the map, but for nodes in a graph of all possible grammars. That means, on step #1 we are investigating grammar #1, at step #2 we are investigating grammar #2 which is nearby, and then we are testing out grammar #3 and so on.

  • Mascia, Franco, et al. "Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools." Computers & operations research 51 (2014): 190-199.
  • 3
    $\begingroup$ "The idea is to traverse the existing search space to fulfill constraints". No, not always. I feel that all your answers that I have read are not on point. "grammatical evolution", hah??? "Grammatical evolution" is definitely not a well-known term used in "local search" algorithms. It's probably some specific terminology. Not sure why you talk about all these esoteric terms. $\endgroup$ – nbro Nov 21 '18 at 9:51
  • $\begingroup$ @nbro “I feel that all your answers that I have read are not on point” Ah, you want to build a software which is able to evaluate the skills of each user. That is an interesting project which has to do natural language parsing for content quality measurement. Please continue. $\endgroup$ – Manuel Rodriguez Nov 21 '18 at 10:18
  • 2
    $\begingroup$ @ManuelRodriguez I think you are overthinking too much.... $\endgroup$ – Jérémy Blain Nov 21 '18 at 16:20

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