投資組合優化的可行性規則人工蜂群算法

劉永波

(瀘州職業技術學院 信息工程系，四川 瀘州 646005)

證券投資是證券市場運行環節中的重要組成部分，而證券組合理論又是最重要的證券投資理論之一，著名學者Markowitz建立了求解最佳證券投資組合的解析模型。由于最佳證券組合的求解實際上屬于一類組合優化問題，通常歸結為二次規劃模型[1-2]，是一類典型的帶約束NP-hard問題。可運用運籌學中的非線性規劃法求解這類問題，但其求解過程往往十分復雜，而且對求解者的數學理論基礎有較高要求[3-4]。

為了避免繁瑣的數學規劃求解，已有許多學者應用智能算法求解證券組合優化問題。張偉等[1]應用二進制編碼遺傳算法(genetic algorithm, GA)求解該問題，具有簡潔、直觀的優勢，但效率不夠高;何洋林等[2]應用整數編碼自適應遺傳算法(adaptive GA, AGA)求解該問題，提高了求解效率;Soleimani等[3]應用GA求解含最大、最小交易量約束的投資組合優化模型;夏夢雨等[4]則應用粒子群算法(particle swarm optimization, PSO)求解該問題;劉曉峰等[5]應用PSO求解允許賣空證券投資和不允許賣空證券投資2種情形下的優化模型;劉衍民等[6]應用具有約束處理機制的PSO求解自融資投資組合優化模型;李磊等[7]應用2種版本的文化算法(cultural algorithm, CA)求解此模型;江家寶等[8]以最大化個人經濟效益或最大化周期結束時個人財富為目標，建立多階段投資組合優化模型，再應用差分進化算法(differential evolution, DE)求解該問題。最近，有學者應用混合智能算法求解這類問題。李國成等[9]提出基于混沌搜索、PSO和引力搜索算法的混合元啟發式搜索算法，并應用該算法求解基數約束投資組合問題；Lwin等[10]提出融合種群增量學習和DE的混合算法，再應用此方法求解約束投資組合模型。近年來，還有學者應用多目標進化算法(multiobjective evolutionary algorithm, MOEA)[11]求解投資組合優化問題。比如，Branke等[12]應用基于包絡的MOEA求解組合投資問題的Pareto最優解。

由于人工蜂群算法(artificial bee colony algorithm, ABC)[13-15]具有良好的尋優性能，近年來受到廣泛關注，故本文探索應用ABC算法求解證券組合優化問題。在引入約束優化問題可行性規則的基礎上，提出面向證券組合優化問題的可行性規則人工蜂群算法(ABC algorithm with the feasibility rule, FRABC)。文中分析了FRABC算法的計算復雜度和全局收斂性。最后，給出數值實例，通過分析可知：FRABC算法的全局最優解好于AGA。同時，還與GA、PSO算法和基本ABC算法(basic ABC algorithm, BABC)進行對比實驗，測試結果表明，FRABC算法具有良好穩健性，且性能指標優于4種對比算法。

1 投資組合優化數學模型

文獻[3]提出了基于我國證券市場現狀的含交易費用的改進資產分配優化模型，簡要描述如下。

設投資者可購買的證券集合為{s1,s2,…,sn}，其中n為證券種數；證券si(i=1,2,…,n)的收益率為ri(隨機變量)，其期望收益率為Ri=E(ri)，σij=cov(ri,rj)為隨機變量ri和rj的協方差(i,j=1,2,…,n)。若允許的最小和最大投資金額分別為C1和C2，則投資金額C[C1,C2]。證券通常是以最小交易量“手”為基本單位買入和賣出的，設1手=Z股(ZZ+)。若證券si的現時報價為pi元/股，交易量為xi手(xiN)，其投資組合向量為則總投資金額為于是證券si的投資比例為μi=Zxipi/C(x)，投資組合x的資金權重向量為

(1)

投資組合x的風險為

(2)

