基于任務(wù)分配與調(diào)度的GSAT算法求解3-SAT問題

付慧敏,徐 揚(yáng)，何星星,寧欣然

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2.西南交通大學(xué)系統(tǒng)可信性自動驗(yàn)證國家地方聯(lián)合工程實(shí)驗(yàn)室,四川 成都 610031)

1 引言

1971年Cook證明了SAT(SATisfiability)問題是NP完全問題，具有廣泛的實(shí)際應(yīng)用。許多學(xué)者將一些組合問題例如人工智能、超大規(guī)模集成電路VLSI(Very Large Scale Intergration)設(shè)計(jì)、積木世界規(guī)劃、Job shop排工等轉(zhuǎn)化為SAT問題來求解[1]。經(jīng)過國內(nèi)外學(xué)者的努力，求解SAT問題的優(yōu)化算法已經(jīng)有很多，總體分成兩類：一是完備的方法，適應(yīng)于應(yīng)用類問題和組合問題，例如基于DPLL(Davis Putnam Logemann Loveland)的SATO(SAtisfiability Testing Optimized)[2]、BerkMin(Berkeley-Minsk)[3]、CDCL(Conflict-Driven Clause Learning)[4]等。其優(yōu)點(diǎn)是對于任意SAT問題都能正確地判斷其可滿足或者不可滿足，缺點(diǎn)是隨著問題規(guī)模的不斷增大，其解空間的復(fù)雜度成指數(shù)增長，計(jì)算效率很低，不適應(yīng)于大規(guī)模問題[5]。二是不完備的方法，適應(yīng)于隨機(jī)生成問題。雖然對于任意SAT問題不能都正確地判斷其可滿足或者不可滿足，但是對于可滿足SAT問題其效率整體上超過完備的方法，因此受到很多學(xué)者的青睞，使得這種方法得以快速地發(fā)展。例如，MP(Message Passing)算法[6]、Local Search算法[7]、遺傳算法[8]、不完備算法之間的結(jié)合[9,10]、組織進(jìn)化算法[11]、多智能體社會進(jìn)化算法[5]、GSAT算法[12,13]、完備算法和不完備算法相結(jié)合的混合算法[14]等。

GSAT算法是一個很有效的局部搜索算法，其主要的技術(shù)是貪心搜索，即通過一系列的搜索得到問題的最優(yōu)解，而每一次搜索都是當(dāng)前狀態(tài)下某種策略的最好選擇。早期在求解SAT領(lǐng)域中，貪心搜索很容易陷入“早熟”，Selman等人[15]用WalkGSAT的局部搜索算法跳出局部最優(yōu)，大量的實(shí)驗(yàn)表明這個技術(shù)很適應(yīng)于隨機(jī)生成的3SAT問題。1998年梁東敏等人[1]在WalkGSAT的基礎(chǔ)上，引進(jìn)了子句權(quán)重的概念，實(shí)驗(yàn)表明其性能優(yōu)于WalkGSAT，尤其對于結(jié)構(gòu)SAT問題。2002年林智勇等人[16]提出的Learning+Weighting+GSAT算法和2010年Bouhmala等人[17]提出的LA-GSATRW算法都是在GSAT算法的基礎(chǔ)上進(jìn)行了改進(jìn)，但是其優(yōu)勢不是很明顯。2015年張玉安等人[8]將局部搜索的GSAT算法與具有全局搜索的改進(jìn)遺傳算法相結(jié)合，明顯彌補(bǔ)了GSAT算法容易出現(xiàn)早熟的缺點(diǎn)，該算法的實(shí)驗(yàn)結(jié)果表明其性能得到了明顯提高。雖然近幾年貪心搜索在SAT領(lǐng)域的研究學(xué)者并不多，但是在其他一些領(lǐng)域得到了快速的發(fā)展與應(yīng)用，例如組合優(yōu)化問題[18]、風(fēng)機(jī)布局優(yōu)化[19]、優(yōu)化貪心算法[20,21]、自動車輛群內(nèi)的信息傳播[22]等等，所以貪心算法具有一定的使用價(jià)值和研究意義。2004年劉靜等人[11]將組織進(jìn)化的思想用到求解3-SAT問題上，而且根據(jù)SAT問題的特點(diǎn)重新定義了組織的概念，并根據(jù)組織和SAT問題的特點(diǎn)提出了新的算子；2014年潘曉英等人[5]的多智能體社會進(jìn)化算法，將智能體對環(huán)境的感知能力的思想用到求解SAT問題上，而且根據(jù)SAT問題的特點(diǎn)重新定義了智能體的概念，并根據(jù)智能體的行為和SAT問題的特點(diǎn)提出了新的3種行為，對于3-SAT問題這兩種算法的性能都得到了顯著提高。

