二階隨機占優約束優化問題的遺傳算法求解

張 宏 偉，　于 海 生，　龐 麗 萍，　王 金 鶴

( 1.大連理工大學 數學科學學院, 遼寧 大連　116024；2.青島理工大學 計算機系， 山東 青島　266033 )

?

二階隨機占優約束優化問題的遺傳算法求解

張 宏 偉*1，于 海 生1，龐 麗 萍1，王 金 鶴2

( 1.大連理工大學 數學科學學院, 遼寧 大連116024；2.青島理工大學 計算機系， 山東 青島266033 )

摘要：隨機占優是經濟學和決策論中的基本概念，在投資組合優化中得到了廣泛的應用．遺傳算法無須求解目標函數和約束函數的次微分，也不用滿足Slater約束規范，解決了約束的半無限性和非光滑性等問題．兩個算例表明，遺傳算法能很好地解決投資組合優化問題，并且效率得到了很大提高．

關鍵詞：二階隨機占優；遺傳算法；投資組合優化

0引言

2003年，Dentcheva等[1]將隨機占優作為約束引入優化模型，作為一種新的風險規避模型得到了國內外學者的廣泛關注．由于約束的非光滑性及其半無限性，模型對算法提出了更高的要求，如何求解這類模型成為大家研究的重要課題．文獻[2-4]提出了用割平面算法求解二階隨機占優模型；文獻[5]提出了隨機擬梯度(SCQ)算法；文獻[5-6]提出了水平函數(LF)算法和投影水平函數(PLF)算法，其中提出的算法以懲罰為主題，這必然離不開Slater約束規范，限制了模型的應用范圍；文獻[2]中的算法雖然不要求約束規范，但是對大規模約束的求解略顯不足．目前提出的算法，很難應用于實際當中，它們不是限制太多，就是得到的結果可以進一步優化，而且對大規模的計算無能為力或是需要很長時間．

遺傳算法(genetic algorithm)是仿生于自然界中的進化機制和生物遺傳機制，由Holland等在1975年提出的．其通過生成初始種群來進行第一步運行，初始種群通常表示為字符串，即二進制符號編碼，然后通過不斷地生成下一代并根據某種規則來求解問題的最優解．適應度高的個體通過將自身的部分字符串與其他個體的部分字符串進行交換得到下一代個體．在遺傳過程中個體的字符串也會發生變異．隨著時間的推移，將適應度差的個體淘汰，然后利用適應度高的個體在隨機選取的相同的字符串點位進行交換得到新的個體，從而產生下一代種群，這種運行方法非常有效．遺傳算法的人工繁殖計劃在20世紀70年代被首先提出，到20世紀80年代末逐漸得到大量學者的關注及研究．遺傳算法給出了一種解決復雜優化問題的通用框架，它直接對問題的目標函數進行操作，不要求約束函數可以微分等條件，對問題具有很強的魯棒性．由于遺傳算法的這些優點，如今它已經被廣泛應用于工程設計、組合優化等諸多領域．本文將遺傳算法應用于投資組合優化問題．

1二階隨機占優模型

二階隨機占優的基本模型為

(1)

式中：g(x,ξ)是關于x的連續凹函數，x是決策向量；ξ:Ω→Ξ是概率空間(Ω,F,P)上的隨機向量，支撐集Ξ?Rq．f:Rn×Ξ是關于x的連續凸函數．Z?Rn是閉凸集，f,g∈L1(Ω,F,P)．y是Z中某一固定的向量．

隨機占優法則是經濟、決策論中的基本概念，隨機占優的定義如下．

定義1 設X、Y是隨機變量，X，Y∈L1(Ω,F,P)，稱隨機變量X二階占優隨機變量Y，若F(2)(X;η)≤F(2)(Y;η)，?η∈R成立，表示為X(2)Y．其中，?η∈R，F(X;η)是X的累積分布函數．

由文獻[7]可知二階隨機占優X(2)Y等價于如下形式：

E[(η-X)+]≤E[(η-Y)+]，?η∈R

由上述二階隨機占優的等價條件可知模型可以重新改寫為