投資者期望收益率高且風險小，因此，計入交易費用的加權優化模型為

maxF(x)=wf(x)-(1-w)g(x)

(3)

(4)

(5)

2 約束優化的人工蜂群算法

2.1 二級標題約束優化的可行性規則

對于最大化問題式(3)，具有總投資金額區間約束條件式(4)和式(5)，屬于約束優化問題，其求解難點在于如何處理約束條件[6]。本文采用可行性規則處理該約束條件，首先引入比較2個候選解的可行性規則[16]：

規則1 若2個候選解都是可行解，則目標函數值大的獲勝。

規則2 若2個候選解都是不可行解，則約束違反度小的獲勝。

規則3 若一個是可行解而另一個是不可行解，則可行解獲勝。

在規則2中，需要應用候選解的約束違反度比較2個不可行解。本文將候選解x的約束違反度定義為

G(x)=max{0,g1(x)}+max{0,g2(x)}

(6)

顯然，當x為可行解時，有G(x)=0。

2.2 可行性規則人工蜂群算法

在Karaboga與Basturk[13-14]提出的ABC算法中，蜂群分為引領蜂群體、跟隨蜂群體和偵察蜂群體，且依靠3種群體之間的交流、轉換和協作來實現采蜜。同時，模型中應用蜜源來代表候選解，蜜蜂采蜜的過程即為搜尋最優解的過程。有關概念見文獻[13-15]，文中不贅述。

設蜂群規模為N，其中引領蜂和跟隨蜂群體規模分別為NL和NF(通常取相同規模，即NL=NF=N/2)。因式(3)系非負整數規劃問題，故在搜索過程中還需對決策變量取整。FRABC算法的流程如下：

1)初始化種群。按式(7)隨機生成NL個候選解，并置采蜜時刻t=0。

k=1,2,…,NL；i=1,2,…,n

(7)

式中:rand( )為(0,1)內服從均勻分布的隨機數，round(·)為四舍五入取整函數。

將在蜜源xk的鄰域內未發現更優新蜜源的連續搜索次數記為δtk，初始時置δtk=0。

2)引領蜂采蜜。采蜜至第t時刻，每只引領蜂均在其當前蜜源的鄰域內搜索，按式(8)生成新蜜源：

k=1,2,…,NL；i=1,2, …,n

(8)

式中:m{1,2,…,NL}(〗k}，ir{1,2,…,n}，m、ir均為隨機生成的自然數；φk為(-1,1)內服從均勻分布的隨機數(對每只引領蜂只作一次采樣，即生成新蜜源時，每維分量采用相同的φk)；psea(0,1)，為每維分量的搜索概率；應保證文獻[2]提出的ABC算法中，t時刻生成的新蜜源與原蜜源x(t)k相比，僅隨機改變一維分量，其搜索能力有限。本文對每維分量都按一定概率執行搜索，以擴大搜索范圍。

對NL只引領蜂(k=1,2,…,NL)，執行NL次上述鄰域搜索。

3)跟隨蜂采蜜。跟隨蜂的鄰域搜索與蜜源更新方式與引領蜂一致。采蜜至第t時刻，每只跟隨蜂均應用輪賭法選擇被跟隨的引領蜂。第k只引領蜂x(t+1)k被選中的概率為

k=1,2,…,NL

(9)

對NF只跟隨蜂(k=1,2,…,NF)，執行NF次上述鄰域搜索。

4)偵察蜂采蜜。當δtk達到預設閾值Δt時，該蜜源對應的引領蜂轉變為偵察蜂，應用式(7)重新隨機產生新蜜源，并置δtk=0。

引領蜂轉變為偵察蜂可增強種群的多樣性，防止蜂群陷入局部最優區域。該操作可改善蜂群的搜索性能，提高獲得最優解的概率。

5)更新最優蜜源。應用可行性規則確定新一代蜂群中的最優蜜源x(t+1)best。