為了進(jìn)一步提高GSAT算法的效率，即提高貪心算法的性能，本文根據(jù)組織進(jìn)化算法、多智能體社會進(jìn)化算法和李炳芬等人彌補(bǔ)GSAT算法具有局部搜索的缺點(diǎn)的思想，在Weighting+WalkGSAT的基礎(chǔ)上，將任務(wù)分配與調(diào)度的主要目的與3-SAT問題的特點(diǎn)相結(jié)合，并重新定義了任務(wù)分配與調(diào)度的概念，提出了基于任務(wù)分配與調(diào)度的GSAT算法求解3-SAT問題。在文獻(xiàn)[23,24]中，任務(wù)分別指的是數(shù)據(jù)并行交換和用戶提交的需求，本文算法的任務(wù)指的是3-SAT問題中的所有變量，與文獻(xiàn)[23,24]中的定義完全不同；而且分配與調(diào)度的概念與文獻(xiàn)[23,24]中的概念也完全不同，文獻(xiàn)[23]中的分配與調(diào)度是根據(jù)任務(wù)的特點(diǎn)和每個影響因素決定任務(wù)的順序，文獻(xiàn)[24]中的分配與調(diào)度是通過不同的分配策略和調(diào)度策略合理高效地處理用戶提交的任務(wù)，通過任務(wù)分配與調(diào)度的思想，他們都取得了很好的效果。不僅文獻(xiàn)[23,24]中的作者使用分配與調(diào)度，而且許多領(lǐng)域的國內(nèi)外研究人員[25 - 28]都用到了這種思想，他們的目的都是為了高效地完成任務(wù)。本文的分配與調(diào)度是在搜索最優(yōu)真值指派的過程中所用到的策略。在該算法中，與傳統(tǒng)的GSAT算法不同，根據(jù)任務(wù)的特點(diǎn)和分配與調(diào)度的思想設(shè)計(jì)了新的貪心策略。實(shí)驗(yàn)結(jié)果表明，本文算法能更快地跳出局部最優(yōu)，減少翻轉(zhuǎn)次數(shù)，提高成功率，具有一定的使用價(jià)值。

2 3-SAT問題及其表示

3-SAT問題是可滿足性問題，尋找一個給定的布爾值公式是否可滿足[29]。在本節(jié)中，首先定義一些相關(guān)概念，然后精確定義3-SAT問題。

定義1真值指派(Value-Assignment)[29]:用符號Xn表示n個布爾變量的集合，xi，i∈{1,2,…,n}表示布爾變量，則Xn={x1,x2,…,xn}。n個布爾變量的真值指派是一個函數(shù)v:{x1,x2,…,xn}→{0,1}，其中每個布爾變量x1,x2,…,xn都被指派為1或0，1表示真，0表示假。在本文的算法中1表示真，-1表示假。

定義2文字(Literal)[29]:每個文字是一個布爾變量或者一個布爾變量的否定，分別表示為xi或者xi(xi的非)，被分別稱為正文字和負(fù)文字，其中i∈{1,2,…,n}。

定義3子句(Clause):m個子句的集合表示為：Cm={c1,c2,…,cm}，每個子句ci由3個文字的析取(∨)組成[29,30]。若文字xi出現(xiàn)在Cm中且xi不出現(xiàn)在Cm中，則稱文字xi為純文字。

