• Ingen resultater fundet

Introduction to Optimization Using Metaheuristics




Academic year: 2022

Del "Introduction to Optimization Using Metaheuristics"

Vis mere ( Sider)

Hele teksten


Introduction to Optimization Using


Thomas J. K. Stidsen



General course information

Motivation, modelling and solving

Hill climbers

Simulated Annealing



Large-Scale Optimization

Wellcome to the course ! Course homepage:


Take a look at the course plan.


The Lecturer: Thomas Stidsen

Name: Thomas Stidsen: tks@imm.dtu.dk

Nationality: Danish.

Languages: Danish and English.

Education: Ph.D. OR/mathematics and Msc. in Computer Science

Teaching: Teaching in Linear Program- ming (42112) and Large Scale Opti- mization using Decomposition (42132),

Optimization using Meta-heuristics (42133) and Advanced OR (42134).

Research: Optimization of telecommu- nication networks




Lectures will be given once each week:

Monday 13.00-17.00, in databar 43 building 303N



Grades will be based on the project as- signment:

1 large 8 week project, starting 7/3, pre-hand in 21/3 and final hand in 26/4, presentation 2/5 and 9/5 (in english). Oral examination 19/5.




The course litterature is:

”Search Metholodogies“, Edmund K.

Burke & Graham Kendall, ISBN0-387- 23460-8.


The different Metaheuristics

In the book you will find 19 different chap- ters, each on a specific metaheuristic or topic. This is too much for this course and not all of it is relevant, but they are:

1. Introduction

2. Classical Techniques

3. Integer Programming

4. Genetic Algorithms*

5. Genetic Programming

6. Tabu Search*



7. Simulated Annealing*

8. Variable Neighborhood Search

9. Constraint Programming

10. Multi-Objective Optimization

11. Complexity Theory and the No Free Lunch Theorem*

12. Machine Learning

13. Artificial Immune Systems

14. Swarm Intelligence*


15. Fuzzy Reasoning

16. Rough Set Based Decision Support

17. Hyper Heuristics

18. Approximation Algorithms

19. Fitness Landscapes


The different Metaheuristics II

You may be confused by the different methods, but there are many more out there !

I only present a selection of the me- tods which I consider essential.

There is no such thing as a best metaheuristic !!!. This has actually been proven mathematically (chapter 11) ! Select the best metaheuristic for the problem at hand.


Determined by counting hits on Google.

2003 2004 2005 2006 2008 2010

SA 81100 143000 342000 266000 654000 534.000 TS 20240 43500 88100 64200 36300 33.300 GLS 688 1540 895 114000 163000 70.600

ILS - 2250 4000 775 3010 81.800

EA - - 988000 250000 547000 203.000

AC - - 105000 2170000 216000 622.000

GRASP - - 4370 22600 26400 14.900

SI - - - 110000 26100 32.600

HI - - - 12600 30.700 19.400

GP - - - 267000 253.000 423.000

AIS - - - 32100 11.200 59.100



Search terms:

SA = <’’simulated annealing’’>

TS = <’’tabu search’’ OR {}‘‘taboo search’’>

GLS = <’’guided local search’’>

ILS = <’’iterated local search’’>

EA = <’’evolutionary algorithms’’ OR {}‘‘genetic AC = <’’ant colony’’ OR {}‘‘ant system’’>

GRASP = <’’greedy randomized adaptive search’’>

SI = <’’swarm intelligence’’>

HH = <’’hyper heuristics’’>

GP = <’’genetic programming’’>


AIS = <’’artificial immune systems’’>

SA and EA are known and used outside the computer science/enginering/OR domain.


Large-Scale Optimization

What is this course about ?

Methods to solve problems which can- not be solved by standard solvers.


An Operations Researchers Work




Solving Modelling

"Real World

Computer models/simulations

Mathematical models Rules of thumb



What are hard problems ?

Problems can be hard for two reasons:



Complex objective functions/constraints:

Non-linear, non-continous

Complex domains for optimisation variables: Integers !

How many of you have heard about com- plexity theory ? (computer science).


Hill Climbers and Simulated Annealing



Computer based optimisation

Assume we have:

A welldefined problem domain, i.e. com- plete identification of design variables (endogenous variables)

A computer model (program) which can calculate the costs of a certain choice of variables

Then we can use a computer to search the problem domain.


Optimisation as search



1 1


1 ...



How to search ?

There are several ways to search the po- ssible solutions:

