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)