基于MPSO算法的IT服務商聯合體的選擇

摘要：為了高效、靈活且低成本地存儲和處理信息數據，采用IT服務商提供的云解決方案.使用灰色關聯綜合評價模型確定與計算服務、存儲服務和軟件服務密切相關的響應時間、服務質量及服務成本等優化指標，對多目標進行定量分析，通過MPSO算法進行尋優求解.實例證明了算法的合理性和有效性.

關鍵詞：IT服務商；聯合體選擇；灰色關聯；多目標優化；MPSO算法；云解決方案

中圖分類號：TP393.09;TP18文獻標志碼：A

0引言

數據是具有重要價值的資產，例如企業的生產經營信息、網上的商品交易信息、人與物的位置信息等.近年來，數據呈幾何級數增長，大大超過現有企業IT架構和設備設施的承載能力，實時性要求也遠遠超過現有的計算能力.若要高效使用這些數據資產，必須依靠IT服務商提供的專業服務，通過這些專業服務對大數據進行處理，最終獲得有價值的信息并用于決策.目前，這些專業服務都是基于云計算的.

云計算是一種新的分布式計算.基于網絡的云服務具有共享、按需分配、可度量及彈性強等特點.通過網絡云，將龐大的數據計算處理程序分解成無數小程序，然后由多臺服務器組成的系統對這些小程序的結果進行處理和分析，并返回給用戶.由于處理過程中需要用到存儲資源、計算資源、軟件資源、網絡資源和安全資源等，阿里云、華為云及騰訊云等眾多專業IT服務商應運而生.因為不同的IT服務商優勢特點各不相同，對于企業而言，如何選擇最合適的IT服務商直接關系其利益.因此，如何根據應用需求選擇IT服務商聯合體實現企業利益最大化是本研究要探討的問題.

針對聯合體選擇的問題，很多研究者在不同領域都進行了探索［1-5］，但這些研究很少涉及云服務市場的資源優化配置問題.本研究選取來源于灰色關聯分析綜合評價模型的優化指標，用改進的粒子群優化（modified particle swarm optimization，MPSO）算法求解IT服務商的最優聯合體.

1問題闡述與數學模型

1.1問題闡述

對IT服務商合作組合進行篩選的最終目的是為了對云服務市場中的計算、存儲等各類資源進行優化配置，最大化程度滿足客戶需求.本研究使用灰色關聯分析綜合評價模型［6］選取優化指標.假設x0（k）為參考序列，表示云服務資源優化配置率的因子序列，而xi（k）為比較序列，表示優化待定選取指標的因子序列（k=1，2，...，n;i=1，2，...，m），則根據灰色關聯分析理論可以推斷下列式子成立.

ξ（X0（k），Xi（k））=

minimink｜x0（k）-xi（k）｜+ρ·maximaxk｜x0（k）-xi（k）｜｜x0（k）-xi（k）｜+ρ·maximaxk｜x0（k）-xi（k）｜（1）

ξ（X0（k），Xi（k））=1nni=1r（X0（k）-Xi（k））（2）

式中，ξ（X0（k），Xi（k））表示所需服務優化指標因子和云服務資源優化配置率之間的關聯度.

δ（X0，Xi）=ξ（X0，Xi）Ni=1ξ（X0，Xi）（3）

式中，δ（X0，Xi）表示所需服務優化指標因子在整個云服務資源優化配置率的比重，表示相應的優化指標對資源最優配置的重要程度.

根據灰色關聯分析理論得出優化指標因子權重排在前3位的是服務響應因子、服務質量因子和服務成本因子.為了實現目標優化的要求，本研究主要考量服務的響應時間、服務質量和服務成本等因素，并用目標函數的形式來描述，從而將選擇IT服務商聯合體問題轉變為優化目標函數，最終使組成的IT服務商聯合體更有競爭力、資源配置更優化.

IT服務商聯合體的選擇問題描述如下：假設IT服務商聯合體需向n個客戶提供某種服務，僅存在m個IT服務商具備提供該服務的能力，即候選聯合體，此時優化目標就是選擇最佳的聯合體去完成某項任務.該問題用數學式子表示為：

任務ω={ωr}=［ω1，ω2，…，ωn］，r=1，2，…，n，則對于任務ωr有候選聯合體如下：

Pr={Prj}={Pr1，Pr2，…，Prm}， j=1，2，…，m（4）

式中，Prj=［trj，qrj，crj］，而trj、qrj與crj分別表示響應時間、服務質量與服務成本.

1.2數學模型

1）多目標優化模型

G（x）=min［g1（x），g2（x），…，gn（x）］（5）

fr（x）≥0（6）

式中，gr（x）是目標函數，fr（x）是約束條件.

為了能篩選出最佳IT服務商聯合體，組成的聯合體應滿足目標函數的要求.

2）目標函數

響應時間目標函數：動態聯合體中IT服務商候選聯合體的響應時間最小表示為min T.

min T=nj=1mr=1Trjθrj（7）

服務質量目標函數：動態聯合體中IT服務商候選聯合體的服務質量最優表示為max Q.

