遺傳算法在用戶感知評估建模中的應(yīng)用

摘要：在建立用戶感知評估變量結(jié)構(gòu)模型的基礎(chǔ)上，利用遺傳算法對KQI-QoE關(guān)系進(jìn)行動態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對比。實(shí)際用戶感知和評估體系的擬合結(jié)果表明，遺傳算法在用戶感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力。這為進(jìn)一步研究和完善用戶感知評估體系提供了新的方法和途徑。

關(guān)鍵詞：移動；數(shù)據(jù)業(yè)務(wù)；用戶感知；評估建模；遺傳算法

隨著通信技術(shù)的發(fā)展，移動通信網(wǎng)絡(luò)可以為用戶提供越來越豐富的移動業(yè)務(wù)和應(yīng)用，如彩信、網(wǎng)頁瀏覽、WAP、流媒體、網(wǎng)絡(luò)游戲等，這些業(yè)務(wù)為移動運(yùn)營商提供了持續(xù)增長的收入來源。因此，如何評估和提升移動通信業(yè)務(wù)的用戶體驗(yàn)質(zhì)量（即用戶感知），成為全球各大運(yùn)營商關(guān)注和研究的重點(diǎn)，同時也是運(yùn)營商在激烈的市場競爭中吸引用戶、保持和擴(kuò)大盈利的關(guān)鍵。

目前，評估用戶感知通常有兩種方法：一種是通過用戶調(diào)查獲取用戶的實(shí)際體驗(yàn)質(zhì)量；另一種則是通過測量用戶所應(yīng)用業(yè)務(wù)的性能，即關(guān)鍵業(yè)務(wù)質(zhì)量指標(biāo)（KQI），推算出用戶的實(shí)際體驗(yàn)質(zhì)量。兩種方法各有利弊。通過用戶調(diào)查獲取用戶感知，優(yōu)點(diǎn)是可以得到實(shí)際的用戶感知；缺點(diǎn)是無法實(shí)現(xiàn)實(shí)時監(jiān)控，滯后性較大，并且每次用戶調(diào)查都將耗費(fèi)較大的人力、物力和時間。通過KQI推算用戶感知，只需在建模期間提供用戶調(diào)查得到的實(shí)際用戶感知數(shù)據(jù)，然后利用該數(shù)據(jù)和相應(yīng)的KQI指標(biāo)建立KQI-QoE數(shù)量關(guān)系模型，即可形成一套穩(wěn)定的實(shí)時監(jiān)測系統(tǒng)。建成之后，無須再進(jìn)行用戶調(diào)查，操作維護(hù)簡單，效費(fèi)比高；其缺點(diǎn)是KQI-QoE模型的不合理性將對推算出的用戶感知造成誤差。如果能夠構(gòu)建出合理的KQI-QoE數(shù)量關(guān)系模型，顯然采用第2種方法更具吸引力。因此，文章重點(diǎn)研究了KQI-QoE數(shù)量關(guān)系模型的構(gòu)建方法。

常用的回歸分析模型包括：線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對數(shù)回歸方程。當(dāng)待擬合數(shù)據(jù)具備其中某一種模型的特性關(guān)系時，采用相應(yīng)的模型方程進(jìn)行曲線擬合，則可以得到良好的趨勢曲線，誤差也較小。但是，對于KQI-QoE這類未知特性的數(shù)據(jù)，如果利用以上固定的模型方程進(jìn)行曲線擬合，則很可能無法得到準(zhǔn)確的趨勢曲線，而且誤差可能也較大[1-3]。

遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，在一定的解空間中搜索最優(yōu)結(jié)果的算法，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，也是進(jìn)化計(jì)算的一種最重要的形式。若采用遺傳算法，則無需給出特定回歸模型方程，可進(jìn)行自適應(yīng)擬合，因而適用于對未知關(guān)系特性的數(shù)據(jù)模型擬合。

1 用戶感知評估相關(guān)的

基本概念

在移動通信業(yè)務(wù)應(yīng)用領(lǐng)域，用戶感知評估就是獲得用戶對某種業(yè)務(wù)的應(yīng)用感受情況，它涉及兩個基本概念：一個是用戶感知，另一個是KQI。

一般情況下，我們所說的“用戶感知”指的是用戶或客戶的體驗(yàn)質(zhì)量（QoE），也就是用戶實(shí)際感受到的服務(wù)網(wǎng)絡(luò)和業(yè)務(wù)的服務(wù)質(zhì)量（QoS）。例如，用戶感受到的語音或圖像的清晰程度、文件收發(fā)的快慢等。

而用戶對某一特定業(yè)務(wù)的質(zhì)量的感受又是多方面或多個類別的，例如，對于語音電話業(yè)務(wù)，用戶的感受主要有4個方面：