(2)

為了避免技術上帶來的不便，實際中，通常考慮如下的松弛問題：

(3)

本文研究ξ是離散分布的情況，即P(ξ=ξi)=pi,i=1,…,m．則由文獻[2]可知模型等價于下面的形式：

g(y,ξi))+， ?j=1,…,m

x∈Z

(4)

其中ηj=g(y,ξj),j=1,…,m．

由以上易知，此模型的約束是非光滑的，且此模型不滿足Slater約束規范，這是因為若取ηj=min{g(y,ξj),j=1,…,m}，則式(4)中不等式兩邊均為零．因此求解非光滑約束的算法難以應用于此模型．

2遺傳算法與數值實驗

遺傳算法通過在種群中利用重組的方式和保持有用的模塊來有效地搜索空間．每個種群成員都能找到其所對應的字符串．例如，字符串1001110代表種群空間1######(其中#代表0或1)中的一個個體．這樣，在樣本空間采樣的方式是隱式采樣．遺傳算法這種內在采樣的能力被稱為隱并行性．這指的是眾多的樣本模塊和有效的采樣模式在種群的每一代中都維持．

遺傳算法的基本運算過程如下．

(Ⅰ)初始化：生成所求問題可行域的初始種群并設定終止準則；

(Ⅱ)個體評價：給出種群中每個個體的適應度函數值；

(Ⅲ)選擇運算:根據第(Ⅱ)步中的適應度函數值對種群進行選擇運算；

(Ⅳ)交叉運算：對種群進行交叉運算；

(Ⅴ)變異運算：對種群進行變異運算；

(Ⅵ)終止條件判斷:若達到終止準則，則將適應度函數值最大的個體作為最優解輸出，終止計算．

遺傳算法適用于高維的含有許多非線性和不連續性目標函數或是約束函數的隨機問題．這些問題具有可靠性設計問題的特點：求解問題的部分解決方案或是一個狀態受另一個狀態影響．Coit等[8]成功地證明遺傳算法可以應用于確定性的組合可靠性問題．遺傳算法是一種啟發式的算法，并不保證得到的解必是全局最優．

遺傳算法在對可行解空間進行搜索的過程中，并不需要來自外部的信息，只通過內部的選擇、交叉和變異即可以完成搜索過程．但是搜索過程卻是依據種群中個體適應度函數值的大小來決定個體遺傳到下一代的概率，并且要用適應度函數值來評價解的好壞程度．因此，適應度函數值必須是非負的，在實際應用中，適應度函數通常滿足下面的條件：(1)單值、連續、非負、最大化；(2)合理、一致性；(3)計算量小；(4)通用性強．

在此部分，由于所取數據為樣本數據，令pi=1/m，則模型化為

(5)

例1 以文獻[5]中的例題1為例用遺傳算法求解，并對所得結果進行比較．考慮10個月份的月收益率及5種資產，具體如表1所示．

表1　5種資產10個月的月收益率

設置遺傳算法的初始種群數分別為100、1 000 和10 000，表示為GA(100)、GA(1 000)、GA(10 000)，應用遺傳算法求解，得到的結果如圖1～3所示．

圖1　初始種群為100時的計算結果

圖2　初始種群為1 000時的計算結果

圖3　初始種群為10 000時的計算結果

表2記錄了由遺傳算法得出的數值結果，并給出了投影水平函數(PLF)算法的結果．從中能夠得出：當遺傳算法初始種群數為100時，E[g(x,ξ)]的計算結果明顯好于PLF算法的結果，而且運行時間大大快于PLF算法的運行時間．當初始種群數為1 000時，遺傳算法運行時間和PLF算法運行時間相當，但E[g(x,ξ)]的計算結果明顯好于PLF算法．從表2中還可以看出，E[g(x,ξ)]的計算結果隨著初始種群數量的增加而改善，但是運行時間相應增加．初始種群數從1 000 增加到10 000，結果改善不明顯，但是計算時間卻大大增加，故初始種群數為1 000時，算法效果最好．

表2　不同最優投資組合策略之間的比較

