Practical Optimization Algorithm Design Lesson 2: The Structure of Optimization
Dr.-Ing. Thomas Weise
Nature Inspired Computation and Applications Laboratory (NICAL)
School of Computer Science and Technology
University of Science and Technology of China (USTC)
Contents
?Example Algorithm ?Problem Space
?Objective Function
?What does “good” mean? ?Search Space
?Genotype-Phenotype Mapping ?Further Definitions
?Overall Structure
?Solving Optimization Problems ?Summary
What is optimization?
? Hm, can you give some examples for optimization problems?
a)Bin Packing: bins of size , objects of size … .
Question: Can we pack them into the bins?
b =5
bin 0
bin 1bin 2bin 3bin 4
to a 110
?Bin Packing: bins of size ,
objects of size … .
?Optimization: Find assignment with
least overflow minimize
? 0,
Problem Space
?Problem Space
The problem space (phenome) of an optimization problem is the set containing all elements which could be its solution. ?Candidate Solution
A candidate solution (phenotype) is an element of the
problem space of a certain optimization problem
Problem Space
?What could possible problem spaces be?
a)Bin Packing
b)Circuit Layout
c)Job Shop Scheduling
d)Routing
e)Find the roots of
f)Find mathematical formula
g)Stock Prediction
h)Truss Optimization
i)Medical Classification
j)Airplane Wing Design
Problem Space
?Practical constraints: Why can a (default) implementation of an optimization algorithm on a 80x86 processor not discover
elements such as 1 10 even if ?
Objective Function
?Objective Function
An objective function : is a (mathematical) function
which is subject to optimization.
?Usually subject to minimization
?Not necessary a function like but may be arbitrarily complex…
Objective Function
?Example: Stone’s Throw
Which is best velocity with which I should throw a stone (in an 15° angle) so that it lands exactly 100 away (assuming
uniform gravity and the absence of drag and wind)?
Objective Function
? Example: Stone’s Throw
? Problem Space:
? Objective function:Minimize | 100 |
sin 2
0.051
?
Objective Function
?Example: Stone’s Throw
?Problem Space:
?Objective function:Minimize | 100 |
Easily solved, since formula and minimal
value of is known and straightforward
Objective Function
?Example: Traveling Salesman Problem
A salesman wants to visit cities in the shortest possible time under
the assumption that no city is visited twice and that he will again
arrive at the origin by the end of the tour.
The goal of the Traveling Salesman Problem (TSP) is to find a cyclic path of minimum total weight which visits all vertices of a weighted
graph.
Objective Function
?
?Beijing, Chengdu, Guangzhou, Shanghai
?Objective function: Hefei, 0 , 1
3 ,Hefei
Objective Function
Hefei Beijing Guangzhou Chengdu Shanghai Hefei 8311 Hefei
Beijing Guangzhou Shanghai Chengdu Hefei 7886 Hefei Beijing Shanghai Chengdu Guangzhou Hefei 7381 Hefei Beijing Shanghai Guangzhou Chengdu Hefei Hefei Chengdu Beijing Guangzhou Shanghai Hefei 8787 Hefei
Chengdu Beijing Shanghai Guangzhou Hefei 7857 Hefei Chengdu Guangzhou Beijing Shanghai Hefei 8602 Hefei Chengdu Shanghai Beijing Guangzhou Hefei 8743 Hefei Guangzhou Beijing Chengdu Shanghai Hefei Hefei Guangzhou Chengdu Beijing Shanghai Hefei 7566
Objective Function
? Example: Traveling Salesman Problem
? The size of the problem space is
1 !
f(x)=x
f(x)=x 2f(x)=x 4
f(x)=x 8
10
f(x)=x 10
x
ms per day picoseconds since big bang x
x
x
Objective Function
?What could possible objective functions be?
a)Bin Packing
b)Circuit Layout
c)Job Shop Scheduling
d)Routing
e)Find the roots of
f)Find mathematical formula
g)Stock Prediction
h)Truss Optimization
i)Medical Classification
j)Airplane Wing Design
Objective Function ?Example: Antenna Design ?Example: Analog Electric Circuit Design ?Example: Interactive Optimization
What does “good” mean?
?Single objective function
1
What does “good” mean?
?Extrema: Minima and Maxima of : and
is local extremum of 0? 0 0 is local minimum ? 0 0 is local maximum ?sign change of ’from –to is local minimum ?sign change of ’from to is local maximum