多目標背包問題在投資組合中的應用研究

黃林峰

摘 要：針對投資組合中收益和風險均需考慮的因素，將其抽象為一個多目標0/1背包問題并使用SPEA2算法進行求解。實驗結果表明，多目標優(yōu)化來求解投資組合問題能更好的揭示出收益與風險之間的關系，為投資者提供更好的決策依據(jù)。

關鍵詞：投資組合；多目標優(yōu)化；多目標背包

0 引言

1952年，Harry.M.Markowitz發(fā)表了著名的論文"Portfolio Selection"[1]，標志了華爾街第一次數(shù)學革命的開始，這是一篇里程碑式的論文，被公認為"現(xiàn)代投資學"的開端。Markowitz提出，投資者不僅要求"高收益率"，還要求"收益率是可以確定的"。這意味著尋求最大預期收益和最小不確定性（即風險）的投資者進行決策時，有一對相互矛盾的目標必須得到平衡。

多目標優(yōu)化是科學研究和工程實踐中非常重要的研究課題。與單目標優(yōu)化每次只能得到一個解相比，多目標優(yōu)化算法能在一次運行中得到一組解[2]。因此，利用多目標0/1背包來求解投資組合問題時，將收益和風險同時作為兩個目標，每次運行都可以得到一個非支配解集，更有利于發(fā)現(xiàn)收益和風險二者之間的關系，為決策者提供更好的依據(jù)。

本文將投資組合抽象為多目標0/1背包問題，并用SPEA2算法進行求解。結果表明，求得的非支配解集中往往包含最優(yōu)解或者接近最優(yōu)解。

1 相關知識

投資組合是現(xiàn)代經(jīng)濟社會中的一個重要問題。人們進行投資，本質上是在不確定性的收益和風險中進行選擇。以某銀行發(fā)行信用卡為例，假設將總量為C的信用額度來分配給一組顧客。收到一組編號為1…n的信用額度申請，每個的信用額度大小為cj， 風險等級為gj，其值越高，風險越低。此外，每個申請的預期收益為pj，當然，其大小與cj和gj有關。目標是收益最大化，這個問題就可以看作是一個簡單的2維背包問題，決定是否批準顧客j的信用額度申請。有兩個約束條件，第一個就是所有的信用額度之和不能大于C，第2個是將所有總的風險和作為約束條件，使它在一個可接受的水平L之內。

顯然，如果將風險總和也作為目標的話，該問題就變?yōu)橐粋€多目標背包問題。這是一個比較簡單的模型，而現(xiàn)實中的投資問題往往會有多個約束條件。

2 算法描述

SPEA2[3]、NSGA2、PAES是目前最具有代表性的多目標進化算法。其中，SPEA2算法是目前公認的求解多目標組合優(yōu)化問題的最有效算法之一。按照第2節(jié)中所述，對于投資組合問題，將收益和風險作為兩個目標來同時進行優(yōu)化，這樣，投資組合問題就被抽象成為多目標0/1背包問題。與單目標0/1背包問題相比，多目標0/1背包問題能在一次求解中得到一組解，可以很好的揭示出收益和風險兩者之間的關系，為投資者提供更準確的依據(jù)。

3 實驗結果與分析

本文采用的實驗數(shù)據(jù)從[4]獲得，算法在VC++6.0上編譯執(zhí)行。為了更好的接近現(xiàn)實中的投資組合問題，將背包問題中的利潤作為收益，而所有約束的和作為風險，優(yōu)化的目標就是使收益盡可能大而風險盡可能小，當然也要滿足數(shù)據(jù)中的所有約束，可能不止一個。

對每個測試用例，算法均獨立運行 30 次，在這些樣本數(shù)據(jù)上的實驗結果表明，改進后的SPEA2算法在大多數(shù)樣本上能找到最優(yōu)解。也就是說，原來單目標的最優(yōu)解被包含在SPEA2算法求得的Pareto解集中。并且，這些結果充分的展示出投資組合問題中收益與風險之間的關系，為投資者提供了更好的決策依據(jù)。

4 結束語

本文首先介紹了投資組合問題并分析了用單目標背包問題求解的不足，然后提出用多目標背包問題求解的思路。用SPEA2算法求解多個樣本的實驗結果表明，用多目標背包來求解投資組合問題可以很好的揭示出收益和風險兩者之間的關系，為投資者提供更準確的依據(jù)。

參考文獻：

[1] Harry Markowitz. Portfolio Selection [ J ] . Journal of Finance ，March 1952 ：77-91.

[2] 謝濤，陳火旺，康立山. 多目標優(yōu)化的演化算法.計算機學報， 2003 ， 26（8） ： 997-1003.

[3] Zitzler E， Laumanns M， and Thiele L. SPEA2： Improving the strength Pareto evolutionary algorithm. TIK-Report 103， Computer Engineering and Networks Laboratory （TIK）， Swiss Federal Institute of Technology， May 2001.

[4] J.E.Beasley . OR-Library. Distributing Test Problems by Electronic Mail. Journal of Operational Research Society. Vol 41， No.11 （1990） 545-552.