What Is The Search Space of A Local Search Algorithm?
Definition, examples, and some important points
When using a local search heuristic algorithm to solve an optimization problem, one basic element of the algorithm that need to be defined is the search space of the local search algorithm.
1. Definition of search space of a local search algorithm
The search space of a local search heuristic algorithm for solving an optimization problem is the space of all possible solutions that can be considered or visited during the search [1].
2. Two examples
For instance, when solving the vehicle routing problem, the search space of the local search heuristic algorithm could be the set of feasible solutions to the problem, where each point in the search space corresponds to a set of vehicle routes satisfying all the specified constraints.
For another instance, when solving the flowshop scheduling problem, the search space of the local search heuristic algorithm could be the set of all possible solutions to the problem, where each solution in the search space corresponds to a production sequence of jobs on the machines.
3. The premise of a good definition of the search space
The definition of the search space of the local search heuristic algorithm to the vehicle routing problem and flowshop scheduling problem seems quite natural, but it is not always so for other optimization problems.
For some problems, the solution to the problem is quite complex as the problem may involve multiple types of decisions to be make. In this context, the solution representation may be very complex, which makes the search space quite complex and large.
In this case, the definition of the solution representation and search space depends on the preferences and experience of the person who is working on it.
Note that the solution representation of a problem affects the efficiency of a local search heuristic algorithm to the problem. A good solution representation should balance between the solution space reduction and the ability to conduct an efficient search in this reduced solution space [2].
A good definition of solution representation and solution space based on a good understanding of the problems at hand. So it is always preferable to understand your problems well before defining the search space.
4. Do all solutions in the search space need to be feasible?
A beginner may think that all solutions in the search space need to be feasible. In fact, it is not always a good idea to restrict the search space to feasible solutions. In many cases, it is necessary to allow the search to move to infeasible solutions as it may lead to desirable solutions.
References
1. Glover, F. W., & Kochenberger, G. A. (Eds.). (2003). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.
2. Fernandez-Viagas, V., Perez-Gonzalez, P., and Framinan, J. M. (2019). Efficiency of the solution representations for the hybrid flow shop scheduling problem with makespan objective. Computers & Operations Research, 109:77–88.