基于雜合遺傳算法的Portfolio整數(shù)規(guī)劃模型

1、 35 / 8基于雜合遺傳算法的Portfolio整數(shù)規(guī)劃模型*基金項目：國家自然科學(xué)基金（79700016） 安向龍 露凌則毅 （1.大學(xué)理學(xué)院 ，300072; 2.中國十三冶公司 ，300301）摘要 本文根據(jù)中國目前的證券交易要求，提出了組合投資的整數(shù)規(guī)劃模型，為了研究，提出一種在遺傳算法中融入神經(jīng)網(wǎng)絡(luò)的雜合遺傳算法，有機結(jié)合了遺傳算法全局最優(yōu)和神經(jīng)網(wǎng)絡(luò)在極值點附近快速搜索的特點。實例表明，這種雜合遺傳算法很有效。關(guān)鍵字 組合投資 整數(shù)規(guī)劃 遺傳算法 神經(jīng)網(wǎng)絡(luò)1引言美國著名經(jīng)濟學(xué)家，諾貝爾獎獲得者M(jìn)arkowitz關(guān)于投資組合理論提出了均值-方差模型，構(gòu)成了現(xiàn)代證券理論的基礎(chǔ)。此后，許

2、多學(xué)者對此模型進(jìn)行了研究和改進(jìn)，取得了很大的進(jìn)步。本文結(jié)合中國證券市場的實際情況，提出了Portfolio整數(shù)規(guī)劃模型。在這類問題的研究中，人工神經(jīng)網(wǎng)絡(luò)和遺傳算法都是重要的方法。但是，它們有各自的優(yōu)點和缺點。人工神經(jīng)網(wǎng)絡(luò)是一種梯度算法，對于復(fù)雜的非線形問題很容易陷入局部最優(yōu)。而遺傳算法則是一種仿生優(yōu)化算法，以概率全局收斂，但是到最后階段，由于自身的算法特點，具有一定的不穩(wěn)定性，搜索效率降低。本文提出把兩者結(jié)合起來，取長補短，既可避免陷入局部最優(yōu)，又可在最優(yōu)點附近快速達(dá)到最優(yōu)。最后，結(jié)合實例證明其有效性。2模型建立Markowitz的組合投資模型可用以下數(shù)學(xué)模型(P1)表示：min F（X）=s

3、.t.這里n表示風(fēng)險證券的數(shù)量，表示第i種證券的投資比例，是第i種證券的期望收益，表示第i種和第j種證券期望收益的協(xié)方差。模型的核心是用證券的期望收益率來表示證券收益，用證券的收益的方差表示風(fēng)險。模型的研究目的是：如何選擇投資組合，在收益一定的條件下，使風(fēng)險最??；或在風(fēng)險一定的條件下，使收益最大。但是，需注意的是，Markowitz的組合投資理論有一些前提條件，如:1) 允許買空賣空。2）股票份額可以無限分割。而中國目前的證券市場是不允許這樣進(jìn)行證券交易。于是，我們對模型做一些改進(jìn)，對其進(jìn)行討論。為此，我們考慮以下幾個問題：1）由于股票只允許整手（100股）購買，所以給定總投資額后，通常會有剩

4、余資金出現(xiàn)，可以將這部分看作不足量資金不予投資。也可以將其存入銀行，看作無風(fēng)險投資。本文不考慮無風(fēng)險投資存在的情況，故采用第一種處理方法。2）限制買空，要求每種股票投資股數(shù)非負(fù)。綜上所述，投資組合模型可改進(jìn)為如下模型（P3）：max F(X)=s.t. 其中，表示第i種證券的期望收益，表示第i種證券和第j種證券的期望收益的協(xié)方差。為第i種證券的投資手?jǐn)?shù)，為第i種證券購買時的價格,y為投資總額,F為可接受風(fēng)險損失。其中、分別由樣本均值、樣本協(xié)方差估計得到。 這里引入投資手?jǐn)?shù)向量X=（, , ）, 收益向量R=（, ），價格向量P=（, ）, 協(xié)方差矩陣則模型簡記為:max F（X）=XPRs.t