max Q=nj=1mr=1Qrjθrj（8）

服務成本目標函數：動態聯合體中IT服務商候選聯合體的服務成本最小表示為min C.

min C=nj=1mr=1Crjθrj（9）

上述式中，θrj=1如果選擇Prj

0否則.Prj表示任務r由候選聯合體j承擔，且nr=1 θrj=1（j=1，2，…，m）.

3）解決多目標優化問題的方式

對于多目標優化問題的解決，通常是將其對應的多目標優化函數轉換為單目標優化函數，從而降低問題解決的難度，最終轉換成如式（10）所示的目標函數形式：

min g（X）=ω1C+ω2T-ω3Q（10）

式中，ωr（r=1，2，3）表示權重，決定動態聯合體中各屬性組成比例的高低.同時，ωr須滿足3r=1 ωr=1.

2應用分析

2.1算例背景

IT服務商聯合體共需提供3種服務，分別是計算服務、存儲服務和軟件服務.假定針對上述服務的IT服務商候選聯合體分別有3個、3個和5 個，其相關數據屬性如表1所示.本研究用A1～A3、B1～B3、C1～C5表示提供上述3種服務的IT服務商，并為每種服務選擇1個IT服務商，以便能尋找到最佳的IT服務商聯合體.

2.2模型求解

本研究先確定權重因子ωi（i=1，2，…，n）.研究對象X={X1，X2，…，Xm}表示所選擇的IT服務商的集合，G={G1，G2，…，Gn}是研究對象測量得到的指標，而W={W1，W2，…，Wn}T表示指標權重的向量，其中，3j=1Wj=1，且Wj≥0（j=1，2，…，n）.決策矩陣［7-8］為A=［αrj］m×n，其中αrj是研究對象即IT服務商Xr在指標Gj上的取值.由于各個指標集的量綱不同，所以在計算時先對決策矩陣進行規范化，規范后用A表示.

通過下列公式表示各指標的權重：

max Z=（Z1，Z2，…，Zn）（11）

nj=1Wj=1，Wj≥0（j=1，2，…，n）（12）

式中，Zr=nj=1｜a*j-arj｜wj1+｜a*j-arj｜wj，且指標Gj的“理想值”是a*j，實際計算時可取a*j=max{a1j，a2j，…，amj}.研究對象與理論最佳方案之間的距離用Zr表示，同時尋找和確定合適的權重向量W，使得Zr（r=1，2，…，n）達到最大值，這樣可以更大限度地將各個研究對象區分開來，以便盡快找到最優方案.

利用線性綜合方法求解模型，即

max Z′=nr=1Zr=nj=1｜a*j-arj｜wj1+｜a*j-arj｜wj（13）

nj=1Wj=1，Wj≥0（j=1，2，…，n）（14）

即可解出W={W1，W2，…，Wn}.

2.3數據標準化處理

不同的指標具有不一樣的量綱，因此本研究需要對這些不同量綱的指標進行標準化處理，使其縮放到相同的數據區間和范圍，以減少規模、特征及分布差異等對模型的影響.原始數據用X={X1，X2，…，Xn}表示，標準化處理后的數據用Y={Y1，Y2，…，Yn}表示.一組數據中的最小值用min X表示，最大值用max X表示［9］.標準化的操作如下：

Yi=Xi+min Xmax X-min X（15）

3多目標優化模型的MPSO算法實現

多目標優化是針對應用中含有多個目標和多個約束的問題進行優化.目前，解決多目標優化問題主要有遺傳算法（genetic algorithm，GA）和粒子群優化（particle swarm optimization，PSO）算法.GA能夠較好地找到全局最優，但是收斂速度較慢.PSO算法收斂速度較快，但是容易陷入局部最優.為了保持尋優過程中種群的多樣性且解決容易陷入局部最優的問題，本研究引入跳數改進機制對PSO算法進行改進，以實現多目標優化.

3.1多目標優化的基本定義

簡單地講，多目標優化問題就是同時需要優化多個目標函數，將這些目標函數組合成目標函數向量.用數學描述多目標優化問題如下：

min F（x）=［f1（x），f2（x），…，fn（x）］（16）

s.t.gi（x）≤0（或≥0），i=1，2，…，n（17）

式中，fi（x）為目標函數，gi（x）為不等式約束，且i=1，2，…，n.

3.2跳數改進機制

本研究引入的一種跳數改進機制［10］可以有效防止外部存儲庫中的粒子陷入局部最優.該機制操作有2個方向：通過內部跳數機制加大對已知搜索區域的搜索深度；通過外部跳數機制增強搜索未知區域的能力.通過該機制可以為外部存儲庫中的粒子提供更多的有效參考信息，獲得更多的非劣解，使種群的多樣性得到保證.引入已知搜索區域外部存儲庫中的自由向量α、β，未知搜索區域的2個新搜索向量用Aα和Aβ表示.

Aα=α+a（α-β）

Aβ=β+b（β-α）0lt;a，blt;1（18）

3.3算法步驟

1）初始化微粒群.用Pbest表示每個個體歷史最佳位置，取初始位置為其初始值.每個粒子的當前最佳位置Pbest通過下列式計算得到：

