Snowfall-inspired Metaheuristics for Portfolio Optimisation

Metaheuristic Search for Portfolio Optimisation

Portfolio optimisation involves selecting a combination of assets to maximise returns or minimise risk, subject to certain constraints. This is optimisation problem, which could be defined using an unconstrained Markowitz model and solved using quadratic programming to yield optimal solutions.

However, traditional exact methods like this may not be appropriate for realistic large-scale combinatorial optimisation problems, due to long computing times or requiring non-realistic simplifications or assumptions to generate analytic solutions. Furthermore, these optimisation problems are often NP-hard, and may involve constraints, such as those due market frictions, investor preferences, or investment bank policies. For solving such complex constrained portfolio optimisation problems, metaheuristic methods have gained popularity due to their ability to efficiently explore large search spaces and find near-optimal solutions.

Popular metaheuristic algorithms often draw inspiration from optimisation inherent in nature, with some examples being particle swarm optimisation, based on the group behaviours of birds or fish searching for food, genetic algorithms, based on evolution and natural selection, and simulated annealing, based on the annealing process in metallurgy where a material gradually cools to a low-energy state.

With our winter theme, we’ll explore metaheuristic algorithms based on the movement of snowflakes from the sky to the ground.

Snowflake Optimisation Algorithm

The Snowflake Optimisation Algorithm (SFO) was developed by Akkoyun and Toz (2018). This algorithm is inspired from snowfall, which is modelled using two concepts from physics: the wind velocity power law and the gravity force.

In this algorithm, each snowflake is a vector representing a possible solutions, containing d components, one for each variable. In the context of portfolio optimisation, these would be the weight of each asset in the portfolio. Initially, n such initial solutions are randomly created and stored in a n⨯d matrix S, representing the snowflake population. The objective function could be defined to maximise the expected return off the portfolio while considering the risk, with constrains being included due to market frictions or desired portfolio characteristics.

At each iteration of the algorithm, a reference snowflake is picked to determine the motion of the entire snowflake population, in a process which favours good solutions according to the objective function. Using this reference snowflake, some randomisation and through calculating the velocity using the wind velocity power law in each dimension, the position of each snowflake is updated. This defines a random walk which promotes exploration of the search space.

Exploitation, or convergence to optimal solutions, is provided by modelling the effect of gravity on the snowflakes. It is assumed that snowflakes with a worse objective value move towards the ground faster due to gravity, and this is used to re-order the rows of S, affecting their chances of becoming the reference snowflake in later iterations. This introduces selective pressure which guides the algorithm to focus on solutions that show promise in terms of the objective function. During the reordering process, metaphorical collisions between snowflakes are defined to occur randomly in order to remove worse solutions from the search and may be replaced with new randomly generated snowflakes to ensure diversity in the population.

This process continues until a fixed number of iterations have occurred and the best solution is chosen as the result.

Re-formulated Snowflake Optimisation Algorithm

The Re-formulated Snowflake Optimisation Algorithm (SFO-R), developed by Metin Toz and Güliz Toz in 2023. SFO-R is an alternate formulation of the same natural phenomenon of snowfall modelled with SFO. SFO uses a simple velocity and gravity based model of snowfall, which is a massive simplification of the complex, real movements of snowflakes. Based on studies into modelling snowfall for computer graphics, one addition made by SFO-R involves considering the drag and lift force on the snowflake, which is the cause of snowflakes moving in circular and irregular patterns. Another difference is the collision mechanism, involving exchanging information between colliding snowflakes to model snow accumulation, as opposed to replacing colliding snowflakes.

Benchmarked against six other algorithms on three sets of optimisation problems, the authors found that SFO-R had “well-balanced exploration and exploitation abilities” and that it “outperformed the other algorithms for all the comparison criteria except the execution time”.

References

[1] Jana Doering, Renatas Kizys, Angel A. Juan, Àngels Fitó, Onur Polat. “Metaheuristics for rich portfolio optimisation and risk management: Current state and future trends” Operations Research Perspectives (2019) Link

[2] Metin Toz, Güliz Toz. “Re‑formulated snowflake optimization algorithm (SFO‑R)” Evolutionary Intelligence (2023) Link