投資組合最佳化問題一直是相當有趣且值得研究的議題。投資組合的標的範圍相當多元，包含：債券、基金、股票等，一個合適的投資組合不僅可提升獲利能力，更能有效的分散風險。故至今已有相當多的演算法被提出用來解決投資組合最佳化問題。其中，考量可提供的投資組合數量與多樣性，透過群組遺傳演算法，許多演算法亦設計用於最佳化群組股票投資組合(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 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.

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 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
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 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

[1]	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
[2]	E. Alba and J. M. Troya, "A Survey of Parallel Distributed Genetic Algorithms," Complexity, Vol. 4, pp. 31-52, 1999
[3]	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
[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. 141-147, 2013
[5]	V. Bevilacqua, V. Pacelli and S. Saladino, "A novel multi objective genetic algorithm for the portfolio optimization," Advanced Intelligent Computing, pp. 186-193, 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. 650-675, 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. 10529-10537, 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. 1657-1678, 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 bi-objective optimization problems," Applied Intelligence, Vol. 38, pp. 331–356, 2013
[12]	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
[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 one-dimensional 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. 4673-4684, 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. 1473-1487, 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 state-of-the-art," 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 real-coded genetic algorithm," Journal of Global Optimization, Vol. 53, pp. 297-315, 2012.
[21]	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.
[22]	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.
[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, "Multi-objective portfolio selection model with fuzzy random returns and a compromise approach-based genetic algorithm," Information Sciences, Vol. 220, pp. 507-521, 2012.
[26]	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.
[27]	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.
[28]	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.
[29]	H. M. Markowitz, "Harry Markowitz: Selected Works," World Scientific Publishing Company, 2009.
[30]	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
[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. 1-6, 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. 119-142, 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. 101-111, 2016
[34]	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
[35]	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 
[36]	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.
[37]	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
[38]	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.
[39]	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.
[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. 635-646, 1998.