5、. (XVX) FXPYX(i)0, 且 X(i)I ,i=1,2,3,n顯然，這是一個典型的整數(shù)規(guī)劃。以往解決整數(shù)規(guī)劃問題，主要有枚舉發(fā)、割平面法、分支定界法等。當(dāng)股票種類很多時，用上述幾種方法解決非常困難，許多人用遺傳算法或人工神經(jīng)網(wǎng)絡(luò)進(jìn)行研究，各有優(yōu)缺點。這里用兩者融合的雜合遺傳算法進(jìn)行研究。3 算法3.1算法引入遺傳算法（Genetic Algorithm，簡稱GA）是一種仿生優(yōu)化算法，自二十世紀(jì)六、七十年代開創(chuàng)以來，經(jīng)許多人不斷改進(jìn)和完善，在理論上、應(yīng)用上都有了很大的發(fā)展。作為一種隨機的優(yōu)化與搜索方法，遺傳算法有其鮮明的特點，如并行性、通用性、全局優(yōu)化性、可操作性。正因為它具有上述特

6、點，遺傳算法已成為非常有用的優(yōu)化算法，在許多領(lǐng)域得到了廣泛的應(yīng)用。但GA的缺點在于收斂到一定程度的時候，通過交叉和變異操作產(chǎn)生更高適應(yīng)值的個體的概率降低，且具有一定的不穩(wěn)定性。 神經(jīng)網(wǎng)絡(luò)（簡稱NN）是模擬人腦的智能優(yōu)化算法，經(jīng)過50多年的曲折發(fā)展，日漸成為智能化的主流方向，但本質(zhì)上它是一種梯度算法，對于復(fù)雜的問題，比如多峰性、非凸性，容易陷入局部最優(yōu)化。另一方面，網(wǎng)絡(luò)結(jié)構(gòu)與權(quán)重大多按經(jīng)驗來給出，可能導(dǎo)致效率降低。本文擬采用兩者融合的雜合遺傳算法，就是以遺傳算法為基礎(chǔ)，在選擇、雜交、變異操作的基礎(chǔ)上加入HNNS學(xué)習(xí)（即離散Hopfield神經(jīng)網(wǎng)絡(luò)系統(tǒng)），這樣，一方面可保證算法的全局最優(yōu)性，另一方

7、面可提供更加多樣化的個體且能加快收斂速度，提高算法的效率。具體作法是在選擇操作時利用輪盤賭選擇一部分下代染色體，用BP操作對適應(yīng)值較好的染色體進(jìn)行運算產(chǎn)生另一部分下代染色體。交叉和變異操作同一般遺傳算法。 3.2算法設(shè)計 1)編碼與搜索空間的確定。編碼和搜索空間的確定。本文采用整數(shù)向量表示每個染色體,向量各元素表示對應(yīng)股票投資股數(shù)，搜索空間可根據(jù)投資總量確定一個整向量空間。 2)初始化。定義整數(shù) popsize作為每代染色體個數(shù)，在搜索空間上隨機產(chǎn)生popsize個初始染色體，并對其可行化。一般來說，對于理性的投資者來說，手里的資金越少，表示其用于投資的資金越多，其投資收益會增加，所以對于理性

8、的投資者來說，其手里的不足量資金越少越好。而對于風(fēng)險來說，投資越分散越少風(fēng)險就越小。本文就根據(jù)這個思想進(jìn)行可行化。具體方法為：對不滿足條件的染色體，根據(jù)股價從高到低的順序逐漸減少投資數(shù)，直到其可行。 3)評價函數(shù)與倍率函數(shù)。本文中評價函數(shù)以基于按目標(biāo)函數(shù)值排名的相對隸屬度 作為染色體的適應(yīng)值evel()，使染色體被選擇的可能性與其適應(yīng)值成正比例，即采用輪盤賭，隨機選擇染色體。BP操作中的倍率函數(shù)就以模型的目標(biāo)函數(shù)為準(zhǔn)。 4)選擇。本文采用基于非線形排名的選擇策略,選擇過程為旋轉(zhuǎn)輪盤賭popsize-n次，每次選擇一個染色體，選擇過程如下： STEP1 對每個染色體計算累積概率=，i=1,2,.