·電話是否能接通，即撥號后是否能聽到回鈴聲。

·電話接通所需要等待的時間長短。

·電話接通后是否會異常斷線，也就是掉話。

·打電話期間的語音質(zhì)量如何，如語音是否清晰、是否會斷斷續(xù)續(xù)、是否存在較大的通話時延等。

因此，QoE指標(biāo)分為子項(xiàng)感知度和整體感知度，子項(xiàng)感知度與用戶對業(yè)務(wù)某一方面的應(yīng)用感受相一致；整體感知度是用戶對某一業(yè)務(wù)應(yīng)用的綜合體驗(yàn)質(zhì)量，是該業(yè)務(wù)對應(yīng)的所有子項(xiàng)感知度的綜合反映。

KQI就是服務(wù)提供商實(shí)際提供的QoS，可通過測量或統(tǒng)計(jì)得到，它反映了業(yè)務(wù)或應(yīng)用的端到端性能。一個或一組KQI指標(biāo)能夠直接地表征業(yè)務(wù)某一方面的性能，如時延特性、網(wǎng)頁瀏覽流暢度等[4]。

2 用戶感知評估變量結(jié)構(gòu)

模型

用戶感知評估變量結(jié)構(gòu)模型定義了用戶感知評估涉及哪些結(jié)構(gòu)變量，以及這些變量之間的邏輯關(guān)系。這是構(gòu)建數(shù)學(xué)描述模型的基礎(chǔ)。

用戶感知的評估是針對某一種業(yè)務(wù)進(jìn)行的。由第1節(jié)中所舉語音電話例子，可以看出，對于任一種業(yè)務(wù)，均可根據(jù)用戶的感受，劃分為多個類別的性能。一個類別的性能既對應(yīng)了一個子項(xiàng)感知度指標(biāo)，又對應(yīng)了一個或一組KQI指標(biāo)。業(yè)務(wù)的端到端性能指標(biāo)將影響相應(yīng)類別的用戶感知（即子項(xiàng)感知度），而用戶對該業(yè)務(wù)的整體感知則受各種類別的用戶感知綜合影響。

基于上述分析，我們建立了如圖1所示的用戶感知評估變量結(jié)構(gòu)模型，變量的影響關(guān)系是自下而上的，具體表現(xiàn)為：

·一個類別的端到端業(yè)務(wù)性能對應(yīng)了一個子項(xiàng)感知度指標(biāo)和一組KQI指標(biāo)。

·KQI指標(biāo)的好壞直接影響了相應(yīng)子項(xiàng)感知度的好壞。

·子項(xiàng)感知度的好壞直接影響了整體感知度的好壞。

因此，從用戶感知評估的角度，模型的輸入變量是待評估業(yè)務(wù)的KQI指標(biāo)，輸出變量是該業(yè)務(wù)的子項(xiàng)感知度和整體感知度。

下面我們將根據(jù)這個結(jié)構(gòu)模型，運(yùn)用遺傳算法建立確定性的KQI-QoE數(shù)量關(guān)系模型。

3遺傳算法應(yīng)用設(shè)計(jì)

采用遺傳算法進(jìn)行自適應(yīng)曲線擬合，是從問題的解空間中一個隨機(jī)產(chǎn)生的種群開始進(jìn)化的。這個種群則由一定數(shù)目的函數(shù)表達(dá)式組成，每一個函數(shù)表達(dá)式則代表著一個個體，同時也有可能是我們所想得到的具體數(shù)學(xué)模型[5]。

個體也就是染色體，它由一定數(shù)目的基因組成，基因的不同和組合方式的不同則決定了個體的特性。因此，使用遺傳算法，首先需要實(shí)現(xiàn)將函數(shù)表達(dá)式從表現(xiàn)型到基因型的映射，也就是編碼。

3.1 編碼方式

常用的編碼方式有二進(jìn)制編碼、二叉樹編碼、實(shí)數(shù)編碼等，對于函數(shù)擬合問題，最常用的編碼方式是二叉樹編碼，即把組成群體的所有個體采用一種動態(tài)的樹狀結(jié)構(gòu)來表示。圖2是一個二叉樹的示例，它表示了函數(shù)f（x， y， z）=（y ^ 6）*ln（x）+exp（z）。

這棵樹的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個節(jié)點(diǎn)就是一個基因。

根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個體二叉樹組成的種群。

（2）對種群個體的相關(guān)適應(yīng)度進(jìn)行評估。

（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個體。

（4）對選取的二叉樹個體進(jìn)行雜交操作。

（5）對種群中的個體進(jìn)行相關(guān)變異操作。

