HackMD
Week 11 & 12 Update
On weeks 11 and 12 worked on:
- 📊 Formulating prover criteria for the optimization model
- 📝 Taking notes on the prover mechanism research
Had a very productive discussion with Norbert. We decided to start designing the simulation model alongside formulating metrics. Preparing for agent-based simulation with cadCAD:
- Here's a great link for getting started: cadCAD Onboarding
- Enrolled in cadCAD bootcamp to learn to use the simulation tool effectively 📚👩🎓
Notes on Optimization
1. Introduction, Optimization Problems (MIT 6.0002 Intro to Computational Thinking and Data Science)
- An objective function that is to be maximized or minimized
- Minimize time spent traveling from New York to Boston
- A set of constraints (possibly empty) that must be honored
- Cannot spend more than $100
- Must be in Boston before 5:00PM
0/1 Knapsack Problem
You have limited strength, so there is a max weight you can carry
- "Each item is represented by a pair, <value, weight>
- The knapsack can accommodate items with a total weight of no more than w
- A vector, L, of length n, represents the set of available items. Each element of the vector is an item
- A vector, V, of length n, is used to indicate whether or not items are taken. If V[i] = 1, item /[i] is taken. If V[i] = 0, item I[i] is not taken
Find a V that maximizes the value
n-1
ΣV[i]* I[i].value
i=0
subject to the constraint that the total weight is less than or equal to w
n-1
ΣV[i]* [[i].weight ≤ w
i=0
Brute Force Algorithm enumerates all possible combinations of the items and remove the combinations whose weight exceeds the allowed weight. It's not very efficient due to the 0/1 knapsack problem being exponential!
Greedy Algorithm puts the "best" available item in the knapsack first
What defines the best?
- Most valuable
- Least expensive
- Highest value/units
def testGreedys(foods, maxUnits):
print('Use greedy by value to allocate', maxUnits,
'calories')
testGreedy(foods, maxUnits, Food.getValue)
print('\nUse greedy by cost to allocate', maxUnits,
'calories')
testGreedy(foods, maxUnits,
lambda x: 1/Food.getCost(x))
print('\nUse greedy by density to allocate', maxUnits,
'calories')
testGreedy(foods, maxUnits, Food.density)
names = ['wine', 'beer', 'pizza', 'burger', 'fries',
'cola', 'apple', 'donut', 'cake']
values = [89,90,95,100,90,79,50,10]
calories = [123,154,258,354,365,150,95,195]
foods = buildMenu(names, values, calories)
testGreedys(foods, 1000)
The problem of the algorithm is it can get stuck on a local optimum (local maximum) rather than the globally optimal solution (global maximum)!
Search Tree Implementation builts top down from the root as items are selected. As another item is added to the bag, a node gets created as a left branch (as long as the constraint are meet). On the other hand a right branch is formed reflecting the consequence of not including the added item. The process is then recursively applied to non-leaf children At the end a node with the highest value is choosen.
The downside is it gets too long to compute a solution with big data sets. The same as brute force, an inherently exponential problem!
Dynamic Programming
- Memoization
If we consider Fibonnaci's recursive implementation, it would repeat the same calculation, which would take a long time. Thus, it is more efficient to create a dictionary of the computations performed and check if the computation has the answer. The system looks it up and returns the value, otherwise will compute it.
def fastFib(n, memo = {}):
"""Assumes n is an int >= 0, memo used only by recursive calls
Returns Fibonacci of n"""
if n == 0 or n == 1:
return 1
try:
return memo[n]
except KeyError:
result = fastFib(n-1, memo) + fastFib(n-2, memo)
memo[n] = result
return result
for i in range(121):
print('fib(' + str(i) + ') =', fastFib(i))
When does it work?
-
Optimal substructure: a globally optimal solution can
be found by combining optimal solutions to local
subproblems- For x > 1, fib(x) = fib(x - 1) + fib(x – 2)
-
Overlapping subproblems: finding an optimal solution
involves solving the same problem multiple times- Compute fib(x) or many times
Summary
- Many problems of practical importance can be formulated as optimization problems.
- Greedy algorithms often provide adequate (though not necessarily optimal) solutions.
- Finding an optimal solution is usually exponentially hard.
- But dynamic programming often yields good performance for a subclass of optimization problems— those with optimal substructure and overlapping subproblems:
- Solution always correct
- Fast under the right circumstances
