- Optimisation problem: search problem with preferences , i.e., with objective function(s).
- They consist of variables , domains , objective function(s)
- Objectives :
- Single objective optimisation problems , e.g., Travelling Salesman Problem (TSP): minimising the cost of the travelling.
- Multi objective optimisation problems , e.g., TSP with an additional objective: minimising the time of the travelling.
- Constraints :
- Unconstrained optimisation problems.
- Constrained optimisation problems.
- Tree search methods may not work for optimisation problems, e.g. in some continuous search space.
- Local search methods can be effective for optimisation problems.
Local Search for Optimisation
- Generally fast and memory efficient.
- Can deal with problems where the search state is difficult to represent/formulate.
- Can be used in an online setting when the problem changes, e.g., in airline scheduling problem.
Local search methods
- Hill climbing, e.g. gradient descent.
- Simulated annealing, tabu search (keep a small list of recently visited solutions and forbid the algorithm to return to those solutions).
- Population based local search: evolutionary computation (e.g., genetic algorithms).