6)終止判斷。若滿足終止條件，則輸出最優蜜源x(t+1)best及其相應目標函數值F(x(t+1)best)；否則，置t=t+1，返回2)。

2.3 計算復雜度分析

設引領蜂群體規模NL和跟隨蜂群體規模NF相同，且NL=NF=N/2，最大迭代代數為tmax。根據第3.2節中各步驟分析FRABC算法的計算復雜度(僅考慮重復執行的次數)。

2)的計算復雜度為：引領蜂執行鄰域搜索生成新蜜源：O(Nn/2)，評價新蜜源：O(N/2)，更新蜜源：O(N/2)，更新計數器δtk：O(N/2)。3)的計算復雜度為：計算引領蜂被選擇的概率：O(N/2)，選擇被跟隨的引領蜂：O(N/2)，跟隨蜂執行鄰域搜索生成新蜜源：O(Nn/2)，評價新蜜源：O(N/2)，更新蜜源：O(N/2)，更新計數器δtk：O(N/2)。5)的計算復雜度為：O(N/2)，因此步存在不確定性，可忽略其復雜度5)的計算復雜度為：確定每代的最優蜜源：O(N/2)，更新最優蜜源：O(1)。略去上述各步中的低階項，則FRABC算法的計算復雜度為O(tmaxNn)，為立方階復雜度[17]。

3 算法收斂性分析

定義1 稱t時刻的蜜源集合X(t)={x(t)k,k=1,2,…,NL}為FRABC算法的第t代種群，t=0,1,…,tmax。

定義2 稱種群集合B={X={xk,k=1,2,…,NL}:X∩M}為問題式(3)的滿意種群集[18]。

由第2.2節的算法流程可知，FRABC算法具有保留精英解的特點，故有以下定理。

定理1 FRABC算法的最優蜜源x(t+1)best不劣于x(t)best，t=0,1,…,tmax。

定理2 FRABC算法的種群序列{X(t),t=0,1,…,tmax}是齊次不可約非周期Markov鏈。

證明因蜂群對種群X(t)執行鄰域搜索，生成新一代種群X(t+1)時，每一蜜源x(t+1)由引領蜂、跟隨蜂及偵察蜂協同完成搜索[19]。借鑒車林仙[20]分析DE算法收斂性的方法，以下分別給出其一步轉移概率(因篇幅所限，不再展開證明)。

1) 引領蜂執行鄰域搜索的一步轉移概率。

引領蜂k在X(t)中隨機選擇一異于x(t)k的蜜源x(t)m，生成中間蜜源y的概率為

(10)

式中:Ts1為算子符號，以下類似；δ(·)為Dirac函數[20]。

(11)

(12)

綜合式(10)～(12)，可得引領蜂k搜索到新蜜源x的一步轉移概率

Pr{TL(x(t)k,X(t))=x

(13)

2) 跟隨蜂執行鄰域搜索的一步轉移概率。

當選中引領蜂k作為被跟隨蜂時，也可用前述方法計算搜索x的一步轉移概率，其表達式與式(13)類似，簡記為Pr{TF(x(t)k,X(t))=x}。

3) 偵察蜂執行隨機搜索的一步轉移概率。

因偵察蜂對解空間S執行隨機搜索，故獲得x的一步轉移概率為

Pr{TSS=x}=1/|S|

式中:|S|表示S內的離散點數。

于是，僅由引領蜂搜出新一代蜜源x(t+1)k時，其概率為

Pr{T1(x(t)k,X(t))=x(t+1)k}=

Pr{TL(x(t)k,X(t))=x(t+1)k}

(14)

由引領蜂和跟隨蜂共同搜出新一代蜜源x(t+1)k時，其概率為

Pr{T1(x(t)k,X(t))=x(t+1)k}=

Pr{TL(x(t)k,X(t))=x′1}Pr{TL(x′1,X(t))=

x′2}…Pr{TL(x′q,X(t))=x(t+1)k}

(15)

