Optimization Techniques: Heuristics, Metaheuristics, and Simulation
Heuristics
Heuristics are any approach to problem-solving or self-discovery that employs a practical method, not guaranteed to be optimal, perfect, or rational, but instead sufficient for reaching an immediate goal. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Mathematical models often give the optimum solution. Heuristics give approximations.
Simulation
Simulation is the process of designing a model of a real system and conducting experiments with this model for the purpose of understanding the behavior of the system and/or evaluating various strategies for the operation of the system.
Purpose:
- Gaining insight into the problem
- Developing policies to improve the performance of a system
- Testing new policies/solutions before implementation
- Not disturbing the actual system when doing the three above
Metaheuristics and Genetic Algorithms
Metaheuristics are computationally intensive heuristics. They carry out many more calculations. They are often based on local search, also based on metaphors with real processes, biology, physics, etc.
- Simulated annealing
- Genetic algorithms
- Tabu Search
- Iterated Greedy, Ant Colony Optimization… there is a world out there
Evolution is this process of adaptation with the aim of improving survival capabilities through processes such as natural selection, survival of the fittest, reproduction, mutation, competition, and symbiosis. Genetic Algorithms (GAs) mimic the processes of natural selection and survival of the fittest and, in general, the evolution of species. They work with a set of solutions, called a “population.” At each step, some genetic operators are applied (selection, crossover, mutation). Solutions (individuals) with a better objective function value (fitness) have more probability of survival, through selection and crossover.
Matheuristics and Simheuristics
Matheuristics are optimization algorithms made by the interoperation of metaheuristics and mathematical programming techniques. An essential feature is the exploitation in some part of the algorithms of features derived from the mathematical model of the problems of interest.
Simheuristics combine heuristics, metaheuristics, and mathematical programming with simulation. They complement the simulation of a system or process by allowing obtaining optimal solutions for the simulated system.
Game Theory
A game is a decision process in which several agents, called players, with conflicting objectives act. At the end of the game, each player receives a payoff. The objective of each player is to maximize their individual payoff, even if other players’ payoffs get worse by doing this. In this class, we’ll assume that players want to maximize a certain benefit. The case of minimizing a certain cost can be done analogously. Game theory can be divided into two branches:
- Non-cooperative game theory: when players are not allowed to cooperate (competition among companies)
- Cooperative game theory: players are allowed to cooperate (cooperation among companies)
Weighting Method
max Z =+- aZ1 +-(1-a)Z2 min-max+
max Z=+- a1Z1 +- a2Z2 +-anZn
α-Lexicographic Modeling
OF ≥ (1-α)Z*
Goal Programming
Ni and Pi are negative and positive deviations
Zi + Ni – Pi = ti
e Y <= X <= MY
Fixed cost MY