Heuristic local search tutorial

Abstract

The Problem:

Real-world problems are usually (if not always) considered hard to be solved because:

* Problems cannot always be represented and solved with a straightforward mathematical approach. * A lot of parameters and constraints are involved. * The number of possible solutions to a problem can be huge. * Good solutions need to be found fast * Checking every possible solution, for finding the best one, is time consuming and sometimes not even feasible. * The quality of a solution may vary according to time, thereby; more than one different solution might be required.

Heuristic Search:

Heuristic search refers to techniques with the aim of finding ‘good’ solutions for a very hard optimization and decision within a reasonable amount of computation time.

Heuristic Local Search:

* A basic heuristic search technique that works with complete solutions and seeks to find better solutions by making small local changes. * All heuristic search techniques share similar concepts; e.g. the search space, feasible/infeasible solutions, neighbourhoods, and the relation(s) between neighbours. * Good understanding of the above concepts and how a basic local search works, is a key knowledge necessary to anyone who wishes to learn and work with heuristic and metaheuristic algorithms for solving hard real-world optimization problems.