STOR-i blogs

In the previous blog post  we discussed how Simulated Annealing can tackle the Travelling Salesperson Problem of connecting $n$ cities with the shortest path (with every city visited exactly once). In this blog post we investigate another method, inspired by biology and Darwin's theory of evolution.  We introduce some evolutionary terms and how they relate to the optimization task;  an individual  is a given solution/route,  a population $N$ of individuals is the set of $N$ solutions/routes,  a generation is the iteration count of the algorithm,  the fitness of an individual is determined by the objective value (the lower the total distance of a route, the fitter that route is), the reproductive   selection process, where individuals are stochastically chosen to become parents and reproduce to give offspring , the chromosome/gene  of a solution is an encoding of that solution, the mutation of a chromosome is an elementary stochastic t...

The traveling salesperson problem (TSP) is a well-studied optimization problem which finds the shortest  path connecting $n$ cities so that each city is visited exactly once. This is a minimization problem where the objective value to be minimized is the total distance travelled. A solution of TSP with $4$ cities Using the formulation of  Dantzig–Fulkerson–Johnson, the problem can be tackled with integer programming. Indeed branch and bound algorithms provide exact solutions to TSP, but since it is an NP-hard problem they can only process small problems containing only 40-60 cities.  Heuristic approaches provide a faster alternative. The simplest method proposed is the nearest neighbour heuristic which takes the salesperson to the nearest unvisited city at each step of the algorithm. Despite its simplicity the output solution is often sub-optimal, as you can see in figure below. Black and blue nodes are current and nearest unvisited cities respectively. In the last st...

 Volatility as a measure of expected or realised deviation in asset returns over a specified period is thoroughly studied in the financial literature. Investors with long market exposure use volatility as a risk gauge, fearing periods of high volatility, since they are historically associated with sudden drops in returns. Historical volatility is a measure of past volatility and despite being conceptually simple and easy to compute, it doesn’t have explanatory power on future volatility. We need to use current market information to infer market expectations of future volatility. Financial models can come to rescue. Financial models attempt to predict future volatility based on the current market’s knowledge/data. In the options market, products such as call/put options allow one to buy/sell a stock on some expiration date $T$ in the future (measured in years) at some price $K$ called the strike price. Since stock price at expiration may deviate significantly from the strik...