式中:q≥1，指引領蜂k被跟隨的次數。

由偵察蜂搜出新一代蜜源x(t+1)k時，其概率為

Pr{T1(x(t)k,X(t))=x(t+1)k}=

Pr{TSS=x(t+1)k}

(16)

那么，由X(t)生成X(t+1)的一步轉移概率為[19-20]

Pr{TX(t)=X(t+1)}=

(17)

證明假設問題式(3)有惟一最優解。對X1,X2SNL，由定理1、2可得如下性質：

1) 當X1B，X2B時，Pr{TX1=X2}>0，Pr{TX2=X1}>0，即X1和X2可互通；

2) 當X1B，X2B時，Pr{TX1=X2}=0，Pr{TX2=X1}>0，即X1不能通向X2。

于是，B為正常返非周期不可約閉集[21]，且有

即X(t)一定能進入B內，且滿足某極限概率分布(X)(XB)。故

?X(0)∈SNL}=1

4 算例與討論

算例來自文獻[2]。假設購買股票1手=100股(即Z=100)，總投資金額上限C2=10萬元，(C2-C1)/C2=0.2%。擬投資的n(=5)支股票的價格為

(元/股)

每支股票的投資金額最多占總金額的60%，進而可確定購買手數上限

每支股票的交易手續費比例ξ1i=0.035%，ξ2i=0.04% (i=1,2,…,5)，且傭金最低額度cmin 1=cmin 2=10元，cmin 3=cmin 4=cmin 5=5元，5支股票的平均收益率列陣為

5支股票的風險方差方陣為

根據第2.2節的FRABC算法流程，應用MATLAB編寫程序，控制參數設置為：蜂群規模N=40，搜索概率psea=0.85，最大迭代代數tmax=600，代數閾值Δt=100。對于不同的風險偏好因子w，對應優化結果見表1(分別獨立運行50次，表中為最好結果)。FRABC算法獨立運行一次的函數評價次數為N×tmax=24 000；而文獻[2]的參數為N=20，tmax=200，AGA獨立運行一次的函數評價次數為N×tmax=4 000。由表1可知，對于不同的w，應用FRABC算法求出的加權優化結果F(x)均明顯優于AGA。因此，雖然FRABC算法的函數評價次數高于AGA，但從優化結果來看，本文認為FRABC算法增加的計算開銷是值得的。

表1 算例中的股票投資策略

續表1

注：表中AGA的計算結果引自文獻[2]。

為了考察FRABC算法的有效性，本文還比較GA、PSO、BABC算法[13-14]和FRABC算法求解投資組合優化問題的優化性能。將可行性規則與GA、PSO和BABC算法結合形成的算法記為FRGA、FRPSO和FRBABC。

為了公平比較，所有算法的種群規模N、最大迭代代數tmax一致，取N=40，tmax=600，即函數評價次數一致。與FRABC算法類似，FRGA、FRPSO和FRBABC算法均采用非負整數編碼，應用函數round(·)取整。FRGA應用概率選擇(按式(9)選擇，記為FRGA1)或2元錦標賽選擇(記為FRGA2)、隨機算術交叉[2]和均勻變異策略，交叉、變異概率分別為pc=0.9，pm=0.2。FRPSO算法的慣性權重線性遞減，取=1.2～0.2，加速度系數為c1=c2=2，最大速度取(i=1,2,…,5)。FRBABC算法除無參數psea外，其余控制參數與FRABC算法一致。

圖1 5種算法的平均進化曲線(w=0.4)Fig.1 The average evolution curve of five algorithms(w=0.4)

圖2 5種算法的平均進化曲線(w=0.5)Fig.2 The average evolution curve of five algorithms(w=0.5)

圖3 5種算法的平均進化曲線(w=0.6)Fig.3 The average evolution curve of five algorithms(w=0.6)

