matlab遗传算法求解整数规划基于杂合遗传算法的Portfolio整数规划模型

《matlab遗传算法求解整数规划基于杂合遗传算法的Portfolio整数规划模型》由会员分享，可在线阅读，更多相关《matlab遗传算法求解整数规划基于杂合遗传算法的Portfolio整数规划模型（15页珍藏版）》请在装配图网上搜索。

1、matlab遗传算法求解整数规划基于杂合遗传算法的Portfolio整数规划模型基于杂合遗传算法的Portfolio整数规划模型*基金项目：国家自然科学基金（79700016） 安向龙 李露凌 刘则毅 （1.天津大学理学院 天津，300072;2.中国十三冶天津公司 天津，300301）摘要 本文根据中国目前的证券交易要求，提出了组合投资的整数规划模型，为了研究，提出一种在遗传算法中融入神经网络的杂合遗传算法，有机结合了遗传算法全局最优和神经网络在极值点附近快速搜索的特点。实例表明，这种杂合遗传算法很有效。关键字 组合投资 整数规划 遗传算法 神经网络 1引言 美国著名经济学家，诺贝尔奖获得者

2、Markowitz关于投资组合理论提出了均值-方差模型，构成了现代证券理论的基础。此后，许多学者对此模型进行了研究和改进，取得了很大的进步。本文结合中国证券市场的实际情况，提出了Portfolio整数规划模型。在这类问题的研究中，人工神经网络和遗传算法都是重要的方法。但是，它们有各自的优点和缺点。人工神经网络是一种梯度算法，对于复杂的非线形问题很容易陷入局部最优。而遗传算法则是一种仿生优化算法，以概率全局收敛，但是到最后阶段，由于自身的算法特点，具有一定的不稳定性，搜索效率降低。本文提出把两者结合起来，取长补短，既可避免陷入局部最优，又可在最优点附近快速达到最优。最后，结合实例证明其有效性。2

3、模型建立 Markowitz的组合投资模型可用以下数学模型(P1)表示： min F（X）=s.t.这里n表示风险证券的数量，表示第i种证券的投资比例，是第i种证券的期望收益，表示第i种和第j种证券期望收益的协方差。模型的核心是用证券的期望收益率来表示证券收益，用证券的收益的方差表示风险。模型的研究目的是：选择投资组合，在收益一定的条下，使风险最小；或在风险一定的条下，使收益最大。但是，需注意的是， Markowitz的组合投资理论有一些前提条，如: 1) 允许买空卖空。2）股票份额可以无限分割。而中国目前的证券市场是不允许这样进行证券交易。于是，我们对模型做一些改进，对其进行讨论。为此，我们

4、考虑以下几个问题： 1）由于股票只允许整手（100股）购买，所以给定总投资额后，通常会有剩余资金出现，可以将这部分看作不足量资金不予投资。也可以将其存入银行，看作无风险投资。本文不考虑无风险投资存在的情况，故采用第一种处理方法。2）限制买空，要求每种股票投资股数非负。综上所述，投资组合模型可改进为如下模型（P3）： max F(X)=s.t.其中，表示第i种证券的期望收益，表示第i种证券和第j种证券的期望收益的协方差。为第i种证券的投资手数，为第i种证券购买时的价格,y为投资总额,F为可接受风险损失。其中、分别由样本均值、样本协方差估计得到。这里引入投资手数向量X=（, , ）, 收益向量R=

5、（, ），价格向量P=（, ）, 协方差矩阵 则模型简记为: max F（X）=XPR s.t.(XVX) F XPYX(i)0, 且 X(i)I ,i=1,2,3,n 显然，这是一个典型的整数规划。以往解决整数规划问题，主要有枚举发、割平面法、分支定界法等。当股票种类很多时，用上述几种方法解决非常困难，许多人用遗传算法或人工神经网络进行研究，各有优缺点。这里用两者融合的杂合遗传算法进行研究。3 算法3.1算法引入 遗传算法（Geic Algorithm，简称GA）是一种仿生优化算法，自二十世纪六、七十年代开创以来，经许多人不断改进和完善，在理论上、应用上都有了很大的发展。作为一种随机的优化与

