紀(jì)昌明，吳 昊，黃 鋒，張驗(yàn)科

(1.華北電力大學(xué)可再生能源學(xué)院，北京 102206；2. 中水珠江規(guī)劃勘測(cè)設(shè)計(jì)有限公司，廣州 510610)

0 引 言

依據(jù)水庫(kù)優(yōu)化調(diào)度的基本約束條件和最優(yōu)原則，其基本任務(wù)就是使水庫(kù)在一定時(shí)期內(nèi)，制定和實(shí)現(xiàn)符合實(shí)際情況較優(yōu)的運(yùn)行方式[1]。然而水庫(kù)發(fā)電優(yōu)化調(diào)度是一個(gè)具有較多約束條件、動(dòng)態(tài)的復(fù)雜非線(xiàn)性?xún)?yōu)化問(wèn)題，目前，國(guó)內(nèi)外學(xué)者們對(duì)其研究方法主要分為兩類(lèi)：一類(lèi)是以線(xiàn)性規(guī)劃法、非線(xiàn)性規(guī)劃法、動(dòng)態(tài)規(guī)劃法[2]、逐次逼近法[3]、逐步優(yōu)化法[4]等為典型代表的傳統(tǒng)方法，這些方法的主要缺點(diǎn)是多約束條件難以處理、算法復(fù)雜、計(jì)算時(shí)間較長(zhǎng)等；另一類(lèi)是以遺傳算法[5]、蟻群算法[6]、粒子群算法[7]、模擬退火算法[8]、人工神經(jīng)網(wǎng)絡(luò)算法[9]等為典型代表的具有啟發(fā)式特點(diǎn)的智能方法，雖然這類(lèi)方法同樣可以對(duì)水庫(kù)運(yùn)行進(jìn)行優(yōu)化，然而存在諸如收斂不穩(wěn)定、容易陷入局部最優(yōu)解的特點(diǎn)。

隨著人工智能學(xué)科的飛速發(fā)展，2002年，李曉磊[10]等提出了人工魚(yú)群算法 ( Artificial Fish Swarm Algorithm，AFSA)。目前，關(guān)于AFSA的研究已經(jīng)滲透到水庫(kù)及水庫(kù)群優(yōu)化調(diào)度領(lǐng)域，并且取得了豐碩的科研成果，已成為水庫(kù)及水庫(kù)群優(yōu)化調(diào)度領(lǐng)域的研究熱點(diǎn)之一。

這種算法具備天然的自組織特征，是通過(guò)分析魚(yú)類(lèi)的活動(dòng)作為出發(fā)點(diǎn)進(jìn)行尋優(yōu)的，是基于動(dòng)物行為的人工智能方法之一。作為一種新型的仿生優(yōu)化算法，在空間搜索相關(guān)問(wèn)題上具有一定的自適應(yīng)能力，對(duì)參數(shù)和初值的設(shè)定不過(guò)于苛刻，魯棒性強(qiáng)、簡(jiǎn)單并易于實(shí)現(xiàn)，并且具有并行處理問(wèn)題的能力。但是該算法后期的尋優(yōu)精度不高，容易陷入求得局部極值的狀況，并且隨著搜索盲目性擴(kuò)大，搜索速度變慢，耗費(fèi)時(shí)間較多。

針對(duì)AFSA后期搜索易陷入局部極值的問(wèn)題，結(jié)合混沌優(yōu)化算法[11](Chaos Optimization Algorithm,COA)，黃鋒[12]在2014年提出了混沌人工魚(yú)群算法(Chaos Artificial Fish Swarm Algorithm, 簡(jiǎn)稱(chēng)CAFSA)。因?yàn)镃OA具有較為精致的內(nèi)在結(jié)構(gòu)，能把系統(tǒng)內(nèi)部運(yùn)動(dòng)束縛在一定的范圍內(nèi)，根據(jù)自身規(guī)律可以不重復(fù)的遍歷各種狀態(tài)，有力克服AFSA后期出現(xiàn)“早熟現(xiàn)象”的缺點(diǎn)。然而結(jié)合混沌遍歷后計(jì)算耗時(shí)在原有基礎(chǔ)上有所增加。如何應(yīng)用并行計(jì)算[13]有效減少計(jì)算耗時(shí)是本文的研究重點(diǎn)。并行計(jì)算是根據(jù)多核計(jì)算機(jī)或計(jì)算機(jī)群可以同一時(shí)刻處理多任務(wù)的特點(diǎn)，研究設(shè)計(jì)如何將一個(gè)應(yīng)用分解成多個(gè)可以并行處理的子任務(wù)，并分配給多核單機(jī)或是機(jī)群的不同處理器，之后各處理器之間相互協(xié)調(diào)，同一時(shí)刻并行處理各子任務(wù)，從而達(dá)到加快求解速度的目的。AFSA中各人工魚(yú)具備自身獨(dú)立處理任務(wù)的特點(diǎn)，另從張志新[14]的研究中可認(rèn)知COA并行化的基本思想，為本文水庫(kù)發(fā)電優(yōu)化調(diào)度雙層并行計(jì)算架構(gòu)設(shè)計(jì)奠定了基礎(chǔ)。

本文在CAFSA基礎(chǔ)上，結(jié)合雙層并行計(jì)算模式，對(duì)水庫(kù)發(fā)電優(yōu)化調(diào)度問(wèn)題進(jìn)行求解，將此稱(chēng)為混沌人工魚(yú)群并行算法(Chaos Artificial Fish Swarm Parallel Algorithm, 簡(jiǎn)稱(chēng)CAFSPA)?；陔p層并行計(jì)算架構(gòu)設(shè)計(jì)的實(shí)例計(jì)算結(jié)果表明該算法能獲得較好的優(yōu)化性能以及運(yùn)行效率，為水庫(kù)發(fā)電優(yōu)化調(diào)度計(jì)算提供一種可行的研究方向。