例2 為了檢驗遺傳算法對含有大規模約束的隨機占優模型的計算能力，隨機選取我國上市公司中的75只股票資產在2000～2012年的月收益率來構建隨機占優模型,E[g(y,ξ)]=1.007 1，當初始種群數為1 000時，用遺傳算法得出的結果如圖4所示．

利用上述根據遺傳算法得出的最優結果求得E[g(x,ξ)]=1.008 3，優于原來的投資組合策略．程序運行時間為6.134 min，相同投資方案組合情況下，大大快于文獻[6]中算法的運行時間，而且從圖5中可以看出，用遺傳算法求出的投資組合結果整體優于原來的投資組合策略．

圖4　遺傳算法得出的最優結果

圖5　不同投資組合的樣本月收益率比較

3結語

通過以上結果，可以看出遺傳算法在解決二階隨機占優模型中的優勢．遺傳算法不需要求解目標函數和約束函數的次微分，也不需要模型滿足Slater約束規范，大大提高了問題的可解決性，而且結果優于其他算法的結果．由于遺傳算法在解決復雜、困難的優化問題方面的優勢，在信息量如此巨大的今天，相信遺傳算法會在金融、運籌領域得到廣泛的應用．

參考文獻：

[1] Dentcheva D, Ruszczynski A. Optimization with stochastic dominance constraints [J]. SIAM Journal on Optimization, 2003, 14(2):548-566.

[2]Fábián C I, Mitra G, Roman D. Processing second order stochastic dominance models using cutting-plane representations [J]. Mathematical Programming, 2011, 130(1):33-57.

[3]Homem-de-Mello T, Mehrotra S. A cutting surface method for uncertain linear programs with polyhedral stochastic dominance constraints [J]. SIAM Journal on Optimization, 2009, 20(3):1250-1273.

[4]Rudolf G, Ruszczynski A. Optimization problems with second order stochastic dominance constraints:Duality, compact formulations, and cut generation methods [J]. SIAM Journal on Optimization, 2008, 19(3):1326-1343.

[5]Meskarian R, XU Hui-fu, Fliege J. Numerical methods for stochastic programs with second order dominance constraints with applications to portfolio optimization [J]. European Journal of Operational Research, 2012, 216(2):376-385.

[6]SUN Hai-lin, XU Hui-fu, Meskarian R,etal. Exact penalization, level function method and modified cutting-plane method for stochastic programs with second order stochastic dominance constraints [J]. SIAM Journal on Optimization, 2013, 23(1):602-631.

[7]Ogryczak W, Ruszczynski A. On consistency of stochastic dominance and mean-semideviation models [J]. Mathematical Programming, 2001, 89(2):217-232.

[8]Coit D W, Smith A E. Solving the redundancy allocation problem using a combined neural network/genetic algorithm approach [J]. Computers & Operations Research, 1996, 23(6):515-526.

Solution to constrained optimization problem of second-order stochastic dominance by genetic algorithm

ZHANGHong-wei*1,YUHai-sheng1,PANGLi-ping1,WANGJin-he2

( 1.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China；2.Department of Computer, Qingdao University of Technology, Qingdao 266033, China )

Abstract：Stochastic dominance is fundamental concept in economics and decision-making theory, and is widely applied to portfolio optimization in recent years. Genetic algorithm has the advantages, which doesn′t need to solve the subdifferential of object function and constrained function or to satisfy Slater constrained rules, so it can solve the constrained semi-infinite and non-smooth problem. Two examples show that the genetic algorithm can well solve the portfolio optimization problem and the efficiency is greatly improved.

Key words：second-order stochastic dominance; genetic algorithm; portfolio optimization

中圖分類號：O224

文獻標識碼：A

doi:10.7511/dllgxb201603012

作者簡介:張宏偉*(1955-)，男，教授，博士生導師，E-mail:hwzhang@dlut.edu.cn；于海生(1989-)，男，碩士生，E-mail:yujianbo6666@163.com.

基金項目:國家自然科學基金資助項目(11171049，31271077).

收稿日期：2015-10-16；修回日期: 2016-01-12．

文章編號：1000-8608(2016)03-0299-05