
系統識別號 
U00020308201712192400 
中文論文名稱

島群為基礎的群組遺傳演算法於多樣群組股票投資組合最佳化之研究 
英文論文名稱

A Study on the Islandbased Grouping Genetic Algorithms for Diverse Group Stock Portfolio Optimization 
校院名稱 
淡江大學 
系所名稱(中) 
資訊工程學系資訊網路與多媒體碩士班 
系所名稱(英) 
Master’s Program in Networking and Multimedia, Department of Computer Science and Information Engine 
學年度 
105 
學期 
2 
出版年 
106 
研究生中文姓名 
沈婉怡 
研究生英文姓名 
WanYi Shen 
學號 
604420157 
學位類別 
碩士 
語文別 
英文 
口試日期 
20170713 
論文頁數 
62頁 
口試委員 
指導教授陳俊豪 委員洪智傑 委員吳牧恩

中文關鍵字 
島群群組遺傳演算法
多樣群組股票投資組合
分組問題
最大多樣性分群問題
投資組合最佳化

英文關鍵字 
Islandbased grouping genetic algorithm
diverse group stock portfolio
grouping problem
maximally diverse grouping problem
portfolio optimization

學科別分類 

中文摘要 
投資組合最佳化問題一直是相當有趣且值得研究的議題。投資組合的標的範圍相當多元，包含：債券、基金、股票等，一個合適的投資組合不僅可提升獲利能力，更能有效的分散風險。故至今已有相當多的演算法被提出用來解決投資組合最佳化問題。其中，考量可提供的投資組合數量與多樣性，透過群組遺傳演算法，許多演算法亦設計用於最佳化群組股票投資組合(group stock portfolio)或多樣群組股票投資組合(diverse group stock portfolio)並藉此提供不同的選擇給使用者制定投資策略。而當母體變大時，演化時間會相當耗時是現有方法的共同問題。故本論文提出兩個島群為基礎的最佳化方法來解決這個問題，分別為：整合式與各個擊破式島群為基礎的最佳化技術。
方法一使用島嶼式群組遺傳演算法解決多樣群組股票投資組合最佳化問題，主要可分為兩階段：(1)多樣群組股票投資組合演化階段；(2)島嶼間個體遷徙階段。在第一階段，首先，每個島嶼會根據個股的現金股利產生初始母體，而每一個體則透過群組、股票與股票組合三部分來表示。接著，方法執行三種遺傳運算來產生新的個體，包括：交配、突變與反轉。此階段演化過程，每固定演化t世代時將觸發第二階段–島嶼間個體遷徙。在第二階段，每個島嶼的最佳個體將被送至主控島嶼，之後主控島嶼將收集的最佳個體遷移至各島嶼。此兩階段將持續執行直到符合結束條件。
然而，當股票家數大幅增加時，方法一常無法有效的找出多樣群組股票投資組合，因此，方法二採用各個擊破策略的島群為基礎的最佳化技術油然而生。相較與方法一，方法二仍然分為兩階段，其主要的不同處在於兩機制：(1)島嶼初始母體產生機制；(2)島嶼母體同步機制。在島嶼初始母體產生機制部分，不同於第一個方法使用全部的n家股票，每各島嶼僅隨機選擇m家股票產生初始母體，如此每個島嶼的搜尋空間將大幅減少。但是也因此造成個體遷移後股票不盡相同，此問題則進一步透過島嶼母體同步機制調整。島嶼母體同步機制首先將保留新舊個體中皆出現的股票，如不足m家股票時，則從剩餘股票選擇風險較低的股票補足。由此，每個島嶼皆有機會得到最佳個體與來自其它島嶼的新股票。
最後，實驗結果透過兩組真實股市資料皆驗證可有效改善問題，當母體大小增加時，方法一相較於現存方法可得到相似甚至更好的報酬；當股票家數增加時，方法二也能有效提升搜尋的效率及效能。

英文摘要 
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 islandbased approaches, integrated and divideandconquer approaches, to deal with this problem.
In first approach, it utilizes islandbased 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 divideandconquer 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.

論文目次 
Contents
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 MeanVariance Model 5
2.2 Portfolio Optimization Approaches 6
2.3 Islandbased Evolutionary Algorithms 8
2.3.1 Islandbased Genetic Algorithms 9
2.3.2 Islandbased Grouping Genetic Algorithms 10
CHAPTER 3 ISLANDBASED 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 ISLANDBASED GROUPING GENETIC ALGORITHMS FOR DIVERSE GROUP STOCK PORTFOLIO OPTIMIZATION  DIVIDEAND CONQUER APPROACH 31
4.1 Motivation 31
4.2 Flowchart of DivideandConquer 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 DivideandConquer 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
REFERENCES 59
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 divideandconquer 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 divideandconquer 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 divideandconquer approach. 54

