遺傳算法在用戶(hù)感知評(píng)估建模中的應(yīng)用
2014-07-21 01:12:59
中興通訊技術(shù) 2014年2期
摘要：在建立用戶(hù)感知評(píng)估變量結(jié)構(gòu)模型的基礎(chǔ)上，利用遺傳算法對(duì)KQI-QoE關(guān)系進(jìn)行動(dòng)態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對(duì)數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對(duì)比。實(shí)際用戶(hù)感知和評(píng)估體系的擬合結(jié)果表明，遺傳算法在用戶(hù)感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力。這為進(jìn)一步研究和完善用戶(hù)感知評(píng)估體系提供了新的方法和途徑。
關(guān)鍵詞：移動(dòng)；數(shù)據(jù)業(yè)務(wù)；用戶(hù)感知；評(píng)估建模；遺傳算法
隨著通信技術(shù)的發(fā)展，移動(dòng)通信網(wǎng)絡(luò)可以為用戶(hù)提供越來(lái)越豐富的移動(dòng)業(yè)務(wù)和應(yīng)用，如彩信、網(wǎng)頁(yè)瀏覽、WAP、流媒體、網(wǎng)絡(luò)游戲等，這些業(yè)務(wù)為移動(dòng)運(yùn)營(yíng)商提供了持續(xù)增長(zhǎng)的收入來(lái)源。因此，如何評(píng)估和提升移動(dòng)通信業(yè)務(wù)的用戶(hù)體驗(yàn)質(zhì)量（即用戶(hù)感知），成為全球各大運(yùn)營(yíng)商關(guān)注和研究的重點(diǎn)，同時(shí)也是運(yùn)營(yíng)商在激烈的市場(chǎng)競(jìng)爭(zhēng)中吸引用戶(hù)、保持和擴(kuò)大盈利的關(guān)鍵。
目前，評(píng)估用戶(hù)感知通常有兩種方法：一種是通過(guò)用戶(hù)調(diào)查獲取用戶(hù)的實(shí)際體驗(yàn)質(zhì)量；另一種則是通過(guò)測(cè)量用戶(hù)所應(yīng)用業(yè)務(wù)的性能，即關(guān)鍵業(yè)務(wù)質(zhì)量指標(biāo)（KQI），推算出用戶(hù)的實(shí)際體驗(yàn)質(zhì)量。兩種方法各有利弊。通過(guò)用戶(hù)調(diào)查獲取用戶(hù)感知，優(yōu)點(diǎn)是可以得到實(shí)際的用戶(hù)感知；缺點(diǎn)是無(wú)法實(shí)現(xiàn)實(shí)時(shí)監(jiān)控，滯后性較大，并且每次用戶(hù)調(diào)查都將耗費(fèi)較大的人力、物力和時(shí)間。通過(guò)KQI推算用戶(hù)感知，只需在建模期間提供用戶(hù)調(diào)查得到的實(shí)際用戶(hù)感知數(shù)據(jù)，然后利用該數(shù)據(jù)和相應(yīng)的KQI指標(biāo)建立KQI-QoE數(shù)量關(guān)系模型，即可形成一套穩(wěn)定的實(shí)時(shí)監(jiān)測(cè)系統(tǒng)。建成之后，無(wú)須再進(jìn)行用戶(hù)調(diào)查，操作維護(hù)簡(jiǎn)單，效費(fèi)比高；其缺點(diǎn)是KQI-QoE模型的不合理性將對(duì)推算出的用戶(hù)感知造成誤差。如果能夠構(gòu)建出合理的KQI-QoE數(shù)量關(guān)系模型，顯然采用第2種方法更具吸引力。因此，文章重點(diǎn)研究了KQI-QoE數(shù)量關(guān)系模型的構(gòu)建方法。
常用的回歸分析模型包括：線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對(duì)數(shù)回歸方程。當(dāng)待擬合數(shù)據(jù)具備其中某一種模型的特性關(guān)系時(shí)，采用相應(yīng)的模型方程進(jìn)行曲線擬合，則可以得到良好的趨勢(shì)曲線，誤差也較小。但是，對(duì)于KQI-QoE這類(lèi)未知特性的數(shù)據(jù)，如果利用以上固定的模型方程進(jìn)行曲線擬合，則很可能無(wú)法得到準(zhǔn)確的趨勢(shì)曲線，而且誤差可能也較大[1-3]。
遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，在一定的解空間中搜索最優(yōu)結(jié)果的算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)行的一種數(shù)學(xué)仿真，也是進(jìn)化計(jì)算的一種最重要的形式。若采用遺傳算法，則無(wú)需給出特定回歸模型方程，可進(jìn)行自適應(yīng)擬合，因而適用于對(duì)未知關(guān)系特性的數(shù)據(jù)模型擬合。
1 用戶(hù)感知評(píng)估相關(guān)的
基本概念
在移動(dòng)通信業(yè)務(wù)應(yīng)用領(lǐng)域，用戶(hù)感知評(píng)估就是獲得用戶(hù)對(duì)某種業(yè)務(wù)的應(yīng)用感受情況，它涉及兩個(gè)基本概念：一個(gè)是用戶(hù)感知，另一個(gè)是KQI。
一般情況下，我們所說(shuō)的“用戶(hù)感知”指的是用戶(hù)或客戶(hù)的體驗(yàn)質(zhì)量（QoE），也就是用戶(hù)實(shí)際感受到的服務(wù)網(wǎng)絡(luò)和業(yè)務(wù)的服務(wù)質(zhì)量（QoS）。例如，用戶(hù)感受到的語(yǔ)音或圖像的清晰程度、文件收發(fā)的快慢等。
而用戶(hù)對(duì)某一特定業(yè)務(wù)的質(zhì)量的感受又是多方面或多個(gè)類(lèi)別的，例如，對(duì)于語(yǔ)音電話業(yè)務(wù)，用戶(hù)的感受主要有4個(gè)方面：
·電話是否能接通，即撥號(hào)后是否能聽(tīng)到回鈴聲。
·電話接通所需要等待的時(shí)間長(zhǎng)短。
·電話接通后是否會(huì)異常斷線，也就是掉話。
·打電話期間的語(yǔ)音質(zhì)量如何，如語(yǔ)音是否清晰、是否會(huì)斷斷續(xù)續(xù)、是否存在較大的通話時(shí)延等。
因此，QoE指標(biāo)分為子項(xiàng)感知度和整體感知度，子項(xiàng)感知度與用戶(hù)對(duì)業(yè)務(wù)某一方面的應(yīng)用感受相一致；整體感知度是用戶(hù)對(duì)某一業(yè)務(wù)應(yīng)用的綜合體驗(yàn)質(zhì)量，是該業(yè)務(wù)對(duì)應(yīng)的所有子項(xiàng)感知度的綜合反映。
KQI就是服務(wù)提供商實(shí)際提供的QoS，可通過(guò)測(cè)量或統(tǒng)計(jì)得到，它反映了業(yè)務(wù)或應(yīng)用的端到端性能。一個(gè)或一組KQI指標(biāo)能夠直接地表征業(yè)務(wù)某一方面的性能，如時(shí)延特性、網(wǎng)頁(yè)瀏覽流暢度等[4]。
2 用戶(hù)感知評(píng)估變量結(jié)構(gòu)
模型
用戶(hù)感知評(píng)估變量結(jié)構(gòu)模型定義了用戶(hù)感知評(píng)估涉及哪些結(jié)構(gòu)變量，以及這些變量之間的邏輯關(guān)系。這是構(gòu)建數(shù)學(xué)描述模型的基礎(chǔ)。
用戶(hù)感知的評(píng)估是針對(duì)某一種業(yè)務(wù)進(jìn)行的。由第1節(jié)中所舉語(yǔ)音電話例子，可以看出，對(duì)于任一種業(yè)務(wù)，均可根據(jù)用戶(hù)的感受，劃分為多個(gè)類(lèi)別的性能。一個(gè)類(lèi)別的性能既對(duì)應(yīng)了一個(gè)子項(xiàng)感知度指標(biāo)，又對(duì)應(yīng)了一個(gè)或一組KQI指標(biāo)。業(yè)務(wù)的端到端性能指標(biāo)將影響相應(yīng)類(lèi)別的用戶(hù)感知（即子項(xiàng)感知度），而用戶(hù)對(duì)該業(yè)務(wù)的整體感知?jiǎng)t受各種類(lèi)別的用戶(hù)感知綜合影響。
基于上述分析，我們建立了如圖1所示的用戶(hù)感知評(píng)估變量結(jié)構(gòu)模型，變量的影響關(guān)系是自下而上的，具體表現(xiàn)為：
·一個(gè)類(lèi)別的端到端業(yè)務(wù)性能對(duì)應(yīng)了一個(gè)子項(xiàng)感知度指標(biāo)和一組KQI指標(biāo)。
·KQI指標(biāo)的好壞直接影響了相應(yīng)子項(xiàng)感知度的好壞。
·子項(xiàng)感知度的好壞直接影響了整體感知度的好壞。
因此，從用戶(hù)感知評(píng)估的角度，模型的輸入變量是待評(píng)估業(yè)務(wù)的KQI指標(biāo)，輸出變量是該業(yè)務(wù)的子項(xiàng)感知度和整體感知度。
下面我們將根據(jù)這個(gè)結(jié)構(gòu)模型，運(yùn)用遺傳算法建立確定性的KQI-QoE數(shù)量關(guān)系模型。
3遺傳算法應(yīng)用設(shè)計(jì)
采用遺傳算法進(jìn)行自適應(yīng)曲線擬合，是從問(wèn)題的解空間中一個(gè)隨機(jī)產(chǎn)生的種群開(kāi)始進(jìn)化的。這個(gè)種群則由一定數(shù)目的函數(shù)表達(dá)式組成，每一個(gè)函數(shù)表達(dá)式則代表著一個(gè)個(gè)體，同時(shí)也有可能是我們所想得到的具體數(shù)學(xué)模型[5]。
個(gè)體也就是染色體，它由一定數(shù)目的基因組成，基因的不同和組合方式的不同則決定了個(gè)體的特性。因此，使用遺傳算法，首先需要實(shí)現(xiàn)將函數(shù)表達(dá)式從表現(xiàn)型到基因型的映射，也就是編碼。
3.1 編碼方式
常用的編碼方式有二進(jìn)制編碼、二叉樹(shù)編碼、實(shí)數(shù)編碼等，對(duì)于函數(shù)擬合問(wèn)題，最常用的編碼方式是二叉樹(shù)編碼，即把組成群體的所有個(gè)體采用一種動(dòng)態(tài)的樹(shù)狀結(jié)構(gòu)來(lái)表示。圖2是一個(gè)二叉樹(shù)的示例，它表示了函數(shù)f（x， y， z）=（y ^ 6）*ln（x）+exp（z）。
這棵樹(shù)的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)就是一個(gè)基因。
根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱(chēng)為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹(shù)結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個(gè)可能的解[6]。
3.2 算法流程
遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個(gè)步驟：
（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個(gè)體二叉樹(shù)組成的種群。
（2）對(duì)種群個(gè)體的相關(guān)適應(yīng)度進(jìn)行評(píng)估。
（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個(gè)體。
（4）對(duì)選取的二叉樹(shù)個(gè)體進(jìn)行雜交操作。
（5）對(duì)種群中的個(gè)體進(jìn)行相關(guān)變異操作。
（6）種群更新，即將完成雜交和變異后的子代個(gè)體替代父代種群中適應(yīng)度低的個(gè)體。
3.3 種群初始化
解空間由預(yù)測(cè)模型涉及的運(yùn)算符集、自變量符號(hào)集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類(lèi)函數(shù)運(yùn)算符；自變量符號(hào)集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類(lèi)常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。
解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹(shù)個(gè)體，并且將會(huì)按如下原則對(duì)每個(gè)個(gè)體的二叉樹(shù)節(jié)點(diǎn)進(jìn)行填充：
·對(duì)于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個(gè)函數(shù)符號(hào)填充。
·對(duì)于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號(hào)集中隨機(jī)選擇一個(gè)自變量填充。
·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個(gè)常數(shù)填充。
3.4 個(gè)體適應(yīng)度評(píng)估
種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個(gè)體的適應(yīng)度函數(shù)。對(duì)于某一個(gè)體，其計(jì)算公式如下：
其中，N表示樣本數(shù)；
[yi]表示因變量；
[f（?）]表示[yi]由[x1，…，xm]表示的個(gè)體函數(shù)表達(dá)式；
3.6 雜交算子
對(duì)選擇復(fù)制出來(lái)的個(gè)體進(jìn)行雜交。雜交的規(guī)則如下：
·對(duì)父代個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，形成雜交配對(duì)池；每一對(duì)父體均在一定概率條件下進(jìn)行雜交。
·對(duì)于雜交的兩個(gè)父代個(gè)體，各自分別隨機(jī)選擇一棵子樹(shù)，然后交換子樹(shù)，得到相應(yīng)的子代個(gè)體。
·對(duì)于根深大于最大樹(shù)根深度限值的子代，則把超過(guò)部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。
3.7 變異算子
父代個(gè)體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：
·對(duì)需要變異的個(gè)體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個(gè)作為變異分界節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)及其所有分支進(jìn)行變異。
·對(duì)于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。
·對(duì)于終結(jié)點(diǎn)，則在自變量符號(hào)集或數(shù)據(jù)集中隨機(jī)選擇一個(gè)進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。
3.8 種群更新
種群更新就是將父代個(gè)體中適應(yīng)度最差的若干個(gè)體用變異后產(chǎn)生的子代個(gè)體進(jìn)行替代。
為了保證每一代中的最好個(gè)體都能保留到下一代中，則直接將最好個(gè)體替代父代中的最差個(gè)體。
3.9 終止條件
終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿(mǎn)足條件即終止：
·達(dá)到繁殖最大次數(shù)。
·達(dá)到算法程序運(yùn)行的最大時(shí)長(zhǎng)。
·種群中最優(yōu)個(gè)體的殘差平方和小于或等于某一給定值。
4建模結(jié)果分析
文章根據(jù)中國(guó)某市的網(wǎng)頁(yè)瀏覽業(yè)務(wù)實(shí)際用戶(hù)調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對(duì)原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對(duì)這些模型的殘差平方和進(jìn)行了對(duì)比分析[7]。
建模目標(biāo)為：建立網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)對(duì)應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁(yè)打開(kāi)成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。
遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號(hào)集X={x}，數(shù)據(jù)集c={-10 如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對(duì)比，相應(yīng)的曲線對(duì)比則如圖4所示。 由上述對(duì)比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。 此外，一般對(duì)于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過(guò)1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過(guò)增加繁衍次數(shù)仍有較大的提升空間。 5結(jié)束語(yǔ) 文章在建立用戶(hù)感知評(píng)估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對(duì)QoE-KQI數(shù)量關(guān)系進(jìn)行了動(dòng)態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對(duì)數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對(duì)比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶(hù)感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無(wú)須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶(hù)感知評(píng)估體系，從而運(yùn)營(yíng)商提升用戶(hù)感知管理水平。
這棵樹(shù)的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)就是一個(gè)基因。
根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱(chēng)為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹(shù)結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個(gè)可能的解[6]。
3.2 算法流程
遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個(gè)步驟：
（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個(gè)體二叉樹(shù)組成的種群。
（2）對(duì)種群個(gè)體的相關(guān)適應(yīng)度進(jìn)行評(píng)估。
（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個(gè)體。
（4）對(duì)選取的二叉樹(shù)個(gè)體進(jìn)行雜交操作。
（5）對(duì)種群中的個(gè)體進(jìn)行相關(guān)變異操作。
（6）種群更新，即將完成雜交和變異后的子代個(gè)體替代父代種群中適應(yīng)度低的個(gè)體。
3.3 種群初始化
解空間由預(yù)測(cè)模型涉及的運(yùn)算符集、自變量符號(hào)集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類(lèi)函數(shù)運(yùn)算符；自變量符號(hào)集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類(lèi)常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。
解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹(shù)個(gè)體，并且將會(huì)按如下原則對(duì)每個(gè)個(gè)體的二叉樹(shù)節(jié)點(diǎn)進(jìn)行填充：
·對(duì)于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個(gè)函數(shù)符號(hào)填充。
·對(duì)于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號(hào)集中隨機(jī)選擇一個(gè)自變量填充。
·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個(gè)常數(shù)填充。
3.4 個(gè)體適應(yīng)度評(píng)估
種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個(gè)體的適應(yīng)度函數(shù)。對(duì)于某一個(gè)體，其計(jì)算公式如下：
其中，N表示樣本數(shù)；
[yi]表示因變量；
[f（?）]表示[yi]由[x1，…，xm]表示的個(gè)體函數(shù)表達(dá)式；
3.6 雜交算子
對(duì)選擇復(fù)制出來(lái)的個(gè)體進(jìn)行雜交。雜交的規(guī)則如下：
·對(duì)父代個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，形成雜交配對(duì)池；每一對(duì)父體均在一定概率條件下進(jìn)行雜交。
·對(duì)于雜交的兩個(gè)父代個(gè)體，各自分別隨機(jī)選擇一棵子樹(shù)，然后交換子樹(shù)，得到相應(yīng)的子代個(gè)體。
·對(duì)于根深大于最大樹(shù)根深度限值的子代，則把超過(guò)部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。
3.7 變異算子
父代個(gè)體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：
·對(duì)需要變異的個(gè)體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個(gè)作為變異分界節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)及其所有分支進(jìn)行變異。
·對(duì)于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。
·對(duì)于終結(jié)點(diǎn)，則在自變量符號(hào)集或數(shù)據(jù)集中隨機(jī)選擇一個(gè)進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。
3.8 種群更新
種群更新就是將父代個(gè)體中適應(yīng)度最差的若干個(gè)體用變異后產(chǎn)生的子代個(gè)體進(jìn)行替代。
為了保證每一代中的最好個(gè)體都能保留到下一代中，則直接將最好個(gè)體替代父代中的最差個(gè)體。
3.9 終止條件
終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿(mǎn)足條件即終止：
·達(dá)到繁殖最大次數(shù)。
·達(dá)到算法程序運(yùn)行的最大時(shí)長(zhǎng)。
·種群中最優(yōu)個(gè)體的殘差平方和小于或等于某一給定值。
4建模結(jié)果分析
文章根據(jù)中國(guó)某市的網(wǎng)頁(yè)瀏覽業(yè)務(wù)實(shí)際用戶(hù)調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對(duì)原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對(duì)這些模型的殘差平方和進(jìn)行了對(duì)比分析[7]。
建模目標(biāo)為：建立網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)對(duì)應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁(yè)打開(kāi)成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。
遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號(hào)集X={x}，數(shù)據(jù)集c={-10 如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對(duì)比，相應(yīng)的曲線對(duì)比則如圖4所示。 由上述對(duì)比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。 此外，一般對(duì)于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過(guò)1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過(guò)增加繁衍次數(shù)仍有較大的提升空間。 5結(jié)束語(yǔ) 文章在建立用戶(hù)感知評(píng)估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對(duì)QoE-KQI數(shù)量關(guān)系進(jìn)行了動(dòng)態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對(duì)數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對(duì)比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶(hù)感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無(wú)須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶(hù)感知評(píng)估體系，從而運(yùn)營(yíng)商提升用戶(hù)感知管理水平。
這棵樹(shù)的結(jié)點(diǎn)由根節(jié)點(diǎn)、中間節(jié)點(diǎn)和終結(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)就是一個(gè)基因。
根結(jié)點(diǎn)和中間結(jié)點(diǎn)統(tǒng)稱(chēng)為內(nèi)部結(jié)點(diǎn)，通常是運(yùn)算符；終結(jié)點(diǎn)則為自變量和函數(shù)常數(shù)項(xiàng)。樹(shù)結(jié)構(gòu)表達(dá)的函數(shù)則是待求函數(shù)形式的一個(gè)可能的解[6]。
3.2 算法流程
遺傳算法的實(shí)現(xiàn)流程如圖3所示，包含以下幾個(gè)步驟：
（1）定義解空間，并進(jìn)行種群初始化，產(chǎn)生由一定數(shù)量個(gè)體二叉樹(shù)組成的種群。
（2）對(duì)種群個(gè)體的相關(guān)適應(yīng)度進(jìn)行評(píng)估。
（3）從當(dāng)前群體中選擇一定數(shù)量適應(yīng)度高的個(gè)體。
（4）對(duì)選取的二叉樹(shù)個(gè)體進(jìn)行雜交操作。
（5）對(duì)種群中的個(gè)體進(jìn)行相關(guān)變異操作。
（6）種群更新，即將完成雜交和變異后的子代個(gè)體替代父代種群中適應(yīng)度低的個(gè)體。
3.3 種群初始化
解空間由預(yù)測(cè)模型涉及的運(yùn)算符集、自變量符號(hào)集和數(shù)據(jù)集的復(fù)合。其中，運(yùn)算符集則包含了模型涉及的加、減、乘、除等各類(lèi)函數(shù)運(yùn)算符；自變量符號(hào)集則包含了模型可能涉及所有自變量；數(shù)據(jù)集則是模型涉及的各類(lèi)常數(shù)的最大取值范圍，例如常數(shù)項(xiàng)、指數(shù)項(xiàng)、系數(shù)項(xiàng)等。
解空間定義之后，隨機(jī)產(chǎn)生一定數(shù)量的二叉樹(shù)個(gè)體，并且將會(huì)按如下原則對(duì)每個(gè)個(gè)體的二叉樹(shù)節(jié)點(diǎn)進(jìn)行填充：
·對(duì)于內(nèi)部節(jié)點(diǎn)，均隨機(jī)由運(yùn)算符集中選擇一個(gè)函數(shù)符號(hào)填充。
·對(duì)于終結(jié)點(diǎn)，則首先隨機(jī)選擇是自變量還是數(shù)據(jù)項(xiàng)，若是自變量，則隨機(jī)從自變量符號(hào)集中隨機(jī)選擇一個(gè)自變量填充。
·若是數(shù)據(jù)項(xiàng)，則在常數(shù)項(xiàng)取值范圍內(nèi)隨機(jī)選擇一個(gè)常數(shù)填充。
3.4 個(gè)體適應(yīng)度評(píng)估
種群進(jìn)化的目標(biāo)是使得擬合曲線的誤差盡量最小，因此我們采用最小二乘法的原則，選擇殘差平方和作為個(gè)體的適應(yīng)度函數(shù)。對(duì)于某一個(gè)體，其計(jì)算公式如下：
其中，N表示樣本數(shù)；
[yi]表示因變量；
[f（?）]表示[yi]由[x1，…，xm]表示的個(gè)體函數(shù)表達(dá)式；
3.6 雜交算子
對(duì)選擇復(fù)制出來(lái)的個(gè)體進(jìn)行雜交。雜交的規(guī)則如下：
·對(duì)父代個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，形成雜交配對(duì)池；每一對(duì)父體均在一定概率條件下進(jìn)行雜交。
·對(duì)于雜交的兩個(gè)父代個(gè)體，各自分別隨機(jī)選擇一棵子樹(shù)，然后交換子樹(shù)，得到相應(yīng)的子代個(gè)體。
·對(duì)于根深大于最大樹(shù)根深度限值的子代，則把超過(guò)部分最大根深限值的枝葉全部直接剪除；然后，將剪除后的最末一層的中間節(jié)點(diǎn)改為終結(jié)點(diǎn)，填充方式與種群初始化方式相同。
3.7 變異算子
父代個(gè)體在一定概率條件下進(jìn)行變異操作，具體規(guī)則如下：
·對(duì)需要變異的個(gè)體，在所有節(jié)點(diǎn)中隨機(jī)選擇其中的一個(gè)作為變異分界節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)及其所有分支進(jìn)行變異。
·對(duì)于內(nèi)部節(jié)點(diǎn)，則在運(yùn)算符集中隨機(jī)選擇其他元素進(jìn)行替換，替換值不同于原值。
·對(duì)于終結(jié)點(diǎn)，則在自變量符號(hào)集或數(shù)據(jù)集中隨機(jī)選擇一個(gè)進(jìn)行替換，替換值允許等同于原值。終結(jié)點(diǎn)的填充方法與種群初始化方式相同。
3.8 種群更新
種群更新就是將父代個(gè)體中適應(yīng)度最差的若干個(gè)體用變異后產(chǎn)生的子代個(gè)體進(jìn)行替代。
為了保證每一代中的最好個(gè)體都能保留到下一代中，則直接將最好個(gè)體替代父代中的最差個(gè)體。
3.9 終止條件
終止條件可僅設(shè)定為以下3種中的任一種；或3種條件都設(shè)定，只要其中一項(xiàng)滿(mǎn)足條件即終止：
·達(dá)到繁殖最大次數(shù)。
·達(dá)到算法程序運(yùn)行的最大時(shí)長(zhǎng)。
·種群中最優(yōu)個(gè)體的殘差平方和小于或等于某一給定值。
4建模結(jié)果分析
文章根據(jù)中國(guó)某市的網(wǎng)頁(yè)瀏覽業(yè)務(wù)實(shí)際用戶(hù)調(diào)查數(shù)據(jù)與KQI統(tǒng)計(jì)指標(biāo)，分別采用遺傳算法和傳統(tǒng)回歸方程對(duì)原始數(shù)據(jù)進(jìn)行擬合，建立了相應(yīng)的數(shù)學(xué)模型，并按照最小二乘法的原則，對(duì)這些模型的殘差平方和進(jìn)行了對(duì)比分析[7]。
建模目標(biāo)為：建立網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)KQI-QoE數(shù)學(xué)模型。QoE指標(biāo)網(wǎng)頁(yè)打開(kāi)成功率滿(mǎn)意指數(shù)對(duì)應(yīng)的KQI指標(biāo)僅一項(xiàng)，為網(wǎng)頁(yè)打開(kāi)成功率。建立的數(shù)學(xué)模型應(yīng)為一元函數(shù)。
遺傳算法的參數(shù)設(shè)定為：運(yùn)算符集為{+，-，*，/，^，exp，log}，自變量符號(hào)集X={x}，數(shù)據(jù)集c={-10 如表1所示，為遺傳算法與其他傳統(tǒng)回歸算法建立的數(shù)學(xué)模型及其殘差平方和運(yùn)算結(jié)果對(duì)比，相應(yīng)的曲線對(duì)比則如圖4所示。 由上述對(duì)比可以看出，遺傳算法所建立的數(shù)學(xué)模型殘差平方和最小，擬合度優(yōu)于其他算法。 此外，一般對(duì)于曲線擬合，遺傳算法的繁衍次數(shù)還可以取得更大，例如10 000到100 000次，隨著繁衍次數(shù)的增加，模型的擬合度也將隨之提高。因此，雖然我們僅通過(guò)1 000次繁衍得到的數(shù)學(xué)模型已經(jīng)具有較好的擬合度，但通過(guò)增加繁衍次數(shù)仍有較大的提升空間。 5結(jié)束語(yǔ) 文章在建立用戶(hù)感知評(píng)估構(gòu)架模型的基礎(chǔ)上，采用遺傳算法對(duì)QoE-KQI數(shù)量關(guān)系進(jìn)行了動(dòng)態(tài)自適應(yīng)建模，并與線性回歸方程、指數(shù)回歸方程、拋物線回歸方程以及對(duì)數(shù)回歸方程等傳統(tǒng)的擬合方法進(jìn)行了對(duì)比。文中給出的一維變量關(guān)系擬合結(jié)果表明，遺傳算法在用戶(hù)感知建模方面具備良好的自適應(yīng)搜索最優(yōu)解的能力，所擬合的模型要明顯優(yōu)于傳統(tǒng)方法。而且由于遺傳算法無(wú)須像傳統(tǒng)方法一樣事先給出特定的關(guān)系模型，使其更適合于建立多變量相互影響的關(guān)系模型，這也更有益于進(jìn)一步研究和完善用戶(hù)感知評(píng)估體系，從而運(yùn)營(yíng)商提升用戶(hù)感知管理水平。