6、搜索方法，遗传算法有其鲜明的特点，如并行性、通用性、全局优化性、可操作性。正因为它具有上述特点，遗传算法已成为非常有用的优化算法，在许多领域得到了广泛的应用。但GA的缺点在于收敛到一定程度的时候，通过交叉和变异操作产生更高适应值的个体的概率降低，且具有一定的不稳定性。神经网络（简称NN）是模拟人脑的智能优化算法，经过50多年的曲折发展，日渐成为智能化的主流方向，但本质上它是一种梯度算法，对于复杂的问题，比如多峰性、非凸性，容易陷入局部最优化。另一方面，网络结构及权重大多按经验来给出，可能导致效率降低。本文拟采用两者融合的杂合遗传算法，就是以遗传算法为基础，在选择、杂交、变异操作的基础上加入HN

7、NS学习（即离散Hopfield神经网络系统），这样，一方面可保证算法的全局最优性，另一方面可提供更加多样化的个体且能加快收敛速度，提高算法的效率。具体作法是在选择操作时利用轮盘赌选择一部分下代染色体，用BP操作对适应值较好的染色体进行运算产生另一部分下代染色体。交叉和变异操作同一般遗传算法。3.2算法设计1)编码及搜索空间的确定。编码和搜索空间的确定。本文采用整数向量表示每个染色体,向量各元素表示对应股票投资股数，搜索空间可根据投资总量确定一个整向量空间。2)初始化。定义整数 popsize作为每代染色体个数，在搜索空间上随机产生popsize个初始染色体，并对其可行化。一般来说，对于理性的

8、投资者来说，手里的资金越少，表示其用于投资的资金越多，其投资收益会增加，所以对于理性的投资者来说，其手里的不足量资金越少越好。而对于风险来说，投资越分散越少风险就越小。本文就根据这个思想进行可行化。具体方法为：对不满足条的染色体，根据股价从高到低的顺序逐渐减少投资数，直到其可行。3)评价函数与倍率函数。本文中评价函数以基于按目标函数值排名的相对隶属度 作为染色体的适应值evel()，使染色体被选择的可能性与其适应值成正比例，即采用轮盘赌，随机选择染色体。BP操作中的倍率函数就以模型的目标函数为准。4)选择。本文采用基于非线形排名的选择策略,选择过程为旋转轮盘赌popsize-n次，每次选择一个

9、染色体，选择过程如下： STEP1 对每个染色体计算累积概率=，i=1,2,.,popsize, STEP2 产生随机实数r0, STEP3 若r，则选择第i个染色体 STEP4 重复第2、3步popsize-n次，得到popsize-n个染色体。1）HNNS学习。用上一步的方法选择n个适应值较高的染色体，i=1,2,n，作为状态向量，然后对每个染色体进行学习。学习算法为： PL-1 分别取，。，为初始状态。PL-2 如果第t代染色体，i=1,2,n,已知，则t+1代染色体=， 为学习算子的第j个分量， 而，k=1,2,m 这里，m是样本观察次数，为第k次观察第j种证券的收益率，为第k次观察的

10、收益率向量。对每个染色体学习给定次数得到n个染色体作为下一代。最后，对非整向量进行四舍五入取整，并使其可行化。2）交叉。本文采用单点交叉，首先设定参数为交叉概率。为了确定交叉操作的父代，从i=1到popsize重复以下过程：从0，1中产生随机数r，若r，则选择染色体为 父代。把被选择的父代表示为、 、，然后把它们进行配对（、）、(、)、，再从1，n中产生随机整数c，对每对染色体第c位进行交换，得到新的染体。如果得到的染色体不是可行解，那么对它们进行可行化。方法同初始化过程的可行化方法。7）变异。首先设定参数为变异概率，按照类似于交叉过程中选择父代的过程，从i=1到popsize重复以下过程：从

