Problems in Operations Research are divided into two types: P problems and NP-hard problems. P-hard problems are problems that have an exact solution approach with polynomial-time exists whereas similar approaches for NP-hard problems are still undiscovered.
One approach for solving NP-hard problems is called heuristics methods and heuristics itself consist of two types: construction heuristics and improvement heuristics. Metaheuristics are one of improvement heuristics approach that design and control the solution to overcome local optimum by temporarily worsening the values of the objective function.
Metaheuristics have two mains strategies, intensification, and diversification. Intensification aims to intensively explore known solution spaces and determine the local optimum within that area, whereas diversification has the purpose to explore new areas and break out from the local optimum. Moreover, Metaheuristics have two variations in modifying the solutions, local search-based, and population-based metaheuristics.
Local search-based algorithms such as Tabu Search and Simulated Annealing consider one solution and evaluating its neighbors for finding the better solution. In the example of Tabu Search, this algorithm applies local search and best find strategy iteratively to identify the best neighbor without comparing them to the current solution and then memorize the solution in a tabu list.
Simulated Annealing also applies the same method however the new better solution is chosen based on a measurement called acceptance probability. Population-based consider several solutions simultaneously and iteratively modified and combined to improve the solution.
One popular example is Genetic Algorithms: this algorithm creates a set of solutions to then iteratively move them from one generation to a new one based on objective function values or generate a new one by crossover.
Metaheuristics approaches are popular because they are easy to implement and applicable to most optimization problems. Moreover, even metaheuristics’ results are rarely optimal, they provide ‘good’ solutions with a small deviation from optimal solution (if known).
Commenti