導(dǎo)語：軟件升級問題多目標優(yōu)化方法研究一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

1引言

隨著開源思想的流行，越來越多的開發(fā)者加入開源軟件世界，F(xiàn)OSS（FreeandOpenSourceSoftware）發(fā)行版操作系統(tǒng)中的開源軟件倉庫的規(guī)模日益壯大。同時，開源軟件倉庫中的軟件包之間的依賴和沖突關(guān)系越來越復(fù)雜，這導(dǎo)致了一個嚴重的問題：當使用系統(tǒng)原生的包管理器安裝或升級軟件包時，可能會遇到軟件包安裝或升級后系統(tǒng)變得不穩(wěn)定或喪失一些功能的情況，甚至可能由于計算上的高復(fù)雜度，包管理器無法找到能夠滿足系統(tǒng)中軟件包之間的依賴和沖突的安裝方案，而直接提示軟件包安裝或升級失敗。這些狀況會影響正常的生產(chǎn)工作，因此有效地解決軟件安裝或升級問題十分必要。如圖1所示，自2001年以來，Debian軟件倉庫中的軟件包數(shù)量持續(xù)增長，截至2019年12月，軟件包數(shù)量已超過59000［1］。然而，由于軟件包之間的聯(lián)系，軟件包的管理在計算上是非常復(fù)雜的。例如，一個軟件包可能依賴某些軟件包或者與某些軟件包沖突，軟件包管理工具必須要能夠維護好一個描述軟件包安裝情況的配置方案，該方案須滿足每個軟件包的依賴項，并且不會造成軟件包之間的沖突，搜索這樣的配置方案就是軟件升級問題。然而，配置方案僅僅滿足軟件包之間的依賴和沖突是不夠的，還需要在這個基礎(chǔ)上達到某種最優(yōu)的要求，軟件包升級問題本質(zhì)上是多目標優(yōu)化問題。考慮到系統(tǒng)的穩(wěn)定性，用戶可能對不同的升級目標感興趣，如要求被移除的軟件包的數(shù)量和版本發(fā)生改變的軟件包的數(shù)量盡可能少；此外，考慮到網(wǎng)絡(luò)傳輸數(shù)據(jù)量，用戶可能希望需要下載的軟件包的體積盡量小等。即使僅考慮其中一個升級目標，軟件升級問題可以簡化為帶權(quán)重的最大可滿足（partialweightedMAXSAT）問題［2］，這也是一個NP難問題。不僅如此，越來越龐大的軟件包倉庫也使得可量測性成為軟件升級過程中的巨大挑戰(zhàn)。現(xiàn)有的升級問題求解器都是以聚合的方式簡單地將多個升級目標加權(quán)轉(zhuǎn)化為一個單目標優(yōu)化問題，再使用單目標優(yōu)化算法進行求解。這種方式未考慮不同目標之間的關(guān)系和沖突，可能存在一定的風險：如果過度重視某一個目標的優(yōu)化，那么單目標優(yōu)化算法在其他目標上的表現(xiàn)就會非常糟糕［3］。針對上述問題和挑戰(zhàn)，本文首次嘗試結(jié)合約束求解和多目標演化算法來處理軟件升級問題，并提出了一個多目標優(yōu)化軟件升級框架———SATMOEA，其能夠同時對多個升級目標進行優(yōu)化，而不會發(fā)生現(xiàn)有的升級問題求解器中“厚此薄彼”的現(xiàn)象。該框架分為實例解析、約束求解、構(gòu)建多目標優(yōu)化問題、演化優(yōu)化4個階段。實例解析是將軟件升級問題實例（CUDF文件）中描述的與用戶請求的軟件包相關(guān)的依賴和沖突關(guān)系抽象出來，表示為描述布爾可滿足性問題（SAT）的CNF文件；約束求解是使用快速采樣技術(shù)得到CNF文件的一系列可行解；構(gòu)建多目標優(yōu)化問題是定義軟件升級問題的各個優(yōu)化目標函數(shù)以及約束條件的計算方法；演化優(yōu)化階段則是使用本文改進的多目標演化算法對構(gòu)建好的多目標優(yōu)化問題進行迭代優(yōu)化求解，并最終得到帕累托解集。本文在MISC提供的升級問題標準實例集上進行了實驗，結(jié)果表明該框架能夠在一次運行后即可得到一系列在各個優(yōu)化目標上均為帕累托最優(yōu)的升級方案，相比現(xiàn)有的軟件升級問題求解器一次只能得到一個升級方案，該框架能夠提供給用戶更多的可選方案以應(yīng)對多樣的應(yīng)用場景，并且在一些升級目標上有顯著的優(yōu)勢。本文第2節(jié)論述了軟件升級問題領(lǐng)域現(xiàn)有的相關(guān)工作和研究進展；第3節(jié)詳細闡述了本文提出的多目標優(yōu)化軟件升級框架的流程與細節(jié)；第4節(jié)介紹了本框架在標準升級問題實例集上的實驗及結(jié)果；最后總結(jié)了本框架的優(yōu)勢與存在的問題，以及未來進一步的研究方向。

