由於金融市場的多變性，金融資料探勘一直是一個吸引人且具有挑戰性的研究議題。例如，股價預測與股票投資組合探勘等都是金融資料探勘的範疇。其中，股票投資組合探勘問題不難理解是一個最佳化問題，故在過去幾十年，很多基於最佳化技術的演算法被提出來解決股票投資組合的問題。然而，現有方法的癥結點在於只提供一組股票投資組合。只提供一組投資組合，在現實應用上則會遇到許多問題。例如：投資者認為股票價格到達相對高點而不願意購買或該股票漲停無法買入。另外，探勘投資組合除了需滿足客觀的目標外，投資者亦常會有個人的主觀需求。客觀目標是指投資組合需要風險低且報酬高，而投資者預計購買股票家數與總投資金額等為投資者的主觀需求。
故本論文提出了二個演算來解決上述問題。首先，我們提出群組遺傳演算法為基礎的群組股票投資組合(Group stock portfolio, GSP)探勘技術，其目標為將n家股票分成K個群組。在群組股票投資組合中，同一個群組中股票是具有相似的特性。為達此目的，每個染色體是由三個部分組成，分別為群組、股票和股票投資組合。群組與股票部分表示如何將n家股票分成K個群組。每一群組在股票投資組合部分則利用兩實數表示是否為購買群組與購買單位。而評估函數則由染色體的群組平衡(Group balance)及投資組合的滿意度(Portfolio satisfaction)組成。群組平衡是用來測量每個群組中的股票家數是否相似，投資組合滿意度則是用於評估群組股票投資組合是否滿足客觀需求與投資者的主觀需求。由此，探勘所得的群組股票投資組合可以提供多種不同的投資組合給投資者。接著，為了提升群組的相似度與獲利穩定度，我們接著提出第二個演算法。在第二個演算法中，額外設計染色體的價格平衡(Price balance)與購買單位平衡(Unit balance)，主要目標分別為量測群組中股票的股價與購買單位是否相似。
最後，所提出的兩個方法透過台灣50中選出來的31家股票進行驗證，包含：群組投資組合分析、適合度函數對於群組投資組合的影響與投資報酬分析。實驗結果顯示，所提的兩個方法都可以探勘出高於標準利潤並提供有用的群組投資組合。

Due to variance of financial market, the financial data mining is always an attractive research issue and a real challenge to researches. For example, stock price prediction and stock portfolio mining are topics of financial data mining. It is easily to understand that the stock portfolio mining problem is an optimization problem. Hence, in the past decades, based on genetic algorithms, many approaches were proposed to deal with it. However, the problem of them is that only one stock portfolio is suggested. When only one stock portfolio is provided, some problems may happen in real application. For example,   investors may think the price of the suggested stock is too high to buy, or the stock price reach the daily limit such that investor cannot buy it. Besides, stock portfolio mining should not only consider the objective criteria but also investors' subjective criteria. The objective criteria are return on investment (ROI) and value at risk (VaR).
This thesis two approaches for solving the mentioned problems. Firstly, we propose a grouping genetic algorithm based approach for mining group stock portfolio (GSP) and its goal is to divide n stocks into K groups. Stocks in the same group means that they have similar properties. To achieve this goal, a chromosome consists of three parts. They are grouping part, stock part and stock portfolio parts. The grouping and stock parts are used to represent how n stock are divided into K groups. For each group in the stock portfolio part uses two real number to indicate whether it is purchased group and it’s purchased units. Each chromosome is then evaluated by the group balance and portfolio satisfaction. The group balance is used to make the number of stocks in groups can as similar as possible. The portfolio satisfaction is utilized to measure the satisfaction degree of objective and subjective criteria of a chromosome. As a result, the derived GSP can provide various stock portfolios to investors. Then, to improve the similarity of groups and profit stability, the second algorithm has been proposed. In second approach, the price balance and unit balance are designed to make the stock prices of stocks and purchased units in groups can as similar as possible. 
At last, the two proposed algorithms are verified on 31 stocks which are selected from Taiwan 50 ETF, including the derived GSP analysis, impact of the fitness functions to the derived GSPs and the ROI of the derived GSPs. The experimental results show that the two proposed algorithms can mine GSPs that provide higher ROI than benchmark.