9、,popsize, STEP2 產(chǎn)生隨機實數(shù)r0, STEP3 若r，則選擇第i個染色體 STEP4 重復(fù)第2、3步popsize-n次，得到popsize-n個染色體。1） HNNS學(xué)習(xí)。用上一步的方法選擇n個適應(yīng)值較高的染色體，i=1,2,n，作為狀態(tài)向量，然后對每個染色體進(jìn)行學(xué)習(xí)。學(xué)習(xí)算法為： PL-1 分別取，。，為初始狀態(tài)。 PL-2 如果第t代染色體，i=1,2,n,已知，則t+1代染色體=， 為學(xué)習(xí)算子 的第j個分量， 而，k=1,2,m 這里，m是樣本觀察次數(shù)，為第k次觀察第j種證券的收益率，為第k次觀察的收益率向量。對每個染色體學(xué)習(xí)給定次數(shù)得到n個染色體作為下一代。最后，對非

10、整向量進(jìn)行四舍五入取整，并使其可行化。 2） 交叉。本文采用單點交叉，首先設(shè)定參數(shù)為交叉概率。為了確定交叉操作的父代，從i=1到popsize重復(fù)以下過程：從0，1中產(chǎn)生隨機數(shù)r，若r，則選擇染色體為 父代。把被選擇的父代表示為、 、 、，然后把它們進(jìn)行配對（、）、( 、)、，再從1，n中產(chǎn)生隨機整數(shù)c，對每對染色體第c位進(jìn)行交換，得到新的染體。如果得到的染色體不是可行解，那么對它們進(jìn)行可行化。方法同初始化過程的可行化方法。 7）變異。首先設(shè)定參數(shù)為變異概率，按照類似于交叉過程中選擇父代的過程，從i=1到popsize重復(fù)以下過程：從0，1中產(chǎn)生隨機數(shù)r，若r，則選擇染色體為父代，把被選擇的父

11、代表示為、 、 、，然后按下面的方法進(jìn)行變異操作：在搜索空間中產(chǎn)生隨機變異方向d，令=+Md。如果+Md不可行，那么置M為0，M中隨機整數(shù)，直到其可行為止。其中M為足夠大正整數(shù)。如果在給定迭代次數(shù)得不到可行解，則置M為0。 通過選擇、BP操作、交叉和變異，生成新一代染色體，再通過上述三種方法，生成更新的染色體。給定進(jìn)化代數(shù)G，共進(jìn)行G次選擇、BP操作、交叉和變異操作，然后從中找出最優(yōu)解。 綜上所述，解決組合投資選擇問題的遺傳算法如下： STEP 0 輸入?yún)?shù)popsize, , , G, Y。 STEP 1 從搜索空間中隨機產(chǎn)生popsize個染色體，并對其進(jìn)行可行化。 STEP 2 通過交叉

12、、變異操作，更新染色體。 STEP 3 計算染色體的適應(yīng)值，采用輪盤賭和BP操作來選擇下一代染色體。 STEP 4 重復(fù)STEP2、STEP3共G次。 STEP 5 記錄最好的染色體，作為問題的最優(yōu)解。4 實例本文考慮證券市場的十種具有代表性的股票進(jìn)行組合投資。以它們2000年中17周的周收益率作為它們的實際收益率，數(shù)據(jù)摘于證券市場周刊，具體數(shù)據(jù)見表1。股票價格表1 證券市場十種具有代表性的股票2000年十七周的周收益率（ %）股票代碼6001046000016000096000054600000600057600085600690600095600100周收益率111.7110.176.94

13、5.328.6918.17.4224.4614.199.922-8.01-8.74-9.10-5.48-10.40-9.24-3.67-9.61-11.08-7.9731.324.511.170.980.297.0812.954.415.5611.3645.902.261.053.713.175.035.084.1810.3523.005-5.50-1.54-0.1-4.89-0.32-8.5319.630.25-6.93-15.6763.062.734.71.155.691.00-6.4621.983.555.867-3.07-1.89-5.144.45-2.97-0.55-7.11-11.

