Objective function
Function that needs to be maximized or minimized
Travelling salesman problem (TSP)
Find the hamiltonian path with minimal cost of a given set of points
What are real-life applications of the TSP?
Last-mile delivery routing
Drilling of printed circuit boards
Computer wiring
The order-picking problem in warehouses
What are real-life applications of the knapsack?
Investment portfolio optimisation
Ordering in a restaurant
What is exhaustive search?
Perform complete enumeration of all possible solutions after which the best one is selected
What is an exact method?
Method that finds the optimal solution using exhaustive search or by excluding subsets of solutions
What is a heuristic?
technique designed for solving a problem more quickly when exact methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution
What is the optimality gap?
Difference of optimal solution and solution found by heuristics
What is a stopping criterion?
Criterion that defines when the heuristic should stop its search
What does problem-dependent search procedures mean?
The need to tailor the rules of the heuristic to the specific problem
What is a metaheuristic?
A high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimisation techniques
What are the four metaheuristic frameworks?
Constructive metaheuristics
Local search metaheuristics
Population-based metaheuristics
Hybrid metaheuristics
What is a constructive metaheuristic?
Metaheuristic that constructs solutions from their constituting elements, by adding moves to partial solution e.g. greedy algorithm
What is the nearest neighbour?
Greedy algorithm finds nearest neighbour from points which has not been added to solution, can add randomness by restricted candidate list
What are look-ahead strategies?
Methods that evaluate the elements that can be added by considering not only the effect of the next move, but of several moves into the future
What are local search metaheuristics?
Metaheuristics that find good solutions by iteratively making changes to a single solution, called the current solution
What are neighbourhood?
Set of solutions that can be obtained by applying a single move to the current solution
What is move strategy / search strategy?
rule used to select new current solution
- Decide on a move type
- Decide on the strategy
What is a local optimum?
No solutions in the neighbourhood improve the current solution
What are hill-climbers?
Best improvement option after performing a local search metaheuristic
What is peturbation?
A large random change to the current solution
What is iterated local search?
Metaheuristic that iteratively performs local serach and peturbation
What is multistart local serach?
Metaheuristic that iteratively performs local serach and restart
What is variable neighbourhood search algorithms?
Metaheurstic that define different move types and change the move type used once a local optimum has been reached
What are tabu search algorithms?
Strategy that uses information on the past progress of the search and record this information in memory structures
What is simulated annealing?
local search with probability that accept inferior solution
What are population-based metaheuristics?
Metaheuristics that find good solutions by iteratively selecting and then combining existing solutions from a set, usually called the population
What are the steps of a genetic algorithm?
- Initialize population
- Evaluate current solutions
- Parent selection
- Recombination (Cross-over operator)
- Repair operator
- Mutation
- Reinsertion of offsprings in population
- Check stopping criterion
What are hybrid metaheuristics?
Metaheuristic that use more than one of the previously discussed metaheuristics
What is GRASP?
Greedy randomized adaptive search procedure
- Construct an initial solution using a randomized greedy algorithm
- Apply local search on the constructed solution
- Update the current best solution
- Start with step 1
What is a memetic algorithm?
Variant of the geneti algorithm, where a local search is added between step 6&7 (mutation & reinsertion of offsprings in population)
