Transcript Document

Introduction
Metaheuristics
Byung-Hyun Ha
R5
Outline
 Introduction
 Optimization problems
 Optimization methods
 Hard problems
 Python programming
1
Introduction
 Metaheuristics
 A major subfield of stochastic optimization
 Assuming little or no information about problems being solved
 Stochastic optimization
 Employing some degree of randomness to find optimal (or as optimal as
possible) solutions to hard (optimization) problems
 (Mathematical) optimization (problems)
 Selection of a best element (the optimal solution) from some set of
available alternatives (feasible solutions)
• e.g., Location of facilities, network optimization, layout planning, routing and
scheduling, optimal control, ...
 And..
 Little or no information?
 Some degree of randomness?
 Hard problems?
2
Optimization Problems
 Described by (usually..)
 objective, input, constraints, output (decision variables or solution)
 Examples
 (0-1) knapsack (optimization) problems (combinatorial optimization)
• Input: Finite set U, for each u  U a size s(u)  Z+ and a value v(u)  Z+, and
positive integer B
• Question: Determine a subset U'  U such that uU' s(u)  B and so that
uU' v(u) is maximized
 Schwefel (nonlinear programming)
 Optimization by logistics simulation (nonanalytic models)
• Find the best logistics network
3
Optimization Problems
 Problem description (e.g., knapsack problems)
 Using natural language and graphics
• Given a set of items, each with size and value,
determine items to be included in a knapsack
so that the total volume is less than or equal to
a given limit and the total value is as large
as possible.
5
2
7
3
?
1
 Using mathematical notation (more precisely..)
• Input: Finite set U, for each u  U a size s(u)  Z+ and a value v(u)  Z+, and
positive integer B
• Question: Determine a subset U'  U such that uU' s(u)  B and so that
uU' v(u) is maximized
 Using mathematical programming form
•
•
•
•
vi: value of item i, si: size of item i
xi = 1, if item i is included; 0, otherwise
max. i vixi
s.t.
i sixi  B
xi  {0, 1}
4
Optimization Problems
 Feasible solutions
 Solutions that satisfy constraints
 The optimal solution
 A feasible solution that gives the best (minimum or maximum) objective
function value
 Solution space
 Collection of all feasible (and infeasible) solutions
• Some of solutions in solution space are optimal solutions
 e.g., n candidate items in knapsack problem: 2n
• 100 items: 1,267,650,600,228,229,401,496,703,205,376 possible solutions!

Knapsack problems




vi: value of item i, si: size of item i
xi = 1, if item i is included; 0, otherwise
max. i vixi
s.t. i sixi  B
xi  {0, 1}
5
Optimization Methods
 Solving problems and obtaining (optimal) solution
 All-enumeration?
• Knapsack problem
• 100 items: 1,267,650,600,228,229,401,496,703,205,376 possibilities
• Schwefel
6
Optimization Methods
 Exact methods
 e.g., find a largest element in a sequence?
 e.g., F-problem of single-machine scheduling
• Problem description
• Given n jobs with processing time given, find the optimal schedule that
minimize the total flowtime (completion time).
• Example instance
• 3 jobs of {1, 2, 3}, with processing time p1 = 5, p2 = 2, p3 = 3
• Q: Number of possible schedules?
• A: Infinite, why?
1
2
2 1
1
1
2
3
2
3
1
3
2
1
2
1
1
3
2
3
3
3
3
1
1
...
1
2
3 2
1
3
...
...
7
Optimization Methods
 Exact methods (cont’d)
 e.g., F-problem of single-machine scheduling (cont’d)
• Properties (theorems)
• Schedule without inserted idle time constitute a dominant set.
• Schedules without preemption constitute a dominant set
 A schedules can be completely specified by a permutation of jobs
1
2
2 1
1
1
2
3
(O)
2
3
(X)
1
(X)
2
3
1
2
1
1
3
(O)
2
3
(X)
3
3
(X)
3
1
1
1
2
3 2
1
3
(O)
...
(X)
...
(X)
...
8
Optimization Methods
 Exact methods (cont’d)
 e.g., F-problem of single-machine scheduling (cont’d)
