Local search is currently one of the most used methods for finding solutions in real-life problems. It is usually considered when the research is interested in the final solution of the problem instead of the how the solution is reached. In this paper, the authors present an implementation of local search with Membrane Computing techniques applied to the N-queens problem as a case study. A CLIPS program inspired in the Membrane Computing design has been implemented and several experiments have been performed. The obtained results show better average times than those obtained with other Membrane Computing implementations that solve the N-queens problem.
Top2. Local Search
Classical search algorithms explore the space of states systematically. This exploration is made by keeping one or more paths in memory and by recording the alternatives in each choice point. When a final state is found, the path, that is, the sequence of transitions, is considered as the solution of the problem. Nonetheless, in many problems, we are only interested in the found state, not properly in the path of transitions. For example, in job-shop scheduling, vehicle routing or telecommunications network optimization, we are only interested in the final state (a concrete disposition of the objects in the world), not in the way in which this state is achieved.
If the sequence of elementary transitions is not important, a good alternative to classical searching algorithms is local search. This type of search operates using a single state and its set of neighbors. It is not necessary to keep in memory how the current state has been obtained.
Since these algorithms do not systematically explore the states, they do not guarantee that a final state can be found, i.e., they are not complete. Nonetheless, they have two advantages that make them interesting in many situations:
- •
Only a little piece of information is stored, so very little memory (usually constant) is used.
- •
These algorithms can often find a reasonable solution in an extremely large space of states where classical algorithms are unsuitable.