面向在線率差異的SaaS訂閱限額及資源配置組合優化

摘 要：軟件即服務（softuare as a service，SaaS）是一種讓用戶通過支付訂閱費來獲得軟件訪問權的云服務模式。由于其業務的多樣性，用戶對不同軟件的在線訪問率存在很大差異，所以不同軟件所消耗的云計算資源也存在差異。為避免違反服務等級協議（service level agreement，SLA）而產生違約賠付的風險，SaaS運營商不僅要優化各種軟件的計算資源配置，還要對各類軟件的訂閱量加以限額。在考慮SLA限制的基礎上，構建了一個以收益最大化為目標的有資源約束的非線性整數規劃模型。由于模型計算的復雜性，其無法在多項式時間內求解，所以設計了基于Q學習-粒子群（particle swarm optimizoction，PSO）的融合算法來求解該NP難題。該算法將Q-學習嵌入到PSO中，動態調整PSO參數，從而避免直接使用PSO時會面臨的局部最優陷阱和計算效率低下的問題。仿真實驗驗證了在不同場景下模型及算法的有效性，結果表明該算法可在云計算資源有限的條件下，以較高的求解效率獲得收益更高的訂閱限額及資源配置方案。其中，當處于需求波動大的情境下時，運營商應盡可能地降低軟件的資源爭用比，通過配置足量的虛擬機資源并設定嚴格的訂閱限額來保障軟件的服務質量，減少違約賠付成本；相反，當處于需求波動小的情境下時，運營商可以提高軟件的資源爭用比，通過放寬訂閱限額來搶占更大的市場，實現收益最大化。

關鍵詞：軟件即服務； 訂閱限額； 資源配置； 粒子群優化； Q-學習

中圖分類號：TP391.9 文獻標志碼：A 文章編號：1001-3695（2024）07-021-2069-10

doi：10.19734/j.issn.1001-3695.2023.10.0542

Combination optimization of SaaS subscription limits andresource allocation considering online disparity

Abstract：SaaS is a cloud service model where users obtain software access rights by paying subscription fees. Due to the diversity of business operations， users exhibit significant variations in the online access rates for different software. Consequently， there are variations in the cloud computing resources consumed by different software applications. To avoid the risk of violating SLAs and incurring penalty payments， SaaS operators optimize the computational resource allocation for various software applications and impose subscription limits on each category of software. Considering SLA constraints， this paper formulated a resource-constrained nonlinear integer programming model with the objective of maximizing revenue. Due to the computational complexity of the model， it cannot be solved in polynomial time，and this paper proposed a Q-learning-PSO hybrid algorithm for this NP-hand problem. This algorithm embedded Q-learning into PSO to dynamically adjust PSO parameters， thereby avoiding the issues of local optima and low computational efficiency associated with direct PSO application. Simulation experiments validate the effectiveness of the model and algorithm in different scenarios. The results indicate that the algorithm can achieve higher revenue for subscription limits and resource allocation with superior solving efficiency under the condition of limited cloud computing resources. Specifically， in scenarios with significant demand fluctuations， operators should aim to reduce the resource contention ratio of software. This can be achieved by provisioning an ample amount of virtual machine resources and enforcing strict subscription limits to ensure the quality of service， consequently reducing penalty payments. Conversely， in scenarios with minimal demand fluctuations， operators have the flexibility to increase the resource contention ratio of software. By relaxing subscription limits， they can seize a larger market share， thus realizing revenue maximization.

Key words：software as a service; subscription limit; resource allocation; particle swarm optimization; Q-learning

0 引言

隨著云計算技術帶來巨大的商業模式變革，軟件即服務（SaaS）模式獲得了飛速發展。SaaS是將多租戶應用部署在云中的軟件交付模式。在該模式下，應用軟件是一類可通過互聯網進行遠程訪問的服務，用戶無須構建IT基礎設施或購買軟件版權，而是根據自身需要向運營商支付訂閱費來取得軟件訪問權，雙方基于服務等級協議（SLA）來規范服務的提供與使用行為［1］。該模式為用戶節省了大量IT投資，深受中小企業的歡迎。據Gartner預測，2023年全球SaaS市場規模將超兩千億美元［2］。近年來，國內外軟件企業，如微軟、SAP、ORACLE、阿里巴巴和用友等，都爭先推出一系列SaaS產品［2］。

考慮到中小企業業務的多樣性，用戶對不同軟件的服務時間需求以及在線訪問率均有著顯著差異，所謂在線率指的是任意時間內在線使用軟件的用戶數占該時間內訂閱總人數的比例。由于在實際使用中，只有在線訪問軟件的用戶才會消耗資源，所以不同軟件所消耗的云計算資源存在很大差異。為保障SaaS服務的可用VnG8qZavw64AK2BA8ynlFQ==性，運營商需要提前為軟件配置適量的虛擬機資源來滿足用戶的訂閱需求。同時，在計算資源有限的條件下，運營商需要對不同軟件的訂閱限額加以限制來避免因違反SLA約束而產生違約賠付。資源配置和訂閱限額均會對企業收益產生顯著影響，且兩者存在相互制約的關系，當運營商過度配置資源來放寬訂閱限額時，其可以接受大量的訂閱請求來占領市場，但由于不同用戶對軟件在線率的需求存在差異，這種策略容易導致虛擬機資源的浪費，造成資源利用率低下。相反，當運營商的資源配置不足時，則必須通過設定嚴格的訂閱限額來保障服務質量，否則將面臨因違反SLA約束而產生賠付的風險，從而影響收益。因此，如何對資源配置和訂閱限額進行組合優化來實現SaaS運營商收益最大化，是一個亟待解決的問題。