Systematic search, i.e. complete enu- meration (branch and bound)

Random search, just try as many ran- dom samples as possible

Smart search, maybe we can create a smart algorithm to solve the particular problem, eventhough the number of possible solutions is huge (P problems ...)

Local search: Start somewhere and t- hen iteratively improve



Local Search Terminology

When working with local search we use a number of terms:

A solution, a possible but not neces- sary optimum to a optimisation pro- blem, i.e. an assignment of variable values

A neighbourhood is a number of so- lutions within a certain “distance” of a solution in parameter space

An evaluation function which maps parameter space into objective space


Local Search Terminology


Intermediate solution Finish

Start S



Example: Branin function

Lets look at a simple example: Branin’s function:

f1(x, y) = 1 2y + 201 sin(4πy) x

f2(x, y) = y 12sin(2πx)

φ(x, y) = 12(f1(x, y)2 + f2(x, y)2)


Zero Points








Hill Climbers

Assuming minimisation we can use a so- called hill climber (actually hill descenter):

select initial solution s0


select s N(si)

if f(s) < f(si) then si+1 = s

until stopping criterion is true

Notice that we could view the simplex al- gorithm as a local hill climber.


Hill climber parts

The main parts of the hillclimber are:

Generation of initial solution

Definition of neighbourhood

Selection from neighbourhood:

Select best

Search entire neighbourhood, but switch when better

Stopping criteria



Problems with hill climbers

There are two main problems with hill climbers:

Local optima, means no optimality gu- arantee

Needs adaptation to the problem

But there are many examples where simp- le hillclimbers perform well.


Hill climbing on Branin

So lets try to hill climb (ok, hill descent) the Branin function.



I admit

Ok, I admit, I am cheating:

I have discretized the variables, i.e. in- stead of two continuous variables in the interval [10,10] they have be- en replaced with two discrete variab- les between 0 and 100. These are then rescaled into the interval.

Actually I am using the Simulated An- nealing algorithm instead of a hill clim- ber, but setting the parameters in a stupid fashion, simulating a hill clim- ber.


Simulated Annealing

select initial solution s0

t = Tstart repeat

select s N(si) δ = f(s) f(si)

if δ < 0 or with probability p(δ, ti) then si+1 = s

ti+1 = ti · α

until stopping criterion is true



Acceptance probability

The analogy to statistical thermodynami- cs gives us the following acceptance pro- bability p(n):

p(δ, ti) = exp(1 tiδ)

where ti is the “temperature” at step i. Typically p(i) decreases with time i and the size of the deteriation (δ).

The laws of thermodynamics state that at temperature t, the probability of an in- crease in energy of magnitude δE is given by:

p(δE) = exp(−δE kt )


Probability function

0 0.2 0.4 0.6 0.8 1

0 2 4 6 8 10

exp(-x/10) exp(-x) exp(-x/0.1)



General Comments

Simulated Annealing is:

Invented in 1983 by Kirkpatrick, Gel- lat and Vecchi (based on earlier work by Metropolis).

The simplest of the metaheuristic al- gorithms

Have only few parameters: Tstart, α and termination parameter ...

Is invented based on the annealing pro- cess of metals (but the analogy is we- ak) ....

Delta evaluation is usually possible


Controlling the temperature

The tempeature should allow (almost) all moves to be accepted in the begin- ning of the execution of the algorithm,

then gradually the temperature is decrea- sed, and

towards the end of the execution of the algorithm almost only improving solutions should be accepted.

Methods for controlling the tempera- ture are called cooling schedules or temperature schedules.



More on the temperature

The start temperature should be high enough to make a large fraction of the neighbours acceptable.

The temperature should not be so high that we spend time working with to high temperatures.

The accept ratio is the ratio between the number of selected solutions and the number of accepted solutions.

Aim to get the accept ratio around 0.5 in the beginning of the search.

Can depend on the structure of the problem.


Now we need to determine t0 on the basis of the accept ratio.

Try different values and see what hap- pens.

If time is not a critical faktor “just choose t0 high enough”.

If we are using a “good” start solution (generated by a construction heuri- stic) high temperatures might “destroy it”. Therefore start lower.


Stopping criterion

When should we stop ? This is a very im- portant point which I will mention many times: We should stop when we are requi- red to stop !!!

If we compare the same metaheuristic on the same problem, but given dif- ferent run-times, the longest running algorithm will on average ALWAYS win.

