Hybrid local search algorithm via evolutionary avalanches for spin glass based portfolio selection

摘要

Nowadays, various imitations of natural processes are used to solve challenging optimization problems faster and more accurately. Spin glass based optimization, specifically, has shown strong local search capability and parallel processing. However, generally, spin glasses have a low rate of convergence, since they use Monte Carlo simulation techniques such as simulated annealing (SA). Here, we investigate a new hybrid local search method based on spin glass (SG) for using adaptive distributed system capability, extremal optimization (EO) for using evolutionary local search algorithm and SA for escaping from local optimum states and trap to global ones. This algorithm improves the state of spins by selecting and changing the low ordered spins with higher probability; after enough steps, the system reaches a high correlation where almost all spins have reached fitness above a certain threshold and ready to avalanche; this activity potentially makes any configuration accessible. Therefore, avalanches allow escaping from local minima and efficiently exploring the configuration space. As shown in this paper, this strategy can lead to faster rate of convergence and improved performance than conventional SA and EO algorithm. The resulting are then used to solve the portfolio selection multi-objective problem that is a non-deterministic polynomial complete (NPC) problem. This is confirmed by test results of five of the world’s major stock markets, reliability test and phase transition diagram; and finally, the convergence speed is compared to other heuristic methods such as Neural Network (NN), Tabu Search (TS), and Genetic Algorithm (GA).