鐘育彬, 鄧文杰

(廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 廣東 廣州 510006)

在目標(biāo)約束函數(shù)尋優(yōu)領(lǐng)域中，目前已經(jīng)有多種尋優(yōu)算法，如魚群算法、蟻群算法、粒子群算法和遺傳算法等.其中,遺傳算法是最為“萬金油”的尋優(yōu)算法，只要從問題中歸納出目標(biāo)函數(shù)與約束條件，便能進(jìn)行運(yùn)算得出結(jié)果.但針對復(fù)雜適應(yīng)度函數(shù)的運(yùn)算速率往往引人詬病[1].遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇“物競天擇，適者生存”，以染色體為媒介，通過交叉、變異產(chǎn)生新個體，然后不斷選擇優(yōu)良個體的尋優(yōu)算法[2].它最初由Holland[3]于1975年首先提出.經(jīng)過多年的發(fā)展，遺傳算法已十分成熟.

本文為在改進(jìn)交叉選擇的前提下，保證遺傳算法盡可能不陷入局部最優(yōu)的情況而選擇綜合多種群遺傳算法.相對于普通遺傳算法，多種群遺傳算法[4]首先將多個個體放于若干遺傳種群中，各種群通過不同的控制參數(shù)調(diào)節(jié)，由各移民算子進(jìn)行聯(lián)系，然后比較每代各種群的最優(yōu)解而獲得當(dāng)代最優(yōu)染色體，實(shí)現(xiàn)了多個種群共存進(jìn)化的效果，從而有效避免了遺傳算法的運(yùn)算陷入局部最優(yōu).

1 針對復(fù)雜適應(yīng)度函數(shù)遺傳算法存在的問題

普通適應(yīng)度函數(shù)是指遺傳機(jī)理框架中僅需放入目標(biāo)函數(shù)與約束條件的適應(yīng)度函數(shù).無論在算法效率或者結(jié)果，遺傳算法應(yīng)用在普通適應(yīng)度函數(shù)上都有滿意的效果.

復(fù)雜適應(yīng)度函數(shù)是指實(shí)際任務(wù)所需要求得的某些未知數(shù)xi,不直接呈現(xiàn)于目標(biāo)函數(shù)，而對未知數(shù)進(jìn)行數(shù)據(jù)量較大的若干計算、判斷，甚至進(jìn)行內(nèi)含計算算子運(yùn)算等操作，最終反作用于目標(biāo)函數(shù).在需要尋優(yōu)的日常生活問題或數(shù)學(xué)建模競賽中，這類復(fù)雜適應(yīng)度函數(shù)出現(xiàn)頻率不低.在2016年的廣東省金融數(shù)學(xué)建模競賽中，要用遺傳算法獲得金融K值，就要對所需求得的未知數(shù)xi進(jìn)行極大的數(shù)據(jù)運(yùn)算，方能放入目標(biāo)函數(shù)中求值.

假設(shè)遺傳代數(shù)為n，交叉產(chǎn)生新個體的數(shù)目為p，運(yùn)算單次復(fù)雜適應(yīng)度函數(shù)的時間花費(fèi)為t，遺傳算法完成所需的時間T.每進(jìn)行一次遺傳機(jī)理框架的計算需要進(jìn)行p次的適應(yīng)度函數(shù)計算，總需執(zhí)行n代,則

T=n·p·t.

設(shè)運(yùn)行一次復(fù)雜適應(yīng)度函數(shù)所需時間為1 s，一般設(shè)置遺傳100代，每代生成200個體.則需要333.3 min運(yùn)算出結(jié)果.某些復(fù)雜適應(yīng)度函數(shù)計算所需時間大于1 s，需計算機(jī)長時間運(yùn)算.

為盡快提高遺傳算法的收斂速度且保證算法不陷入局部最優(yōu)，本文提出針對復(fù)雜適應(yīng)度函數(shù)的因素遺傳算法.

2 基于復(fù)雜適應(yīng)度函數(shù)的因素遺傳算法