定義4合取范式(CNF):每個合取范式由若干子句的合取(∧)組成，形如F=c1∧c2∧…∧cm。

合取范式F在真值指派下為真當(dāng)且僅當(dāng)每個子句c1,c2,…,cm在真值指派下都為真[5]。

3-SAT問題就是?ck∈F,k∈{1,2,…,m}，是否存在一個真值指派使F為真，若存在這樣的真值指派，則稱3-SAT問題可解決[29]。

3 基于任務(wù)分配與調(diào)度的GSAT算法

3.1 求解3-SAT問題的任務(wù)定義

定義5任務(wù)i是布爾變量集合Xn中的一個變量xi，i∈{1,2,…,n}，任務(wù)的取值只有兩種，分別為真和假。

子句ck權(quán)重記為Weight(ck),k∈{1,2,…,m}，這里的權(quán)重與Weighting+WalkGSAT的權(quán)重定義相同。根據(jù)對任務(wù)的賦值，包含該任務(wù)的子句有兩種—取值為真的子句稱為可滿足子句，取值為假的子句稱為不可滿足子句；包含該任務(wù)的子句權(quán)重有兩種—取值為真的子句其權(quán)重稱為可滿足子句權(quán)重，取值為假的子句其權(quán)重稱為不可滿足子句權(quán)重；包含該任務(wù)的不可滿足子句權(quán)重有兩種，分別是翻轉(zhuǎn)該任務(wù)前稱為前不可滿足子句權(quán)重和翻轉(zhuǎn)該任務(wù)后稱為后不可滿足子句權(quán)重。本文的大任務(wù)指所有任務(wù)的集合，即包含問題的所有變量，與文獻(xiàn)[31]中的類似。任務(wù)貪心搜索是大任務(wù)的前不可滿足子句權(quán)重之和與后不可滿足子句權(quán)重之和的差達(dá)到最大，若這個差值的最大值(記為best_Diff)不小于0，則進(jìn)行翻轉(zhuǎn)[16]。

在搜索最優(yōu)真值指派的過程中，每個任務(wù)在當(dāng)前真值指派下需要記錄一些信息，一個任務(wù)i的結(jié)構(gòu)表達(dá)如下：

任務(wù)貪心搜索策略：記錄該任務(wù)翻轉(zhuǎn)的條件，即:

best_Diff>0,k∈{1，2，…，n}

大任務(wù)規(guī)模：所有子任務(wù)的個數(shù)記為Size,即Size=n。

從任務(wù)的結(jié)構(gòu)可以看出，一個任務(wù)就是原問題的一個變量，而當(dāng)該任務(wù)達(dá)到搜索策略要求時(shí)，翻轉(zhuǎn)這個任務(wù)，使得假子句權(quán)重之和減少，真子句權(quán)重之和增加，同時(shí)通過增加不可滿足子句的權(quán)重提高了假子句為真的幾率，加快搜索的進(jìn)程。當(dāng)假子句權(quán)重之和減少到0時(shí)，該變量就找到了一個解。顯然，當(dāng)假子句權(quán)重之和為0的任務(wù)集合等于大任務(wù)規(guī)模時(shí)，就得到大任務(wù)的一個最優(yōu)解。因此，要解決原問題，就要解決含有所有子句的大任務(wù)，這就要使不同任務(wù)間進(jìn)行相互作用。

任務(wù)分配與調(diào)度問題是NP完全問題[32]。本文并不關(guān)心如何分成適當(dāng)?shù)淖尤蝿?wù),如何將子任務(wù)分配給各個處理機(jī)，如何安排子任務(wù)的執(zhí)行順序，而是將重點(diǎn)放在子任務(wù)的相互作用上。任務(wù)分配與調(diào)度的主要目的是為了尋找一個合適的分配調(diào)度，使得任務(wù)執(zhí)行結(jié)束后所花費(fèi)的時(shí)間盡量地小。受此啟發(fā)，我們另外設(shè)計(jì)了兩種任務(wù)貪心策略來引導(dǎo)任務(wù)的完成。