2相關(guān)工作

2．1軟件升級問題求解器。在類UNIX操作系統(tǒng)中有各種用于解決軟件包管理問題的自動化工具，如Debian中的apt－get、RedHat中的yum、ma－cOS中的fink等。這些工具基于軟件包的依賴和沖突信息來決定如何在已安裝其他軟件包的系統(tǒng)中安裝用戶請求安裝的新包，并且滿足其依賴［4］。然而，由于軟件包之間依賴和沖突關(guān)系的復(fù)雜性，這些工具通常使用某種啟發(fā)式方法，因此是不完備的求解工具。在有些情況下，盡管某個軟件包是可以安裝的，但是這些工具卻不能成功地找到一個安裝方案［5］。早期有些工作采用了基于布爾可滿足性問題（BooleanSatisfiability，SAT）的工具來求解復(fù)雜的依賴和沖突，并能確保在安裝及升級軟件包前后，軟件包倉庫和系統(tǒng)原已安裝的軟件包的一致性。Mancinelli等［6］將軟件包安裝問題形式化描述為SAT問題，并首次使用基于SAT的工具為發(fā)行編輯提供支持。他們開發(fā)的自動化工具能夠確保完整性，并且比內(nèi)置的和手動的工具更加可靠。后來，Argelich等［7］應(yīng)用最大可滿足問題（MaximalSatisfiability，MaxSAT）的思想從用戶角度求解軟件包安裝問題。Tucker等［4］提出了優(yōu)化的方法，通過使用SAT求解器、偽布爾問題求解器、整數(shù)線性規(guī)劃求解器來達到更好的結(jié)果。他們設(shè)計出Opium工具用于優(yōu)化用戶提供的一個目標函數(shù)。Argelich等［8］從布爾多級優(yōu)化（BooleanMulti－levelOptimization，BMO）的視角求解軟件升級問題，他們提出了兩種不同的算法，分別基于MaxSAT和偽布爾優(yōu)化（Pseudo－BooleanOptimization，PBO）。他們的實驗表明，專門用于BMO的算法比最好的MaxSAT和PB求解器效率提高了幾個數(shù)量級。Daniel等［9］開發(fā)了一個基于SAT4J偽布爾求解器的軟件包升級工具P2，用于處理E－clipse平臺上的插件安裝問題。Paulo等［10］將軟件安裝問題形式化描述為偽布爾優(yōu)化問題再進行求解。至止，以上求解工具都是采用在不同的軟件包管理環(huán)境中的不同語言來描述軟件升級問題。為了便于評估和比較這些求解工具的性能，MANCOOSI項目人員設(shè)計了一種標準的文檔格式CUDF（CommonUp－gradabilityDescriptionFormat）來描述軟件升級問題［11］。自此，各種CUDF求解器開始出現(xiàn)，它們將CUDF文件描述的升級問題轉(zhuǎn)換為SAT問題、混合整數(shù)線性規(guī)劃（MixedInte－gerLinearProgramming，MILP）問題、偽布爾優(yōu)化（PBO）問題、ASP（AnswerSetProgramming）問題、最大可滿足問題（MaxSAT）等形式，再采用相應(yīng)的專門算法進行求解。這些求解器包括mccs［12］，aspcud［13］，P2CUDF（P2的新版本）［14］，PackUp［15］和PackUpHyb［3］。本文使用CUDF實例進行實驗探究。上述現(xiàn)有的求解器大多是將軟件升級問題按照用戶的個性化請求轉(zhuǎn)換為某個單目標優(yōu)化問題，然后以聚合的方式處理多個升級目標。盡管這些求解器能夠得到一個某種意義上的最優(yōu)解，但是這些方法具有明顯的局限性：在現(xiàn)有的方法中，多個升級請求以聚合的方式被處理，如加權(quán)和（weightedsum）標量化轉(zhuǎn)換方法和字典序組合方法。因此，這些方法存在一個潛在的風險：不同的升級目標之間的關(guān)系可能沒有被恰當?shù)乜紤]。2．2基于搜索的技術(shù)在軟件工程中的應(yīng)用。軟件升級問題在于找到能夠滿足軟件包的依賴關(guān)系并避免沖突的軟件包安裝方案，這是一個NP難問題。使用精確算法求解NP難問題需要指數(shù)級別的復(fù)雜度，但是每一個NP難問題都可以用一些近似算法來獲得可接受的優(yōu)化解。基于搜索的軟件工程倡導(dǎo)應(yīng)用運籌學(xué)領(lǐng)域的優(yōu)化技術(shù)或（元）啟發(fā)式計算方法來解決軟件工程問題［16］，這些技術(shù)或方法按照構(gòu)建的問題模型主要分為單目標優(yōu)化方法和多目標優(yōu)化方法。對于本文涉及的多目標優(yōu)化領(lǐng)域，目前已有許多成功應(yīng)用的實例，如優(yōu)化需求搜索以求解NRP（NextReleaseProb－lem）［17］問題、優(yōu)化測試數(shù)據(jù)選擇和優(yōu)先級排序［18］、優(yōu)化軟件項目管理［19］，以及用于優(yōu)化軟件產(chǎn)品線中特征選擇問題的SATIBEA框架［20］。此外，基于搜索的技術(shù)在軟件測試數(shù)據(jù)自動生成［24－25］、程序錯誤自動修復(fù)［26］、軟件缺陷定位［27］、軟件產(chǎn)品線配置［28－29，32］、云計算構(gòu)件優(yōu)化［30－31］等軟件工程領(lǐng)域也取得了豐碩的成果。本文從軟件升級問題的自然本質(zhì)出發(fā)，此問題實質(zhì)上是多目標優(yōu)化問題。我們首次采用多目標演化算法來進行求解，同時優(yōu)化多個升級目標，而不是以聚合的方式處理這些目標，最后得到一組帕累托最優(yōu)解提供給用戶或服務(wù)器管理員，以供他們在不同場景下進行選擇。

