I.O.P.S. 5 :: Meta-heuristics and bio-inspired heuristics

Classification of optimization methods

Meta-heuristics

Evolutionary optimization

Evolutionary optimization

2 main questions


  1. How to represent a solution to my problem ? How does the genome/chromosome/value vector look like ?

  2. How to evaluate the fitness ? = What is the fitness function ?


if You can answer these questions, You can construct an evolutionary algorithm. the rest (hyper-parameters etc.) is just "tuning".


NOTE: The fitness landscape of Your problem has to be at least little bit structured.

Example: Rocket launch

https://bleuje.github.io/p5js-myprojects/rocket-optimization/index.html

Example: identification of atomic tomb location candidates

Simulated annealing

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It is often used when the search space is discrete (e.g., the traveling salesman problem). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent, Branch and Bound.

https://en.wikipedia.org/wiki/Simulated_annealing

Annealing ? WTF ?

Simulated Annealing :: What it does

S.A. exercise: Rocket launch revisited

https://bleuje.github.io/p5js-myprojects/rocket-optimization-sa/index.html

S.A. How & why it works

Simulated Annealing :: Exercise

You will be divided into two break-out rooms, each group will include at least two Python ninjas.

Task: transform Maurice's Genetic algorithm for detection of furthest point into Simulated Annealing form

Hint: check https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.optimize.anneal.html

Ant colony optimization

Ant colony optimization

Tabu search