Our ‘bespoke’ simulated annealer

Summary: Our team wrote a custom simulated annealer (about a page of Python code) that often solves a 60x60 stock picking universe in 15 seconds.

A simulated annealer simulates the annealing, or temperature-based solution process, using a classical computer algorithm. We know annealing from the steelmaking industry where coils of hot-rolled steel (the expensive kind used by carmakers) are annealed to align the molecules and add characteristics to the metal. We simulate that process using Python. During high temperatures, the solver jumps easily to potentially better solutions.

As the temperature cools, it becomes harder to jump. We look for better answers closer to the best answer we have. When we are at the cold temperature, we stop and examine the resulting portfolio. Our custom coded simulated annealer first found the best portfolio in a 60 asset universe in 23 seconds, but now works in 15 seconds. It does not always find the best answer.

Wikipedia has a great explanation of simulated annealing.

At that time, July 2, 2020, our best method was a genetic algorithm. That algorithm starts with either random or ‘good’ set of solutions and breeds children (with a mix of the same stocks), or mutations (where we add or take away random stocks). This method finds the best solution. When we ran it last night on 60 assets, we found the best solution in 12 seconds (we tuned a few settings since July), and when we fed it D-Wave quantum annealing solutions, it found the best solution in 10 seconds. Feeding in all quantum annealing solutions (even as few as 22), makes it run faster than when fed with random portfolios.

Here is the Wikipedia write-up on genetic algorithms.

How does our simulated annealer work?

  1. We create a set of functions in Python which we run, and we feed it our NxN covariance matrix. In this case, N = number of assets in our universe. We also feed it an array of expected returns raised to a power.
  2. We define a cost or scoring function. This gives us the Chicago Quantum Net Score back for each portfolio. This is the value we wish to minimize, to find the best portfolio. You can read more about our portfolio optimization method here.
  3. We flip a bit, to either add or take out a stock from the portfolio.
  4. We define a neighboring solution. This one is ‘nearby’ to the solution we are looking at, but is guaranteed to be different. It can be different by 1 to N stocks.
  5. We figure out when to accept another solution, or stay where we are. This is a function of temperature, so that at higher temperatures it can ‘jump’ more often.
  6. We code the annealing process. This one has three ways to control the process, the minimum temperature, the cooling rate, and the number of trials per degree. We spend more time annealing when the minimum temperature is lower, the cooling rate is slower, or the number of trials (or D-Wave calls these sweeps) is higher. Our 23 second solution is not optimal, but it returns the best solution consistently.
Image for post
Image for post
Output from our custom coded simulated annealer

You can see above how our annealer starts with an average solution, but then finds better solutions until it settles on a 2-asset solution with the best Chicago Quantum Net Score. Those stocks are AMP (Ameriprise) and APA (Apache), and over the past year these stocks have moves in a way that cancels out many intra-period losses. Today’s stock-picks are different (no longer AMP and APA).

In summary, our custom coded simulated annealer finds very good solutions on its way to finding the optimal solution for portfolio optimization solutions out of 60 stocks. It takes a reasonable number of seconds (15) to sift through 1.1 x 10¹⁸ solutions. It allows us another way to both validate the D-Wave quantum annealing solutions, and to raise the bar on quantum advantage.

We also ‘recruited’ the D-Wave Simulated Annealer. With tuning, this morning it found the best solution we allowed it to see in 11 seconds.

GG Sword: The equivalent of our simulated annealers against the 60 asset problem

Our team at Chicago Quantum is looking for more ways to solve our portfolio optimization problem classically (meaning with today’s x86 computer technology) faster and more efficiently than brute force or Monte Carlo random sampling. Our goal is to make it harder for the quantum annealing computer to show quantum advantage for us as compared to open-source solutions. This was a ‘to-do’ from our last arXiv research article.

As a final note, we are not having similar luck with the D-Wave Tabu Sampler. It returns average sampling results and is not returning good solutions. We have discontinued its use moving forward.

Notes: We are using the same technology (2013 iMAC with 16GB RAM using Python 3.7 in a Jupyter notebook) and analyzing the same stocks as in our prior article, here.

Jeffrey Cohen, President of US Advanced Computing Infrastructure, Inc., & founder of Chicago Quantum (SM). We use quantum algorithms & our quantum platform

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store