二階隨機(jī)占優(yōu)約束優(yōu)化問題的遺傳算法求解

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

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

?

二階隨機(jī)占優(yōu)約束優(yōu)化問題的遺傳算法求解

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

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

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

關(guān)鍵詞：二階隨機(jī)占優(yōu)；遺傳算法；投資組合優(yōu)化

0引言

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

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

1二階隨機(jī)占優(yōu)模型

二階隨機(jī)占優(yōu)的基本模型為

(1)

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

隨機(jī)占優(yōu)法則是經(jīng)濟(jì)、決策論中的基本概念，隨機(jī)占優(yōu)的定義如下．

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

由文獻(xiàn)[7]可知二階隨機(jī)占優(yōu)X(2)Y等價于如下形式：

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

由上述二階隨機(jī)占優(yōu)的等價條件可知模型可以重新改寫為

(2)

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

(3)

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

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

x∈Z

(4)

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

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

2遺傳算法與數(shù)值實驗

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

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

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

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

(Ⅲ)選擇運算:根據(jù)第(Ⅱ)步中的適應(yīng)度函數(shù)值對種群進(jìn)行選擇運算；

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

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

(Ⅵ)終止條件判斷:若達(dá)到終止準(zhǔn)則，則將適應(yīng)度函數(shù)值最大的個體作為最優(yōu)解輸出，終止計算．

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

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

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

(5)

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

表1　5種資產(chǎn)10個月的月收益率

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

圖1　初始種群為100時的計算結(jié)果

圖2　初始種群為1 000時的計算結(jié)果

圖3　初始種群為10 000時的計算結(jié)果

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

表2　不同最優(yōu)投資組合策略之間的比較

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

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

圖4　遺傳算法得出的最優(yōu)結(jié)果

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

3結(jié)語

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

參考文獻(xiàn)：

[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

文獻(xiàn)標(biāo)識碼：A

doi:10.7511/dllgxb201603012

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

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

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

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