鐘育彬, 鄧文杰

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

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

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

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

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

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

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

T=n·p·t.

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

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

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

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

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

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

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

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

步驟1編碼

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

步驟2選擇

確定符號(hào)集為因素集{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)算的染色體個(gè)數(shù).

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

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

步驟3交叉

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

步驟4變異

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

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

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

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

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

T=3mn+2m.

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

4 實(shí)例分析

本文以基于混合堆疊模型的廣告轉(zhuǎn)化率預(yù)測(cè)[11]為例.數(shù)據(jù)來(lái)源為2018年天池算法競(jìng)賽“阿里媽媽搜索廣告轉(zhuǎn)化預(yù)測(cè)”.由于原始數(shù)據(jù)特征偏少、稠密且復(fù)雜，LightBGM和XGBoost的預(yù)測(cè)效果遠(yuǎn)優(yōu)于其他預(yù)測(cè)模型，且對(duì)數(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ù)測(cè)，混合是指不同預(yù)測(cè)模型所得到的結(jié)果加權(quán)平均處理，該權(quán)重的選取會(huì)對(duì)最終預(yù)測(cè)結(jié)果產(chǎn)生直接影響.尋優(yōu)思想解決權(quán)重選取問(wèn)題，以對(duì)數(shù)損失最少作目標(biāo)函數(shù)，建立尋優(yōu)模型如下：

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

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

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

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

固定樹參數(shù)值，分別用針對(duì)復(fù)雜目標(biāo)函數(shù)的因素遺傳算法與多種群遺傳算法對(duì)該目標(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é)果對(duì)比Fig.1 The comparison of algoritlm

表3 算法效果對(duì)比表Table 3 The comparison of algorithm effect

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

5 結(jié) 論

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

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

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