應用變動鄰域搜尋法於投資組合最佳化問題之研究

Using Variable Neighborhood Search for Portfolio Optimization Problem

林書羽(Shu-Yu Lin)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

摘要

在現今經濟不景氣的情況下，低利率之定期儲蓄已經無法滿足個人的理財需求，許多人會把手中多餘的資金轉投資，以賺取更多的利潤，其中最常見的投資理財工具就是股票，然而，股票市場中可供選擇的股票種類繁多，因此如何從眾多股票中決定投資組合以得到最佳獲利便成為一個非常重要且困難的議題。投資者在考慮期望報酬時，同時也需要考慮到風險的問題，因此投資組合問題隸屬於多目標最佳化之範疇，亦屬於NP-Hard類型之問題（Stummer，2005）。當股票的數量越多時，求解時間會跟著增長，複雜度及困難度也相對提高，如果使用傳統的圖解法（Graphical）或是二次規劃法（Quadratic Programming；QP）將會花非常久的時間，不符合效益，因此本研究使用萬用啟發式演算法（metaheuristic）來求解，希望能在合理的時間內得到有效的投資組合以供決策者參考。
本研究主要應用變動鄰域搜尋法（Variable Neighborhood Search；VNS）來求解股票投資組合問題，其目標式為風險最小化以及期望報酬最大化。在考慮不同進入鄰域結構的方式以及不同的基準解取代時機之下，本研究共計提出七種VNS架構，並透過5種全球性股票指標實際數據來作為測試例題，與OR-Library中所提供之參考柏拉圖集合進行比較，使用 、GD、SP、Hit rate、非支配解個數和求解時間來評估演算法的效率。除了比較不同VNS架構在各種例題下的優劣外，也與文獻中的模擬退火法（Simulated Annealing，SA）、禁忌搜尋法（Tabu Search，TS）進行比較，結果顯示VNS的求解效率以及求解品質較優良。

關鍵字

變動鄰域搜尋法；股票投資組合問題；圖解法；二次規劃法

並列摘要

Term deposit has been one of the most stable investment tool for many years. However, the low interest rate has encouraged people to reconsider the investment target in order to acquire more profit financial tools, stocks have attracted much attention of investors. However, how to effectively choose right stocks and properly arrange the proportion of each chosen stock invested have always been a difficult but important issue. Due to its NP-Hard property, this study employs a metaheuristic algorithm-Variable Neighborhood Search（VNS）to solve this bi-objective optimization problem-portfolio optimization to minimize risk and maximize expected return simultaneously. Based on varied neighborhood implementation sequences and the base solution replacement strategies, seven variations of VNS algorithms are developed. The historical data from five stock markets all over North America, Asia, and Europe are used as the benchmark. 、GD、SP、 Hit Rate、the number of non-dominated solutions and CPU time are employed as performance measures. VNS algorithms are compared with Simulated Annealing and Tabu Search methods in the literature. The results show that VNS performs competitively in both solution quality and computation efficiency.

並列關鍵字

Stock Portfolio；Variable Neighborhood Search；Graphical, Quadratic Programming

參考文獻

[2] 田佳芸，2007，「變動鄰域搜尋法於雙目標平行機台排程問題之研究」，元智大學，碩士論文。

[6] 郭男極，2008，「變動鄰域搜尋法於多目標專案投資組合問題之研究」，元智大學，碩士論文。

[4] 吳詩敏，2007，「組合編碼遺傳演算法於投資策略資金分配之應用」，國立中央大學，碩士論文。

[5] 范沛綱，2003，「最佳投資組合研究」，國立中央大學，碩士論文。

[7] 徐崇禮，2002，「模擬股票選擇權避險策略最佳化系統」，元智大學，碩士論文。