遺傳算法的進(jìn)化究其根本在于染色體進(jìn)化，染色體的進(jìn)化在其編碼長度與對應(yīng)位置的數(shù)值進(jìn)化，亦是交叉變異的內(nèi)涵[5].由于二進(jìn)制編碼中每一代對應(yīng)位置的數(shù)值在0,1間變化，則染色體編碼位置構(gòu)造對染色體進(jìn)化起著決定性作用.因素空間理論中成熟的模糊評價體系[6-7]能更有效地提取遺傳性更強(qiáng)個體.本文根據(jù)遺傳算法進(jìn)化本質(zhì)提出因素遺傳算法

定義1 (相似數(shù))設(shè)遺傳算法的兩個編碼集為{A1,A2,…An}，{B1,B2,…Bn},則其對應(yīng)位置的相似數(shù)記為

ci=|Ai-Bi| (i=1,2…n).

定義2 (相似度)因?yàn)檫z傳編碼多樣，需要對相似集進(jìn)行歸一化處理，其相似度記為

定義3(貼近度)下文方法需要設(shè)計遺傳性質(zhì)更優(yōu)的染色體，其內(nèi)含位置及染色體長度不僅要盡可能地與最優(yōu)適應(yīng)度最相似，且與最差染色體最不相似，則定義其貼近度為

步驟1編碼

編碼的方式有二進(jìn)制編碼、格雷碼法、符號編碼法等.復(fù)雜適應(yīng)度函數(shù)一般具有其復(fù)雜問題背景.符號編碼法符合有意義積木塊編碼原則，適合解決針對性問題且容易與其他相關(guān)算法混合使用.故本文以符號編碼法為例，建立代碼符號集{A,B,C…}.二進(jìn)制編碼法只需進(jìn)行位置劃分同樣可達(dá)本文效果[8].

步驟2選擇

確定符號集為因素集{A1,A2,…Ai}，設(shè)預(yù)選比較進(jìn)化參數(shù)為j，用以下方法選擇最大適應(yīng)度染色體X.

其中，X為最大適應(yīng)度染色體，f為當(dāng)代進(jìn)入遺傳機(jī)理框架運(yùn)算的染色體，n為當(dāng)代進(jìn)入遺傳機(jī)理框架運(yùn)算的染色體個數(shù).

同理，取最小適應(yīng)度染色體與適應(yīng)度排名前j個的染色體，對選中染色體進(jìn)行貼近度計算，獲得貼近度度矩陣R.

最后，根據(jù)最大隸屬度原則[9]，構(gòu)建每個劃分位置最優(yōu)的最佳遺傳性質(zhì)染色體Q.

步驟3交叉

遺傳算法適用交叉算子有pmx、pbx、obx、cxo等，針對不同的問題背景可自行選擇合適的交叉算子.遺傳機(jī)理進(jìn)入交叉過程時，將適應(yīng)度最優(yōu)染色體X與最佳遺傳性質(zhì)染色體Q代入.

步驟4變異

亦然，將適應(yīng)度最優(yōu)染色體X與染色體Q代入變異過程，設(shè)定變異概率產(chǎn)生新個體[10].

步驟5循環(huán)迭代

重復(fù)進(jìn)行步驟2-4，直到遺傳代數(shù)達(dá)到預(yù)設(shè)代數(shù)后，算法終止.

3 算法時間復(fù)雜度分析

對一個當(dāng)代預(yù)選比較進(jìn)化參數(shù)為m，染色編碼長度劃分為n的因素遺傳算法，分別計算m個染色體與當(dāng)代最優(yōu)、最差染色體的相似數(shù)計算量為2mn.作m次歸一化處理，求貼近度計算量為m.再作nm次比較獲得全新染色體.故本文改進(jìn)點(diǎn)的計算量為

T=3mn+2m.

本文加入的算法時間復(fù)雜度為o(n2)，即相對普通MPGA,其適應(yīng)度函數(shù)內(nèi)除標(biāo)準(zhǔn)目標(biāo)函數(shù)與約束條件框架外，還有計算量大于上式的程序操作，可選用本文方法進(jìn)行操作.