1 混沌人工魚(yú)群并行算法(CAFSPA)原理

1.1 基本人工魚(yú)群算法(AFSA)

AFSA基本思想源自魚(yú)群的覓食行為。在某一水域，個(gè)體魚(yú)能夠通過(guò)自行或尾隨其他魚(yú)的方式，找到營(yíng)養(yǎng)物質(zhì)豐富的地方，因此魚(yú)群聚數(shù)目最多。根據(jù)這一特點(diǎn)，可以通過(guò)構(gòu)造人工魚(yú)來(lái)模擬魚(yú)群的覓食、聚群、追尾及隨機(jī)行為來(lái)實(shí)現(xiàn)尋優(yōu)目的[15]。在人工魚(yú)群算法中主要研究如何利用簡(jiǎn)便有效的方式來(lái)構(gòu)造并實(shí)現(xiàn)這些行為。

人工魚(yú)是真實(shí)個(gè)體魚(yú)的虛擬實(shí)體，內(nèi)部封裝了一系列的行為和自身參數(shù)數(shù)據(jù)，通過(guò)感官參數(shù)接收環(huán)境刺激信息，并通過(guò)人工魚(yú)的控制參數(shù)做出相應(yīng)的行為活動(dòng)。問(wèn)題的解空間和其他人工魚(yú)的狀態(tài)構(gòu)成了某條人工魚(yú)所在的環(huán)境。而該條人工魚(yú)目前的自身狀態(tài)和所處環(huán)境為其下一刻的行為決定做出前提條件，同時(shí)，該條人工魚(yú)通過(guò)自身行為活動(dòng)影響環(huán)境以及其他同伴的行為活動(dòng)。

公告板的作用是記錄最優(yōu)人工魚(yú)的個(gè)體狀態(tài)，每條人工魚(yú)執(zhí)行完一次迭代后會(huì)把自身當(dāng)前狀態(tài)與公告板的數(shù)據(jù)進(jìn)行比較，若優(yōu)于公告板中記錄的數(shù)據(jù)則會(huì)用當(dāng)前的狀態(tài)更新公告板，否則公告牌數(shù)據(jù)保持不變。解決問(wèn)題時(shí)通常采用的是選擇最優(yōu)行為執(zhí)行和選擇較優(yōu)方向兩種方式評(píng)價(jià)，最后通過(guò)連續(xù)多次所得值的均方差是否小于允許誤差等方法來(lái)終止算法的迭代。等整個(gè)算法數(shù)次迭代結(jié)束后，輸出公告板的值便是所求最優(yōu)值。

1.2 混沌優(yōu)化算法(COA)

非線(xiàn)性系統(tǒng)中的混沌運(yùn)動(dòng)，表面上看似運(yùn)動(dòng)混亂，但實(shí)際上是有章可循的，是一種無(wú)固定周期的循環(huán)行為[16]。該混沌現(xiàn)象的獨(dú)特性可歸納如下：①隨機(jī)性，即具有隨機(jī)變量雜亂表現(xiàn)。②遍歷性，即可以在一定的狀態(tài)空間中不重復(fù)的經(jīng)歷所有狀態(tài)。③規(guī)律性，即此混沌運(yùn)動(dòng)可以應(yīng)用確定性的數(shù)學(xué)迭代表達(dá)式進(jìn)行描述。

其中第二點(diǎn)是本文研究與應(yīng)用COA的重要特點(diǎn)。

COA的基本思想是構(gòu)造混沌變量序列，通過(guò)函數(shù)形式把混沌變量映射到優(yōu)化變量的取值范圍內(nèi)，充分利用混沌變量的遍歷性這一主要特點(diǎn)來(lái)尋求全局最優(yōu)解。

在COA中最經(jīng)典模型之一便是Logistic模型，表達(dá)式如下：

Xi+1=UXi(1-Xi)Xi∈(0,1)

(1)

式中U作為控制參數(shù)，取值范圍[0,1]。當(dāng)U=4時(shí)，系統(tǒng)便處于混沌狀態(tài)。取任意初始點(diǎn)，即得Xi在(0,1)區(qū)間上的遍歷點(diǎn)列。

1.3 AFSA存在問(wèn)題與解決方案

在水庫(kù)發(fā)電優(yōu)化調(diào)度計(jì)算中，基于原有AFSA，結(jié)合COA的遍歷特性，學(xué)者黃鋒提出的CAFSA，有效控制了AFSA在后期搜索中容易陷入求得局部極值的局面。然而AFSA后期搜索盲目性擴(kuò)大、速度變慢，從而導(dǎo)致耗費(fèi)時(shí)間較多的局面并未改觀(guān)，另外COA進(jìn)一步增加了一定的尋優(yōu)計(jì)算耗時(shí)。為了進(jìn)一步提高優(yōu)化解的精度，可增加人工魚(yú)群的種群數(shù)，但是此舉也會(huì)增加一定計(jì)算耗時(shí)。

