States have an associated score, and the goal is to find the state with the best score. We do not care about the search path, only the best state.
Hill climbing
A simple strategy for solving optimization problems in which neighboring states are listed and the search proceeds to the neighbor with the best score. The search stops when no better neighbor exists.
Neighborhood
The set of neighbors of a state s, also called the move set. The neighbors must be defined in a problem-specific manner.
Greedy search
Picking the best option at each step.
Local optimum
In an optimization problem, a state that has a better score than all of its neighbors but not the best score out of all states.
Global optimum
In an optimization problem, a state that has the best score out of all states.
Random restarts
Starting a local search multiple times from different randomly-selected initial states.
Stochastic hill climbing
A variant of hill climbing in which the next state is selected at random, with more likelihood assigned to higher scoring neighbors.
First-choice hill climbing
A variant of hill climbing for problems in which the neighborhood is too large to completely enumerate. Randomly generates neighbors until a neighbor with a better score is found.
Simulated annealing
An optimization strategy in which a neighbor is randomly selected and then accepted as the next state if it is better than the current state or with a small probability if it is worse. The probability is a function of the iteration number and how much worse the neighbor’s score is.
Genetic algorithm
An optimization strategy modeled after biological evolution. States are generated based on crossover moves between two parents and mutation moves to a generated state. The score of a state is treated as its fitness, which determines the probability with which it will be selected as a parent.