4 實(shí)例分析

本文以基于混合堆疊模型的廣告轉(zhuǎn)化率預(yù)測[11]為例.數(shù)據(jù)來源為2018年天池算法競賽“阿里媽媽搜索廣告轉(zhuǎn)化預(yù)測”.由于原始數(shù)據(jù)特征偏少、稠密且復(fù)雜，LightBGM和XGBoost的預(yù)測效果遠(yuǎn)優(yōu)于其他預(yù)測模型，且對數(shù)損失(Logloss)值低于wide_deep 和 wide_cross 神經(jīng)網(wǎng)絡(luò)模型.混合融合模型的思想是混合與堆疊.LightBGM堆疊XGBoost是指將部分?jǐn)?shù)據(jù)放入LightBGM訓(xùn)練得到新的特征組放入原始數(shù)列放入到XGBoost進(jìn)行預(yù)測，混合是指不同預(yù)測模型所得到的結(jié)果加權(quán)平均處理，該權(quán)重的選取會對最終預(yù)測結(jié)果產(chǎn)生直接影響.尋優(yōu)思想解決權(quán)重選取問題，以對數(shù)損失最少作目標(biāo)函數(shù)，建立尋優(yōu)模型如下：

其中，N為樣本總數(shù)，yi是0，1變量，表示第i個樣本的label,pi為模型預(yù)測第i個樣本label為1的概率，xi為混合模型權(quán)重取值,Q為混合模型，modle1為LightBGM，modle2為XGBoost堆疊LightBGM，modle3為LightBGM堆疊XGBoost.

固定LightBGM和XGBoost的參數(shù)設(shè)置，比較多種群遺傳算法與基于因素空間的多種群遺傳算法.由于本文著重比較權(quán)重選取尋優(yōu)算法，故只提出部分參數(shù)取值，其他未提及的參數(shù)皆取默認(rèn)值.其中，兩個樹模型的部分參數(shù)選取見表1及表2.

表1 XGBoost參數(shù)取值表Table 1 Paramet value of XGBoost

表2 LightBGM參數(shù)取值表Table 2 Paramet value of LightBGM

固定樹參數(shù)值，分別用針對復(fù)雜目標(biāo)函數(shù)的因素遺傳算法與多種群遺傳算法對該目標(biāo)函數(shù)尋優(yōu).參數(shù)設(shè)置：初始種群100，變異概率于0.001～0.050隨機(jī)產(chǎn)生，交叉概率于0.7～0.9隨機(jī)產(chǎn)生，遺傳代數(shù)為80，算法運(yùn)算次數(shù)為30，取各次遺傳中每代染色體均值，結(jié)果見圖1及表3.

圖1 算法結(jié)果對比Fig.1 The comparison of algoritlm

表3 算法效果對比表Table 3 The comparison of algorithm effect

由圖1,表3可知，因素遺傳算法在保證得出最優(yōu)解的同時能更快地達(dá)到最優(yōu)代數(shù)，到達(dá)最優(yōu)代數(shù)成功減少了8代，到達(dá)最優(yōu)代數(shù)時間減少將近16 min,達(dá)到降低遺傳代數(shù)，加速遺傳的效果.

5 結(jié) 論

(1)本文提出因素遺傳算法以因素空間為媒介引入最佳遺傳個體，深究遺傳進(jìn)化本質(zhì)對最佳遺傳個體進(jìn)行模糊綜合評價；結(jié)合多種群遺傳算法，避免遺傳陷入局部最優(yōu)且減少達(dá)到最優(yōu)時所需代數(shù)；減少適應(yīng)度函數(shù)運(yùn)算次數(shù)，快速達(dá)到進(jìn)化最優(yōu).

(2)普通適應(yīng)度函數(shù)在遺傳算法尋優(yōu)時間不長，因此，無需使用此方法.本文方法僅針對復(fù)雜適應(yīng)度函數(shù).

(3)本文加入算法的時間復(fù)雜度不高，適用于大部分復(fù)雜適應(yīng)度函數(shù).