并行算法是基于多核計(jì)算機(jī)或是多臺(tái)互聯(lián)的計(jì)算機(jī)群，對(duì)問(wèn)題進(jìn)行聯(lián)合求解的方法和步驟。其基本思想是將待解決問(wèn)題分解成若干個(gè)盡量相互獨(dú)立的子任務(wù),然后使用多核計(jì)算機(jī)或多臺(tái)互聯(lián)計(jì)算機(jī)群同時(shí)求解這些被分解的子任務(wù),最終求得原問(wèn)題的整體優(yōu)化解[17]。并行計(jì)算主要目的是為了充分利用閑置有效的計(jì)算資源，盡量縮減原問(wèn)題的計(jì)算耗時(shí)，提高解決問(wèn)題的工作效率。因此在水庫(kù)發(fā)電優(yōu)化調(diào)度中并行化處理CAFSA是解決計(jì)算耗時(shí)問(wèn)題的有效途徑。

1.4 混沌人工魚(yú)群并行算法(CAFSPA)

并行計(jì)算基本思想是實(shí)現(xiàn)分解后子任務(wù)各自計(jì)算時(shí)間的相互重疊。在CAFSA中，每條人工魚(yú)的自身?xiàng)l件和周?chē)h(huán)境決定了其具體行為，因此算法的靈活性比較強(qiáng)，設(shè)計(jì)思路中必須考慮如何利用魚(yú)群協(xié)作來(lái)進(jìn)行全局尋優(yōu)，然而個(gè)體人工魚(yú)具體行為運(yùn)動(dòng)是相互獨(dú)立的，以此可作為并行計(jì)算的必要條件之一。CAFSA中具備COA中Logistic映射產(chǎn)生的序列，能不重復(fù)遍歷一定范圍內(nèi)的所有點(diǎn)[18]。張志新[14]應(yīng)用COA求解時(shí)，為了提高尋優(yōu)精度，設(shè)置了多個(gè)混沌初始值進(jìn)行計(jì)算，其中各初始值作為起點(diǎn)計(jì)算是相互獨(dú)立的，從而提出的COA并行化，為本文并行計(jì)算提供了一定的思考方向。

因此可以采用互聯(lián)的多核計(jì)算機(jī)群來(lái)模擬各個(gè)體人工魚(yú)尋優(yōu)的子任務(wù)，結(jié)合并行算法設(shè)計(jì)在同一時(shí)刻解決多子任務(wù)可以較大提高求最優(yōu)解效率。

基于黃鋒的CAFSA，在水庫(kù)發(fā)電優(yōu)化調(diào)度計(jì)算中提出了CAFSPA即混沌人工魚(yú)群并行算法，具有效率高、收斂快、結(jié)果精度高等優(yōu)點(diǎn)。CAFSPA首先也采用兩種集成模式：一是通過(guò)Logistic映射產(chǎn)生的序列，放大到?jīng)Q策變量的取值空間，然后以此作為AFSA的初始解，這將有助于提高求解質(zhì)量。二是通過(guò)人工魚(yú)群中各個(gè)體魚(yú)Xi(i=1,2,…Np)進(jìn)行能量判定之后，執(zhí)行某個(gè)移動(dòng)，例如覓食、群聚、追尾或隨機(jī)等行為動(dòng)作，便得到相應(yīng)的Xinext，對(duì)Xinext的每個(gè)分量zti,next(t=1,2,…,T)可以進(jìn)行一次混沌優(yōu)化搜索，將此視同對(duì)混沌優(yōu)化計(jì)算附上不同的初始值，可對(duì)各自獨(dú)立計(jì)算進(jìn)行并行化處理。根據(jù)機(jī)群中工作計(jì)算機(jī)數(shù)目M，將人工魚(yú)群分成M個(gè)子魚(yú)群，分配到對(duì)應(yīng)的多核計(jì)算機(jī)進(jìn)行計(jì)算，實(shí)現(xiàn)各子魚(yú)群的并行計(jì)算，相互之間通過(guò)MPI進(jìn)行數(shù)據(jù)通信。每條人工魚(yú)的行為動(dòng)作以及每個(gè)Xinext分量的混沌優(yōu)化搜索，可以采用所在多核計(jì)算機(jī)的OpenMP進(jìn)行并行計(jì)算處理。這樣人工魚(yú)群內(nèi)外雙層并行混沌搜索的隨機(jī)性、遍歷性既可以避免魚(yú)群陷入局部最優(yōu)，又能提升收斂速度，充分利用閑置資源，有效減少計(jì)算耗時(shí)。

2 基于CAFSPA的水庫(kù)發(fā)電優(yōu)化調(diào)度

2.1 水庫(kù)發(fā)電優(yōu)化調(diào)度模型建立

本文主要研究的是水庫(kù)發(fā)電優(yōu)化調(diào)度，可以采用水庫(kù)在整個(gè)調(diào)度期限內(nèi)的總電能最大作為優(yōu)化調(diào)度準(zhǔn)則，優(yōu)化調(diào)度模型建立如下：

(2)

其中約束條件為：

蓄水量約束：Vtmin≤Vt≤Vtmax

(3)

放水量約束：Qtmin≤Qt≤Qtmax

(4)

出力約束：Ntmin≤Nt≤Ntmax

(5)

水量平衡方程：Vt=Vt-1+(It-Qt)Δt

(6)

非負(fù)約束：Qt>0

(7)

邊界約束：z1=CZ1,z(T+1)=CZ(T+1)

(8)

各式中變量含義解釋如下：

式(2)中：F為發(fā)電量最大值；T為年調(diào)節(jié)水庫(kù)中劃分的時(shí)段總數(shù)(一般取值12)；K為出力系數(shù)(取常數(shù)值)；qt為第t個(gè)時(shí)段的發(fā)電流量；ht為第t個(gè)時(shí)段發(fā)電平均水頭；Δt為一個(gè)時(shí)段的計(jì)時(shí)，s。