風險偏好因子w算法最好值Fb最差值Fw平均值Fav標準方差σ2F0.4FRGA17.939×10-36.147×10-37.098×10-33.427×10-4FRGA28.009×10-36.699×10-37.176×10-32.672×10-4FRPSO8.287×10-36.962×10-38.096×10-32.715×10-4FRBABC8.087×10-37.263×10-37.761×10-32.178×10-4FRABC8.287×10-38.270×10-38.283×10-36.931×10-60.5FRGA11.304×10-21.131×10-21.208×10-23.995×10-4FRGA21.271×10-21.153×10-21.209×10-22.849×10-4FRPSO1.347×10-21.192×10-21.325×10-22.776×10-4FRBABC1.324×10-21.219×10-21.271×10-22.623×10-4FRABC1.347×10-21.345×10-21.347×10-24.575×10-60.6FRGA11.923×10-21.718×10-21.820×10-24.555×10-4FRGA22.011×10-21.785×10-21.851×10-24.195×10-4FRPSO2.050×10-21.833×10-22.012×10-24.318×10-4FRBABC2.013×10-21.841×10-21.932×10-23.605×10-4FRABC2.051×10-22.031×10-22.049×10-23.462×10-5

5 結論

1) 給出包含交易費用基于投資者風險偏好的最佳證券投資組合模型；針對其約束條件，定義了約束違反度函數，進而引入求解約束優化問題的可行性規則。

2) 新型智能算法ABC在求解非線性優化問題中具有很強的全局尋優能力和很好的實用性，本文應用ABC算法求解最佳證券投資組合模型，形成面向該類問題的FRABC算法。

3) FRABC算法的計算復雜度為立方階復雜度，與基本算法FRBABC一致。還應用Markov鏈分析其種群狀態的一步轉移概率，證明了該算法的全局收斂性。

4) 應用MATLAB編寫FRABC算法的計算程序，通過實例驗證了該算法具有很強的尋優性能和良好的穩健性，且結果優于AGA。在相同函數評價次數的條件下，FRABC算法的各項優化指標均好于FRGA、FRPSO和FRBABC等對比算法，表明了本文方法的有效性和實用性。

參考文獻:

[1]張偉, 周群, 孫德寶. 遺傳算法求解最佳證券組合[J]. 數量經濟技術經濟研究, 2001(10): 114-116.

ZHANG Wei, ZHOU Qun, SUN Debao. Genetic algorithm for portfolio investment optimizations[J]. Quantitative and Technical Economics, 2001(10): 114-116.

[2]何洋林, 葉春明, 徐濟東. 基于改進AGA算法求解含交易費用組合投資模型[J]. 計算機工程與應用, 2007, 43(11): 235-237.

HE Yanglin, YE Chunming, XU Jidong. Portfolio investment model including transaction fee and solution based on adaptive genetic algorithm[J]. Computer Engineering and Applications, 2007, 43(11): 235-237.

[3]SOLEIMANI H, GOLMAKANI H R, SALIMI M H. Markowitz-based portfolio selection with minimum transaction lots, cardinality constraints and regarding sector capitalization using genetic algorithm[J]. Expert Systems with Applications, 2009, 36(3): 5058-5063.

[4]夏夢雨, 葉春明, 徐濟東. 用微粒群算法求解含交易費用的組合投資模型[J]. 上海理工大學學報, 2008, 30(4): 379-381, 386.

XIA Mengyu, YE Chunming, XU Jidong. Solution of portfolio investment model including transaction fee with particle swarm algorithm[J]. Journal of University of Shanghai for Science and Technology, 2008, 30(4): 379-381, 386.

[5]劉曉峰, 陳通, 張連營. 基于微粒群算法的最佳證券投資組合研究[J]. 系統管理學報, 2008, 17(2): 221- 224, 234.

LIU Xiaofeng, CHEN Tong, ZHANG Lianying. Study on the portfolio problem based on particle swarm optimization[J]. Journal of Systems and Management, 2008, 17(2): 221- 224, 234.