14、39-2.52-2.6781.362.130.100.72-1.840.862.110.922.112.2494.3214.740.89-0.99-0.84-2.66-0.53-0.23-2.612.11109.29-0.843.581.531.780.23-1.165.530.22-2.83110.29-0.671.98-0.51-0,252.83-4.23-1.59-3.281.23126.380.22-1.830.74-0.46-0.0910.04-0.9-0.218.0113-2.95-3.32-2.31-3.37-4.51-5.23-3.403.94-5.47-6.5414-1.73

15、-1.18-0.61-3.110.880.195.561.52-1.87-7.32153.161.331.13-0.32-0,831.525.273.284.148.0416-0.77-0.39-0.20-0.81-0.791.41-1.01-2.52-3.81-3.61170.861.580.006.34-0.091.02-2.382.350.00-0.39表2 2000年11月3日收盤價股票代碼600104600001600009600054600000600057600085600690600095600100價 格678781990145615761876207823352789478

16、6表3 計算結(jié)果F=3000F=3500F=4000F=4500P2P3P2P3P2P3P2P36001040.0954200.0990320.16581120.14831476000010.10791060.13971500.1229750.13781066000090.5322360.068000.035300.012546000540.48091700.24741250.1590960.1174186000000.008600.011000.021300.025806000570.002500.007300.025000.003006000850.2254870.2921870.3037

17、1250.31591106006900.018540.0844870.1062980.19811166000950.003100.012150.009510.025206001000.004500.039080.0810200.01600Returns0.10396000.136138000.0152153100.017218400risk0.030030000.035035000.040040000.04504500（指每手價格）以2000年11月3日收盤價為準(zhǔn)，見表2。設(shè)定交叉概率=0.8，變異概率=0.1，投資總額 Y=1000000，每代染色體數(shù)量popsize=100，進(jìn)化代數(shù)G=5

18、00,HNNS學(xué)習(xí)次數(shù)為50次，計算結(jié)果見表3。 表3表明，本方法得到的結(jié)果與傳統(tǒng)模型得到的結(jié)果很接近。由于約束條件不同，如本模型允許不足量資金的存在，所以結(jié)果與傳統(tǒng)模型得到的結(jié)果有偏差。 經(jīng)驗證結(jié)果好于采用連續(xù)方式選擇然后取整的結(jié)果，也好于使用普通遺傳算法進(jìn)化一樣代數(shù)得到的結(jié)果。5 結(jié)論 通過以上實例，我們可以看到把雜合遺傳算法應(yīng)用于整數(shù)組合投資問題很有效，能有效應(yīng)用于目前中國證券市場。而且，它也是解決整數(shù)規(guī)劃問題的一種很有效的方法 。相比于枚舉法、割平面法、分支定界法而言，更具有可操作性。而且比純粹的遺傳算法或神經(jīng)網(wǎng)絡(luò)效率更高。另外，本文的模型未考慮交易費用與無風(fēng)險投資存在的情況，這些問題

19、筆者將作進(jìn)一步研究。參考文獻(xiàn)1Markowitz H. Portfolio selection. Journal of Finance , 1952,7:77-912 馬仲蕃.線性整數(shù)規(guī)劃的數(shù)學(xué)基礎(chǔ).科學(xué).19983 Goldberg D.E. Genetic Algorithms in search , optimization and learning M. New Nork: Addison-Wesley, 1989,1834 Holland JH. Adaption in natural and artificial system . Ann Arbor: University of

20、Michigan Press,19755 Michalewicz Z . Genetic Algorithms + data structure =evolution programs. New York:Springer,19946 Mitsuo G. Runwei C. Genetic algorithms and engineering design. Wiley , New York: 19977 焦成.神經(jīng)網(wǎng)絡(luò)系統(tǒng)理論.電子科技大學(xué).19908 Hawley D,Johnson D,reaina D. Artificial Neural Systems: A New Tool For

21、 Financial Decision MakingJ,Financial Analysis Journal,1990:46(1):63729 Yusen Xia,Baoding Liu,Shouyang Wang,K.K.Lai.A model for portfolio selection with order of expected returns puter & Operation Research 27(2000)409422A Integer Project Model for Portfolio Selection Based on Hybrid Genetic AlgorithmsXianglon