3多目標優(yōu)化軟件升級框架

針對軟件升級問題，本文提出一個多目標優(yōu)化框架SATMOEA，該框架結(jié)合了可滿足問題（SAT）的求解和多目標演化算法（MOEA）。框架的結(jié)構(gòu)設(shè)計如圖2所示。本框架求解一個軟件升級問題實例的流程如下：（1）使用CUDF解析器（Parser），將輸入的描述一個升級問題實例的CUDF文件解析為相應(yīng)的描述可滿足問題的CNF文件，即把CUDF實例轉(zhuǎn)為CNF實例；同時，生成一個映射文件（Map），描述CNF中的數(shù)值編號與CUDF中的軟件包之間一對一的映射關(guān)系。（2）對于步驟（1）中得到的CNF實例，使用MaxSAT快速采樣技術(shù)高效地得到一定數(shù)量的解，即為升級問題的一部分可行解，然后選取這些解中的部分或全部作為演化算法的初始種群。QuickSampler采樣工具實現(xiàn)了MAX－SAT快速采樣技術(shù)，通過較少次數(shù)地調(diào)用MaxSAT求解器就能得到大量CNF實例的有效解。（3）建立有約束的多目標最小化問題。其中，約束條件為問題解必須為CNF的可行解。目標有5個，分別為：1）需要移除的軟件包的數(shù)量；2）版本發(fā)生變化的軟件包的數(shù)量；3）新增的軟件包的數(shù)量；4）非最新版本的軟件包的數(shù)量；5）未滿足的推薦軟件包的數(shù)量。（4）選擇演化算法并配置演化相關(guān)參數(shù)（種群大小、演化代數(shù)、變異策略及概率、交叉策略及概率、選擇策略），然后執(zhí)行演化算法，得到帕累托最優(yōu)解集（ParetoFront）。3．1軟件升級問題的形式化構(gòu)建。本文將軟件升級問題構(gòu)建為“可滿足問題＋多目標優(yōu)化問題”的形式，以便使用約束求解算法和多目標演化算法逐步求解軟件升級問題。3．1．1構(gòu)建可滿足問題一個典型的CUDF實例文件的結(jié)構(gòu)如圖3所示，它能夠描述軟件倉庫中所有軟件包的信息（Universe）、當前系統(tǒng)中已安裝的軟件包的信息（Installed）、用戶的請求（Request），以及軟件包之間錯綜復(fù)雜的依賴沖突關(guān)系［11］。每個軟件包的信息由多個字段描述，主要包括軟件包名字、版本號、是否已安裝、依賴項、沖突項等。關(guān)于依賴項和沖突項的說明如下：假設(shè)軟件包A的依賴項中有軟件包B，那么，當安裝軟件包A時，必須先安裝軟件包B；當卸載軟件包B時，軟件包A也將隨之被卸載。假設(shè)軟件包A的沖突項中有軟件包B，那么，A和B不能同時存在于同一個系統(tǒng)中，即當安裝軟件包A時，須保證軟件包B未被安裝或已被卸載。求解軟件升級問題的先決條件是：必須首先解決軟件包之間的沖突和依賴問題，在此基礎(chǔ)上才能進一步搜索最優(yōu)的升級方案，即一個軟件升級方案一定是滿足系統(tǒng)中所有軟件包的沖突和依賴的升級方案。基于CUDF的文件結(jié)構(gòu)，本文設(shè)計了專門的語法解析器，用于解析CUDF文件，獲取其中蘊含的軟件包之間的依賴與沖突關(guān)系信息；然后將沖突和依賴關(guān)系形式化為布爾可滿足性問題，也就是SAT問題。因此，CUDF解析器的作用是將CUDF文件轉(zhuǎn)化為描述相應(yīng)的SAT問題的CNF文件。SAT問題用于判斷是否存在一組變量賦值滿足給定的布爾表達式，它的定義如下：一個布爾表達式由變量、合取操作符（∧）、析取操作符（∨）、否操作符（）和括號組成，當存在一種對變量的賦值方案，使得布爾表達式的值為真時，稱這個布爾表達式可滿足。考慮圖4所示的升級問題實例，假設(shè)從一個CUDF實例中獲取到的軟件包之間的關(guān)系如圖4（a）所示，用戶的請求是安裝軟件包a。圖4中，實線單箭頭表示“與”依賴關(guān)系，在圖4表示的關(guān)系中，軟件包b和c均已安裝的情況下，軟件包a才能被安裝；虛線單箭頭表示“或”依賴關(guān)系，即軟件包d和e中安裝任意一個之后，才能安裝軟件包b，軟件包c，e，f同理；實線雙箭頭表示沖突關(guān)系，即軟件包d和e不能同時安裝在一個系統(tǒng)中，只能安裝其中一個。可以用式（1）所示的布爾表達式描述軟件包a，b，c之間的關(guān)系：a∧（a∨b）∧（a∨c）（1）這是一個合取范式，要使合取范式的取值為真，必須使每一個子句的取值為真。當某個變量值為true時，表示安裝對應(yīng)的軟件包；否則表示不安裝。式（1）中，第1個子句a表示用戶請求安裝軟件包a，即a的取值必須為true；第2個子句a∨b表示當a的取值為true時，b必須為true，才能使子句的取值為真，也就是軟件包a依賴軟件包b的關(guān)系；第3個子句同理。式（2）描述了軟件包b依賴軟件包d或e的關(guān)系以及軟件包d與e之間的沖突關(guān)系：（b∨d∨e）∧（d∨e）（2）在第1個子句中，當b為true時，須使d或e中至少一個為true，才能使子句為真，這就表示了軟件包b與軟件包d和e之間的“或”依賴關(guān)系。與之同理，可以用式（3）來描述軟件包c，e，f之間的關(guān)系。在第2個子句中，當變量d和e之間任意一個取值為true時，另一個變量必須為false，才能使子句為真，即兩個變量不能同時為true。（c∨e∨f）（3）使用合取符號將式（1）—式（3）連接起來可得到式（4），這樣就完整地表達了圖4實例中的依賴和沖突關(guān)系。a∧（a∨b）∧（a∨c）∧（b∨d∨e）∧（d∨e）∧（c∨e∨f）（4）為了數(shù)值化表示這些關(guān)系，CUDF解析器首先對所有涉及的軟件包進行編號，編號從1開始，即生成軟件包與數(shù)值編號的一一映射關(guān)系，如圖4（b）所示的Map文件（Sample．map）。圖4（c）所示的CNF文件（Sample．cnf）是由式（4）直接轉(zhuǎn)化得到的。其中，第1行“pcnf66”是問題描述行，表示這是一個CNF文件，并且包含6個變量和6個子句。從第2行開始的每一行都對應(yīng)式（4）中的一個子句，轉(zhuǎn)化的規(guī)則是：使用Map文件定義的軟件包的編號替換公式中的字母變量；使用空格替換析取符號（∨）；最后再加上空格和數(shù)字0作為結(jié)尾，數(shù)字0表示子句結(jié)束符。CNF文件所描述的SAT問題實例可以通過SAT求解器進行求解。當構(gòu)建的SAT問題在有限時間內(nèi)找不到可行的賦值方案時，求解器會將其標記為“UNSATIFIABLE”，即該CUDF實例所描述的用戶請求很難被滿足；當SAT求解器能夠找到一個可行的賦值方案時，會將問題標記為“SAT－ISFIABLE”，并提供一個可行的賦值方案。賦值方案規(guī)定了每一個軟件包是否被安裝，當編號為正數(shù)時，表示安裝對應(yīng)的軟件包，當編號前面加上了負號變成負數(shù)時，表示不安裝對應(yīng)的軟件包。另外，賦值方案以“v”為起始標志，以“0”為結(jié)束標志。例如，對于圖4所示的問題實例，SAT求解器的輸出文件如圖5所示。根據(jù)它提供的賦值方案并對照圖4（b）的Map文件，即可得出：需要安裝的軟件包有a，b，c，d，f，不需要安裝的軟件包是e。傳統(tǒng)的SAT求解器最多只能提供一個可行解，直到2018年Dutra等［21］提出了一個高效的SAT問題求解工具QuickSampler，它一次能夠得到大量的可行解。這也是我們在本工作采用多目標演化算法搜索最優(yōu)的軟件升級方案的動機之一，使用QuickSampler工具一次性得到CNF實例的大量可行解恰好可以作為演化算法的初始種群。3．1．2構(gòu)建多目標優(yōu)化問題對于多目標優(yōu)化問題的構(gòu)建，本文選擇MISC提出的5個優(yōu)化準則作為最小化目標，分別是：1）需移除的軟件包數(shù)量（Remove），對應(yīng)目標函數(shù)為R（X）；2）版本發(fā)生改變的軟件包數(shù)量（Change），對應(yīng)目標函數(shù)為C（X）；3）新增的軟件包數(shù)量（New），對應(yīng)目標函數(shù)為N（X）；4）不是位于最新版本的軟件包數(shù)量（Notdate），對應(yīng)目標函數(shù)為Nd（X）；5）未滿足推薦軟件包的數(shù)量（Unsatisfied－recommend），對應(yīng)目標函數(shù)為Us（X）。本文將約束條件設(shè)置為：必須滿足CNF實例中的每一個子句，即賦值方案須保證真值為假的析取范式的數(shù)量為0。我們用長度為n（表示CNF實例涉及到的軟件包數(shù)量）的二進制串來表示一個解，第i位上的取值即表示編號為i的軟件包是否需要安裝：0代表不需安裝，1代表需要安裝。例如，圖5所示的一個可行解可以轉(zhuǎn)化為二進制串“111101”。在演化算法中，優(yōu)化函數(shù)的每一個解X表示一個個體，若干個體組成一個種群，我們稱之為代；選擇種群中的部分個體，讓它們隨機配對交叉或隨機變異，產(chǎn)生新的個體，即構(gòu)成新一代種群，這就是生物進化的思想。我們用Xpk表示演化第p代中的第k個解，它是一個特殊的n維向量，每一位只能取值1或0，表示某個軟件包是否需要安裝，我們稱之為二進制向量。該解對應(yīng)的上述5個目標函數(shù)值分別定義為：1）R（Xpk），表示解決方案Xpk導(dǎo)致的原來系統(tǒng)中需要移除的軟件包的數(shù)量；2）C（Xpk），表示解決方案Xpk使原來系統(tǒng)發(fā)生版本變更的軟件包的數(shù)量；3）N（Xpk），表示解決方案Xpk使原來系統(tǒng)新增軟件包的數(shù)量；4）Nd（Xpk），表示解決方案Xpk中不是位于最新版本的軟件包的數(shù)量；5）Us（Xpk），表示解決方案Xpk中軟件包的推薦項未被滿足的數(shù)量。這些函數(shù)值可以根據(jù)Xpk定義的軟件包的安裝方案與CUDF實例中描述的軟件包的安裝情況以及軟件包的版本信息、推薦安裝列表對比計算得出。另外，我們用Violate（Xpk）表示違背子句的數(shù)量，即Xpk定義的賦值方案使得CNF實例中結(jié)果為假的子句（析取范式）的數(shù)量。例如，對于圖4所示的實例來說，當Xpk＝（1，0，1，0，1，0）時，它對應(yīng)的CNF賦值方案是“1－23－45－6”，CNF中的違背子句有且僅有“－120”，原因是“－120”規(guī)定的是賦值方案中須包含－1或2，而Xpk對應(yīng)的賦值方案中既不包含－1，也不包含2。此時，Violate（Xpk）＝1。綜上所述，軟件升級問題可以構(gòu)建為如下形式的包含5個優(yōu)化目標和1個約束條件的多目標最小化問題。minF（X）＝（R（X），C（X），N（X），Nd（X），Us（X））Ts．t．Violate（X）＝0，X是一個二進制向量3．2演化及中間解修正算法。當多目標優(yōu)化問題模型構(gòu)建完成后，我們使用多目標演化算法進行求解。演化算法的輸入是初始種群，因此首先需要確定初始種群。初始種群可以完全隨機化，即隨機產(chǎn)生若干個體構(gòu)成初始種群，這些個體的每一位都是隨機的0或1，不能保證滿足多目標優(yōu)化問題的約束條件；借助QuickSam－pler工具，能夠一次性得到CNF實例的若干個可行解，于是我們還可以將這些可行解全部作為初始種群中的個體。確定初始種群之后，正式進入演化過程。與生物進化論相似，選擇、交叉、變異是演化算法中的3種常用操作。選擇是指從種群中選出適應(yīng)度較好的個體，用于進行交叉操作從而產(chǎn)生新一代個體，不同的選擇算法計算適應(yīng)度的方法有所不同。交叉是指將兩個父代個體的基因局部進行交換，產(chǎn)生兩個新的子代個體，在本問題中，我們用二進制向量表示問題的解就可以很方便地進行單點或多點交叉操作。個體的基因有一定的概率發(fā)生變異，我們采用位翻轉(zhuǎn)的變異策略，當問題的解的某一位從0變?yōu)?或相反時，表示發(fā)生了變異。如果父代個體是可行解，當它們完成交叉和變異操作（交叉操作對于解的改變是非常顯著的）之后，產(chǎn)生的新解極有可能變成不可行解，而不可行解違背了優(yōu)化問題的約束條件。因此，將產(chǎn)生的不可行解調(diào)整為可行解，是十分必要的。我們在多目標演化算法的基礎(chǔ)上，增加了中間解修正操作，以維持解的可行性。中間解修正算法如算法1所示。該算法的基本思想是：先找出不包含在被違背的約束條件中的軟件包，固定它們的取值（0或1），具體來講就是將它們的取值作為約束條件，添加到原來的CNF約束條件之后；然后由SAT求解器計算出其余的軟件包的取值。下面考慮這樣的一個CNF實例：（p1∨p5）∧（p2∨p3）∧（p2∨p5）當我們得到了它的一個不可行解M的賦值方案（0，0，1，1，0）時可知，該方案違背了CNF定義的兩個約束條件（p1∨p5）和（p2∨p5），這兩個約束條件涉及p1，p2，p53個軟件包，我們將這3個軟件包的取值從C中移除，將p3和p4的取值作為約束條件添加到原來的CNF實例中，則新的CNF變?yōu)椋海╬1∨p5）∧（p2∨p3）∧（p2∨p5）∧p3∧p4我們將新的CNF交給SAT求解器進行求解，計算出p1，p2，p5的取值，得到一個新的可行解N＝（1，1，1，1，0）。于是，一個中間解的修正操作就完成了。算法1中間解修正算法輸入：一個演化過程的中間解M＝（x1，x2，…，xm），滿足Violate（M）＞0；CNF文件Fold中的子句集合C＝（c1，c2，…，cn）輸出：修正后的可行解N1．令集合B表示中間解中需要修正的索引集合；2．B←；3．fori←1tondo4．ifci＝falsethen5．將ci包含的索引添加到集合B中；6．endif7．endfor8．fori←1tomdo9．if集合B中不包含xithen10．將子句“xi0”添加到集合C中；11．endif12．endfor13．使用集合C中的子句構(gòu)造出一個新的CNF文件Fnew；14．調(diào)用SAT求解模塊對Fnew進行求解，得到可行解N；15．returnN．