[6]劉衍民, 趙慶禎, 牛奔. 約束粒子群算法求解自融資投資組合模型研究[J]. 數學的實踐與認識, 2011, 41(2): 78-84.

LIU Yanmin, ZHAO Qingzhen, NIU Ben. Constrain particle swarm optimizer for solving self-financing portfolio model[J]. Mathematics in Practice and Theory, 2011, 41(2): 78-84.

[7]李磊, 程晨, 張穎. 基于文化算法的投資組合規劃問題求解[J]. 江南大學學報: 自然科學版, 2009, 8(1): 108-111.

LI Lei, CHENG Chen, ZHANG Ying. Solving portfolio programming problem based on cultural algorithm[J]. Journal of Jiangnan University: Natural Science Edition, 2009, 8(1): 108-111.

[8]江家寶, 尤振燕, 孫俊. 基于微分進化算法的多階段投資組合優化[J]. 計算機工程與應用, 2007, 43(3): 189 -193.

JIANG Jiabao, YOU Zhenyan, SUN Jun. Multi-stage portfolio optimization using differentiation evolution algorithms[J]. Computer Engineering and Applications, 2007, 43(3): 189-193.

[9]李國成, 肖慶憲. 基數約束投資組合問題的一種混合元啟發式算法求解[J]. 計算機應用研究, 2013, (8): 2292-2297.

LI Guocheng, XIAO Qingxian. Hybrid meta-heuristic algorithm for solving cardinality constrained portfolio optimization[J]. Application Research of Computers, 2013, 30(8): 2292-2297.

[10]LWIN K, QU R. A hybrid algorithm for constrained portfolio selection problems[J]. Applied Intelligence, 2013, 39(2): 251-266.

[11]PONSICH A, JAIMES A L, COELLO C A. A survey on multiobjective evolutionary algorithms for the solution of the portfolio optimization problem and other finance and economics applications[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(3): 321-344.

[12]BRANKE J, SCHECKENBACH B, STEIN M, et al. Portfolio optimization with an envelope-based multi-objective evolutionary optimization[J]. European Journal on Operations Research, 2009, 199(3): 684-693.

[13]KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3): 459-471.

[14]KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687-697.

[15]段海濱, 張祥銀, 徐春芳. 仿生智能計算[M]. 北京: 科學出版社, 2011: 88-106.

DUAN Haibin, ZHANG Xiangyin, XU Chunfang. Bio-inspired Computing[M]. Beijing: Science Press, 2011: 88-106.

[16]MALLIPEDDI R, SUGANTHAN P N. Ensemble of constraint handling techniques[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(4): 561-579.

[17]溫濤, 盛國軍, 郭權, 等. 基于改進粒子群算法的Web服務組合[J]. 計算機學報, 2013, 36(5): 1 031- 1046.

WEN Tao, SHENG Guojun, GUO Quan, et al. Web service composition based on modified particle swarm optimization[J]. Chinese Journal of Computers, 2013, 36(5): 1031-1046.

[18]張文修, 梁怡. 遺傳算法的數學基礎[M]. 2版. 西安: 西安交通大學出版社, 2003: 118-122.

[19]寧愛平, 張雪英. 人工蜂群算法的收斂性分析[J]. 控制與決策, 2013, 28(9): 1 554-1 558.

NING Aiping, ZHANG Xueying. Convergence analysis of artificial bee colony algorithm[J]. Control and Decision, 2013, 28(9): 1 554-1 558.

[20]車林仙. 面向機構分析與設計的差分進化算法研究[D]. 徐州: 中國礦業大學, 2012: 21-30.

CHE Linxian. Study on differential evolution algorithms orientating analysis and design of mechanisms[D]. Xuzhou: China University of Mining and Technology, 2012: 21-30.

[21]ZHANG Xiangyin, DUAN Haibin, YU Yaxiang. Receding horizon control for multi-UAVs close formation control based on differential evolution[J]. Science China Information Sciences, 2010, 53(2): 223-235.