3.2 貪心策略

本文的另外兩種任務(wù)貪心策略分別為分配策略和調(diào)度策略。分配策略是提前指導(dǎo)任務(wù)貪心搜索的趨勢，它利用原問題本身的信息進(jìn)行貪心指派任務(wù)，本質(zhì)是減少搜索空間，實(shí)際上起到快速找到最優(yōu)解的作用。調(diào)度策略是當(dāng)不能滿足任務(wù)貪心搜索策略條件時(shí)，起用調(diào)度策略決定翻轉(zhuǎn)的子任務(wù)，有效地防止搜索陷入局部最優(yōu)，加快搜索進(jìn)程。

3.2.1 如何任務(wù)分配

在SATLAB庫[33]中，“Uniform Random-3-SAT”問題集共有3 700個3-SAT問題，文獻(xiàn)[5,11]表明該問題集已經(jīng)被大量用于測試求解SAT問題算法的性能,這些問題的子句個數(shù)和變量個數(shù)之比均為4.3左右，此類問題屬于不可滿足和可滿足的概率幾乎是相等的，屬于難解的一類問題集，所以通過測試這些問題更能反映出算法性能的優(yōu)越性。根據(jù)變量的個數(shù)可以將這3 700個問題分成10個集合，分別記為S1,S2,…,S10，以下通過表1給出這10個集合所包含的問題和相應(yīng)的參數(shù)。

Table 1 Uniform Random-3-SAT problems in experiments

SAT問題類似數(shù)學(xué)約束問題，所以我們可以先分析問題庫中變量之間的關(guān)系以及SAT問題的解空間，然后分配一些變量的真值指派，最后通過算法搜索加快解的進(jìn)程。通過分析SATLAB庫中的每個問題集和每個問題集所對應(yīng)的解可以發(fā)現(xiàn)，最優(yōu)的真值指派T與問題集中的每個布爾變量的正負(fù)比例值有關(guān)，即當(dāng)某個布爾變量的正負(fù)比例值大于某個恰當(dāng)?shù)臄?shù)或者小于某個合適的數(shù)時(shí)，此布爾變量的最優(yōu)真值指派直接確定為真或者假的成功率是90%左右。在GSAT類算法和其他類解決SAT問題的不完備算法中，它們大多數(shù)都是通過隨機(jī)產(chǎn)生一個真值指派作為搜索的起點(diǎn)[34]。若一個問題的布爾變量個數(shù)為n且只有一個最優(yōu)真值指派，則隨機(jī)產(chǎn)生的真值指派有2n種情況且一次產(chǎn)生最優(yōu)真值指派的概率為1/2n。在2n種情況中，我們的想法是通過每個布爾變量的正負(fù)比例值分配一個求解3-SAT問題的初始指派，即提前指導(dǎo)最優(yōu)真值指派搜索的趨勢，從而加快找到最優(yōu)解。這種利用每個問題集中每個布爾變量的正負(fù)文字比例值確定初始指派的想法，叫做“分配”，以下定義給出了本文算法中所使用的公式。

定義6變量分配度Vad(Variable allocation degree)，?i∈{1,2,…,n}，它的變量分配度等于:

(1)

其中，在一個3-SAT問題中，pi為所有子句中含有正文字i的總個數(shù)，ni為所有子句中含有負(fù)文字i的總個數(shù)(問題集中負(fù)文字的形式為-i)，當(dāng)Vad(i)≥1時(shí)，稱為i的正變量分配度，當(dāng)Vad(i)<1時(shí)，稱為i的負(fù)變量分配度。pad(positive variable allocation degree)為正變量分配度參數(shù)，nad(negative variable allocation degree)為負(fù)變量分配度參數(shù)。在求解3-SAT問題的過程中，不同的變量分配度參數(shù)值對于算法的性能有著直接的影響，在時(shí)間運(yùn)行上，甚至?xí)嗖?0倍以上，而且也會影響解的成功率。

定義7變量分配值Vav(Variable allocation value)，?i∈1,2,…,n，它的變量分配值等于:

