遺傳算法在用戶感知評估建模中的應用

摘要：在建立用戶感知評估變量結構模型的基礎上，利用遺傳算法對KQI-QoE關系進行動態自適應建模，并與線性回歸方程、指數回歸方程、拋物線回歸方程以及對數回歸方程等傳統的擬合方法進行了對比。實際用戶感知和評估體系的擬合結果表明，遺傳算法在用戶感知建模方面具備良好的自適應搜索最優解的能力。這為進一步研究和完善用戶感知評估體系提供了新的方法和途徑。

關鍵詞：移動；數據業務；用戶感知；評估建模；遺傳算法

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

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

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

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

1 用戶感知評估相關的

基本概念

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

一般情況下，我們所說的“用戶感知”指的是用戶或客戶的體驗質量（QoE），也就是用戶實際感受到的服務網絡和業務的服務質量（QoS）。例如，用戶感受到的語音或圖像的清晰程度、文件收發的快慢等。

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

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

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

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

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

因此，QoE指標分為子項感知度和整體感知度，子項感知度與用戶對業務某一方面的應用感受相一致；整體感知度是用戶對某一業務應用的綜合體驗質量，是該業務對應的所有子項感知度的綜合反映。

KQI就是服務提供商實際提供的QoS，可通過測量或統計得到，它反映了業務或應用的端到端性能。一個或一組KQI指標能夠直接地表征業務某一方面的性能，如時延特性、網頁瀏覽流暢度等[4]。

2 用戶感知評估變量結構

模型

用戶感知評估變量結構模型定義了用戶感知評估涉及哪些結構變量，以及這些變量之間的邏輯關系。這是構建數學描述模型的基礎。

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

基于上述分析，我們建立了如圖1所示的用戶感知評估變量結構模型，變量的影響關系是自下而上的，具體表現為：

·一個類別的端到端業務性能對應了一個子項感知度指標和一組KQI指標。

·KQI指標的好壞直接影響了相應子項感知度的好壞。

·子項感知度的好壞直接影響了整體感知度的好壞。

因此，從用戶感知評估的角度，模型的輸入變量是待評估業務的KQI指標，輸出變量是該業務的子項感知度和整體感知度。

下面我們將根據這個結構模型，運用遺傳算法建立確定性的KQI-QoE數量關系模型。

3遺傳算法應用設計

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

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

3.1 編碼方式

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

這棵樹的結點由根節點、中間節點和終結點組成，每個節點就是一個基因。

根結點和中間結點統稱為內部結點，通常是運算符；終結點則為自變量和函數常數項。樹結構表達的函數則是待求函數形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實現流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進行種群初始化，產生由一定數量個體二叉樹組成的種群。

（2）對種群個體的相關適應度進行評估。

（3）從當前群體中選擇一定數量適應度高的個體。

（4）對選取的二叉樹個體進行雜交操作。

（5）對種群中的個體進行相關變異操作。

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

3.3 種群初始化

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

解空間定義之后，隨機產生一定數量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節點進行填充：

·對于內部節點，均隨機由運算符集中選擇一個函數符號填充。

·對于終結點，則首先隨機選擇是自變量還是數據項，若是自變量，則隨機從自變量符號集中隨機選擇一個自變量填充。

·若是數據項，則在常數項取值范圍內隨機選擇一個常數填充。

3.4 個體適應度評估

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

其中，N表示樣本數；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數表達式；

3.6 雜交算子

對選擇復制出來的個體進行雜交。雜交的規則如下：

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

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

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

3.7 變異算子

父代個體在一定概率條件下進行變異操作，具體規則如下：

·對需要變異的個體，在所有節點中隨機選擇其中的一個作為變異分界節點，對該節點及其所有分支進行變異。

·對于內部節點，則在運算符集中隨機選擇其他元素進行替換，替換值不同于原值。

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

3.8 種群更新

種群更新就是將父代個體中適應度最差的若干個體用變異后產生的子代個體進行替代。

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

3.9 終止條件

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

·達到繁殖最大次數。

·達到算法程序運行的最大時長。

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

4建模結果分析

文章根據中國某市的網頁瀏覽業務實際用戶調查數據與KQI統計指標，分別采用遺傳算法和傳統回歸方程對原始數據進行擬合，建立了相應的數學模型，并按照最小二乘法的原則，對這些模型的殘差平方和進行了對比分析[7]。

建模目標為：建立網頁打開成功率滿意指數KQI-QoE數學模型。QoE指標網頁打開成功率滿意指數對應的KQI指標僅一項，為網頁打開成功率。建立的數學模型應為一元函數。

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

如表1所示，為遺傳算法與其他傳統回歸算法建立的數學模型及其殘差平方和運算結果對比，相應的曲線對比則如圖4所示。

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

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

5結束語

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

這棵樹的結點由根節點、中間節點和終結點組成，每個節點就是一個基因。