（6）種群更新，即將完成雜交和變異后的子代個體替代父代種群中適應(yīng)度低的個體。

3.3 種群初始化

解空間由預(yù)測模型涉及的運(yùn)算符集、自變量符號集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類函數(shù)運(yùn)算符；自變量符號集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。

解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節(jié)點(diǎn)進(jìn)行填充：

·對于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個函數(shù)符號填充。

·對于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號集中隨機(jī)選擇一個自變量填充。

·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個常數(shù)填充。

3.4 個體適應(yīng)度評估

種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個體的適應(yīng)度函數(shù)。對于某一個體，其計(jì)算公式如下：

其中，N表示樣本數(shù)；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數(shù)表達(dá)式；

3.6 雜交算子

對選擇復(fù)制出來的個體進(jìn)行雜交。雜交的規(guī)則如下：

·對父代個體進(jìn)行兩兩隨機(jī)配對，形成雜交配對池；每一對父體均在一定概率條件下進(jìn)行雜交。

·對于雜交的兩個父代個體，各自分別隨機(jī)選擇一棵子樹，然后交換子樹，得到相應(yīng)的子代個體。

·對于根深大于最大樹根深度限值的子代，則把超過部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。

3.7 變異算子

父代個體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：

·對需要變異的個體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個作為變異分界節(jié)點(diǎn)，對該節(jié)點(diǎn)及其所有分支進(jìn)行變異。

·對于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。

·對于終結(jié)點(diǎn)，則在自變量符號集或數(shù)據(jù)集中隨機(jī)選擇一個進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。

3.8 種群更新

種群更新就是將父代個體中適應(yīng)度最差的若干個體用變異后產(chǎn)生的子代個體進(jìn)行替代。

為了保證每一代中的最好個體都能保留到下一代中，則直接將最好個體替代父代中的最差個體。

3.9 終止條件

終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿足條件即終止：

·達(dá)到繁殖最大次數(shù)。

·達(dá)到算法程序運(yùn)行的最大時長。

·種群中最優(yōu)個體的殘差平方和小于或等于某一給定值。

4建模結(jié)果分析

文章根據(jù)中國某市的網(wǎng)頁瀏覽業(yè)務(wù)實(shí)際用戶調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對這些模型的殘差平方和進(jìn)行了對比分析[7]。

建模目標(biāo)為：建立網(wǎng)頁打開成功率滿意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁打開成功率滿意指數(shù)對應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁打開成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。

遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號集X={x}，數(shù)據(jù)集c={-10

如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對比，相應(yīng)的曲線對比則如圖4所示。

由上述對比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。

此外，一般對于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過增加繁衍次數(shù)仍有較大的提升空間。

5結(jié)束語

文章在建立用戶感知評估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對QoE-KQI數(shù)量關(guān)系進(jìn)行了動態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶感知評估體系，從而運(yùn)營商提升用戶感知管理水平。

這棵樹的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個節(jié)點(diǎn)就是一個基因。

根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個體二叉樹組成的種群。

（2）對種群個體的相關(guān)適應(yīng)度進(jìn)行評估。

（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個體。

（4）對選取的二叉樹個體進(jìn)行雜交操作。

（5）對種群中的個體進(jìn)行相關(guān)變異操作。

（6）種群更新，即將完成雜交和變異后的子代個體替代父代種群中適應(yīng)度低的個體。

3.3 種群初始化

解空間由預(yù)測模型涉及的運(yùn)算符集、自變量符號集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類函數(shù)運(yùn)算符；自變量符號集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。

解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節(jié)點(diǎn)進(jìn)行填充：

·對于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個函數(shù)符號填充。

·對于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號集中隨機(jī)選擇一個自變量填充。

·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個常數(shù)填充。

3.4 個體適應(yīng)度評估

種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個體的適應(yīng)度函數(shù)。對于某一個體，其計(jì)算公式如下：

其中，N表示樣本數(shù)；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數(shù)表達(dá)式；

3.6 雜交算子

對選擇復(fù)制出來的個體進(jìn)行雜交。雜交的規(guī)則如下：

·對父代個體進(jìn)行兩兩隨機(jī)配對，形成雜交配對池；每一對父體均在一定概率條件下進(jìn)行雜交。

·對于雜交的兩個父代個體，各自分別隨機(jī)選擇一棵子樹，然后交換子樹，得到相應(yīng)的子代個體。

·對于根深大于最大樹根深度限值的子代，則把超過部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。

3.7 變異算子

父代個體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：

·對需要變異的個體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個作為變異分界節(jié)點(diǎn)，對該節(jié)點(diǎn)及其所有分支進(jìn)行變異。

·對于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。

·對于終結(jié)點(diǎn)，則在自變量符號集或數(shù)據(jù)集中隨機(jī)選擇一個進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。

3.8 種群更新

種群更新就是將父代個體中適應(yīng)度最差的若干個體用變異后產(chǎn)生的子代個體進(jìn)行替代。

為了保證每一代中的最好個體都能保留到下一代中，則直接將最好個體替代父代中的最差個體。

3.9 終止條件

終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿足條件即終止：

·達(dá)到繁殖最大次數(shù)。

·達(dá)到算法程序運(yùn)行的最大時長。

·種群中最優(yōu)個體的殘差平方和小于或等于某一給定值。

4建模結(jié)果分析

文章根據(jù)中國某市的網(wǎng)頁瀏覽業(yè)務(wù)實(shí)際用戶調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對這些模型的殘差平方和進(jìn)行了對比分析[7]。

建模目標(biāo)為：建立網(wǎng)頁打開成功率滿意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁打開成功率滿意指數(shù)對應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁打開成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。

遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號集X={x}，數(shù)據(jù)集c={-10

如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對比，相應(yīng)的曲線對比則如圖4所示。

由上述對比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。

此外，一般對于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過增加繁衍次數(shù)仍有較大的提升空間。

5結(jié)束語

文章在建立用戶感知評估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對QoE-KQI數(shù)量關(guān)系進(jìn)行了動態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶感知評估體系，從而運(yùn)營商提升用戶感知管理水平。

這棵樹的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個節(jié)點(diǎn)就是一個基因。

根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個體二叉樹組成的種群。

（2）對種群個體的相關(guān)適應(yīng)度進(jìn)行評估。

（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個體。

（4）對選取的二叉樹個體進(jìn)行雜交操作。

（5）對種群中的個體進(jìn)行相關(guān)變異操作。

（6）種群更新，即將完成雜交和變異后的子代個體替代父代種群中適應(yīng)度低的個體。

3.3 種群初始化

解空間由預(yù)測模型涉及的運(yùn)算符集、自變量符號集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類函數(shù)運(yùn)算符；自變量符號集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。

解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節(jié)點(diǎn)進(jìn)行填充：

·對于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個函數(shù)符號填充。

·對于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號集中隨機(jī)選擇一個自變量填充。

·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個常數(shù)填充。

3.4 個體適應(yīng)度評估

種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個體的適應(yīng)度函數(shù)。對于某一個體，其計(jì)算公式如下：

其中，N表示樣本數(shù)；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數(shù)表達(dá)式；

3.6 雜交算子

對選擇復(fù)制出來的個體進(jìn)行雜交。雜交的規(guī)則如下：

·對父代個體進(jìn)行兩兩隨機(jī)配對，形成雜交配對池；每一對父體均在一定概率條件下進(jìn)行雜交。

·對于雜交的兩個父代個體，各自分別隨機(jī)選擇一棵子樹，然后交換子樹，得到相應(yīng)的子代個體。

·對于根深大于最大樹根深度限值的子代，則把超過部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。

3.7 變異算子

父代個體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：

·對需要變異的個體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個作為變異分界節(jié)點(diǎn)，對該節(jié)點(diǎn)及其所有分支進(jìn)行變異。

·對于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。

·對于終結(jié)點(diǎn)，則在自變量符號集或數(shù)據(jù)集中隨機(jī)選擇一個進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。

3.8 種群更新

種群更新就是將父代個體中適應(yīng)度最差的若干個體用變異后產(chǎn)生的子代個體進(jìn)行替代。

為了保證每一代中的最好個體都能保留到下一代中，則直接將最好個體替代父代中的最差個體。

3.9 終止條件

終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿足條件即終止：

·達(dá)到繁殖最大次數(shù)。

·達(dá)到算法程序運(yùn)行的最大時長。

·種群中最優(yōu)個體的殘差平方和小于或等于某一給定值。

4建模結(jié)果分析

文章根據(jù)中國某市的網(wǎng)頁瀏覽業(yè)務(wù)實(shí)際用戶調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對這些模型的殘差平方和進(jìn)行了對比分析[7]。

建模目標(biāo)為：建立網(wǎng)頁打開成功率滿意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁打開成功率滿意指數(shù)對應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁打開成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。

遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號集X={x}，數(shù)據(jù)集c={-10

如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對比，相應(yīng)的曲線對比則如圖4所示。

由上述對比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。

此外，一般對于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過增加繁衍次數(shù)仍有較大的提升空間。

5結(jié)束語

文章在建立用戶感知評估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對QoE-KQI數(shù)量關(guān)系進(jìn)行了動態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶感知評估體系，從而運(yùn)營商提升用戶感知管理水平。