If we build a meta-heuristic algorit- hm for a specific purpose, we ask the problem-owners to say how much ti- me we have ! Then we will use ALL this time.

Hence time is not a parameter, it is externally given.


Hence our algorithms always termina- te after the time has expired.


A little theory

The behaviour of simulated annealing can be modelled using Markov chains.

At constant temperature the proba- bility pij of moving from one solution i to another solution j depends only on i and j.

This type of transition give rise to a homogenous Markov chain.

This process converges towards a sta- tionary distribution which is indepen- dent of the starting solution.


As the temperature tends to zero the distributions tends to a uniform distri- bution over the set of optimal solu- tions.

As the temperature is not constant t- he process can be seen as a number of different homogenour Markov chains.


What about the neighbourhood?

A difference to Tabu Search is that we do not have to check the whole neighbourhood. Size is not that criti- cal anymore.

Is the change easy to compute?

Allow non-feasible solutions to be part of the solution space.


Tips and tricks

Consider making some of the constraints into “soft constraints”.

Consider the number of accepted m- oves rather than the number of tri- als when deciding when to change the temperature. This number is denoted the cut-off parameter). Short time will be spend at high temperatures. Be ca- reful about not using too much time at low temperatures.

Replace the computation of exp(−δ/tn) by an approximation or precomputed exponentials.

Use cyclic sampling instead of random sampling (requires enumeration of the neighbourhood).



Reheating? (non-monotonic SA).

Many short runs instead of one long run.

Look at pictures or traces of the e- xecution of the algorithm.



Problems with the algorithm:

The theory is weak ...

Very little direction, means long runs ...

Difficult to parallelize

Difficult to use for Multi Criteria op- timisation




Similarly to the randomized algorithm, we store in safe memory the search key, e, and the left and right sequence indices, l and r, used by the binary search.. Initially, l = −1 is

By combining the unit commitment optimization problem and the economic model predictive control problem, it is possible to obtain an intelligent control strategy that can overcome

Solve the LP problem with column generation, and after the column generation algorithm has finished, the MIP model is solved using a.

performance and power optimization in NoC design using Tabu Search optimization method. • New approach to contention relief using Layered Queuing Networks (LQN) and a

A classic problem which is widely used to solve many different problems. Very often the problem arises after

The crucial insight: The number of non-zero variables (the basis variables) is equal to the number of constraints, hence eventhough the number of possible variables (columns) may

In the Newsletter, in addition to concordance search, Copy/Cut à Copy Source to Target à Insert, termbase search, Google search, search in online dictionary, search in

“A tabu search algorithm for the open shop scheduling problem”, C-F..

The result of exact line search is normally a good approximation to the result, and this can make descent methods with exact line search find the local minimizer in fewer

The result of exact line search is normally a good approximation to the result, and this can make descent methods with exact line search find the local minimizer in fewer

We can solve problems fast (even big problems with hundreds of constraints and thousands of variables solve in seconds or fractions hereof).. We can model a lot of problem type

s.t. It is again a linear programming problem, so nothing is gained with respect to ease of solution – we have no reason to believe that DP is any easier to solve than P. However,

s.t. It is again a linear programming problem, so nothing is gained with respect to ease of solution – we have no reason to believe that DP is any easier to solve than P. However,

%/LTR DESIGN 33 considered fulfils a minimum phase condition (although the reduction is possible also for certain non-minimum phase systems) yielding an

To solve the puzzle of transitioning to smart energy on both nation and global level, the resulting research objective addresses the following question: What role can islands

The most common approach is to fit a CPH model, (Cox, 1972), and search for significant, in terms of p-values, independent predictors of the survival time using a stepwise

we can solve a convex problem with about the same effort as solving 30 least-squares

An important part of this ability to represent solutions is in the fact that patterns can represent solutions to small part of the application (such as search functionality),

Sudoku is a member of the N P-complete subset and is therefore an ideal problem to investigate, when considering multi-agent systems to solve N P -complete problems.. There

The quote: “For the Benders decomposition algorithm to be effective it is essential that the linear programming subproblem have special structure so that it is easily optimized”, p.

At present, it is not possible to search for the passive form of verbs in THE D ANISH I NTERNET D ICTIONARY.. However, the log fi le reveals that quite a large number of

We think an introduction to the modelling technique is helpful, but it seemed to be possible to start a participatory design process using modelling methods almost

The proposed building optimization method uses the gradient-free SQP filter algorithm in order to solve the formulated optimization problem, which involves performance measures that