Metaheuristic and Simulated annealing

Question 1

When do we apply Metaheuristics?

Answer 1

When the search space is too large

Question 2

Why is Metaheuristics applied on large search spaces instead of Exact Methods?

Answer 2

Exact methods will take too long to return a solution

Question 3

What is Metaheuristics in a way?

Answer 3

Heuristics of heuristics. Swapping values in a search space or widening search space

Question 4

What are the types of optimization problems?

Answer 4

Continuous, Discrete

Question 5

What is the difference between Continuous and discrete problems?

Answer 5

discrete = finite set of distinct values. Continuous = the values can change

Question 6

What type of problems do Branch and Bound solve?

Answer 6

Exact solutions

Question 7

What type of problems do Metaheuristics solve?

Answer 7

Deterministic + randomization

Question 8

How is a Combinatorial optimization problem defined as?

Answer 8

P = (S,f)
S = search space
f = objective function

Question 9

What are the characteristics of a Metaheuristic search?

Answer 9

It guides the search
Searches for near optimal solution
Not problem specific
Random
Provide no guarantee of Global/local optimality
long time thus stopping criteria is needed

Question 10

What are the 2 classifications of Metaheuristics?

Answer 10

Single point search and Population based.

Question 11

What is the difference between Single point search and Population based search?

Answer 11

Single point = work on a single solution iteratively improving it
population based = work on population of individuals each representing a solution

Question 12

What are the examples of single point searches?

Answer 12

Tabu search
Hill climbing
Simulated annealing
ILS
Variable Neighborhood Search

Question 13

What are examples of multipoint (population) search?

Answer 13

Genetic A
Genetic Programming
Grammatical Evolution
Particle swarm optimization
Ant Colony Optimization

Question 14

What is encoding?

Answer 14

The representation of a problem
(problem dependent + must be able to evolve feasible solutions)

Question 15

What is the main idea of Simulated Annealing?

Answer 15

Simulate metal cooling

Question 16

How does the Temperature affect the solutions in SA?

Answer 16

At each iteration a new candidate solution is chosen whose distance from the ideal is proportional to the temperature.
If the temperature is high it could still accept potentially worse solutions

Question 17

What is needed for SA?

Answer 17

initial solution generator
Next candidate selection generator
Cost function
Evaluation criteria
stop criteria

Question 18

Steps in SA

Answer 18

1) generate initial solution
2)get cost
3) generate solutions from neighbourhood
4) let Vn be best of the neighbours
5) if( cost of Vc < cost of Vn) then Vc = Vn (if you are looking for the highest value)
6) update temp ( T = T0/(log t+1))
Repeat until stopping criteria is met

Question 19

Adv of SA

Answer 19

easy to apply to many problems
Tune parameters easily
Is capable of finding the best solution

Question 20

Dis-Adv of SA

Answer 20

Can leave optimal solution
Results are usually not reproducible
Can take a lot of time