本文研究的問題是基于收益管理的視角，收益管理作為一種通過控制消耗易逝資源產品的價格和可用性來提高收益的理論［3］，已經較為成熟地應用于航空、酒店和互聯網等易逝產品領域。由于云計算資源具有無法長期存儲且在銷售期結束后其價值幾乎為零的易逝品特點，所以可以將收益管理應用于SaaS云服務領域。當前對收益管理在SaaS領域的研究主要集中在定價策略上［4～6］，對資源配置和訂閱限額控制的研究則相對較少。其中，Zhang等人［7］針對供需不確定的情景，設計了一種資源優化配置算法來實現SaaS運營商收益最大化的目標；Zhu等人［8］提出了一種基于深度強化學習的實時任務調度方法來智能地為不斷達到的用戶任務請求分配適當的資源，從而提高資源的利用率；Sikora等人［9］提出了自適應的準入控制框架來滿足SLA約束，并將違反SLA的賠付納入考量；Han等人［10］通過切片技術識別不耐煩用戶，并設計準入控制系統來最大化云提供商的效用。

收益管理的各項策略在實際中都得到了應用，Pimentel等人［11］證明在一些行業中設置訂閱限額能產生更多的收益。當前，許多行業都采用閾值控制的方法優化資源配置及訂閱限額來提高收益或服務質量。王航臣等人［12］基于蒙特卡羅模擬來研究航空公司機票的預定限制；Luo等人［3］考慮設置嵌套預訂限制來合理配置頭等艙與經濟艙的座位數量，從而避免因接受低票價預訂而拒絕高票價預訂的行為，并采用基于仿真的優化算法進行求解；鄧連波等人［13］針對高鐵列車的最大超售數量問題構建了基于隨機規劃的非線性整數規劃超售模型，從而提高企業收益；Nababan等人［14］提出了適用于酒店行業的訂閱限制模型，并利用機器學習算法預測用戶的取消預訂率來提高收益；You等人［15］構建了互聯網行業中的帶寬資源分配及訂閱限額模型，解決了需求過載問題。這些領域的研究為本文提供了借鑒，然而相較于這些行業，SaaS云服務具有SLA約束的特點。越來越多的學者開始研究SaaS中提高SLA收益的優化方法［16］，SLA包括可用性、安全性與響應時間，本文重點關注軟件的可用性，即保障用戶的服務質量。當訪問軟件違約率超過合同限定值，用戶將對服務提供商進行懲罰［17］，即SaaS供應商向用戶進行賠付。Buyya等人［18］描述了通過避免過度使用資源來保證服務質量滿足SLA的準入控制機制；Yuan等人［19］提出了運營商在違反SLA后的賠付算法來提高用戶效用。為了實現收益最大化和用戶滿意度最大化的目標，SaaS運營商需要通過制定適當的準入控制策略來優化訂閱限額。因此，為了滿足客戶差異化的需求以及更好地利用資源獲得最大化收益，本文采用基于仿真的優化方法來解決隨機需求下的資源配置及訂閱限額問題。

本文對SaaS資源配置及訂閱限額策略的優化研究屬于大規模組合優化問題，云計算環境下的大規模服務組合優化問題被視為NP難題［20］，該類問題的求解復雜度會隨著運營商提供軟件類別的增加而呈指數級增長，因此無法使用傳統的數學規劃方法來精確地解決該類問題［21，22］。目前常用粒子群優化算法（PSO）對組合優化問題進行求解［3］，然而直接采用PSO求解本文模型會面臨由于依賴先驗知識而陷入局部最優以及計算效率低下的問題。針對這一問題，可參考其他領域中基于強化學習的融合算法。為解決可復用產品的最優經濟訂購批量難題，Fallahi等人［23］將強化學習算法分別與差分學習算法（differential evolution，DE）和粒子群優化算法相結合，并使用Q-學習來自適應DE和PSO中的控制參數，提高算法性能；在解決柔性作業車間調度難題時，Chen等人［24］提出了自學習遺傳算法（self-learning genetic algorithm，SLGA），該算法以遺傳算法（genetic algorithm，GA）為基本優化方法，并基于強化學習（reinforcement learning，RL）對關鍵參數進行智能調整，提高了算法優化水平。由此可見，利用強化學習動態調整元啟發算法的關鍵參數，對提高算法性能有顯著的作用。

本文在上述研究的基礎上，對SaaS運營商有限時間內虛擬機資源配置及訂閱限額進行研究，貢獻表現為：a）在考慮SLA約束的基礎上，為SaaS運營商構建了以收益最大化為目標的有資源約束的非線性整數規劃模型，該模型考慮了用戶對不同軟件在線率的差異以及SLA違約賠付，從而對資源配置及訂閱限額進行組合優化；b）由于模型計算的高復雜度，其無法在多項式時間內求解，所以在搜索解的過程中提出基于Q學習-粒子群的融合算法作為解決方法，通過在PSO中嵌入Q-學習算法來動態調整PSO關鍵參數，提高算法性能；c）通過仿真實驗發現不同情景下的最優訂閱限額及資源配置策略組合，為運營商的銷售決策提供指導，實現收益最大化。

1 問題描述與模型構建

為保障軟件可用性，SaaS運營商需要提前為各類軟件配置虛擬機資源，同時確定訂閱限額來管理用戶的訂閱請求，避免出現需求過載的情況。資源配置及訂閱限額均對企業收益有較大的影響，資源配置過量或訂閱限額設定過低會產生資源供過于求的情況，導致部分虛擬機資源浪費，影響企業收益；而資源配置不足或訂閱限額設定過高則會產生資源供不應求的情況，導致虛擬機過載，從而出現用戶訪問請求被拒絕的現象，影響企業信譽的同時產生違約賠付，造成企業收益下降。因此，如何配置資源及優化訂閱限額來提升企業收益是本文主要解決的問題。