式(3)中：Vtmin和Vtmax分別表示為水庫(kù)第t個(gè)時(shí)段庫(kù)容上限和下限；Vt表示為水庫(kù)第t個(gè)時(shí)段的初庫(kù)容。其中Vtmin取值為死水位相應(yīng)庫(kù)容，在汛期時(shí)，Vtmax取值為防洪限制水位的相應(yīng)庫(kù)容，非汛期時(shí)Vtmax取值為正常蓄水位相應(yīng)庫(kù)容。

式(4)中：Qtmin和Qtmax分別為水庫(kù)第t個(gè)時(shí)段的最小和最大放水量；Qt則為第t個(gè)時(shí)段的放水量，其中包括發(fā)電流量qt，也有可能包括棄水。

當(dāng)水庫(kù)放水量都用來(lái)發(fā)電時(shí)，Qt=qt；當(dāng)水庫(kù)放水量大于水庫(kù)發(fā)電流量，就會(huì)產(chǎn)生棄水，此時(shí)Qt>qt。式(2)作為目標(biāo)函數(shù)是以發(fā)電為目標(biāo)，故用qt表示；約束條件中，放水量可能包括棄水，故用Qt表示。

式(5)中：Ntmin和Ntmax分別為第t個(gè)時(shí)段水庫(kù)的最小出力和最大出力；Nt則為第t個(gè)時(shí)段的出力。

式(6)中：Vt-1和Vt分別為第t個(gè)時(shí)段水庫(kù)的初、末庫(kù)容大??；It為第t個(gè)時(shí)段的入庫(kù)流量；Qt為第t個(gè)時(shí)段的出庫(kù)流量。

式(8)中：z1，z(T+1)分別為第一個(gè)時(shí)段初和最后一個(gè)時(shí)段末的水位值；CZ1，CZ(T+1)都為常數(shù)(取水庫(kù)死水位值)。

2.2 基于CAFSPA水庫(kù)發(fā)電優(yōu)化調(diào)度的求解步驟

據(jù)水庫(kù)發(fā)電優(yōu)化調(diào)度特點(diǎn)，參考黃鋒的CAFSA，CAFSPA即混沌人工魚(yú)群并行算法的計(jì)算步驟如下：

(1)劃分年調(diào)水庫(kù)調(diào)度期為T(mén)=12時(shí)段，決策變量為各時(shí)段的初水庫(kù)水位，取值空間設(shè)為[Ztmin,Ztmax]，即在水庫(kù)第t個(gè)時(shí)段庫(kù)容下限值Vtmin和上限值Vtmax之間。

(2)設(shè)定算法中各主要參數(shù)值，如確定整個(gè)算法的最大迭代次數(shù)，以MaxNumber表示；人工魚(yú)群規(guī)模，以Np表示；人工魚(yú)的視野范圍，以Visual表示；移動(dòng)步長(zhǎng)，以step表示；擁擠度因子，以δ表示；最大嘗試次數(shù)，以TryNumber表示。

(3)每條人工魚(yú)的混沌初始化。為便于區(qū)分每條人工魚(yú)，可對(duì)人工魚(yú)進(jìn)行編號(hào)，命名為n(n∈[1,Np])，令某條人工魚(yú)編號(hào)為n=1，由調(diào)度期內(nèi)被劃分的時(shí)段數(shù)，可隨機(jī)生成T個(gè)初始值xnt(t=1,2,…,T)，并令X1=(x11,x12,…,x1T)，即為該條編號(hào)為n=1的人工魚(yú)。X1代入式(1)后，可迭代成系列混沌向量{Xn}n=2,3,…,Np，其中Xn=(xn1,xn2,…,xnT)，即是人工魚(yú)群中其他編號(hào)的個(gè)體人工魚(yú)。

znt=Ztmin+(Ztmax-Ztmin)xnt

(9)