(2)

Vad(i)>pad或者Vad(i)

(3)

若任務(wù)不滿足分配策略，則其變量分配值是由隨機(jī)數(shù)決定的。通過變量分配度的定義我們可以發(fā)現(xiàn)，當(dāng)ni=0或者pi=0時(shí)，i一定滿足分配策略，因?yàn)榇藭r(shí)的i或者-i為純文字，在搜索最優(yōu)真值指派的過程中，只需要將i或者-i的變量分配值為1或者-1，若此情況對i或者-i進(jìn)行翻轉(zhuǎn)，不會使不可滿足子句的總和減少。因此，通過分配策略縮小了搜索空間。

定義8滿足度Sd(Satisfaction degree)，是在一個3-SAT問題中滿足分配策略的任務(wù)在大任務(wù)中所占的比例 ，即:

(4)

3.2.2 分配的直觀解釋

子句集C4={x1∨x3∨x4，x1∨x2∨x4,x2∨x3∨x4,x2∨x3∨x4}，若nad=0.3，則分別通過計(jì)算各個任務(wù)所對應(yīng)的分配度、分配值、分配真值和滿足度，得到任務(wù)的分配流程，如表2所示。

Table 2 Distribution flow sheet

表2中，x2和x4的分配值是隨機(jī)產(chǎn)生的，而且所有變量的分配值剛好是子句集C4的一個最優(yōu)真值指派。因?yàn)閷Ψ峙涠鹊亩x是為了更好地提前確定容易判定的變量的最優(yōu)真值指派，減少搜索過程中的翻轉(zhuǎn)次數(shù)和減小搜索的解空間，因而加快算法搜索的進(jìn)程。若randomf(0,1)表示產(chǎn)生(0,1)的隨機(jī)數(shù)，Vad(N)={Vad(1),Vad(2),…,Vad(n)},Vav(N)={Vav(1),Vav(2),…,Vav(n)}，則分配策略的具體算法描述如下：

算法1Allocation Strategy

步驟1讀取子句集Cm；

步驟2計(jì)算所有任務(wù)的分配度Vad(N)；

步驟3計(jì)算所有任務(wù)的分配值A(chǔ)av(N)，分配一個搜索的初始指派。

3.2.3 調(diào)度策略

算法2Scheduling Strategy

步驟1IFbest_Diff小于或等于0 THEN

從cF中隨機(jī)選擇一個子句cr，在該子句中隨機(jī)選擇一個變量task1；

步驟2IFtask1滿足分配策略THEN

翻轉(zhuǎn)task1。

3.3 基于任務(wù)分配與調(diào)度的GSAT算法

三種任務(wù)貪心策略起著不同的作用，我們只有有序地采用上面的三種策略才能達(dá)到求解3-SAT問題的目的。在整個搜索過程中，本文算法采用貪心的方式控制任務(wù)間的相互作用。設(shè)滿足任務(wù)貪心搜索策略的第一個任務(wù)記為temp，具體描述如下：

輸入：各初始化參數(shù):最大翻轉(zhuǎn)次數(shù)MAXFLIPS,最大嘗試次數(shù)MAXTRIES,pad,nad,pad′,nad′,子句集元素總個數(shù),Size,p。

輸出：任務(wù)的最優(yōu)解或“no solution found!”。

步驟1讀取子句集Cm；

步驟2計(jì)算每個任務(wù)的分配度；

步驟3所有子句的權(quán)重初始化為1；

步驟4FORi:=1toMAXTRIESDO

步驟5根據(jù)分配策略的條件，計(jì)算每個任務(wù)的分配值，作為搜索的起點(diǎn)；∥分配策略條件

步驟6FORj:=1toMAXFLIPSDO

步驟7產(chǎn)生一個[0,1)的隨機(jī)數(shù)r；