1.1 問題描述

考慮一家提供L種軟件訂閱服務的SaaS運營商需要在限定服務時間內，利用有限的虛擬機資源來獲得最大化收益。令l（l=1，2，…，L）表示軟件類型的序列標識，t（t=1，2，…，T+1）表示時間段的序列標識，V表示虛擬機資源總量。假設在整段服務時間內運營商的虛擬機資源總量保持不變，用rl來描述單位時間內每位用戶訪問軟件l所需要的虛擬機資源量。SaaS運營商通過與用戶簽訂合約并收取訂閱費來獲得收益，合約中包含了用戶所選擇訂閱的軟件種類及訂閱的服務時間范圍。為此，將用戶的訂閱請求標記為（l，i，j），其中i和j（i，j=1，2，…，T+1，i ≤j）分別表示訂閱的起始時間和終止時間，如果i=j則表示用戶訂閱一個時間周期的軟件服務。為簡化模型的復雜度，假設訂閱請求需要在下一個時間段生效，即任何包含時間段t的訂閱請求都應在時間段t-1之前進行訂閱。因此，SaaS運營商的銷售計劃周期是從第1個到第T個時間段，而用戶的有效訂閱時長是從第2個到第T+1個時間段。

SaaS運營商的目的是將所有的虛擬機資源分配給各類軟件，并在SLA約束下確定各種訂閱需求的訂閱限額，實現總收益最大化。因此，設定vl和sl，i，j為模型的決策變量，其中vl表示分配給軟件l的虛擬機資源，sl，i，j表示訂閱請求（l，i，j）的訂閱限額。具體的符號說明如表1所示。

1.2 模型構建

設Rl，t表示考慮（l，i，j）的訂閱限額為sl，i，j時，時間段t+1內軟件l的訂閱收益。由于在時間段t訂閱的軟件服務的起始時間i必須晚于t+1，即i≥t+1，所以時間段t內可供訂閱的軟件服務集合為{（l，i，j）|t≤i≤j≤T}，則Rl，t具體表示為

人數，即i≤t≤j。由于服務時間涵蓋時間段t+1的訂單只能在時間段t之前訂閱，所以如果用戶在時間段k（1≤k≤t）訂閱了服務時間包含時間段t+1的軟件服務，則該訂閱的服務起始時間i和服務終止時間j必須分別滿足k+1≤i≤t+1和t+1≤j≤T+1。因此，在時間段k提供的服務時間包含了時間段t+1的軟件服務集合為{（l，i，j）|k≤i≤t，t≤j≤T}，則Wl，t表示為

由式（2）可知，軟件l在時間段t+1內所需的虛擬機資源總量預計為Wl，tωlrl，其中Wl，tωl表示時間段t+1內在線訪問軟件的人數。在SLA約束下，SaaS運營商需對未達到服務質量水平的服務進行違約賠付，令Pel，t為軟件l在時間段t內產生的違約率，其根據規定的服務水平αl與實際服務水平的差值來計算，若實際服務水平低于αl，則視為違約行為。其中軟件l的實際服務水平用分配給軟件l的虛擬機資源vl超過該類別實際所需的虛擬機資源Wl，tωlrl的概率來表示，違約率Pel，t具體表示為

Pel，t=max{αl-prob（vl≥Wl，tωlrl），0}

其中：prob（vl≥Wl，tωlrl）表示在時間段t內軟件l的實際服務水平。令PCl，t表示在時間段t內軟件l產生的違約賠付成本，其依賴賠付比例βl與違約率Pel，t，則賠付成本表示如下：

PCl，t=βlPel，tpl，t，t（3）

其中：pl，t，t表示訂閱軟件l一個時間周期的價格。設Π表示訂閱限額為s時的總收益，由于l=1，2，…，L，i，j=1，2，…，T且i≤j，則i=1時，j=1，2，…，T，共T種服務時間組合；i=2時，j=2，3，…，T，共T-1種服務時間組合；i=T時，j=T，共1種服務時間組合，由此可知可能存在0.5LT（T+1）種不同的訂閱需求，則s是維度為0.5LT（T+1）的向量，元素sl，i，j位于第0.5（l-1）T（T+1）+0.5j（j-1）+i個條目。總收益函數由訂閱收益減去賠付成本構成，其為L類產品在整個收益周期下產生的收益總和，表示如下：

根據模型假設，SaaS運營商將有限的虛擬機資源全部分配給L類軟件產品，則分配給各類軟件的虛擬機資源vl之和等于總可用虛擬機資源V，因此該問題具有如下約束：

SaaS運營商的目標是通過確定向量v和s的值使收益最大化，其中v中包含了L個元素，是L維向量，元素vl位于第l個條目。因此，該問題建模如下：

1.3 模型求解難點分析

本文構建的SaaS資源配置及訂閱限額模型屬于大規模非線性整數規劃模型，面臨著求解難題，主要表現在以下方面：

a）大規模的決策空間。SaaS訂閱問題面向眾多用戶，且運營商提供L種軟件類型供用戶選擇，同時每個用戶對于每種軟件l都有不同的訂閱時間需求，他們在訂閱時根據需求自主選擇訂閱軟件的起始時間i和終止時間j，這使得SaaS運營商會面臨0.5LT（T+1）種不同的訂閱請求組合，即訂閱限額量sl，i，j是一個維度為0.5LT（T+1）的向量，資源配置量v是一個維度為L的向量。在實際應用中，決策空間會隨著軟件種類L和銷售周期T的增加而呈指數級增加，導致求解的搜索空間規模很大，在實際求解過程中不能使用窮盡式搜索的方法對所有訂閱組合進行嘗試和計算。