將此系列混沌向量{Xn}n=2,3,…,Np，依據(jù)式(9)被放大至決策變量取值空間[Ztmin,Ztmax]，可以得到初始的決策變量。此時(shí)第n號(hào)個(gè)體人工魚(yú)表示為Zn=(zn1,zn2,…,znT)n=1,2,…,Np，其中znt(t=1,2,…,T)表示為第n號(hào)個(gè)體人工魚(yú)在第t時(shí)段的初水位。其實(shí)一條人工魚(yú)表示的就是水庫(kù)發(fā)電調(diào)度的一種運(yùn)行決策?？梢圆粩嗾{(diào)整混沌人工魚(yú)的水位值，以致滿(mǎn)足各約束條件，最終目的是使得每條混沌人工魚(yú)都是滿(mǎn)足此水庫(kù)發(fā)電調(diào)度的可行范圍之內(nèi)，同時(shí)也可以加快算法收斂速度。

為了滿(mǎn)足水量平衡方程，決策變量的取值空間可以由以下方法來(lái)確定：

關(guān)注某時(shí)段t，其水量平衡方程為Vt+1=Vt+(It+1-Qt+1)Δt，由式(8)可知，Vt為一個(gè)固定值，再根據(jù)約束條件V(t+1)min

上界：

Q*tmax=min{Qtmax,(Vt-V(t+1)min+qt)/Δt}

(10)

下界：

Q*tmin=max{Qtmin,(Vt-V(t+1)max+qt)/Δt}

(11)

Vt+1的取值范圍由此可以被確定，根據(jù)庫(kù)容特征曲線(xiàn)便可求出相應(yīng)的水位取值范圍[Z(t+1)min,Z(t+1)max]。由此得到的初始種群必滿(mǎn)足各約束條件。

(4)根據(jù)計(jì)算機(jī)群中單機(jī)的數(shù)目M，按個(gè)體混沌人工魚(yú)的總數(shù)Np和各自編號(hào)n，將混沌人工魚(yú)群平均分成M個(gè)混沌人工魚(yú)子群(除最后一個(gè)子群其他每個(gè)子群中單體混沌人工魚(yú)的數(shù)目為Np/M的整數(shù)位，即[Np/M],最后一個(gè)子群中單體混沌人工魚(yú)的數(shù)目為Np-(M-1)·[Np/M]，作為進(jìn)程，被分配到對(duì)應(yīng)的不同編號(hào)多核計(jì)算機(jī)中，通過(guò)MPI傳輸協(xié)議實(shí)時(shí)傳遞各處理機(jī)的有效數(shù)據(jù)。這樣便可實(shí)現(xiàn)不同處理機(jī)同一時(shí)刻處理不同子任務(wù)，即外層并行計(jì)算。

在各處理機(jī)中，計(jì)算各單體混沌人工魚(yú)的能量值，將最好的單體混沌人工魚(yú)的狀態(tài)及能量值記錄在公告板上。

單體混沌人工魚(yú)能量值的計(jì)算步驟歸納如下：①準(zhǔn)備好水庫(kù)庫(kù)容特征曲線(xiàn)、下游水位流量關(guān)系曲線(xiàn)；②根據(jù)水庫(kù)庫(kù)容特征曲線(xiàn)，求出各時(shí)段如第t時(shí)段初庫(kù)容值Vnt，其中第(t+1)時(shí)段的初庫(kù)容值Vn(t+1)亦是第t時(shí)段的末庫(kù)容值，之后可以根據(jù)式(6)水量平衡方程計(jì)算得出下泄流量Qnt。第t時(shí)段下游平均水位便可根據(jù)下游水位流量關(guān)系曲線(xiàn)將下泄流量Qnt代入計(jì)算得出；③第n條單體混沌人工魚(yú)在第t時(shí)段對(duì)應(yīng)的凈水頭可由以下公式計(jì)算得出，其中ΔH表示的是水頭損失，見(jiàn)式(12)。④根據(jù)式(2)計(jì)算得出第n條單體混沌人工魚(yú)Xn的能量值F(Xn)。

(12)

(5)初始化參數(shù)j，表示單體混沌人工魚(yú)序號(hào)，其中j為正整數(shù)。對(duì)于第一號(hào)處理機(jī)中單體人工魚(yú)的起始序號(hào)為j=1(j∈[1,[Np/M]])；第二號(hào)處理機(jī)中單體人工魚(yú)的起始序號(hào)為j=[Np/M]+1(j∈[[Np/M]+1,2[Np/M]])；依次類(lèi)推，直至第M號(hào)處理機(jī)中單體人工魚(yú)的起始序號(hào)為j=(M-1)·[Np/M]+1(j∈[(M-1)·[Np/M]+1,Np])。

(6)對(duì)于每條混沌人工魚(yú)的個(gè)體行為及其分量的混沌優(yōu)化搜索都是相互獨(dú)立的，因此混沌人工魚(yú)子群進(jìn)程中的可并行部分可以通過(guò)OpenMP隨機(jī)分配到不同線(xiàn)程上計(jì)算，即可被較均勻地分配到處理機(jī)的多核中，實(shí)現(xiàn)至少有兩個(gè)單體混沌人工魚(yú)同一時(shí)刻進(jìn)行個(gè)體行為及其分量的混沌優(yōu)化搜索的內(nèi)層并行計(jì)算,如圖1、圖2。

每條混沌人工魚(yú)通過(guò)比較自身的能量值選擇符合自身的個(gè)體行為，為尋優(yōu)做準(zhǔn)備。以混沌人工魚(yú)群的平均能量值Fave作為基準(zhǔn)，若單體混沌人工魚(yú)Xj的能量值F(Xj)Fave，則該魚(yú)執(zhí)行追尾行為；若該魚(yú)的聚群行為和追尾行為都不成功，則執(zhí)行覓食行為。行為結(jié)束后，便得到該單體混沌人工魚(yú)Xj的另一個(gè)新?tīng)顟B(tài)，表達(dá)式可記為Xjnext=(znextj1,znextj2,…,znextjT)。

(7)對(duì)單體混沌人工魚(yú)的新?tīng)顟B(tài) ，可以通過(guò)Logistic映射產(chǎn)生混沌隨機(jī)變量，進(jìn)行混沌優(yōu)化搜索。步驟如下：

①t∈[1,T]，由第j條混沌人工魚(yú)在第t時(shí)段的水位znextjt，按式(13)可計(jì)算得到混沌映射的初始變量值，各時(shí)段計(jì)算是相互獨(dú)立的，可由OpenMP組件分配到單機(jī)不同處理器計(jì)算，組成內(nèi)層并行計(jì)算可行條件之一，如圖1。

(13)

②將式(13)的計(jì)算結(jié)果s0，由式(1)計(jì)算出混沌隨機(jī)變量sjt=4s0(1-s0)。之后由式(14)將sjt(區(qū)間為[0,1])轉(zhuǎn)換為混沌隨機(jī)變量s*jt(區(qū)間為[-1,1])。

s*jt=2sjt-1

(14)

③可將式(14)求得的混沌隨機(jī)變量s*jt代入式(15)，計(jì)算得出新的庫(kù)水位z*jt。

z*jt=znextjt+step·s*jt·(Ztmax-Ztmin)

(15)

其中step為搜索步長(zhǎng)，取值范圍通常為0.001～0.1，同時(shí)需要檢查 是否滿(mǎn)足邊界約束條件。