11、0，1中产生随机数r，若r，则选择染色体为父代，把被选择的父代表示为、 、，然后按下面的方法进行变异操作：在搜索空间中产生随机变异方向d，令=+Md。如果+Md不可行，那么置M为0，M中随机整数，直到其可行为止。其中M为足够大正整数。如果在给定迭代次数内得不到可行解，则置M为0。通过选择、BP操作、交叉和变异，生成新一代染色体，再通过上述三种方法，生成更新的染色体。给定进化代数G，共进行G次选择、BP操作、交叉和变异操作，然后从中找出最优解。综上所述，解决组合投资选择问题的遗传算法如下： STEP 0 输入参数popsize, , , G, Y。STEP1 从搜索空间中随机产生popsize个

12、染色体，并对其进行可行化。STEP2 通过交叉、变异操作，更新染色体。STEP 3 计算染色体的适应值，采用轮盘赌和BP操作来选择下一代染色体。STEP 4 重复STEP2、STEP3共G次。STEP 5 记录最好的染色体，作为问题的最优解。4 实例 本文考虑上海证券市场的十种具有代表性的股票进行组合投资。以它们2000年中17周的周收益率作为它们的实际收益率，数据摘于证券市场周刊，具体数据见表1。股票价格 表1 上海证券市场十种具有代表性的股票2000年十七周的周收益率（ %）股票代码 600104 600001 600009 6000054 600000 600057 600085 600

13、690 600095 600100 周 收 益 率 1 11.71 10.17 6.94 5.32 8.69 18.1 7.42 24.46 14.19 9.92 2 -8.01 -8.74 -9.10 -5.48 -10.40 -9.24 -3.67 -9.61 -11.08 -7.97 3 1.32 4.51 1.17 0.98 0.29 7.08 12.95 4.41 5.56 11.36 4 5.90 2.26 1.05 3.71 3.17 5.03 5.08 4.18 10.35 23.00 5 -5.50 -1.54 -0.1 -4.89 -0.32 -8.53 19.63 0.2

14、5 -6.93 -15.67 6 3.06 2.73 4.7 1.15 5.69 1.00 -6.46 21.98 3.55 5.86 7 -3.07 -1.89 -5.14 4.45 -2.97 -0.55 -7.11 -11.39 -2.52 -2.67 8 1.36 2.13 0.10 0.72 -1.84 0.86 2.11 0.92 2.11 2.24 9 4.32 14.74 0.89 -0.99 -0.84 -2.66 -0.53 -0.23 -2.61 2.11 10 9.29 -0.84 3.58 1.53 1.78 0.23 -1.16 5.53 0.22 -2.83 11

15、 0.29 -0.67 1.98 -0.51 -0,25 2.83 -4.23 -1.59 -3.28 1.23 12 6.38 0.22 -1.83 0.74 -0.46 -0.09 10.04 -0.9 -0.21 8.01 13 -2.95 -3.32 -2.31 -3.37 -4.51 -5.23 -3.40 3.94 -5.47 -6.54 14 -1.73 -1.18 -0.61 -3.11 0.88 0.19 5.56 1.52 -1.87 -7.32 15 3.16 1.33 1.13 -0.32 -0,83 1.52 5.27 3.28 4.14 8.04 16 -0.77

16、-0.39 -0.20 -0.81 -0.79 1.41 -1.01 -2.52 -3.81 -3.61 17 0.86 1.58 0.00 6.34 -0.09 1.02 -2.38 2.35 0.00 -0.39 表22000年11月3日收盘价 股票代码 600104 600001 600009 600054 600000 600057 600085 600690 600095 600100 价 格 678 781 990 1456 1576 1876 2078 2335 2789 4786 表3 计算结果 F=3000 F=3500 F=4000 F=4500 P2 P3 P2 P3 P

