Optimization using Hill Climbing

The following example shows how to find the best portfolio configuration given that only the price of a single stock can be incremented by 10 cents at a time. Since we are using Hill Climbing technique, we can find the local optimal value easily but the same cannot be said for finding the global optimal value, unless you continuously repeat the climbing procedure in an iterative manner or use variable number of restarts.

portfolio = {
                'VRNG'  : 3.54,
                'BBY'   : 13.75,
                'AMD'   : 1.86,
                'S'     : 5.48,
                'CHK'   : 16.62,
                'CLWR'  : 2.19,
                'SCGLY' : 6.22,
                'HES'   : 48.91,
                'BAC'   : 9.12,
                'FB'    : 23.56
            }

stockCount = [random.randint(10, 100) // 10 * 10 for k in portfolio]

def optimize():
    """ Using Hill Climbing technique to find total valuation of a portfolio due
     to 10BP (Basis Point) movement in the price of the stock.
     Assuming I own 100 quantities of each stock """

    import sys
    bestValue = -sys.maxint
    bestPrices = None
    stockNames = portfolio.keys()
    stockPrices = [portfolio[k] for k in stockNames]

##    print 'Your current portfolio contains the following stocks:'
    from itertools import izip
##    for sn, sp, sc in izip(stockNames, stockPrices, stockCount):
##        print '{0:5} {1:5} {2:5}'.format(sn, sc, sp)
##    print

    neighbours = []
    for idx in xrange(len(stockPrices)):
        neighbours.append(stockPrices[ :idx] + [stockPrices[idx] - 0.10] + stockPrices[idx + 1 :])
        neighbours.append(stockPrices[ :idx] + [stockPrices[idx] + 0.10] + stockPrices[idx + 1 :])

    def computeSum(arr):
        return sum([sp * sc for sp, sc in izip(arr, stockCount)])

    currValuation = computeSum(stockPrices)
    for n in neighbours:
        newValuation = computeSum(n)
        if newValuation > bestValue:
            bestValue = newValuation
            bestPrices = n

    if currValuation == bestValue:
        print 'Current Portfolio value will still remain profitable!'
    else:
        print 'Possibility to make a profit of $%s with the following portfolio (using Hill Climbing): ' % (bestValue - currValuation)
        print 'Name     Qty     Old        New     chg'
        for sn, sp, bp, sc in izip(stockNames, stockPrices, bestPrices, stockCount):
            print '{0:5} {4:5} {1:10} {2:10} {3:5}'.format(sn, sp, bp, bp - sp, sc)
        print 'Original Valuation: %s Profitable Valuation: %s' % (currValuation, bestValue)


def main():
    optimize()

Output:

>>> 
Quite possible to make a profit of $9.0 with the following portfolio (using Hill Climbing): 
Name     Qty     Old        New     chg
HES      30      48.91      48.91   0.0
S        80       5.48       5.48   0.0
BAC      30       9.12       9.12   0.0
BBY      90      13.75      13.85   0.1
SCGLY    90       6.22       6.22   0.0
VRNG     50       3.54       3.54   0.0
FB       70      23.56      23.56   0.0
CHK      50      16.62      16.62   0.0
AMD      70       1.86       1.86   0.0
CLWR     20       2.19       2.19   0.0
Original Valuation: 6807.8 Profitable Valuation: 6816.8
>>> 
Quite possible to make a profit of $10.0 with the following portfolio (using Hill Climbing): 
Name     Qty     Old        New     chg
HES      60      48.91      48.91   0.0
S        70       5.48       5.48   0.0
BAC      90       9.12       9.12   0.0
BBY      50      13.75      13.75   0.0
SCGLY    30       6.22       6.22   0.0
VRNG     60       3.54       3.54   0.0
FB      100      23.56      23.66   0.1
CHK      10      16.62      16.62   0.0
AMD      90       1.86       1.86   0.0
CLWR     90       2.19       2.19   0.0
Original Valuation: 8112.2 Profitable Valuation: 8122.2

leave your comment