④計(jì)算混沌優(yōu)化搜索后單體混沌人工魚(yú)的能量值F(Xopt)，若F(Xopt)>F(Xj)，則可令zjt=z*jt。

(8)執(zhí)行混沌優(yōu)化搜索后的單體混沌人工魚(yú)Xj的最終狀態(tài)，若優(yōu)于公告板狀態(tài)則取代之，否則保持公告板的狀態(tài)不變。

之后令j=j+1，如果前(M-1)個(gè)處理機(jī)中均滿(mǎn)足j>[Np/M]且第M個(gè)處理機(jī)中滿(mǎn)足j>Np-(M-1)·[Np/M]條件，轉(zhuǎn)到步驟(9)；若其中某個(gè)或多個(gè)處理機(jī)未達(dá)到此條件，則未達(dá)到此條件的處理機(jī)轉(zhuǎn)向步驟(6)，其他已達(dá)條件的處理機(jī)等待。

(9)尋優(yōu)次數(shù)若達(dá)到最大迭代次數(shù)MaxNumber，則輸出最優(yōu)結(jié)果，否則轉(zhuǎn)到步驟(5),開(kāi)始新一輪的混沌人工魚(yú)群并行尋優(yōu)。

基于CAFSPA的水庫(kù)發(fā)電優(yōu)化調(diào)度程序流程，如圖2，多核單機(jī)內(nèi)子群的混沌優(yōu)化搜索模塊可參考圖1。

3 實(shí)例計(jì)算與分析

為更好的比較CAFSPA相對(duì)于黃鋒CAFSA在計(jì)算時(shí)間上的優(yōu)越性，選取文獻(xiàn)[12]中相同水庫(kù)在某年的徑流資料，以相同的目標(biāo)函數(shù)和約束表達(dá)式作為基本條件。在該庫(kù)的中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中，比較分析了在標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法(DP)、COA、AFSA、黃鋒的CAFSA以及本文重點(diǎn)研究的CAFSPA等各算法下對(duì)應(yīng)的發(fā)電量結(jié)果和計(jì)算時(shí)間。其中對(duì)于智能優(yōu)化算法COA、AFSA、CAFSA、CAFSPA，為減小隨機(jī)性對(duì)各算法結(jié)果產(chǎn)生的影響，可以進(jìn)行仿真模擬計(jì)算150次，并將計(jì)算出的最優(yōu)值作為實(shí)例的仿真結(jié)果。

從被選取的資料可知，該實(shí)驗(yàn)水庫(kù)的正常蓄水位庫(kù)容為2.41億m3，有效庫(kù)容為1.35億m3，死庫(kù)容為1.05億m3。該水庫(kù)的保證出力為0.233億W，裝機(jī)容量為2×0.61億W，設(shè)計(jì)年發(fā)電量為5 010億kWh，同時(shí)具有不完全年調(diào)節(jié)作用的性質(zhì)。該水庫(kù)的水頭損失系數(shù)為0.000 086 81，最大水頭損失為5.61 m，出力系數(shù)為8.3。該水庫(kù)的死水位為819 m，正常蓄水位837 m，其中6月-10月汛期水位為820 m。

5種優(yōu)化算法都基于visual studio 2010軟件開(kāi)發(fā)平臺(tái)采用C++語(yǔ)言編程。其中針對(duì)CAFSPA，為了體現(xiàn)其并行處理問(wèn)題的特點(diǎn)，硬件設(shè)備采用兩臺(tái)互聯(lián)的雙核計(jì)算機(jī)，參照上文的算法步驟，將混沌人工魚(yú)群平分于兩臺(tái)計(jì)算機(jī)上進(jìn)行計(jì)算，應(yīng)用MPI組件處理兩臺(tái)計(jì)算機(jī)之間的數(shù)據(jù)傳輸，實(shí)現(xiàn)外層并行計(jì)算；并同時(shí)應(yīng)用OpenMP組件控制單機(jī)中多線(xiàn)程促使雙處理器的工作時(shí)間重疊，實(shí)現(xiàn)內(nèi)層并行計(jì)算。其他算法沒(méi)有進(jìn)行并行設(shè)計(jì)，只需在單機(jī)上運(yùn)行即可。

在CAFSPA中，設(shè)定整個(gè)算法的最大迭代次數(shù)MaxNumber=50，混沌人工魚(yú)群的規(guī)模,Np=50，單體混沌人工魚(yú)的視野范圍Visual=5.0，擁擠度因子δ=0.618，移動(dòng)步長(zhǎng)step=1.0，搜索步長(zhǎng)α=0.01，最大嘗試次數(shù)TryNumber=5。為了便于數(shù)據(jù)的可靠性比較，COA、AFSA、CAFSA的最大迭代次數(shù)也定為MaxNumber=50(圖3源自黃鋒[12]的研究,由此可知3種智能算法迭代次數(shù)為35以上時(shí)，最優(yōu)值基本趨于穩(wěn)定狀態(tài))，并且基本AFSA、CAFSA其他參數(shù)設(shè)定與CAFSPA一致。5種算法最優(yōu)發(fā)電量和運(yùn)算時(shí)間值，見(jiàn)表1。

圖1 被分配混沌人工魚(yú)子群在多核單機(jī)中的內(nèi)層并行計(jì)算模塊原理圖

圖2 水庫(kù)發(fā)電優(yōu)化調(diào)度CAFSPA整體程序流程圖

