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

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

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

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

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

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

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

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

9、,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次觀察的收益率向量。對每個染色體學習給定次數得到n個染色體作為下一代。最后，對非

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

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

12、、變異操作，更新染色體。 STEP 3 計算染色體的適應值，采用輪盤賭和BP操作來選擇下一代染色體。 STEP 4 重復STEP2、STEP3共G次。 STEP 5 記錄最好的染色體，作為問題的最優解。4 實例本文考慮證券市場的十種具有代表性的股票進行組合投資。以它們2000年中17周的周收益率作為它們的實際收益率，數據摘于證券市場周刊，具體數據見表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 計算結果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日收盤價為準，見表2。設定交叉概率=0.8，變異概率=0.1，投資總額 Y=1000000，每代染色體數量popsize=100，進化代數G=5

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

19、筆者將作進一步研究。參考文獻1Markowitz H. Portfolio selection. Journal of Finance , 1952,7:77-912 馬仲蕃.線性整數規劃的數學基礎.科學.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 焦成.神經網絡系統理論.電子科技大學.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