• Q: How many schedules do we need to consider, then?
• A: 3! = 6, why?
1
2
2
3
3
1
1
3
3
1
2
2
2
3
1
2
3
1
• Hence, a schedules can be completely specified by a permutation of integers
• (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
• Size of solution space with n jobs
• n!
• How many possible schedules if we have 30 jobs?
• 30! = 265,252,859,812,191,058,636,308,480,000,000
9
Optimization Methods
 Exact methods (cont’d)
 e.g., F-problem of single-machine scheduling (cont’d)
• Theorem
• Total flowtime is minimized by shortest processing time (SPT)
sequencing
• Proof sketch (proof by contradiction)
• Suppose there is a sequence S that is optimal but not SPT sequence.
• In S, there exists a pair of adjacent jobs, i and j, with j following i, such
that pi  pj .
• Construct sequence S' in which job i and j are interchanged.
• Fi + Fj  Fj' + Fi' implies that F  F', which is a contradiction.
• Therefore, for all S, if S is optimal, then S is SPT sequence.
• To get optimal solution,
• Sort jobs by processing-time-decreasing order!
10
Optimization Methods
 Exact methods (cont’d)
 e.g., knapsack problems?
 e.g., T-problem of single-machine scheduling
• Problem description
• Given n jobs with processing time and due date given, find the optimal
schedule that minimize the total tardiness.
• Example instance
tardiness
Job j
1
2
3
pj
dj
3
8
8
6
3
10
due date
completion time
• Property?
• Total tardiness is minimized by earliest due date (EDD) sequencing?
• NO!!! (why? prove it.)
11
Hard Problems
 How about it?
 If it takes long time to solve a problem, it is a hard problem.. ;-)
 Solve a problem?
 Using an algorithm with input of size n
 Algorithms
 A finite list of well-defined instructions for solving a problem
 e.g., selection sort of sequence of n items (x1, x2, ..., xn)
• for each i = 2, ..., n do:
• ji
• t  xj
• while j > 1 and t < xj –1:
xj  xj –1
jj–1
• xj  t
• Is it a hard problem?
• How much time it takes to sort?
12
Hard Problems
 Measuring the time complexity of algorithms
 Definition: big-O notation (upper bound)
• An algorithm has a complexity f(n) = O(g(n)) if there exist positive constant n0
and c such that n > n0, f(n)  cg(n).
 Definition: big- notation (lower bound)
• An algorithm has a complexity f(n) = (g(n)) if there exist positive constant n0
and c such that n > n0, f(n)  cg(n).
 e.g., selection sort of sequence of n items?
 Important classes
 Polynomial-time algorithm
• Time complexity is O(p(n)), where p(n) is a polynomial function of n.
 Exponential-time algorithm
• Time complexity is (cn), where c is a real constant strictly greater than 1.
 Complexity of a problem
 Equivalent to the complexity of the best algorithm solving the problem
13
Hard Problems
 Example of time complexity
 Size of largest problem instance solvable in 1 hour (Garey and Johnson,
1969)
Time
complexity
With present
computer
With computer
100 times faster
With computer
1000 times faster
n
N1
100 N1
1000 N1
n2
N2
10 N2
31.6 N2
n3
N3
4.64 N3
10 N3
n5
N4
2.5 N4
3.98 N4
2n
N5
N5 + 6.64
N5 + 9.97
3n
N6
N6 + 4.19
N6 + 6.29
14
Hard Problems
 Example of time complexity (cont’d)
 Comparing algorithms with complexity of n, nlogn, n2, n8, 2n, 3n
• Assuming that our computer executes 106 computations per second
0.009
0.008
0.007
0.006
0.005
0.004
0.003
0.002
0.001
0
9E+05
8E+05
7E+05
6E+05
5E+05
4E+05
3E+05
2E+05
1E+05
0E+00
0
20
40
60
80
100
9E+17
8E+17
7E+17
6E+17
5E+17
4E+17
3E+17
2E+17
1E+17
0
0
20
40
60
80
100
0
20
40
60
80
100
80
100
• Assuming that our computer has become 103 times faster than above
0.009
0.008
0.007
0.006
0.005
0.004
0.003
0.002
0.001
0
9E+05
8E+05
7E+05
6E+05
5E+05
4E+05
3E+05
2E+05
1E+05
0E+00
0
20
40
60
80
100
9E+17
8E+17
7E+17
6E+17
5E+17
4E+17
3E+17
2E+17
1E+17
0
0
20
40
60
80
100
0
20
40
60
15
Hard Problems
 Then, how about it (more formally)?
 A problem is hard, if we are sure that there is not any polynomial-time
algorithm to solve the problem (to get the optimal solution)..?
 The above statement implies..
hard problems
clear boundary
easy problems
 But until now (sadly..),
 the clear boundary has not been proved yet
 i.e., neither one could present a polynomial-time algorithm, nor one