步驟8IF (r

步驟9ELSE

步驟10IF(best_Diff>0)THEN 翻轉(zhuǎn)temp

∥任務(wù)貪心搜索策略

步驟11ELSE

步驟12執(zhí)行任務(wù)調(diào)度策略；∥調(diào)度策略

步驟13IFSizecF不等于0 THEN

從cF中隨機(jī)挑選一個子句，并將它的權(quán)加1。

步驟14ENDFOR

步驟15ENDFOR

步驟16RETURN “no solution found!”；

4 仿真實(shí)驗(yàn)結(jié)果和分析

本文的實(shí)驗(yàn)環(huán)境為：處理器(Intel(R) Core(TM)i5-4590 CPU @ 3.30 GHz)，RAM(8.00 GB)，Windows 7 64位操作系統(tǒng)。實(shí)驗(yàn)數(shù)據(jù)是SATLAB庫中的“Uniform Random-3-SAT”標(biāo)準(zhǔn)問題集。因?yàn)镚SAT算法容易導(dǎo)致早熟的缺點(diǎn)，自2002年以后，從文獻(xiàn)中可以發(fā)現(xiàn)，很少有學(xué)者單獨(dú)研究GSAT算法求解3-SAT問題，大多都是將GSAT算法與具有全局搜索的算法相結(jié)合。2002年以前比較優(yōu)秀的GSAT算法有WalkSAT、Weighting+WalkGSAT和Learning+Weighting+GSAT，2002年以后在文獻(xiàn)[17]中提到了兩種新的GSAT算法LA-GSATRW和GSATRW。我們主要選擇具有高性能的Weighting+WalkGSAT算法、普通性能的GSATRW算法和2016年將GSAT算法與云計(jì)算相結(jié)合的遺傳算法進(jìn)行比較，用于驗(yàn)證本文算法中分配策略和調(diào)度策略的有效性。

將本文算法、Weighting+WalkGSAT算法和GSATRW算法的最大任務(wù)(變量)改變次數(shù)都設(shè)為MAXFLIPS*MAXTRIES=107。若一次運(yùn)行在規(guī)定的時(shí)間和最大變量改變次數(shù)內(nèi)找到3-SAT問題的一個最優(yōu)解，則此次運(yùn)行成功。成功率是成功運(yùn)行的次數(shù)與總運(yùn)行次數(shù)之比。

實(shí)驗(yàn)中這三種算法每個問題獨(dú)立運(yùn)行10次，而且參數(shù)pad和pad′在0.3～0.6，nad和nad′在1.8～2。在表3中分別給出每個問題集中的最大平均變量改變次數(shù)、最小平均變量改變次數(shù)、總平均變量改變次數(shù)和平均成功率，其中將Weighting+WalkGSAT算法在以下表中用WW表示，本文算法用AS表示，GSATRW算法用RW表示，最小平均變量改變次數(shù)用MAC表示，總平均變量改變次數(shù)用TAC表示，平均成功率用ASR表示。

從表3中的結(jié)果可以看出，本文算法具有較好的性能。在這三種算法中，本文算法的成功率是最高的，它對SATLAB庫中的8組問題集中的所有問題都能找到最優(yōu)真值指派，另外兩組都是只有一個問題沒有完全找到最優(yōu)解。與Weighting+WalkGSAT算法相比，雖然它們前7組問題集中的每一個問題都能找到解，但是本文算法比Weighting+WalkGSAT算法所需的變量改變次數(shù)明顯減少，尤其MAC分別減少了6倍左右;而且對于后3組問題集，其成功率分別提高了5%左右;對于前8組問題集，本文算法都是以更少的變量改變次數(shù)得到了更好的結(jié)果；對于后2組問題集，雖然本文算法所需的變量改變次數(shù)明顯增多，但是其成功率提高了6%左右。這說明Weighting+WalkGSAT算法在規(guī)定的時(shí)間內(nèi)找到最優(yōu)真值指派的比例明顯少于本文算法，即本文算法的時(shí)間復(fù)雜度明顯較低，體現(xiàn)了本文算法具有更好的時(shí)間性能。與GSATRW算法相比，本文算法更具有優(yōu)勢，其成功率分別提高了10%左右，MAC總體減少了12倍左右，TAC分別減少了5倍左右。因?yàn)樗惴ㄋ枳兞扛淖兇螖?shù)的多少影響時(shí)間效率，所以在表中沒有列舉出算法花費(fèi)的時(shí)間，即在成功率一樣的情況下，變量改變次數(shù)越少，算法花費(fèi)的時(shí)間越少?？傮w來說，對于前8組問題集，與另外兩種算法相比本文算法都體現(xiàn)了較好的性能，但是對于S9和S10集合它的MAC性能較弱，仍存在一定的改進(jìn)空間。