由表1結(jié)果可知，CAFSA與CAFSPA的最優(yōu)發(fā)電量的計(jì)算結(jié)果基本一致，因?yàn)镃AFSPA是在CAFSA的基礎(chǔ)上增加了雙層并行計(jì)算處理，實(shí)現(xiàn)各子任務(wù)在計(jì)算時(shí)間上的重疊，數(shù)據(jù)運(yùn)算方式是一致的，如圖3。在運(yùn)算時(shí)間上CAFSPA接近于CAFSA算法的1/4，因?yàn)閮膳_(tái)雙核計(jì)算機(jī)，通過(guò)雙層并行計(jì)算，把混沌人工魚(yú)群的計(jì)算平均分到4個(gè)處理器，在同一時(shí)刻進(jìn)行工作，充分利用了閑置資源，實(shí)現(xiàn)各子任務(wù)處理時(shí)間的重疊。CAFSPA保持了CAFSA的尋優(yōu)質(zhì)量上的優(yōu)勢(shì)，與單一的COA和AFSA相比，最優(yōu)發(fā)電量分別提升了1 102.67、1 939.65 萬(wàn)kWh。CAFSA的計(jì)算時(shí)間比AFSA略多0.1 s，是因?yàn)閷?duì)單體人工魚(yú)多了混沌優(yōu)化搜索的計(jì)算時(shí)間，然而經(jīng)過(guò)雙層并行計(jì)算后，運(yùn)算時(shí)間明顯減少。CAFSPA的最優(yōu)發(fā)電量比標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃算法(DP)少了75.89萬(wàn)kWh，但縮小幅度僅為0.158%，計(jì)算時(shí)間卻是DP的8%?？梢?jiàn)，本文研究的CAFSPA在收斂速度、尋優(yōu)質(zhì)量以及運(yùn)算時(shí)間等綜合因素上與其他算法相比都占了很大的優(yōu)勢(shì)，尤其是在減少運(yùn)算時(shí)間上優(yōu)勢(shì)更為突出。各算法的計(jì)算結(jié)果對(duì)比充分驗(yàn)證了CAFSPA應(yīng)用于水庫(kù)中長(zhǎng)期發(fā)電優(yōu)化調(diào)度中的可行性和高效性。

表1 各算法的最優(yōu)結(jié)果比較

圖3 各算法尋優(yōu)過(guò)程比較圖

除DP外各智能算法150次仿真模擬計(jì)算的發(fā)電量與運(yùn)算時(shí)間平均值如表2所示。

表2 各智能算法150次仿真模擬計(jì)算發(fā)電量與運(yùn)算時(shí)間平均值比較

由表2中數(shù)據(jù)可知，CAFSPA與CAFSA的150次發(fā)電量平均值基本一致，而CAFSPA的平均運(yùn)算時(shí)間接近CAFSA的1/4；這兩種算法的150次發(fā)電量平均值都高于AFSA和COA；4種算法的150次發(fā)電量平均值比表1中對(duì)應(yīng)的發(fā)電量最優(yōu)值分別減少了0.88%、0.89%、3.91%、1.18%，其中CAFSPA的發(fā)電量平均值是表1中DP發(fā)電量最優(yōu)值的98.96%。為進(jìn)一步驗(yàn)證CAFSPA的穩(wěn)定性，分別將CAFSPA、CAFSA、AFSA、COA的150次仿真模擬計(jì)算結(jié)果存儲(chǔ)在計(jì)算機(jī)中，對(duì)各算法對(duì)應(yīng)發(fā)電量進(jìn)行方差分析，經(jīng)計(jì)算，對(duì)應(yīng)的各方差比值是0.582 633 4∶0.595 950 6∶10.591 044 4∶1。從中可以發(fā)現(xiàn)CAFSPA與CAFSA的150次發(fā)電量求解穩(wěn)定性基本一致，比COA的穩(wěn)定性略強(qiáng)，但都比AFSA的穩(wěn)定性強(qiáng)許多。由此可見(jiàn)在算法穩(wěn)定性上CAFSPA與CAFSA的優(yōu)越所在。

通過(guò)以上分析可以得出結(jié)論如下3點(diǎn)：①CAFSPA繼承了CAFSA，充分結(jié)合了AFSA操作簡(jiǎn)單的特點(diǎn)以及COA的全局搜索能力，提高了該水庫(kù)發(fā)電量尋優(yōu)計(jì)算的穩(wěn)定性、搜索精度以及結(jié)果質(zhì)量，達(dá)到了預(yù)期效果；②CAFSPA與CAFSA一致，充分融合了COA遍歷性特點(diǎn)，提高了計(jì)算后期的搜索效率，有效解決了AFSA后期搜索的盲目性以及計(jì)算的停滯，避免AFSA陷入求得局部最優(yōu)值的困境；③CAFSPA充分利用AFSA中單體人工魚(yú)尋優(yōu)并行化的特點(diǎn)，將人工魚(yú)群分成多個(gè)子群，并均分到不同的處理單元進(jìn)行并行計(jì)算，以及個(gè)體人工魚(yú)行為分量混沌優(yōu)化搜索的并行化處理，充分利用閑置資源，實(shí)現(xiàn)子群計(jì)算時(shí)間的重疊，相對(duì)較大幅度減少了運(yùn)行時(shí)間。

4 結(jié) 語(yǔ)

