||A Study on the Island-based Grouping Genetic Algorithms for Diverse Group Stock Portfolio Optimization
||Master’s Program in Networking and Multimedia, Department of Computer Science and Information Engine
Island-based grouping genetic algorithm
diverse group stock portfolio
maximally diverse grouping problem
||投資組合最佳化問題一直是相當有趣且值得研究的議題。投資組合的標的範圍相當多元，包含：債券、基金、股票等，一個合適的投資組合不僅可提升獲利能力，更能有效的分散風險。故至今已有相當多的演算法被提出用來解決投資組合最佳化問題。其中，考量可提供的投資組合數量與多樣性，透過群組遺傳演算法，許多演算法亦設計用於最佳化群組股票投資組合(group stock portfolio)或多樣群組股票投資組合(diverse group stock portfolio)並藉此提供不同的選擇給使用者制定投資策略。而當母體變大時，演化時間會相當耗時是現有方法的共同問題。故本論文提出兩個島群為基礎的最佳化方法來解決這個問題，分別為：整合式與各個擊破式島群為基礎的最佳化技術。
||Portfolio optimization is always an interesting and valuable research issue. Assets of portfolio are various, including bonds, funds, stocks, etc. A suitable portfolio can not only increase profitability but also decrease risk effectively. There are already many existing researches have been presented to solve portfolio optimization problems. Considering number and diversity of portfolios can be provided to users, using the grouping genetic algorithm, many algorithms have also been designed to optimize group stock portfolio or diverse group stock portfolio that can provide different ways to investors making investment strategies. Evolution process will take time when the population becomes bigger is a common problem in existing approaches. This thesis proposes two island-based approaches, integrated and divide-and-conquer approaches, to deal with this problem.
In first approach, it utilizes island-based grouping genetic algorithm to solve the diverse group stock portfolio optimization problem. It includes two phases that chromosome evolution phase and chromosome migration phase. In the first phase, each island generates initial population in accordance with cash dividends. A chromosome is represented by the grouping part, stock part, and stock portfolio part. Then, three genetic operations are executed, including crossover, mutation and inversion, to generate offspring. During the evolution, the second phase will be started when the migration period t is reached in first phase. In second phase, the best individual in every island is sent to master island. Master island then migrates those best chromosomes to islands. These two phases are repeated until stop condition is reached.
However, the first approach usually cannot find an effective way to find a diverse group stock portfolio when number of stocks is increase. Hence, the second approach that uses divide-and-conquer strategy is proposed to handle this problem. Comparing with the first approach, the two main differences are: (1) the island initial population initialization mechanism; (2) the island stock synchronization mechanism. Instead using all n stocks to generate initial population in the first approach, only m stocks are randomly selected to initialize initial population for each island, and because of that, the searching space is reduced in every island in second approach. Since m stock is used, stocks may different in every island after chromosome migration, the island stock synchronization mechanism is then used to fix it. The stocks appear in new and old chromosomes are kept for every island. If number of kept stocks is smaller than m, the gap will be filled with low risky stocks. Therefore, every island has chance to get best individual and stocks from other islands.
At last, experimental results made on two real datasets show that the proposed approaches can solve the problems significantly. Compare to existing approaches, the first approach can reach similar or even better returns when population size is increased; Besides, the effectiveness and efficiency of the second approach can also be improved when number of stocks is increased.
CHAPTER 1 INTRODUCTION 1
1.1 Problem Definition and Motivation 1
1.2 Contributions 3
1.3 Reader’s Guide 4
CHAPTER 2 BACKGROUND KNOWLEDGE AND RELATED WORK 5
2.1 Mean-Variance Model 5
2.2 Portfolio Optimization Approaches 6
2.3 Island-based Evolutionary Algorithms 8
2.3.1 Island-based Genetic Algorithms 9
2.3.2 Island-based Grouping Genetic Algorithms 10
CHAPTER 3 ISLAND-BASED GROUPING GENETIC ALGORITHMS FOR DIVERSE GROUP STOCK PORTFOLIO OPTIMIZATION - INTEGRATED APPROACH 11
3.1 Motivation 11
3.2 Flowchart of Integrated Approach 13
3.3 Chromosome Evolution Phase 14
3.3.1 The Components of the Used Algorithm 14
3.3.2 The Pseudo Code of the Used Algorithm 18
3.4 Chromosome Migration Phase 20
3.5 Algorithm of Integrated algorithm 21
3.6 An Example 23
CHAPTER 4 ISLAND-BASED GROUPING GENETIC ALGORITHMS FOR DIVERSE GROUP STOCK PORTFOLIO OPTIMIZATION - DIVIDE-AND -CONQUER APPROACH 31
4.1 Motivation 31
4.2 Flowchart of Divide-and-Conquer Approach 32
4.3 Initial Population of Chromosome Migration Phase 33
4.4 Stocks Synchronization of Chromosome Migration Phase 34
4.5 An Example 35
CHAPTER 5 EXPERIMENTAL RESULTS 39
5.1 Data Descriptions 39
5.2 Experimental Results of the Integrated Approach 41
5.2.1 Fitness Convergence 42
5.2.2 Comparison Results of Proposed and Previous Approaches 44
5.2.3 The Optimized DGSP 49
5.3 Experimental Results of Divide-and-Conquer Approach 50
5.3.1 Fitness Convergence 51
5.3.2 Comparison Results of Second and First Approaches 52
5.3.3 The Optimized DGSP 54
CHAPTER 6 CONCLUSION AND FUTURE WORKS 56
List of Figures
Figure 1. Flowchart of integrated approach. 13
Figure 2. Encoding scheme of chromosome Cq. 15
Figure 3. Pseudo code of Phase I: Chromosome Evolution. 19
Figure 4. Pseudo code of Phase II: Chromosome migration. 20
Figure 5. Flowchart of divide-and-conquer approach. 32
Figure 6. The stock price series of 30 companies from 2012 to 2014. 40
Figure 7. The stock price series of 50 companies from 2012 to 2014. 41
Figure 8. Fitness convergence of integrated approach on the first dataset. 43
Figure 9. Fitness convergence of integrated approach on the second dataset. 44
Figure 10. Fitness convergence of divide-and-conquer approach on the second dataset 52
List of Tables
Table 1. Stocks used in the example. 23
Table 2. The portfolio satisfactions of all chromosomes. 25
Table 3. The group balances of all chromosomes. 25
Table 4. The dissimilarity matrix of all stocks. 26
Table 5. The diversity value of all chromosomes. 26
Table 6. The fitness values of all chromosomes. 27
Table 7. Stocks used in the example 37
Table 8. Comparison of the proposed approach without chromosome migration and previous approach. 45
Table 9. Comparing of proposed approach with chromosome migration under different migration periods. 46
Table 10. Execution times of the proposed and previous approaches. 46
Table 11. Comparison results of the previous approach and the proposed approach with different number of islands in terms of returns on the two datasets. 47
Table 12. Execution times of the proposed and previous approaches. 48
Table 13. Initial and final best DGSP on the first dataset. 49
Table 14. Initial and final best DGSP with 50 stocks. 50
Table 15. Comparison results of the second and first approaches in terms of returns on the second dataset. 53
Table 16. Execution times of the second and first approaches. 53
Table 17. Initial and final best DGSP using divide-and-conquer approach. 54
|| L.E. Agustı´n-Blas, S. Salcedo-Sanz, S. Jiménez-Fernández, L. Carro-Calvo, J. Del Ser and J.A. Portilla-Figueras, "A new grouping genetic algorithm for clustering problems," Expert Systems with Applications, Vol. 39, pp. 9695–9703, 2012
 E. Alba and J. M. Troya, "A Survey of Parallel Distributed Genetic Algorithms," Complexity, Vol. 4, pp. 31-52, 1999
 M.A. Al-Betara, M.A. Awadallah, A.T. Khader and Z.A. Abdalkareem, "Island-based harmony search for optimization problems," Expert Systems with Applications, Vol. 42, pp. 2026–2035, 2015
 S. Barak, M. Abessi, and M. Modarres, "Fuzzy turnover rate chance constraints portfolio model," European Journal of Operational Research, Vol. 228, No. 1, pp. 141-147, 2013
 V. Bevilacqua, V. Pacelli and S. Saladino, "A novel multi objective genetic algorithm for the portfolio optimization," Advanced Intelligent Computing, pp. 186-193, 2012.
 J. Brimberg, N. Mladenović and D. Urošević, "Solving the maximally diverse grouping problem by skewed general variable neighborhood search," Information Sciences, Vol. 295, pp. 650-675, 2015.
 T. J. Chang, S. C. Yang and K. J. Chang, "Portfolio optimization problems in different risk measures using genetic algorithm," Expert Systems with Applications, Vol. 36, pp. 10529-10537, 2009.
 C. H. Chen, C. B. Lin and C. C. Chen, "Mining group stock portfolio by using grouping genetic algorithms," The IEEE Congress on Evolutionary Computation, pp. 738 - 743, 2015.
 C. H. Chen and C. Y. Hsieh, "Mining actionable stock portfolio by genetic algorithms," Journal of Information Science and Engineering, Vol. 32 No. 6, pp. 1657-1678, 2016.
 C. H. Chen, C. Y. Lu, T. P. Hong and J. H. Su, "Using grouping genetic algorithm to mine diverse group stock portfolios," The IEEE Congress on Evolutionary Computation, 2016.
 H.R. Cheshmehgaz, M. I.Desa and A. Wibowo, "Effective local evolutionary searches distributed on an island model solving bi-objective optimization problems," Applied Intelligence, Vol. 38, pp. 331–356, 2013
 H. R.Cheshmehgaz, M.I. Desa, A. Wibowo, "An effective model of multiple multi-objective evolutionary algorithms with the assistance of regional multi-objective evolutionary algorithms: VIPMOEAs," Applied Soft Computing, Vol. 13, pp.2863–2895, 2013
 I. De Falco, A. Della Cioppa, D. Maisto, U. Scafuri and E. Tarantino, "Biological invasion–inspired migration in distributed evolutionary algorithms, "Information Sciences, Vol.207,pp.50–65, 2012.
 T. Dokeroglu and A. Cosar, "Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms", Computers & Industrial Engineering, Vol. 75,pp. 176–186, 2014
 J.J. Durillo, Q. Zhang, A.J. Nebro, E. Alba, "Distribution of computational effortin parallel MOEA/D," International Conference on Learning and Intelligent Optimization, pp. 488–502, 2011
 M. El Hachloufi, Z. Guennoun , F. Hamza, "Stocks portfolio optimization using classification and genetic algorithms," Applied Mathematical Sciences, Vol. 6, pp. 4673-4684, 2012.
 R. H. Gálvez and A.Gravano, "Assessing the usefulness of online message board mining in automatic stock prediction systems," Journal of Computational Science, Vol. 19, pp. 1877–7503, 2017.
 L. D. Gaspero, G. D. Tollo, A. Roli and A. Schaerf, "Hybrid metaheuristics for constrained portfolio selection problems," Quantitative Finance, Vol. 11, No. 10, pp. 1473-1487, 2011.
 Y.J. Gonga, W.N. Chen, Z.H. Zhan, J. Zhang, Y. Li, Q. Zhang, J.J. Li, "Distributed evolutionary algorithms and their models: A survey of the state-of-the-art," Applied Soft Computing, Vol.34, pp. 286–300, 2015
 P. Gupta, M. K. Mehlawat and G. Mittal, "Asset portfolio optimization using support vector machines and real-coded genetic algorithm," Journal of Global Optimization, Vol. 53, pp. 297-315, 2012.
 P. Gupta, M. K. Mehlawat and A. Saxena, "Hybrid optimization models of portfolio selection involving financial and ethical considerations," Knowledge-Based Systems, Vol. 37, pp. 318-337, 2012.
 L. R. Z. Hoklie, "Resolving multi objective stock portfolio optimization problem using genetic algorithm," International Conference on Computer and Automation Engineering, pp. 40-44, 2010.
 M. Kurdi, "An effective new island model genetic algorithm for job shop scheduling problem," Computers & Operations Research, Vol.67, pp.132–142, 2016
 M. Kurdi, "A new hybrid island model genetic algorithm for job shop scheduling problem," Computers & Industrial Engineering,Vol.88,pp.273–283, 2015
 J. Li and J. Xu, "Multi-objective portfolio selection model with fuzzy random returns and a compromise approach-based genetic algorithm," Information Sciences, Vol. 220, pp. 507-521, 2012.
 P. C. Lin, "Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm," Journal of Industrial and Management Optimization, Vol. 8, pp. 549-564, 2012.
 Y. J. Liu and W. G. Zhang, "Fuzzy portfolio optimization model under real constraints," Insurance: Mathematics and Economics, Vol. 53, No. 3, pp. 704-711, 2013.
 K. Lwin, R. Qu and G. Kendall, "A learning-guided multi-objective evolutionary algorithm for constrained portfolio optimization," Applied Soft Computing, Vol. 24, pp. 757-772, 2014.
 H. M. Markowitz, "Harry Markowitz: Selected Works," World Scientific Publishing Company, 2009.
 F. Peng, K. Tang, G. Chen and X. Yao, "Population-Based Algorithm Portfolios for Numerical Optimization," IEEE Computational Intelligence Society, Vol. 14, pp. 782-800, 2010
 T.Preis, H. S. Moat and H. E. Stanley, "Quantifying trading behavior in financial markets using google trends," Scientific Reports, Vol. 3, No.1684 , pp. 1-6, 2013.
 S.H. Razavi, E.O.M. Ebadati, S. Asadi, and H. Kaur, "An Efficient Grouping Genetic Algorithm for Data Clustering and Big Data Analysis," Computational Intelligence for Big Data Analysis, Vol. 19, pp. 119-142, 2015
 S. Sagnika, B.S.P. Mishraand, S. Dehuri, "Parallel GA in Big Data Analysis, "Techniques and Environments for Big Data Analysis, Vol. 17, pp. 101-111, 2016
 S. Salcedo-Sanz,J. Del Ser and Z. W. Geem, "An Island Grouping Genetic Algorithm for Fuzzy Partitioning Problems," The Scientific World Journal, Vol. 2014, pp.1-15, 2014
 J. Straßburg, C. Gonz´alez-Martel and V. Alexandrov, "Parallel genetic algorithms for stock market trading rules," Procedia Computer Science, Vol. 9, pp. 1306-1313, 2012
 S. Salcedo-Sanz, L. Carro-Calvo, J. A. Portilla-Figueras, L.Cuadra, and D. Camacho, "Fuzzy clustering with grouping genetic algorithms, "Intelligent Data Engineering and Auto-mated Learning, Vol. 8206,pp. 334–341, 2013.
 C. Segura, E. Segredo and C. León, "Parallel island-based multiobjectivised memetic algorithms for a 2D packing problem," Genetic and evolutionary computation, pp. 1611-1618
 G. D. Tollo and A. Roli, "Metaheuristics for the portfolio selection problem," International Journal of Operations Research, Vol. 5 No. 1, pp. 13-35, 2007.
 G. A. VijayalakshmiPai, and Thierry Michel, "Evolutionary optimization of constrained k-means clustered assets for diversification in small portfolios," IEEE Transactions on Evolutionary Computation, Vol. 13, No. 5, pp. 1030 - 1053, 2009.
 R. R. Weitz and S. Lakshminarayanan, "An empirical comparison of heuristic methods for creating maximally diverse groups," Journal of the operational Research Society, pp. 635-646, 1998.