Contents
CHAPTER 1	INTRODUCTION	1
1.1	Problem Definition and Motivation	1
1.2	The Contributions	3
1.3	Reader's Guide	4
CHAPTER 2	EREVIEW OF RELATED WORK	5
2.1	Grouping Genetic Algorithm and Grouping Problem	5
2.2	The M-V Model based Approaches	7
2.3	Non M-V Model based Approaches	8
CHAPTER 3	MINING GROUP STOCK PORTFOLIO BY USING GROUPING GENETIC ALGORITHM	10
3.1	Encoding scheme	10
3.1.1	Initial population	11
3.1.2	Fitness Evaluation	13
3.1.3	Genetic operations	15
3.1.3.1	Two-Phase Crossover	16
3.1.3.2	Two-Phase Mutation and Inversion	17
3.2	The GGA-based algorithm for mining GSP	17
3.3	An Example	20
CHAPTER 4	THE ENHANCED GGA-BASE ALGORITHM FOR MINING GROUP STOCK PORTFOLIO	25
4.1	Enhanced Encoding scheme	25
4.1.1	Initial population	26
4.1.2	Fitness Evaluation	28
4.1.3	Genetic operations	32
4.1.3.1	Two-Phase Crossover	32
4.1.3.2	Two-Phase Mutation and Inversion	33
4.2	The enhanced GGA-based algorithm for mining GSP	34
4.3	An Example	36
CHAPTER 5	EXPERIMENTAL RESULTS	43
5.1	Experimental Results for Method (Ⅰ)	43
5.1.1	Dataset Descriptions	43
5.1.2	The analysis of the derived group stock portfolio	44
5.2	Experimental Results for Method (Ⅱ)	45
5.2.1	Convergence of the proposed approach	46
5.2.2	Impact of the designed fitness functions	47
5.2.3	Profits of the derived GSP	52
CHAPTER 6	CONCLUSIONS AND FUTURE WORKS	55
References	57
APPENDIXES: ENGLISH PAPER	59
I.	INTRODUCTION	60
II.	A. GGA AND GROUPING PROBLEMS	60
III.	STOCK PORTFOLIO OPTIMIZATION APPROACHES	61
IV.	COMPONENTS OF THE PROPOSED APPROACH	62
V.	PROPOSED MINING ALGORITHM	64
VI.	EXPERIMENTAL RESULTS	65
VII.	CONCLUSION AND FUTURE WORK	66
List of Figures
Figure 1. Encoding scheme of Cq.	10
Figure 2. An example of encoding scheme.	11
Figure 3.Encoding scheme of Cq.	25
Figure 4. An example of encoding scheme.	26
Figure 5: The stock price series of the dataset	46
Figure 6. The convergence of the proposed approach with the four fitness functions	47
Figure 7. The average group balance values of the proposed approach by using fitness functions f1 to f4.	48
Figure 8. The average unit balance values of the proposed approach by using fitness functions f1 to f4.	49
Figure 9. The average price balance values of the proposed approach by using fitness functions f1 to f4.	50
Figure 10. The stock price series in groups derived by f1.	51
Figure 11. The stock price series in groups derived by f3.	51

 
List of Tables
Table 1. Cash dividend yields of two companies	12
Table 2. Cash dividend (yi) of each stock	12
Table 3. Proportion of average cash dividend of each group to all groups	13
Table 4 Stocks used in this example	20
Table 5. The portfolio satisfactions of all chromosomes	22
Table 6. The group balances of all chromosomes	23
Table 7. The fitness values of all chromosomes	23
Table 8. Cash dividend yields of two companies	27
Table 9. Cash dividend (yi) of each stock	27
Table 10. Proportion of average cash dividend of each group to all groups	28
Table 11. Twelve stocks used in this example	37
Table 12. The portfolio satisfactions of all chromosomes	39
Table 13. The group balances of all chromosomes	39
Table 14. The unit balances of all chromosomes	40
Table 15. The price balance of all chromosomes	40
Table 16. The fitness values of all chromosomes	40
Table 17.Information of the dataset	44
Table 18. Initial and final best group stock portfolios	44
Table 19.The average purchased units of groups	49
Table 20. Comparing the proposed approach with the benchmark in terms of ROI	53
Table 21.The derived GSP by using fitness function f4	54

References