could prove there does not exist a polynomial-time algorithm, for
knapsack problems, T-problems, traveling salesman problems, ...
 It’s about NP-completeness (will be discussed next class)
16
Optimization Methods (revisited)
 Exact methods




Dynamic programming
Branch and bound
A*-search
...

Knapsack problems




 Example
 Dynamic programming for knapsack problems
vi: value of item i, si: size of item i
xi = 1, if item i is included; 0, otherwise
max. i vixi
s.t. i sixi  B
xi  {0, 1}
• g(k, b) =  g(k – 1, b),
if sk > b
g(k, b) =  max{g(k – 1, b), g(k – 1, b – sk) + vk}, otherwise
• g(k, 0) = 0 k, g(0, b) = 0 b
 Q: solve the following knapsack problem with B = 5.
Item j
1
2
3
4
vj
sj
3
2
4
3
5
4
6
5
 Exploiting information of problems HEAVILY!
17
Optimization Methods
 Approximation methods
 Approximation algorithms
 Heuristic algorithms
• Problem-specific heuristics
• e.g., EDD rule for T-problem
 Metaheuristics
•
•
•
•
•
Simulated annealing
Tabu search
Genetic algorithms
Ant colony optimization
...
 Using randomness to solve problems
 e.g., randomly choose next job among 2 earliest-due-date jobs for Tproblem
Job j
1
2
3
 Optimality?
pj
dj
3
8
8
6
3
10
18
Python Programming
 Why programming?
 No computer programming, no logical thinking (in my opinion)!
 Python
 A general-purpose, high-level programming language whose design
philosophy emphasizes code readability
 Supporting multiple programming paradigms
• Object-oriented, imperative, functional programming, ...
 Dynamic type system and automatic memory management
 Anyway.. powerful and beautiful (in my opinion)
 Why python?
 For computer programming experts
• It’s easy, so it gives no burden at all. (still powerful and can learn a lot!)
 For beginners
• It’s easy, so it’s best for the first programming language.
19
Python Programming
 Describing algorithms using Python
 Algorithm 1 -- Active Schedule Generation
1. Let k = 0 and begin with PS(k) as the null partial schedule. Initially, SO(k)
includes all operations with no predecessors.
2. Determine f* = minjSO(k) {fj} and the machine m* on which f* could be
realized.
3. For each operation j  SO(k) that requires machine m* and for which
sj  f*, create a new partial schedule in which operation j is added to
PS(k) and started at time sj .
4. For each new partial schedule PS(k + 1) created in Step 3, update the
data set as follows:
(a) Remove operation j from SO(k).
(b) Form SO(k + 1) by adding the direct successor of j to SO(k).
(c) Increment k by one.
5. Return to Step 2 for each PS(k + 1) created in Step 3, and continue in
this manner until all active schedules have been generated.
sj -- the earliest time at which operation j  SO(k) could be started
fj -- the earliest time at which operation j  SO(k) could be finished
20
Python Programming
 Describing algorithms using Python (cont’d)
def active_schedule_generation(X):
# active list (bs, vs, ps, s), set(X), current best
A, SX, z_best = [(0, 0, sum(j.p for j in X), [])], set(X), None
i, s_max = 0, 0 # iter #, max sequence size
# loop
while True:
bs, vs, ps, s = heappop(A) # subproblem
s_max = max(s_max, len(s))
s_ = SX.difference(set(s)) # set(s')
if len(s) == len(X): break # optimality check
djobs = [(j.d, j) for j in s_ if j.d >= ps]
if djobs: # step 3
j = max(djobs)[1]
pjs, vjs, js = ps - j.p, vs, [j] + s
s_.remove(j)
if s_: bjs = vjs + min(max(0, pjs - x.d) for x in s_)
else: bjs, z_best = vjs, vjs
heappush(A, (bjs, vjs, pjs, js))
else: # step 4
for j in s_:
pjs, vjs, js = ps - j.p, vs + ps - j.d, [j] + s
s_.remove(j)
if s_: bjs = vjs + min(max(0, pjs - x.d) for x in s_)
else: bjs, z_best = vjs, vjs
s_.add(j)
heappush(A, (bjs, vjs, pjs, js))
21
Summary
 (Mathematical) optimization (problems)
 Selection of a best element (the optimal solution) from some set of
available alternatives (feasible solutions)
 Stochastic optimization
 Employing some degree of randomness to find optimal (or as optimal as
possible) solutions to hard (optimization) problems
 Metaheuristics
 A major subfield of stochastic optimization
 Assuming little or no information about problems being solved
 Python programming
22