根結點和中間結點統稱為內部結點，通常是運算符；終結點則為自變量和函數常數項。樹結構表達的函數則是待求函數形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實現流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進行種群初始化，產生由一定數量個體二叉樹組成的種群。

（2）對種群個體的相關適應度進行評估。

（3）從當前群體中選擇一定數量適應度高的個體。

（4）對選取的二叉樹個體進行雜交操作。

（5）對種群中的個體進行相關變異操作。

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

3.3 種群初始化

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

解空間定義之后，隨機產生一定數量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節點進行填充：

·對于內部節點，均隨機由運算符集中選擇一個函數符號填充。

·對于終結點，則首先隨機選擇是自變量還是數據項，若是自變量，則隨機從自變量符號集中隨機選擇一個自變量填充。

·若是數據項，則在常數項取值范圍內隨機選擇一個常數填充。

3.4 個體適應度評估

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

其中，N表示樣本數；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數表達式；

3.6 雜交算子

對選擇復制出來的個體進行雜交。雜交的規則如下：

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

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

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

3.7 變異算子

父代個體在一定概率條件下進行變異操作，具體規則如下：

·對需要變異的個體，在所有節點中隨機選擇其中的一個作為變異分界節點，對該節點及其所有分支進行變異。

·對于內部節點，則在運算符集中隨機選擇其他元素進行替換，替換值不同于原值。

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

3.8 種群更新

種群更新就是將父代個體中適應度最差的若干個體用變異后產生的子代個體進行替代。

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

3.9 終止條件

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

·達到繁殖最大次數。

·達到算法程序運行的最大時長。

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

4建模結果分析

文章根據中國某市的網頁瀏覽業務實際用戶調查數據與KQI統計指標，分別采用遺傳算法和傳統回歸方程對原始數據進行擬合，建立了相應的數學模型，并按照最小二乘法的原則，對這些模型的殘差平方和進行了對比分析[7]。

建模目標為：建立網頁打開成功率滿意指數KQI-QoE數學模型。QoE指標網頁打開成功率滿意指數對應的KQI指標僅一項，為網頁打開成功率。建立的數學模型應為一元函數。

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

如表1所示，為遺傳算法與其他傳統回歸算法建立的數學模型及其殘差平方和運算結果對比，相應的曲線對比則如圖4所示。

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

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

5結束語

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

這棵樹的結點由根節點、中間節點和終結點組成，每個節點就是一個基因。

根結點和中間結點統稱為內部結點，通常是運算符；終結點則為自變量和函數常數項。樹結構表達的函數則是待求函數形式的一個可能的解[6]。

3.2 算法流程

遺傳算法的實現流程如圖3所示，包含以下幾個步驟：

（1）定義解空間，并進行種群初始化，產生由一定數量個體二叉樹組成的種群。

（2）對種群個體的相關適應度進行評估。

（3）從當前群體中選擇一定數量適應度高的個體。

（4）對選取的二叉樹個體進行雜交操作。

（5）對種群中的個體進行相關變異操作。

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

3.3 種群初始化

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

解空間定義之后，隨機產生一定數量的二叉樹個體，并且將會按如下原則對每個個體的二叉樹節點進行填充：

·對于內部節點，均隨機由運算符集中選擇一個函數符號填充。

·對于終結點，則首先隨機選擇是自變量還是數據項，若是自變量，則隨機從自變量符號集中隨機選擇一個自變量填充。

·若是數據項，則在常數項取值范圍內隨機選擇一個常數填充。

3.4 個體適應度評估

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

其中，N表示樣本數；

[yi]表示因變量；

[f（?）]表示[yi]由[x1，…，xm]表示的個體函數表達式；

3.6 雜交算子

對選擇復制出來的個體進行雜交。雜交的規則如下：

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

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

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

3.7 變異算子

父代個體在一定概率條件下進行變異操作，具體規則如下：

·對需要變異的個體，在所有節點中隨機選擇其中的一個作為變異分界節點，對該節點及其所有分支進行變異。

·對于內部節點，則在運算符集中隨機選擇其他元素進行替換，替換值不同于原值。

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

3.8 種群更新

種群更新就是將父代個體中適應度最差的若干個體用變異后產生的子代個體進行替代。

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

3.9 終止條件

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

·達到繁殖最大次數。

·達到算法程序運行的最大時長。

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

4建模結果分析

文章根據中國某市的網頁瀏覽業務實際用戶調查數據與KQI統計指標，分別采用遺傳算法和傳統回歸方程對原始數據進行擬合，建立了相應的數學模型，并按照最小二乘法的原則，對這些模型的殘差平方和進行了對比分析[7]。

建模目標為：建立網頁打開成功率滿意指數KQI-QoE數學模型。QoE指標網頁打開成功率滿意指數對應的KQI指標僅一項，為網頁打開成功率。建立的數學模型應為一元函數。

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

如表1所示，為遺傳算法與其他傳統回歸算法建立的數學模型及其殘差平方和運算結果對比，相應的曲線對比則如圖4所示。

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

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

5結束語

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