17、2 P3 P2 P3 600104 0.0954 20 0.0990 32 0.1658 112 0.1483 147 600001 0.1079 106 0.1397 150 0.1229 75 0.1378 106 600009 0.532 236 0.0680 0 0.0353 0 0.0125 4 600054 0.4809 170 0.2474 125 0.1590 96 0.1174 18 600000 0.0086 0 0.0110 0 0.0213 0 0.0258 0 600057 0.0025 0 0.0073 0 0.0250 0 0.0030 0 600085 0.22

18、54 87 0.2921 87 0.3037 125 0.3159 110 600690 0.0185 4 0.0844 87 0.1062 98 0.1981 116 600095 0.0031 0 0.0121 5 0.0095 1 0.0252 0 600100 0.0045 0 0.0390 8 0.0810 20 0.0160 0 Returns 0.103 9600 0.136 13800 0.0152 15310 0.0172 18400 risk 0.0300 3000 0.0350 3500 0.0400 4000 0.0450 4500 （指每手价格）以2000年11月3日

19、收盘价为准，见表2。设定交叉概率=0.8，变异概率=0.1，投资总额 Y=1000000，每代染色体数量popsize=100，进化代数G=500,HNNS学习次数为50次，计算结果见表 3。表3表明，本方法得到的结果与传统模型得到的结果很接近。由于约束条不同，如本模型允许不足量资金的存在，所以结果与传统模型得到的结果有偏差。经验证结果好于采用连续方式选择然后取整的结果，也好于使用普通遗传算法进化相同代数得到的结果。5 结论 通过以上实例，我们可以看到把杂合遗传算法应用于整数组合投资问题很有效，能有效应用于目前中国证券市场。而且，它也是解决整数规划问题的一种很有效的方法 。相比于枚举法、割平面

20、法、分支定界法而言，更具有可操作性。而且比纯粹的遗传算法或神经网络效率更高。另外，本文的模型未考虑交易费用及无风险投资存在的情况，这些问题笔者将作进一步研究。参考文献 1 Markowitz H.Portfolioselection.Journalof Finance ,1952,7:77-91 2 马仲蕃.线性整数规划的数学基础.科学出版社.1998 3 Goldberg D.E.GeicAlgorithms in search , optimization and learning M.NewNork: Addison-Wesley,1989,183 4 Holland JH.Adapti

21、onin natural and artificial system .AnnArbor: University of Michigan Press,19755 Michalewicz Z .GeicAlgorithms + data structure =evolution programs.NewYork:Springer,1994 6 Mitsuo G.RunweiC.Geicalgorithms and engineering design.Wiley, New York:1997 7 焦李成.神经网络系统理论.西安电子科技大学出版社.1990 8 Hawley D,Johnson D

22、,reaina D.ArtificialNeural Systems: A New Tool For Financial Decision MakingJ,Financial Analysis Journal,1990:46(1):6372 9 Yusen Xia,Baoding Liu,Shouyang Wang,K.K.Lai.A model for portfolio selection with order of expected returns.puter & Operation Research27(2000)409422 A Integer Project Model for P

23、ortfolio Selection Based on Hybrid Geic Algorithms Xianglong An Luling Li Zeyi liu (1.Science school, Tianjin University, Tianjin 300072;2.China13th Metallurgical Construction Corporation Tianjin Branch, Tianjin 300301) Abstract This paper propose a integral project model for portfolio selection acc

24、ording to the situation of Chinese stock market and demand of stock transaction.Tostudy the model, we design a hybrid geic algorithm adding neural work into geic algorithm.Thenew algorithm bines the global optimality of geic algorithm and the forte of searching quickly of neural work near the optimal solution.Thealgorithm is proved to be more effective with an exle. Keywords Portfolio Integral project Geic algorithm Neural work 第 15 页 共 15 页