因此，本文構建的模型具有非線性特性及大規模決策空間等特點，計算復雜度較高，是一個NP難題［26］。該模型無法利用分枝定界法等傳統的數學規劃方法在多項式時間內進行精確求解［27］，需采用元啟發式算法來近似求解。當前粒子群優化算法是求解上述模型的主流算法之一［28］，PSO是一種基于群體優化的元啟發式算法，可以有效地解決各種組合優化問題［3］，因此，本文利用PSO來解決多目標優化問題，并結合資源配置及訂閱限額模型特性設計求解算法。

2 基于Q學習-粒子群融合算法的模型求解方法

針對模型求解難題，本章設計了基于Q學習-粒子群的融合算法（簡記為Q-PSO），通過將Q學習算法嵌入到PSO中，動態調整PSO的參數來提高算法性能，確保求解的效率與質量。

2.1 問題求解的粒子群算法

PSO是1995年提出的進化計算方法［29］，通過模仿鳥群覓食行為設計而來。群體中的個體稱為粒子，每個粒子代表一個潛在的解決方案，粒子通過在搜索空間中運動來尋找最優解，粒子的運動由其位置和速度決定，其中位置代表一個可能的解，速度代表下一步要移動的距離。PSO利用隨機解進行初始化，后續每個粒子依靠其自身歷史最佳位置的信息、全局歷史最佳位置的信息以及當前位置和速度來調整下一步的位置。在該算法中，粒子的局部最優與全局最優位置信息共享，將局部搜索與全局搜索相結合來搜索最優解。算法的具體步驟如圖2所示。

2.1.1 粒子定義

在PSO中，粒子是算法的基本單元，可以看作是候選解在搜索解空間中的一個位置，因此為了將PSO應用到模型中，需要建立決策變量和PSO粒子之間的關系。當前模型中有L個虛擬機資源分配變量和0.5LT（T+1）個訂閱限額變量，因此該問題的搜索空間需設定為L+0.5LT（T+1）維空間，粒子則設定為維度為L+0.5LT（T+1）的向量。為此，第n個粒子的位

2.1.2 種群初始化

PSO中每個粒子都代表了一個候選解，即一組資源配置量及訂閱限額量，因此需要初始化PSO的粒子，使得每個粒子對應一個合法的候選解。PSO從一個種群大小為Npop的初始粒子群開始，初始化過程主要包括初始化粒子的位置和速度兩個方面，具體創建方法如下。

1）位置初始化

為了保證每個粒子代表的候選解都是合法的，需要對初始位置向量進行限制，使其滿足資源配置和訂閱限額的約束條件，用式（6）構造初始種群中各粒子前L個元素的位置：

其中：r表示0～1的隨機變量；tv（m）表示為前m種軟件分配資源后，剩余的虛擬機資源，tv（1）=V。式（6）可以保證粒子前L個元素位置向量之和等于運營商總資源量，即滿足模型的資源約束條件。粒子中其余元素的初始位置根據式（7）生成。

其中：dl，i，j為（l，i，j）的訂閱需求所服從泊松分布的參數，符號·」表示向下取整。

2）速度初始化

其中：rb是一個二進制隨機數；r是0～1的隨機變量；Δa是一個預先確定的常數。速度向量中剩余的元素由式（9）生成。

其中：Δb是一個預先確定的常數。

2.1.3 速度更新

1）計算速度

在迭代過程中，粒子n在第k次迭代的速度及其到自身最佳位置pn和全局最佳位置g的距離決定了下一步的速度，該粒子在k+1次迭代時的速度Vk+1n計算公式如下：

Vk+1n=wVkn+c1r1（pn-Xkn）+c2r2（g-Xkn）（10）

其中：Vkn是粒子n在第k次迭代中的速度；Xkn是粒子n在第k次迭代中的位置；pn是粒子n的歷史最佳位置；g是種群中所有粒子的歷史最佳位置；w為慣性權重;r1和r2為0～1的隨機值；c1和c2是控制粒子在搜索空間中運動的加速度因子。

2）速度調整程序

算法1 速度調整程序

2.1.4 位置更新

在速度調整后，將對粒子進行位置更新。粒子下一步迭代所處的位置取決于當前位置及其下一步的運動速度。因此，粒子n在第k+1次迭代中的位置更新公式為

Xk+1n=Xkn+Vk+1n（11）

在完成位置更新后，需對粒子的自身最佳位置和全局最佳位置進行更新，用于更新下一次迭代的速度。PSO通過比較粒子當前的位置和自身歷史最佳位置來更新每個粒子的局部最佳位置pn，更新方法如下：

同時，如果粒子局部最佳位置的目標函數f（pn）大于全局最佳位置的目標函數f（g），則更新全局最佳位置。設置最大迭代次數kmax作為算法的停止條件，PSO的偽代碼如算法2所示。

算法2 PSO

2.2 粒子群算法中的參數估計難題

運用經典粒子群算法可以完成對模型的求解，但是該算法的性能在很大程度上依賴于加速度因子參數的選擇［28］，參數選擇不當可能導致算法陷入局部最優解，同時在求解高維問題時計算效率較低。PSO中參數的最佳取值往往與模型特性有關，因此需要采用試錯方法進行調參。然而，采用傳統的試錯方法需要耗費大量的經驗和計算時間，在求解NP難題時面臨極大的挑戰。

在本文的問題背景下，運營商需要實時決定是否接受用戶的訂閱請求，考慮到SaaS運營商會面臨SLA違約賠付的風險，這要求運營商必須在短時間內完成訂閱限額和資源配置的決策，并相應地給出接受或拒絕請求的反饋，這對算法的求解效率提出了更高的要求。為了解決這一問題，本文將Q學習算法嵌入到PSO中來動態調整PSO的參數，提高粒子搜索能力，在避免算法陷入局部最優解的同時提高算法求解效率，提高算法性能。