[1] 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.
[2] M. H. Babaei, M. Hamidi, E. Jahani and H. Pasha, "A new approach to solve an extended portfolio selection problem," International Conference on Industrial Engineering and Operations Management, pp. 1954-1960, 2012.
[3] V. Bevilacqua, V. Pacelli and S. Saladino, "A novel multi objective genetic algorithm for the portfolio optimization," Advanced Intelligent Computing, pp. 186-193, 2012.
[4] A. L. Blum and R. L. Rivest, "Training a 3-node neural networks is NP-complete," Neural Networks, Vol. 5, pp. 117-127, 1992.
[5] J. Bermúdez, J. Segura and E. Vercher, "A multi-objective genetic algorithm for cardinality constrained fuzzy portfolio selection," Fuzzy Sets and Systems, Vol. 188, pp. 16-26, 2012.
[6] C. H. Chen and C. Y. Hsieh, "Mining actionable stock portfolio by genetic algorithms," accepted and to appear in Journal of Information Science and Engineering, 2016.
[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] Z. G. M. Elhachloufi and F. Hamza, "Stocks portfolio optimization using classification and genetic algorithms," Applied Mathematical Sciences, Vol. 6, pp. 4673-4684, 2012.
[9] E. Falkenauer, “A new representation and operators for genetic algorithms applied to grouping problems,” Evolutionary Computation, Vol. 2, pp. 123-144, 1994.
[10] E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing," Journal of Heuristics, Vol. 2, pp.5-30, 1996.
[11] M. R. Garey and D. S. Johnson, "Computers and intractability: a guide to the theory of NP-completeness", Macmillan Higher Education, 1979.
[12] 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.
[13] 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.
[14] D. E. Goldberg, "Genetic algorithms in search, optimization, and machine learning," Addison Wesley, 1989.
[15] J. J. Grefenstette, "Optimization of control parameters for genetic algorithms," IEEE Transactions on System Man, and Cybernetics, Vol. 16, pp. 122-128, 1986.
[16] J. H. Holland, "Adaptation in natural and artificial systems," University of Michigan Press, 1975.
[17] F. Hassanzadeh, M. Collan and M. Modarres, "A practical approach to R&D portfolio selection using the fuzzy pay-off method," IEEE Transactions on Fuzzy Systems, Vol. 20, pp. 615-622, 2012.
[18] 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.
[19] R. Kumar and S. Bhattacharya, "Cooperative search using agents for cardinality constrained portfolio selection problem," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 42, pp. 1510 - 1518, 2012.
[20] H. Kellerer, R. Mansini and S. M. Grazia, "Selecting portfolios with fixed costs and minimum transaction lots," Annals of Operations Research, Vol. 99, pp. 287-304, 2000.
[21] H. Konno and A. Wijayanayake, "Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints," Mathematical Programming, Vol. 89, pp. 233-250, 2001.
[22] 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.
[23] C. C. Lin and Y. T. Liu, "Genetic algorithms for portfolio selection problems with minimum transaction lots," European Journal of Operational Research, Vol. 185, pp. 393-404, 2008.
[24] 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.
[25] 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.
[26] 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.
[27] H. M. Markowitz, "Harry Markowitz: Selected Works," World Scientific Publishing Company, 2009.
[28] R. Mansini and M. G. Speranza, "Heuristic algorithms for the portfolio selection problem with minimum transaction lots," European Journal of Operational Research, Vol. 114, pp. 219-233, 1999.
[29] R. Mansini and M. G. Speranza, "An exact approach for portfolio selection with transaction costs and rounds," IIE transactions, Vol. 37, pp. 919-929, 2005.
[30] G. Pankratz, "A grouping genetic algorithm for the pickup and delivery problem with time windows," Operations Research Spectrum, Vol. 27, pp. 21-41, 2005.
[31] T. P. Patalia and G. Kulkarni, "Design of genetic algorithm for knapsack problem to perform stock portfolio selection using financial indicators," International Conference on Computational Intelligence and Communication Networks, pp. 289-292, 2011.
[32] M. Quiroz-Castellanos, L. Cruz-Reyes, J. Torres-Jimenez, Claudia Gómez S., H. J. F. Huacuja and A. C.F. Alvim, "A grouping genetic algorithm with controlled gene transmission for the bin packing problem," Computers & Operations Research, Vol. 55, pp. 52-64, 2015.
[33] A. D. Roy, "Safety first and the holding of assets," Econometrica, Vol. 20, pp. 431-449, Jul. 1952.
[34] B. Rekiek, A. Delchambre and H. A. Saleh, "Handicapped person transportation: An application of the grouping genetic algorithm," Engineering Application of Artificial Intelligence, Vol. 19, pp. 511–520, 2006.
[35] E. Wah, Y. Mei and B. W. Wah, "Portfolio optimization through data conditioning and aggregation," IEEE International Conference on Tools with Artificial Intelligence, pp. 253-260, 2011.