A search space is the set of candidate states or solutions an algorithm may consider. Decision variables describe a candidate; an objective function scores it; constraints rule out candidates that are not feasible. The feasible search space contains only solutions satisfying all constraints. Search then aims for a feasible solution with the best—or a sufficiently good—objective value. section 1.3 section 1.5
The space determines both what can be found and how hard finding it may be:
- A global optimum is best across the feasible space; a local optimum is best only among nearby candidates. A search that improves nearby solutions can therefore miss a better region. section 1.3
- Exploration investigates new regions. Exploitation concentrates on a promising region. Balancing them helps avoid both premature focus and excessive searching. section 1.5
- A clearly defined space can still be too large for naive enumeration: a 13-city traveling salesman problem has 13! possible routes. section 1.4.3
States in a robot task
For a pick-and-place robot, a state can include arm position and speed plus gripper orientation and status. Motion and gripper commands lead to successor states. The goal is to move a defective workpiece into a waste box and return home; duration can evaluate the resulting path. Defining states, allowable moves, a goal, and an evaluation criterion makes the search problem concrete. section 1.4.1
When the space grows or changes
Dispatching four elevators across ten floors involves roughly 10²¹ possible states when positions and button states are considered. New calls also change the situation after a decision is made. A fixed optimum is difficult to identify when the search space is both enormous and only partly observable. section 1.4.2
In practice, define the candidate representation and constraints before choosing a search method. For a 20-city traveling salesman problem, a genetic algorithm represents routes as permutations and minimizes round-trip distance. A repair operator rotates each offspring route to start at city index 0, keeping the algorithm focused on the intended feasible representation. Population size, sampling, crossover, and mutation are parameters to experiment with rather than guarantees of an optimum. section 8.6
problem = TravelingSalesman(cities,distance_matrix) #1
algorithm = GA(
pop_size=20,
sampling=PermutationRandomSampling(),
mutation=InversionMutation(),
crossover=OrderCrossover(),
repair=StartFromZeroRepair(),
eliminate_duplicates=True
) #2
termination = DefaultSingleObjectiveTermination(period=300, n_max_gen=np.inf) #3
res = minimize(
problem,
algorithm,
termination,
seed=1,
verbose=False
) #4
The solver configuration connects the search space to permutation sampling, crossover, mutation, repair, and a stopping rule. section 8.6