2.3 Q學習-粒子群融合算法

2.3.1 強化學習

強化學習是機器學習的一種學習方式，主要由智能體、環境、狀態、動作與獎勵五個組件組成。在反復實驗中智能體與環境進行交互，通過環境給予的獎勵不斷訓練優化其狀態與動作的對應關系，從而獲得最大回報的學習機制。具體模型如圖3所示。

本文重點研究強化學習算法中帶有Q值表的Q-學習算法，該算法將不同狀態下的學習經驗即狀態與動作的對應關系存儲在Q值表中，其中行代表狀態，列代表動作，Q表的示意圖如圖4所示，然后根據Q值選取獲得最大收益的動作。

在Q-學習算法中，智能體通過學習給定動作獲得獎勵來更新Q值表。初始Q值表中所有值都等于零，這表示智能體沒有經驗供算法使用。設S={s1，s2，…，sm}為系統的狀態集合，A={a1，a2，…，am}為待執行的候選動作集合。智能體在不同的狀態下，根據Q值表中提供的累積信息進行動作選擇，此時環境給出獎勵rt+1，狀態變為st+1。Q表的值根據智能體的經驗，通過貝爾曼方程進行更新，具體如下：

Q（st，at）=（1-α）Q（st，at）+α（rt+γmaxaQ（st+1，at+1））（13）

其中：Q（st，at）是在狀態st下執行動作at獲得的Q值；γ是折扣因子，α是Q-學習算法的學習因子，決定算法對于獎勵的反映程度。該值越大，每次實驗后Q值表的波動也越大。算法3中給出了Q-學習的偽代碼。

算法3 Q-學習算法

2.3.2 Q學習調參

在利用PSO搜索解的過程中，加速度系數c1和c2是兩個重要的參數，這些參數會極大影響算法的效率［30］。因此，本文將在PSO的基礎上嵌入Q-學習算法，來幫助PSO在每次迭代中選擇c1和c2最優對。Q學習-粒子群融合算法試圖根據Q值表中的累積信息選擇加速度系數c1和c2的最佳對。在該算法中，PSO被認為是一個環境，每次迭代都將該環境的狀態從st更改為st+1。具體實現步驟如圖5所示，算法中狀態、動作、策略及獎勵值定義如下。

1）狀態

在這里環境狀態被定義為一個加權函數，其包含平均種群適應度Z*1、總體方差Z*2和最佳個體適應度Z*3三個特征，具體表示為

s*=w1Z*1+w2Z*2+w3Z*3（14）

其中：w1、w2和w3是權重系數，w1+w2+w3=1。式（14）中的Z*1、Z*2和Z*3定義如下：

式（15）計算第k次迭代中種群的平均適應度，并通過除以第一次迭代的平均適應度對其進行歸一化。式（16）表示第k次迭代中的總體方差，同樣通過除以第一次迭代的方差進行歸一化。最后根據式（17）計算歸一化后的最佳個體適應度作為狀態函數的第三個分量。

2）動作

算法中的動作集被定義為A={（c11，c12），（c21，c22），…，（ck1，ck2）}，表示PSO第k次迭代時用于更新速度向量的加速度系數c1和c2的值。加速度參數在限定范圍內被劃分為若干個離散值，并分別對應一個Q值，在算法執行過程中根據Q值的大小來選擇動作。

3）策略

在Q學習-粒子群融合算法中使用ε-貪心策略作為動作選擇策略［24］，其是一種基于隨機性和貪心性的策略，在選擇動作時會以1-ε的概率選擇當前已知最優的行動，以ε的概率選擇隨機行動，其中ε∈（0，1），并通常會取一個較小的值。該策略可以平衡探索和利用之間的關系，保證算法在搜索過程中有機會嘗試一些新的選擇，不會陷入過于貪心的困境。ε-貪心策略具體如式（18）所示。

其中：ε為勘探率系數。

4）獎勵

在每次迭代結束后需要計算獎勵來反映算法當前所選擇動作的優劣，該算法的獎勵r*根據最佳個體適應度r1和平均群體適應度r2求取。

在這里，計算以上兩個函數值并進行比較，選擇其中較大值作為第k次迭代的獎勵，即r*=max{r1，r2}。如果選擇的獎勵優于第k-1次迭代中的獎勵，則說明當前選擇的參數對是有效的，將計算得出的獎勵r*作為反饋返回給算法，并據此對Q值表進行更新。算法4展示了Q學習-粒子群融合算法的偽代碼。

算法4 Q學習-粒子群融合算法

3 數值實驗

3.1 實驗參數設定

為了評價本文提出的Q學習-粒子群融合算法（Ｑ-PSO）在求解資源配置及訂閱限額問題上的性能，本節開發了小型和大型兩種規模問題集。問題集由商品類別數量L和規劃周期T來區分。小型和大型兩個問題集的（L，T）值分別固定為（3，3）和（4，6）。

本文利用PSO求解SaaS資源配置及訂閱限額模型，其中算法中啟發式參數描述為種群總體規模Npop，最大迭代次數kmax，慣性權重w，加速度系數c1和c2以及與粒子速度相關的跳步Δa和Δb。在實驗中，通過下列方法控制參數值，將種群總體規模Npop設置為2L+T，最大迭代次數kmax設為5（L+T），慣性權重w設為0.85，Δa和Δb均設為10，加速度系數c1和c2通過Q-學習算法獲得。算法均用Python編程軟件編寫，并在配置為2.7 GHz Intel Core i5處理器和8 GB內存的MacBook Pro個人筆記本電腦上運行。

3.2 模型及算法有效性驗證