Table 3 Results comparison with other improved GSAT algorithms with 10 times running for 3-SAT problem

我們考慮到這些算法都是不完備算法，其結(jié)果有一定的隨機(jī)性，即在相同實(shí)驗(yàn)環(huán)境下，在不同時(shí)間段內(nèi)所測的結(jié)果可能會出現(xiàn)很大的偏差，所以為了使算法的性能比較更具有說服力，實(shí)驗(yàn)中對問題集中的每個問題獨(dú)立運(yùn)行10 000次，且參數(shù)設(shè)置與表3相同。我們考慮到一方面運(yùn)行次數(shù)太多，另一方面隨著變量的不斷增加，解空間的復(fù)雜性也隨著增加，算法所花費(fèi)的時(shí)間也隨著增加，其中對于含有100個變量問題集中的某個問題，本文算法需要花費(fèi)10個小時(shí)左右，所以如果對10組問題集中的每個問題都運(yùn)行10 000次，總共需要花費(fèi)的時(shí)間至少5個月，所以實(shí)驗(yàn)中我們只選擇了前4組問題集進(jìn)行分別測試。表4分別給出了每個問題集中的最多時(shí)間、最少時(shí)間、平均時(shí)間和總平均變量改變次數(shù)。

Table 4 Results comparison with different improved GSAT algorithms with 10000 times running for 3-SAT problem

另外，求解3-SAT問題的本文算法是通過設(shè)計(jì)兩種新的策略來完成整個貪心過程的，為了進(jìn)一步明確兩種策略在整個搜索過程中所起的作用，分別對這兩種策略的性能進(jìn)行了測試分析。我們在10組問題集中隨機(jī)選擇了3組問題集進(jìn)行測試，它們分別為S4、S7和S9，然后逐一對只有分配策略、只有調(diào)度策略、無分配策略和調(diào)度策略來完成整個貪心搜索過程，其中參數(shù)設(shè)置與表3中的實(shí)驗(yàn)完全相同，實(shí)驗(yàn)結(jié)果見表5。

Table 5 Algorithm comparision

從表5的結(jié)果可以看出，分配策略對算法性能的影響比較大，若除去該策略，變量改變次數(shù)大多明顯增加，所以相對花費(fèi)的時(shí)間也增加，貪心策略的作用是局部搜索，而分配策略的作用是全局搜索，剛好彌補(bǔ)了貪心策略的不足，通過分配策略指導(dǎo)貪心搜索的全局方向，減小搜索空間，從而減少變量改變次數(shù)和相應(yīng)的搜索時(shí)間。另外，調(diào)度策略在整個貪心搜索過程中也起到了不同程度的影響，通過調(diào)度策略防止算法陷入早熟，加快搜索的進(jìn)程。

5 結(jié)束語

本文根據(jù)任務(wù)分配與調(diào)度的主要目的提出了一種新的求解3-SAT問題的GSAT算法，并結(jié)合3-SAT問題的特點(diǎn)設(shè)計(jì)了兩種相應(yīng)的貪心策略。實(shí)驗(yàn)中采用標(biāo)準(zhǔn)數(shù)據(jù)庫中的3-SAT問題對算法進(jìn)行了全面的測試，并與其他改進(jìn)的GSAT算法進(jìn)行了比較，結(jié)果表明，不管在成功率方面還是總體平均變量改變次數(shù)方面，本文算法都優(yōu)于所比較的高效和普通性能改進(jìn)的GSAT算法。