4實驗與分析

4．1實驗設(shè)置。本文選擇國際軟件包安裝與升級問題求解器競賽［22］提供的CUDF標準實例數(shù)據(jù)集進行實驗，其中CUDF實例模擬了真實系統(tǒng)環(huán)境中軟件包的復(fù)雜度。實驗按照軟件包名稱計數(shù)，這些實例包含的軟件包全集的數(shù)量為27710～59094，平均數(shù)量為35275．5，與Debian實際的軟件包倉庫的規(guī)模十分接近。因此，本文獲得的實驗結(jié)果可以模擬現(xiàn)實環(huán)境中求解器的性能表現(xiàn)。在多目標演化模塊中，本文在開源的多目標優(yōu)化算法框架jMetal［23］提供的基于指示器的演化算法（Indicator－BasedEvolutionaryAlgorithm，IBEA）的基礎(chǔ)上，調(diào)整了交叉算子和變異算子的實現(xiàn)方式以適配軟件升級問題，并且增加了演化中間解的修正操作。演化算法中的一些重要參數(shù)設(shè)置如表1所列。4．2實驗結(jié)果與分析。本文主要對以下4個研究問題進行實驗分析。RQ1：提高初始種群中可行解的比例對演化算法結(jié)果的提升效果如何？RQ2：相比其他高維多目標演化算法，IBEA算法是否具有優(yōu)勢？RQ3：中間解修正會對演化結(jié)果造成怎樣的影響？RQ4：SATMOEA的性能是否優(yōu)于其他軟件升級問題求解器？4．2．1探究約束求解對演化結(jié)果的提升效果對于初始種群，有兩種構(gòu)建策略：1）使用SAT求解器對CNF實例進行求解，得到一個可行解作為初始種群中的一個個體，其余個體隨機生成（必定包含大量的不可行解），構(gòu)成完整的初始種群；2）使用QuickSampler工具，它能快速得到指定數(shù)量的可行解，然后使用這些可行解建立初始種群，即初始種群全部為可行解。我們使用以上兩種方法構(gòu)建初始種群，分別執(zhí)行基于指示器的演化算法：初始種群的大小設(shè)為30，迭代4次，統(tǒng)計演化算法終止時得到的帕累托解集中可行解的情況，如表2所列。實驗結(jié)果表明，初始種群中可行解的數(shù)量越多，演化得到的帕累托解集中的可行解的數(shù)量就越多。因此，最好是將初始種群全部設(shè)為可行解（可以借助QuickSampler工具實現(xiàn)），以便在最后的帕累托解集中得到更多的可行解。4．2．2不同多目標演化算法的對比Sayyad等［32］在軟件產(chǎn)品線工程中的特征選擇問題的研究中發(fā)現(xiàn)，相比其他多目標演化算法（Multi－ObjectiveEvolu－tionaryAlgorithm，MOEA），基于指示器的演化算法（IBEA）表現(xiàn)更好。為了驗證IBEA在軟件升級問題上是否也具有同樣的優(yōu)勢，本文在軟件升級問題實例上對比了IBEA，NS－GAII，SPEA2，NSGAIII4種演化算法的表現(xiàn)。選取這幾種算法，一方面是參考Sayyad等的研究工作中對比的算法，另一方面是因為它們都支持二進制類型的問題解。在本實驗中，設(shè)置種群大小為30，迭代次數(shù)為10，4種演化算法的演化結(jié)果如表3所列。其中，第2－6列數(shù)據(jù)是不同的演化算法得到的帕累托集在各個目標函數(shù)上的值。HV和Spread是衡量多目標演化算法得到的帕累托集的兩個重要的質(zhì)量指標，可以由jMetal演化算法框架方便地計算出來，Size表示帕累托集包含解的數(shù)量。HV代表帕累托集構(gòu)成的前沿面所覆蓋的空間的體積（HyperVolume）［33］，這個體積越大，表示帕累托集越接近真實的帕累托前沿面，說明帕累托集的質(zhì)量越高。Spread代表帕累托集擴展的程度［34］，多目標演化算法希望得到的帕累托集能夠在真實的帕累托前沿面上分布得更廣泛、更均勻。Spread的計算方式如式（5）所示：其中，N表示帕累托集中包含的點（解）的數(shù)量，di表示兩個相鄰解之間的歐氏距離，d－是di的平均值，df和dl分別是帕累托集中的邊界解與極值點（Extremesolution）之間的歐氏距離。當帕累托集中只包含一個解時，Spread的值為1。一個好的帕累托集應(yīng)該包含各個目標的極值點（df＝dl＝0），并且各個解分布均勻（di－d－趨近于0），此時Spread的值接近于0。因此，Spread的值越小說明帕累托集的分布情況越好。IBEA與其他3種多目標演化算法對比的實驗結(jié)果如表3所列。該結(jié)果顯示，IBEA得到的帕累托集中不僅包含更多的解，并且在HV和Spread兩個質(zhì)量指標上均表現(xiàn)出了一定的優(yōu)勢。因此，本文選擇IBEA作為優(yōu)化軟件升級問題的多目標演化算法。4．2．3探究中間解修正操作對演化結(jié)果的影響為了探究增加中間解修正操作對演化算法結(jié)果的影響，本文設(shè)置初始種群的大小為50（全部由QuickSampler得到的可行解構(gòu)成）、迭代次數(shù)為10，分別執(zhí)行無修正操作的演化算法和有修正的操作的演化算法各一輪，然后計算帕累托解集中可行解所占的比例。實驗結(jié)果如表4所列。其中，無修正操作的演化算法得到的帕累托解集中包含43個解，超過了有修正操作的演化算法得到的帕累托解集；然而，無修正操作的帕累托解集中可行解的數(shù)量是0，也就是說，無修正操作的演化算法最終得到的解全部為不可行解，這對軟件升級問題的求解是沒有意義的。有修正操作的演化算法得到的帕累托解集中全部為可行解，因此中間解修正操作對于演化結(jié)果的質(zhì)量有顯著的提升。4．2．4探究SATMOEA框架與其他求解器的性能對比情況為了探究SATMOEA框架求解軟件升級問題的性能是否優(yōu)于現(xiàn)有的其他求解器，本文對比了它們求解同一個CUDF實例得到的解在不同的升級目標上的表現(xiàn)，結(jié)果如表5所列。其中，R（X）表示需要移除原來系統(tǒng)中軟件包的數(shù)量，C（X）表示原來系統(tǒng)中發(fā)生版本變更的軟件包的數(shù)量，N（X）表示新增軟件包的數(shù)量，Nd（X）表示不是最新版本的軟件包的數(shù)量，Us（X）表示未滿足已安裝的軟件包中的推薦的數(shù)量。前5行數(shù)據(jù)分別表示由現(xiàn)有的5種不同的求解器得到的升級方案計算出的各個目標函數(shù)值，第6－12行數(shù)據(jù)表示SATMOEA框架得到的帕累托解集中的每一個解對應(yīng)的各個目標函數(shù)值。需要注意的是，對于一個CUDF實例，其他求解器只能得到單一的升級方案，而SATMOEA框架運行一次就能夠計算出一組帕累托最優(yōu)解集，其中包含一系列可行的升級方案，用戶可以從中選擇不同的升級方案，以應(yīng)對不同的場景。另外，從表5中加粗的數(shù)據(jù)可以看出，本框架能夠找到不被其他求解器占優(yōu)的解，即一個或多個目標函數(shù)值優(yōu)于其他求解器相應(yīng)的目標函數(shù)值。因此，當用戶希望新增的軟件包數(shù)量盡可能少時，可以選擇SATMOEA框架提供的第1，2，3，6，7個解，對應(yīng)表5中的第6，7，8，11，12行；而當用戶希望位于最新版本的軟件包盡可能多時，可以選擇SATMOEA框架提供的第5個解，對應(yīng)表5中的第10行。為了更顯著地表現(xiàn)SATMOEA框架的優(yōu)勢，我們將各個優(yōu)化目標上能達到的最小值單獨列出來，如表6所列。其中，第1行表示其他求解器的解綜合起來所能達到的各個目標函數(shù)的最小值，第2行表示SATMOEA框架演化得到的帕累托解集中的解在各個目標上能夠達到的最小值。數(shù)據(jù)表明，在R（X）目標函數(shù)上，SATMOEA框架所能達到的最小值與其他求解器相當，均為0；在C（X），N（X），Nd（X）3個目標函數(shù)上，SATMOEA表現(xiàn)出了明顯的優(yōu)勢；然而，對于Us（X）目標函數(shù)，SATMOEA與其他求解器相比，表現(xiàn)更差。因此，SATMOEA框架不僅在解的數(shù)量上明顯優(yōu)于其他求解器，而且在解的質(zhì)量上也有一定的優(yōu)勢。

為了避免聚合的方式對不同升級目標之間的關(guān)系處理不當而引起的風險，本文從多目標優(yōu)化的角度解決軟件升級問題，成功構(gòu)建了一個結(jié)合約束求解和多目標演化優(yōu)化的軟件升級問題求解框架SATMOEA，并在演化算法的基礎(chǔ)上增加了中間解修正算法，使帕累托解集中可行解的比例達到了100％；與其他求解器只能提供單一的升級方案相比，該框架能夠提供一系列不同的軟件升級方案，以應(yīng)對不同的軟件升級場景，為軟件升級問題的求解研究提供了一種新的思路。同時，由于演化算法需要對種群中每個個體計算適應(yīng)度等，一定程度上增加了計算量，這是演化算法先天的缺陷，未來將考慮采用并行化的演化算法對SATMOEA框架進行優(yōu)化，以提高求解的效率。

作者:趙松輝 任志磊 江賀 單位:大連理工大學(xué)軟件學(xué)院