為驗證本文算法在計算效率與決策效果上的表現，本節將Q-PSO與經典PSO以及目前廣泛應用于求解資源配置問題的基于混沌映射的PSO算法（chaotic particle swarm optimization，CPSO）［31～33］進行比較。其中CPSO在PSO基礎上引入混沌映射策略，對初始化種群和位置更新的計算方式進行改進，并通過對粒子位置進行變異更新來跳出局部最優解，從而提高了算法的求解準確性。因此本節將從算法的準確性和求解效率兩個方面，對Q-PSO與CPSO進行對比來驗證本文算法的有效性。

為了驗證算法的準確性，本節對精確算法與近似算法對小型規模問題求解的結果進行比較，其中精確算法的結果利用CPLEX求解得到，而近似算法則為PSO、CPSO以及本文Q-PSO，求解的具體結果如圖6所示。

圖6分別展示了采用CPLEX求解器、PSO、CPSO以及Q-PSO的求解結果，其中橫坐標為訂閱請求標識，縱坐標為求解的訂閱限額值。從圖6可以發現采用四種方法的求解結果相似，說明本文算法求得的近似解與最優解的差距較小，算法的準確性較高。

為了貼合實際，后續采用大規模問題數據集進行仿真。利用啟發式算法求解資源配置及訂閱限額模型，得到的可行解如表3所示，此處僅展示在大規模問題下第一個測試集q11的求解結果。

表3分別給出了利用PSO、CPSO和Q-PSO求解得到的結果，根據基于Q-PSO結果可知，SaaS運營商分配給各個產品類別的虛擬機資源量分別為40 970、40 122、45 682和73 224。由表3可知，當到達一個新的訂閱需求為（1，2，3）時，需要判斷當前系統中該訂閱需求的訂閱數量是否已達到379，只有當訂閱數量未達到379時，SaaS運營商才能夠接受該用戶的訂閱需求。同理可得，如果訂閱（2，1，3）的數量已經達到了315，那么SaaS運營商將不再接受任何相同的訂閱需求。

接下來利用平均目標函數、最佳目標函數、平均CPU時間和相對偏差指數（RDI）四個指標來評價解的質量并比較三種算法的有效性。其中RDI計算公式如下［34］：

其中：Algsol表示當前算法的目標函數值；Maxsol表示算法中的最優函數值；Minsol表示所有實驗中最小函數值。RDI值越小，表示算法性能越好。每種規模的問題利用9個測試集重復求解。大規模問題的求解結果如表4所示。

從表4可以發現，在對本文模型的求解中，利用Q-學習調參的方法能在不增加計算時間的情況下增強了PSO的性能，即Q-PSO求解不同規模的有約束非線性模型要比經典粒子群算法表現更好；相較于CPSO而言，Q-PSO的求解準確性較低，但是求解效率高，說明本文算法在不損失求解準確度的同時提高了求解效率。

為了衡量算法的性能可靠性，本節繪制元啟發式算法的平均目標函數箱線圖，結果如圖7所示。從圖7可以看出，Q-PSO及CPSO的箱體均小于PSO求解結果的箱體，可以認為Q-PSO的嵌入成功地降低了算法求解的方差，即Q-PSO比PSO具備更高的可靠性和魯棒性。三種算法的收斂圖如圖8所示。

從圖8可以看出在不同規模下，Q-PSO都比PSO收斂得更快，并獲得了更優解；對比CPSO和Q-PSO的收斂結果可以發現，在不同規模下Q-PSO收斂更快，且兩者的求解結果相近，說明Q-PSO在不降低算法準確性的同時提高了求解效率。此外，為了了解Q-學習算法如何自適應PSO的參數，圖9展示了算法在迭代過程中加速度參數的變化趨勢。

除了上述比較外，實驗還對每種問題規模求解得到的平均目標函數進行統計比較。首先，根據表4的實驗結果繪制大型規模問題的正態概率圖，結果如圖10所示。

從圖10可以發現，三種算法所求結果的p值都大于0.05，說明三種算法所求得的平均目標函數都呈正態分布。接著根據單因素方差分析方法的流程假設三組數據兩兩之間的總體方差相等，即服從同一正態分布。其中，Q-PSO與經典PSO的檢驗結果如表5所示，發現p值小于0.05，因此可以拒絕原假設，即認為組間差異顯著。由此可知，兩種算法所求得的平均目標函數之間存在顯著差異，即基于Q-PSO的性能高于PSO。Q-PSO與CPSO的檢驗結果如表6所示，發現p值大于0.05，說明利用兩種算法所求得的結果無顯著差異，即Q-PSO在提高求解效率的同時保證了求解的準確性。

綜上，在解決訂閱限額及資源配置問題上，本文Q-PSO具有更好的性能表現。Q-PSO通過自適應地調整PSO的參數，顯著提高了算法的收斂速度，同時保證了求解的準確性，具備更高的穩定性和魯棒性。

3.3 不同情境下實驗結果分析

為了在不同在線率差異場景下，優化資源配置及訂閱限額策略，本文引入了資源爭用比來描述資源利用情況，資源爭用比指的是某一軟件的潛在用戶數與分配給該軟件的虛擬機資源之間的比例［35］，用c_rl來表示軟件l在銷售期內的資源爭用比。資源爭用比的具體計算方法為

圖11展示了四種軟件在不同在線率差異下的最優資源爭用比變化情況，可以據此分析不同情境下最優資源配置及訂閱限額策略。