Vij（g+1）=ωVij（g）+c1r1ij（g）

［Pbestij（g）-xij（g）］+c2r2ij（g）［Gbestj（g）-xij（g）］（19）

xij（g+1）=xij（g）+Vij（g+1）（20）

Pbestij（g+1）=Pbestij（g），如果f（xij（g+1））≥

f（Pbestij（g））

xij（g+1），如果f（xij（g+1））lt;

f（Pbestij（g））（21）

式中，ω是平衡全局搜索和局部搜索的參數.

2）粒子群中每個粒子空間位置的迭代更新如下：

Gbestj（g）=argminPbestijf（Pbestij（g+1））（22）

3）更新外部存儲庫.利用跳數改進機制的方法將粒子群中更新后的非支配解與外部存儲庫中的非劣解進行對比，最終決定粒子群中的非劣解是否需要存放到外部歸檔集中.

4）更新粒子的局部最優位置，確定存檔的粒子.

5）若滿足終止條件則終止運算，否則轉入步驟2）進行迭代.

3.4結果分析

利用Matlab 軟件對根據問題構建的模型進行求解.根據2.2節，權重值分別取W1=0.05、W2=0.05、W3=0.9［5］，則通過計算得到最佳優化選擇聯合體的結果，分別是提供計算服務的服務商A1、提供存儲服務的服務商B1、提供軟件服務的服務商C2，即對應最佳聯合體的IT服務商組合是（A1，B1，C2）.隨機選擇包含IT服務商組合（A1，B1，C2）在內的任意15組IT服務商組合，從響應時間、服務質量和年成本屬性進行對比，其目標函數值如圖1所示.

從圖1可以直觀看出，IT服務商組合（A1，B1，C2）對應的目標函數值在隨機選取的15組IT服務商組合中其目標函數值最小，由此可以得出（A1，B1，C2）即為最佳IT服務商組合.

4結束語

IT服務商聯合體的選擇非常具有現實意義，但影響選擇的因素較多，因此篩選的過程比較復雜.要確保篩選結果的有效性，首先需要確定影響選擇的多個關鍵指標和因素，其次構建多目標優化模型，再使用MPSO算法求解，通過求得的最優適應度值來最終獲取最佳的IT服務商聯合體方案.本研究通過實例驗證了算法的合理性和實用性.由于多目標優化應用場景眾多，本研究為此類應用提供了新的思路和方法.未來將針對多目標優化及優化過程中容易陷入局部最優等問題展開進一步的研究和探索，力求取得更好的效果.

參考文獻：

［1］盧志剛，申康.基于粒子群蟻群算法的供應鏈合作伙伴選擇研究［J］.計算機工程與科學，2016，38（5）：946-953.

［2］Wang X H，Yang T J，Yang H Y.Design of the information system model frame for virtual enterprises［C］//Proceedings of Conference on Web Based Business Management（WBM 2012）.Shanghai，China：IEEE，2012：725-728.

［3］Chen D Q，Preston D S，Xia W D.Enhancing hospital supply chain performance：a relational view and empirical test［J］.J Oper Manag，2013，31（6）：391-408.

［4］Tao F，Zhang L，Zhang Z H，et al.A quantum multi-agent evolutionary algorithm for selection of partners in a virtual enterprise［J］.CIRP Ann Manuf Technol，2010，59（1）：485-488.

［5］康艷芳，聶規劃，陳冬林，等.基于遺傳算法的云服務商伙伴選擇問題研究［J］.計算機應用研究，2015，32（1）：26-29.

［6］楊柳，羅文倩，鄧春林，等.基于灰色關聯分析的輿情分級與預警模型研究［J］.情報科學，2020，38（8）：28-34.

［7］楊堅.基于群決策模型的虛擬企業合作伙伴選擇問題研究［J］.統計與決策，2011，27（16）：42-44.

［8］陳振頌，王先甲，王欣儀，等.基于Pd-Hflts與Bwm的多產品可持續供應商選擇［J］.計算機集成制造系統，2018，26（2）：508-521.

［9］肖芳雄.面向QoS 的Web 服務組合建模和驗證研究［D］.南京：南京航空航天大學，2010.

［10］馮金芝，陳興，鄭松林，等.一種改進的多目標粒子群化算法及其應用［J］.計算機應用研究，2014，31（3）：675-678.

（實習編輯：黃愛明）

Selection of IT Service Provider Consortium

Based on MPSO Algorithm

HU Yun（School of Mechatronics and Information，Wuxi Open University，Wuxi 214011，China）Abstract：In order to store and process information data efficiently，flexibly and locally，the cloud solution provided by IT service providers was adopted.The grey relational comprehensive evaluation model was used to determine the response time，service quality and service cost closely related to computing service，storage service and software service as the optimization indexes and to make quantitative analysis of multi objectives.Besides，MPSO algorithm was used to find the optimization solution.An example was used to verify the rationality and effectiveness of the algorithm.

Key words：IT service provider;consortium selection;grey relational analysis;multi-objective optimization;MPSO algorithm;cloud solution