單一的人工魚(yú)群算法易于實(shí)現(xiàn)，對(duì)各種參數(shù)的選擇不太敏感，是水庫(kù)發(fā)電優(yōu)化調(diào)度中應(yīng)用較廣的智能算法之一[19]。CAFSA有效控制易陷入求得局部最優(yōu)解的局面，黃鋒[12]通過(guò)實(shí)驗(yàn)證明了該算法在求解質(zhì)量和精度上的顯著提高。在此基礎(chǔ)上，根據(jù)人工魚(yú)群并行運(yùn)動(dòng)的特點(diǎn)以及行為分量混沌優(yōu)化搜索的并行性，結(jié)合雙層并行計(jì)算架構(gòu)設(shè)計(jì)，在運(yùn)算時(shí)間上的減少也是卓有成效的。本文研究的主要目的是基于水庫(kù)中長(zhǎng)期發(fā)電優(yōu)化調(diào)度，研究如何有效并行化改進(jìn)CAFSA，能夠充分利用閑置硬件資源，在較短運(yùn)算時(shí)間內(nèi)可求得較滿(mǎn)意的近似最優(yōu)解，從而提高水庫(kù)發(fā)電效益，通過(guò)實(shí)例證明改進(jìn)后的CAFSPA具有一定的實(shí)用性，在實(shí)際生產(chǎn)過(guò)程中，具有一定的參考性。梯級(jí)水庫(kù)群發(fā)電優(yōu)化調(diào)度計(jì)算更為復(fù)雜、維度更高、計(jì)算時(shí)間大幅度增加[20]，如何有效利用CAFSPA解決梯級(jí)水庫(kù)群的問(wèn)題是之后重點(diǎn)科研方向。

□

[1] 鄒 進(jìn),劉可真. 水資源系統(tǒng)運(yùn)行與優(yōu)化調(diào)度[M].北京：冶金工業(yè)出版社，2006:13-14.

[2] Nandalal K D W,Bogardi,Janos J. Dynamic Programming Based Operation of Reservoirs: Applicability and Limits[M]. New York:Cambridge University Press,2007:4-18.

[3] 馬立亞,雷曉輝,蔣云中.基于DPSA的梯級(jí)水庫(kù)群優(yōu)化調(diào)度[J].中國(guó)水利水電科學(xué)研究院學(xué)報(bào),2012,10(2):140-144.

[4] 劉 新,紀(jì)昌明,楊子俊,等.基于逐步優(yōu)化算法的梯級(jí)水電站中長(zhǎng)期優(yōu)化調(diào)度[J].人民長(zhǎng)江,2010,40(21):32-34.

[5] 張忠波,張雙虎,蔣云鐘,等.改進(jìn)的遺傳算法在水庫(kù)調(diào)度中的應(yīng)用[J].人民黃河,2012,34(8):54-56.

[6] 宋朝紅,羅 強(qiáng),紀(jì)昌明.基于混合蟻群算法的水庫(kù)群優(yōu)化調(diào)度研究[J].武漢大學(xué)學(xué)報(bào),2003,36(4):28-31.

[7] 向 波,紀(jì)昌明,羅慶松.免疫粒子群算法及其在水庫(kù)優(yōu)化調(diào)度中的應(yīng)用[J].河海大學(xué)學(xué)報(bào),2008,36(2):198-201.

[8] 馮玉蓉.模擬退火算法的研究及其應(yīng)用[D].昆明：昆明理工大學(xué)，2005.

[9] 田景文,高美娟. 人工神經(jīng)網(wǎng)絡(luò)算法研究及應(yīng)用[M].北京：北京理工大學(xué)出版社，2006:45-61.

[10] 李曉磊.一種新型智能優(yōu)化算法-人工魚(yú)群算法[D].杭州：浙江大學(xué)，2003.

[11] 邱 琳,田景環(huán),段春青,等.混沌優(yōu)化算法在水庫(kù)優(yōu)化調(diào)度中的應(yīng)用[J].中國(guó)農(nóng)村水利水電,2005,(7):17-20.

[12] 黃 鋒，王麗萍，向騰飛，等. 基于混沌人工魚(yú)群算法的水庫(kù)發(fā)電優(yōu)化調(diào)度研究[J].中國(guó)農(nóng)村水利水電，2014,(10):149-153.

[13] 陳國(guó)良，孫廣中，徐 云，等.并行算法研究方法學(xué)[J],計(jì)算機(jī)學(xué)報(bào)，2008,31(9):1 493-1 501.

[14] 張志新,張明廉.基于并行混沌和單純形法的混合全局優(yōu)化算法[J].系統(tǒng)仿真學(xué)報(bào),2004,16(1):35-37.

[15] 白小勇,王晨華,李允軍,等.人工魚(yú)群算法與離散微分動(dòng)態(tài)規(guī)劃結(jié)合在水庫(kù)優(yōu)化調(diào)度中的應(yīng)用[J].水電廠(chǎng)自動(dòng)化,2008,29(3):135-138.

[16] 原文林,曲曉寧.混沌蟻群優(yōu)化算法在梯級(jí)水庫(kù)發(fā)電優(yōu)化調(diào)度中的應(yīng)用研究[J].水力發(fā)電學(xué)報(bào),2013,32(3):47-53.

[17] 王 堃. 基于多核的并行程序設(shè)計(jì)及優(yōu)化[D]. 南京：南京大學(xué)，2012.

[18] 曲良東,何登旭.一種混沌人工魚(yú)群算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(22):40-42.

[19] 王正初,周幕遜,李 軍,等.基于人工魚(yú)群算法的水庫(kù)優(yōu)化調(diào)度研究[J].繼電器,2007,35(21):43-46.

[20] 吳 昊，紀(jì)昌明，蔣志強(qiáng)，等. 梯級(jí)水庫(kù)群發(fā)電優(yōu)化調(diào)度的大系統(tǒng)分解協(xié)調(diào)模型[J]. 水力發(fā)電學(xué)報(bào)，2015,34(11):40-50.