圖11反映出四種軟件的資源爭用比均隨著在線率差異率的升高而降低，說明在需求波動大的情境下，即用戶對不同軟件的在線率差異率較大時，運營商應盡可能降低軟件的資源爭用比，通過配置足量的虛擬機資源并設定嚴格的訂閱限額來保障軟件的服務質量，從而減少違約賠付成本來提高收益；相反，在需求波動小的情境下，即用戶對不同軟件的在線率差異率較小時，運營商可以提高軟件的資源爭用比，通過放寬訂閱限額來搶占更大的市場。此時由于在線率差異較小，該策略不會造成資源閑置，可以在保證資源利用率的同時提高運營商收益。此外，圖11還反映了隨著在線率差異率的升高，軟件4的資源爭用比下降幅度最大，并且一直低于其他軟件。由參數設置可知，相較于其他軟件，軟件4的平均在線率最高且最穩定，因此運營商應盡可能為在線率高且穩定的軟件配置更多的虛擬機資源，并相應地放寬訂閱限額，從而增加收益。

4 結束語

為了保障軟件可用性，在提供服務的過程中SaaS運營商需要提前為各種軟件配置虛擬機資源，同時需要考慮各種訂閱請求的訂閱限額。本文針對該問題提出了一個以收益最大化為目標的有資源約束的非線性整數規劃模型。模型考慮了用戶對軟件的在線率差異、用戶訂閱時間差異以及運營商的SLA違約賠付等實際因素，以此來研究SaaS運營商在不同的時間規劃期內如何確定分配給各類軟件的虛擬機資源量以及在SLA限制下每種訂閱需求的訂閱限額。由于求解所建立模型的計算復雜度較高，本文采用PSO進行求解，同時提出了一種基于Q-PSO的改進方法。該算法利用Q學習對PSO進行動態調參，能更好地避免陷入局部最優陷阱，提高PSO性能。借助仿真實驗，本文針對需求波動大和需求波動小兩種情境分別得出了最優資源配置及訂閱限額策略。當處于需求波動大的情境下時，運營商應盡可能降低軟件的資源爭用比，通過配置足量的虛擬機資源并設定嚴格的訂閱限額來保障軟件的服務質量，減少違約賠付成本；相反，當處于需求波動小的情境下時，運營商可以提高軟件的資源爭用比，通過放寬訂閱限額來搶占更大的市場，此時由于在線率差異較小，該策略不會造成資源閑置，可以在保證資源利用率的同時提高運營商收益。其中，針對在線率高且穩定的軟件，運營商應為其配置更多的虛擬機資源，并相應地放寬訂閱限額來增加收益。上述策略在實踐中具有指導意義，可以幫助運營商在不同場景下進行更合理的銷售決策，實現收益最大化。

本文只考慮了SaaS訂閱模式下的資源配置及訂閱限額組合優化問題，后續可以針對SaaS的其他定價策略，如按需付費及現貨定價等模式展開研究。

參考文獻：

［1］吳士亮， 仲琴. 云計算環境下應用軟件服務定價策略研究——基于兩階段壟斷模型的分析［J］. 價格理論與實踐， 2017，21（8）： 144-147. （Wu Shiliang， Zhong Qin. Pricing strategy of application access service in cloud computing environment-based on the analysis of two-stage model of monopoly［J］. Price： Theory & Practice， 2017， 21（8）： 144-147.）

［2］Gartner Inc.. Gartner forecasts worldwide public cloud end-user spending to reach nearly SMonlam Uni Chouk|Ap 500 billion in 2022［EB/OL］. （2022-04-19） ［2023-07-11］. https：//www.gartner.com/en/newsroom/press-releases/2022-04-19-gartner-forecasts-worldwide-public-cloud-end-user-spending-to-reach-nearly-500-billion-in-2022.

［3］Luo Yongji， Yan Haifeng， Zhang Shoushuai. Simulation-based integrated optimization of nesting policy and booking limits for revenue management［J］. Computers & Industrial Engineering， 2020， 150（4）： 106864-106878.

［4］Lee I. Pricing and profit management models for SaaS providers and IaaS providers［J］. Journal of Theoretical and Applied Electronic Commerce Research， 2021，16（4）： 859-873.

［5］Ladas K， Kavadias S， Loch C. Product selling vs. pay-per-use ser-vice： a strategic analysis of competing business models［J］. Management Science， 2022， 68（7）： 4964-4982.

［6］Zhang Zan. Competitive pricing strategies for software and SaaS products［J］. Information & Management， 2020， 57（8）： 103367.

［7］Zhang Longchang， Bai Jing， Xu Jiajun. Optimal allocation strategy of cloud resources with uncertain supply and demand for SaaS providers［J］. IEEE Access， 2023， 11： 80997-81010.

［8］Zhu Jian， Li Qian， Ying Shi. SAAS parallel task scheduling based on cloud service flow load algorithm［J］. Computer Communications， 2022， 182（6）： 170-183.

［9］Sikora T D， Magoulas G D. Neural adaptive admission control framework： SLA-driven action termination for real-time application service management［J］. Enterprise Information Systems， 2021， 15（2）： 133-173.

［10］Han Bin， Sciancalepore V， Costa-Perez X， et al. Multiservice-based network slicing orchestration with impatient tenants［J］. IEEE Trans on Wireless Communications， 2020，19（7）： 5010-5024.

［11］Pimentel V， Aizezikali A， Baker T. An evaluation of the bid price and nested network revenue management allocation methods［J］. Computers & Industrial Engineering， 2018，115（1）： 100-108.

［12］王航臣， 曹宇露， 趙迪. 一種基于蒙特卡羅模擬的航空公司機票超售數量確定方法［J］. 民用飛機設計與研究， 2021，10（2）： 130-136. （Wang Hangchen， Cao Yulu， Zhao Di. A method to determine the overbooking quantity of airline tickets based on Monte Carlo simulation［J］. Civil Aircraft Design & Research， 2021，10（2）： 130-136.）

