多目标背包问题在投资组合中的应用研究

黄林峰

摘 要：针对投资组合中收益和风险均需考虑的因素，将其抽象为一个多目标0/1背包问题并使用SPEA2算法进行求解。实验结果表明，多目标优化来求解投资组合问题能更好的揭示出收益与风险之间的关系，为投资者提供更好的决策依据。

关键词：投资组合；多目标优化；多目标背包

0 引言

1952年，Harry.M.Markowitz发表了著名的论文"Portfolio Selection"[1]，标志了华尔街第一次数学革命的开始，这是一篇里程碑式的论文，被公认为"现代投资学"的开端。Markowitz提出，投资者不仅要求"高收益率"，还要求"收益率是可以确定的"。这意味着寻求最大预期收益和最小不确定性（即风险）的投资者进行决策时，有一对相互矛盾的目标必须得到平衡。

多目标优化是科学研究和工程实践中非常重要的研究课题。与单目标优化每次只能得到一个解相比，多目标优化算法能在一次运行中得到一组解[2]。因此，利用多目标0/1背包来求解投资组合问题时，将收益和风险同时作为两个目标，每次运行都可以得到一个非支配解集，更有利于发现收益和风险二者之间的关系，为决策者提供更好的依据。

本文将投资组合抽象为多目标0/1背包问题，并用SPEA2算法进行求解。结果表明，求得的非支配解集中往往包含最优解或者接近最优解。

1 相关知识

投资组合是现代经济社会中的一个重要问题。人们进行投资，本质上是在不确定性的收益和风险中进行选择。以某银行发行信用卡为例，假设将总量为C的信用额度来分配给一组顾客。收到一组编号为1…n的信用额度申请，每个的信用额度大小为cj， 风险等级为gj，其值越高，风险越低。此外，每个申请的预期收益为pj，当然，其大小与cj和gj有关。目标是收益最大化，这个问题就可以看作是一个简单的2维背包问题，决定是否批准顾客j的信用额度申请。有两个约束条件，第一个就是所有的信用额度之和不能大于C，第2个是将所有总的风险和作为约束条件，使它在一个可接受的水平L之内。

显然，如果将风险总和也作为目标的话，该问题就变为一个多目标背包问题。这是一个比较简单的模型，而现实中的投资问题往往会有多个约束条件。

2 算法描述

SPEA2[3]、NSGA2、PAES是目前最具有代表性的多目标进化算法。其中，SPEA2算法是目前公认的求解多目标组合优化问题的最有效算法之一。按照第2节中所述，对于投资组合问题，将收益和风险作为两个目标来同时进行优化，这样，投资组合问题就被抽象成为多目标0/1背包问题。与单目标0/1背包问题相比，多目标0/1背包问题能在一次求解中得到一组解，可以很好的揭示出收益和风险两者之间的关系，为投资者提供更准确的依据。

3 实验结果与分析

本文采用的实验数据从[4]获得，算法在VC++6.0上编译执行。为了更好的接近现实中的投资组合问题，将背包问题中的利润作为收益，而所有约束的和作为风险，优化的目标就是使收益尽可能大而风险尽可能小，当然也要满足数据中的所有约束，可能不止一个。

对每个测试用例，算法均独立运行 30 次，在这些样本数据上的实验结果表明，改进后的SPEA2算法在大多数样本上能找到最优解。也就是说，原来单目标的最优解被包含在SPEA2算法求得的Pareto解集中。并且，这些结果充分的展示出投资组合问题中收益与风险之间的关系，为投资者提供了更好的决策依据。

4 结束语

本文首先介绍了投资组合问题并分析了用单目标背包问题求解的不足，然后提出用多目标背包问题求解的思路。用SPEA2算法求解多个样本的实验结果表明，用多目标背包来求解投资组合问题可以很好的揭示出收益和风险两者之间的关系，为投资者提供更准确的依据。

参考文献：

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

[2] 谢涛，陈火旺，康立山. 多目标优化的演化算法.计算机学报， 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.