參考文獻 
[1] L.E. Agustı´nBlas, S. SalcedoSanz, S. JiménezFernández, L. CarroCalvo, J. Del Ser and J.A. PortillaFigueras, "A new grouping genetic algorithm for clustering problems," Expert Systems with Applications, Vol. 39, pp. 9695–9703, 2012
[2] E. Alba and J. M. Troya, "A Survey of Parallel Distributed Genetic Algorithms," Complexity, Vol. 4, pp. 3152, 1999
[3] M.A. AlBetara, M.A. Awadallah, A.T. Khader and Z.A. Abdalkareem, "Islandbased harmony search for optimization problems," Expert Systems with Applications, Vol. 42, pp. 2026–2035, 2015
[4] S. Barak, M. Abessi, and M. Modarres, "Fuzzy turnover rate chance constraints portfolio model," European Journal of Operational Research, Vol. 228, No. 1, pp. 141147, 2013
[5] V. Bevilacqua, V. Pacelli and S. Saladino, "A novel multi objective genetic algorithm for the portfolio optimization," Advanced Intelligent Computing, pp. 186193, 2012.
[6] 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. 650675, 2015.
[7] 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. 1052910537, 2009.
[8] 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.
[9] 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. 16571678, 2016.
[10] 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.
[11] H.R. Cheshmehgaz, M. I.Desa and A. Wibowo, "Effective local evolutionary searches distributed on an island model solving biobjective optimization problems," Applied Intelligence, Vol. 38, pp. 331–356, 2013
[12] H. R.Cheshmehgaz, M.I. Desa, A. Wibowo, "An effective model of multiple multiobjective evolutionary algorithms with the assistance of regional multiobjective evolutionary algorithms: VIPMOEAs," Applied Soft Computing, Vol. 13, pp.2863–2895, 2013
[13] 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.
[14] T. Dokeroglu and A. Cosar, "Optimization of onedimensional Bin Packing Problem with island parallel grouping genetic algorithms", Computers & Industrial Engineering, Vol. 75,pp. 176–186, 2014
[15] 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
[16] M. El Hachloufi, Z. Guennoun , F. Hamza, "Stocks portfolio optimization using classification and genetic algorithms," Applied Mathematical Sciences, Vol. 6, pp. 46734684, 2012.
[17] 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.
[18] 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. 14731487, 2011.
[19] 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 stateoftheart," Applied Soft Computing, Vol.34, pp. 286–300, 2015
[20] P. Gupta, M. K. Mehlawat and G. Mittal, "Asset portfolio optimization using support vector machines and realcoded genetic algorithm," Journal of Global Optimization, Vol. 53, pp. 297315, 2012.
[21] P. Gupta, M. K. Mehlawat and A. Saxena, "Hybrid optimization models of portfolio selection involving financial and ethical considerations," KnowledgeBased Systems, Vol. 37, pp. 318337, 2012.
[22] L. R. Z. Hoklie, "Resolving multi objective stock portfolio optimization problem using genetic algorithm," International Conference on Computer and Automation Engineering, pp. 4044, 2010.
[23] M. Kurdi, "An effective new island model genetic algorithm for job shop scheduling problem," Computers & Operations Research, Vol.67, pp.132–142, 2016
[24] M. Kurdi, "A new hybrid island model genetic algorithm for job shop scheduling problem," Computers & Industrial Engineering,Vol.88,pp.273–283, 2015
[25] J. Li and J. Xu, "Multiobjective portfolio selection model with fuzzy random returns and a compromise approachbased genetic algorithm," Information Sciences, Vol. 220, pp. 507521, 2012.
[26] P. C. Lin, "Portfolio optimization and risk measurement based on nondominated sorting genetic algorithm," Journal of Industrial and Management Optimization, Vol. 8, pp. 549564, 2012.
[27] Y. J. Liu and W. G. Zhang, "Fuzzy portfolio optimization model under real constraints," Insurance: Mathematics and Economics, Vol. 53, No. 3, pp. 704711, 2013.
[28] K. Lwin, R. Qu and G. Kendall, "A learningguided multiobjective evolutionary algorithm for constrained portfolio optimization," Applied Soft Computing, Vol. 24, pp. 757772, 2014.
[29] H. M. Markowitz, "Harry Markowitz: Selected Works," World Scientific Publishing Company, 2009.
[30] F. Peng, K. Tang, G. Chen and X. Yao, "PopulationBased Algorithm Portfolios for Numerical Optimization," IEEE Computational Intelligence Society, Vol. 14, pp. 782800, 2010
[31] 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. 16, 2013.
[32] 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. 119142, 2015
[33] S. Sagnika, B.S.P. Mishraand, S. Dehuri, "Parallel GA in Big Data Analysis, "Techniques and Environments for Big Data Analysis, Vol. 17, pp. 101111, 2016
[34] S. SalcedoSanz,J. Del Ser and Z. W. Geem, "An Island Grouping Genetic Algorithm for Fuzzy Partitioning Problems," The Scientific World Journal, Vol. 2014, pp.115, 2014
[35] J. Straßburg, C. Gonz´alezMartel and V. Alexandrov, "Parallel genetic algorithms for stock market trading rules," Procedia Computer Science, Vol. 9, pp. 13061313, 2012
[36] S. SalcedoSanz, L. CarroCalvo, J. A. PortillaFigueras, L.Cuadra, and D. Camacho, "Fuzzy clustering with grouping genetic algorithms, "Intelligent Data Engineering and Automated Learning, Vol. 8206,pp. 334–341, 2013.
[37] C. Segura, E. Segredo and C. León, "Parallel islandbased multiobjectivised memetic algorithms for a 2D packing problem," Genetic and evolutionary computation, pp. 16111618
[38] G. D. Tollo and A. Roli, "Metaheuristics for the portfolio selection problem," International Journal of Operations Research, Vol. 5 No. 1, pp. 1335, 2007.
[39] G. A. VijayalakshmiPai, and Thierry Michel, "Evolutionary optimization of constrained kmeans clustered assets for diversification in small portfolios," IEEE Transactions on Evolutionary Computation, Vol. 13, No. 5, pp. 1030  1053, 2009.
[40] R. R. Weitz and S. Lakshminarayanan, "An empirical comparison of heuristic methods for creating maximally diverse groups," Journal of the operational Research Society, pp. 635646, 1998.

論文使用權限 
同意紙本無償授權給館內讀者為學術之目的重製使用，於20220808公開。同意授權瀏覽/列印電子全文服務，於20220808起公開。 