［13］鄧連波， 許景， 彭齊， 等. 基于隨機規劃的高鐵列車超售策略分析［J］. 鐵道科學與工程學報， 2022，19（10）： 2813-2819. （Deng Lianbo， Xu Jing， Peng Qi， et al. Overbooking strategy analysis of high-speed train based on stochastic programming［J］. Journal of Railway Science and Engineering， 2022，19（10）： 2813-2819.）

［14］Nababan A A， Jannah M， Nababan A H. Prediction of hotel booking cancellation using K-nearest neighbors（K-NN） algorithm and synthe-tic minority over-sampling technique（SMOTE）［J］. INFOKUM， 2022， 10（3）： 50-56.

［15］You P S， Hsieh Y C， Huang C M. A particle swarm optimization based algorithm to the Internet subscription problem［J］. Expert Systems with Applications， 2009， 36（3）： 7093-7098.

［16］Chen Fuzan， Lu Aijun， Wu H， et al. Compensation and pricing strategies in cloud service SLAs： considering participants’ risk attitudes and consumer quality perception［J］. Electronic Commerce Research and Applications， 2022， 56（2）： 101215.

［17］Jain R， Sharma N. A quantum inspired hybrid SSA–GWO algorithm for SLA based task scheduling to improve QoS parameter in cloud computing［J］. Cluster Computing， 2023， 26（6）： 3587-3610.

［18］Buyya R， Garg S K， Calheiros R N. SLA-oriented resource provisioning for cloud computing： challenges， architecture， and solutions［C］//Proc of International Conference on Cloud and Service Computing. Piscataway， NJ： IEEE Press， 2011： 1-10.

［19］Yuan Shuai， Das S， Ramesh R， et al. Availability-aware virtual resource provisioning for infrastructure service agreements in the cloud［J］. Information Systems Frontiers， 2023， 25（4）： 1495-1512.

［20］Gabrel V， Manouvrier M， Moreau K， et al. QoS-aware automatic syntactic service composition problem： complexity and resolution［J］. Future Generation Computer Systems， 2018， 80（3）： 311-321.

［21］Kashani M H， Mahdipour E. Load balancing algorithms in fog computing［J］. IEEE Trans on Services Computing， 2022， 16（2）： 1505-1521.

［22］Ghafouri S H， Hashemi S M， Hung P C K. A survey on web service QoS prediction methods［J］. IEEE Trans on Services Computing， 2020， 15（4）： 2439-2454.

［23］Fallahi A， Bani E A， Niaki S T A. A constrained multi-item EOQ inventory model for reusable items： reinforcement learning-based differential evolution and particle swarm optimization［J］. Expert Systems with Applications， 2022， 207（11）： 118018-118038.

［24］Chen Ronghua， Yang Bo， Li Shi， et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem［J］. Computers & Industrial Engineering， 2020， 149（11）： 106778.

［25］Chang Chenglin， Lin Qucheng， Liao Zuwei， et al. Globally optimal design of refinery hydrogen networks with pressure discretization［J］. Chemical Engineering Science， 2022， 247： 117021.

［26］郭文文， 計明軍， 祝慧靈. 集裝箱碼頭泊位與堆場協調分配模型與算法［J］. 系統工程， 2020，38（3）： 64-72. （Guo Wenwen， Ji Mingjun， Zhu Huiling. Model and algorithm of coordinated allocation for berth and yard in container terminals［J］. Systems Enginee-ring， 2020， 38（3）： 64-72.）

［27］Yin Lei， Liu Jin， Fang Yadong， et al. Two-stage hybrid genetic algorithm for robot cloud service selection［J］. Journal of Cloud Computing， 2023， 12（1）： 1-16.

［28］王純子， 郭偉， 張斌. 求解非線性混合整數規劃的算法設計與仿真［J］. 計算機科學與探索， 2013，7（9）： 854-864. （Wang Chunzi， Guo Wei， Zhang Bin. Algorithm design and simulation of solving nonlinear mixed integer programming problem［J］. Journal of Frontiers of Computer Science and Technology， 201jC1+kf5T2Byqo5Qd2mPTDA==3， 7（9）： 854-864.）

［29］Kennedy D D， Zhang Haibo， Rangaiah G P， et al. Particle swarm optimization with re-initialization strategies for continuous global optimization［M］. New York： Nova Science Publishers， 2013.

［30］Hou S， Gebreyesus G D， Fujimura S. Day-ahead multi-modal demand side management in microgrid via two-stage improved ring-topology particle swarm optimization［J］. Expert Systems with Applications， 2024， 238（2）： 122135.

［31］Zheng Qingshuai， Gu Yujiong， Liu Yuhang， et al. Chaotic particle swarm algorithm-based optimal scheduling of integrated energy systems［J］. Electric Power Systems Research， 2023， 216： 108979.

［32］劉陳偉， 孫鑒， 雷冰冰， 等. 基于改進粒子群算法的云數據中心能耗優化任務調度策略［J］. 計算機科學， 2023， 50（7）： 246-253. （Sun Chenwei， Sun Jian， Lei Bingbing， et al. Task scheduling strategy for energy consumption optimization of cloud data center based on improved particle swarm algorithm［J］. Computer Science， 2023， 50（7）： 246-253.）

［33］Zhang Feng. Intelligent task allocation method based on improved QPSO in multi-agent system［J］. Journal of Ambient Intelligence and Humanized Computing， 2020，11（2）： 655-662.

［34］Sadeghi J， Sadeghi S， Niaki S T A. Optimizing a hybrid vendor-managed inventory and transportation problem with fuzzy demand： an improved particle swarm optimization algorithm［J］. Information Sciences， 2014， 272（8）： 126-144.

［35］You P S， Hsieh Y C， Ikuta S. A heuristic to bandwidth allocation and sales limit setting for Internet service providers［J］. International Journal of Systems Science， 2012， 43（11）： 2135-2143.