一種求解Max-SAT問題的快速模擬退火算法

吳宇翔, 王曉峰,2, 于 卓, 謝志新, 莫淳惠, 曹澤軒

(1.北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 寧夏 銀川 750021; 2.北方民族大學(xué) 圖像圖形智能處理國(guó)家民委重點(diǎn)實(shí)驗(yàn)室 寧夏 銀川 750021)

0 引言

可滿足性問題(satisfiability problem,SAT)是如今計(jì)算機(jī)科學(xué)和人工智能研究的核心問題,也是著名的NP完全問題[1]。在理論研究與實(shí)際應(yīng)用方面,有著至關(guān)重要的作用。人工智能中的大多數(shù)難解問題,諸如規(guī)劃問題、組合優(yōu)化問題等都可通過編碼技術(shù)轉(zhuǎn)為SAT問題,再利用SAT問題求解器求解。隨著SAT問題的迅速發(fā)展,很多實(shí)際問題更多時(shí)候需要的是更優(yōu)解,而不僅僅用“是”或“否”來判斷,使得很多學(xué)者便開始研究SAT的優(yōu)化問題,如Max-SAT問題、Min-SAT問題、SMT問題、QBF問題[2-5]等。

最大可滿足性問題(maximum satisfiability,Max-SAT)是SAT問題的一種優(yōu)化版本,指尋找一組布爾變?cè)x值,使得滿足的子句數(shù)目最多。Max-SAT問題在統(tǒng)計(jì)物理、機(jī)器人路徑規(guī)劃[6]、組合拍賣和概論推理等領(lǐng)域有著廣泛的應(yīng)用,同時(shí)圖論中的最大割問題和最大團(tuán)問題[7]也可以轉(zhuǎn)換成Max-SAT問題進(jìn)行求解。目前,求解Max-SAT問題的算法一般分為基于回溯機(jī)制的完備性算法和基于局部搜索的非完備算法。完備性算法可以保證找到最優(yōu)解,主要代表有WmaxSatz[8]、MiniMaxSat[9]等,但在求解大規(guī)模問題時(shí),由于復(fù)雜度高,難以在合理時(shí)間內(nèi)找到結(jié)果,求解效率較低。相對(duì)于完備性算法,非完備性算法不保證一定能找到問題的精確解,但可通過問題的特性利用啟發(fā)式策略,在短時(shí)間內(nèi)找到一個(gè)較好解,并在面對(duì)大規(guī)模問題實(shí)例時(shí),該類求解方法有很重要的實(shí)際意義。

近些年,隨著物聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的迅速發(fā)展,數(shù)據(jù)量越來越大,Max-SAT的問題規(guī)模也逐漸增大,求解Max-SAT問題的原有算法已不再適用,設(shè)計(jì)新的求解算法或?qū)σ延械那蠼馑惴ㄟM(jìn)行優(yōu)化是目前研究的熱點(diǎn)。已有求解Max-SAT問題的算法主要包括遺傳算法、禁忌搜索算法、蟻群算法、正交免疫克隆粒子群算法、人工蜂群算法、模擬退火算法和路徑重連算法[10-16]等。其中模擬退火算法是一種經(jīng)典的基于局部搜索的智能優(yōu)化算法,作為一種有效的非線性組合優(yōu)化算法,該算法具有較好的局部搜索能力,并且理論基礎(chǔ)十分完善。目前,模擬退火算法已應(yīng)用于各種組合優(yōu)化問題,文獻(xiàn)[17]將模擬退火算法求解TSP問題。文獻(xiàn)[18]使用模擬退火算法求解構(gòu)造路徑規(guī)劃問題,但是對(duì)于Max-SAT問題,傳統(tǒng)的模擬退火算法存在搜索的盲目性和隨機(jī)性、收斂速度慢等問題。

本文提出了一種改進(jìn)的快速模擬退火算法(quick simulated annealing algorithm, QSA)求解Max-SAT問題。在QSA中,算法的初始解不是隨機(jī)生成,而是利用變?cè)獧?quán)值計(jì)算[19],生成一組初始解,為了進(jìn)一步提高算法的局部搜索和收斂能力,采用降溫函數(shù)進(jìn)行分段,起到快速降溫的效果;同時(shí),在降溫過程中引入不同的干擾策略和在Metropolis接受準(zhǔn)則中加入記憶功能[20],確保在同一溫度下,找到局部最優(yōu)解。對(duì)該算法的性能進(jìn)行實(shí)驗(yàn)分析,數(shù)值結(jié)果表明:QSA算法無論是在易解區(qū)域還是難解區(qū)域都能取得較好的性能,與傳統(tǒng)的啟發(fā)式搜索算法相比,有較好的優(yōu)越性。因此,QSA在求解Max-SAT問題方面起到了積極作用。

1 最大可滿足性問題(Max-SAT)

1.1 相關(guān)定義

Max-SAT問題是SAT的優(yōu)化形式,先對(duì)Max-SAT的構(gòu)成要素進(jìn)行說明。

定義1文字。每一個(gè)布爾變?cè)猉={x1,x2,…,xn}={0,1}n,變?cè)獂i取正時(shí)表示正文字;變?cè)獂i取反時(shí)表示負(fù)文字。

定義2子句。C={c1,c2,…,cm},對(duì)m個(gè)不同的子句形成一個(gè)子句集合,每一個(gè)子句由一個(gè)或多個(gè)文字組成,文字與文字之間通過析取運(yùn)算連接,記c=x1∨x2∨…∨xn,當(dāng)且僅當(dāng)子句中至少有一個(gè)文字為1時(shí),該子句滿足,反之子句不滿足。

定義3合取范式(conjunctive normal form,CNF)。由若干個(gè)子句合取構(gòu)成,即F=c1∧c2∧…∧cm,當(dāng)且僅當(dāng)CNF公式的每一個(gè)子句都滿足時(shí),稱合取范式CNF可滿足。

定義4最大可滿足性問題Max-SAT。給定一組命題變?cè)獂i∈X,由這些變?cè)纬梢唤M子句,構(gòu)成CNF公式,使得CNF公式中滿足子句的個(gè)數(shù)最多,也就是使得不滿足的子句個(gè)數(shù)最少。Max-SAT問題的數(shù)學(xué)模型為

(1)

ca∈{0,1},xi∈{0,1},

(2)

1.2 問題轉(zhuǎn)換

Max-SAT問題中每個(gè)子句中的變?cè)≈刀季哂须x散的特性,依據(jù)命題邏輯理論的相關(guān)結(jié)論,可以將Max-SAT問題轉(zhuǎn)成一個(gè)求解定義在{0,1}n的多項(xiàng)式函數(shù)f(X)的最大值的優(yōu)化問題。令l={x1,x2,…,xn},其是由n個(gè)0或1的整型變?cè)獦?gòu)成的集合,其中l(wèi)中的xi對(duì)應(yīng)子句c中的變?cè)獂i,1-xi對(duì)應(yīng)xi。于是在CNF公式中,F=c1∧c2∧…∧cm,可將符號(hào)∧看成一種普通的加法,而子句中c=x1∨x2∨…∨xn,可將符號(hào)∨看成一種特殊的乘法,記1⊕0=0⊕1=1⊕1=1,0⊕0=0。例如:CNF公式中,F=(x1∨x2∨x3)∧(x1∨x3∨x4),其中子句分別對(duì)應(yīng)c1=x1⊕x2⊕(1-x3),c2=x1⊕x3⊕(1-x4),函數(shù)f(X)=c1+c2=(x1⊕x2⊕(1-x3))+(x1⊕x3⊕(1-x4)),假設(shè)一組賦值X={x1=0,x2=1,x3=0,x4=1},可以得到f(X)=1,即最多滿足一個(gè)子句。因此,求解Max-SAT問題就可以轉(zhuǎn)化成

2 改進(jìn)的快速模擬退火算法

2.1 傳統(tǒng)的模擬退火算法

模擬退火算法(simulated annealing algorithm,SA)是一種全局統(tǒng)計(jì)優(yōu)化算法,其思想來源于模擬對(duì)固體進(jìn)行退火的過程,當(dāng)固體物質(zhì)溫度很高時(shí),固體內(nèi)部粒子做雜亂無序的運(yùn)動(dòng);當(dāng)溫度逐漸降低時(shí),固體內(nèi)部粒子運(yùn)動(dòng)逐漸有序,最終,整個(gè)物體達(dá)到內(nèi)能最低,便處于穩(wěn)定狀態(tài)。利用對(duì)溫度逐漸降低的過程,使算法在解空間中搜索出一個(gè)最優(yōu)近似解。

模擬退火算法常常用于求解組合優(yōu)化最小值問題,隨機(jī)初始一組解,以該解為起點(diǎn),在同一溫度下,不斷地對(duì)變?cè)x值進(jìn)行干擾,從而產(chǎn)生新解,將新舊解進(jìn)行比較,然后利用Metropolis接受準(zhǔn)則判斷是否接受新解。假設(shè)當(dāng)前解為xold,干擾后得到新解xnew,若新解的內(nèi)能Enew小于當(dāng)前解的內(nèi)能Eold,即ΔE=Enew-Eold<0,則接受該新解。否則,則以概率exp[-(Enew-Eold)/T]接受新解。重復(fù)上述過程,隨著迭代次數(shù)的增加和Metropolis接受準(zhǔn)則對(duì)新解的判斷,逐漸向該溫度下的最優(yōu)解靠近,當(dāng)溫度達(dá)到限制的迭代次數(shù)后,依據(jù)冷卻進(jìn)度表中的溫度衰減函數(shù)進(jìn)行降溫,再重復(fù)上述過程,最終可以求得問題的整體最優(yōu)解。標(biāo)準(zhǔn)Metropolis準(zhǔn)則表示為

(3)

其中:k代表卡爾茲曼常數(shù);T代表當(dāng)前狀態(tài)下的溫度。

對(duì)于Max-SAT問題,設(shè)X={x1,x2,…,xn}是一組布爾賦值,把目標(biāo)函數(shù)定義為不可滿足的子句數(shù)目,即找到不可滿足的最少子句數(shù)。如式(4)和式(5):

(4)

變?cè)獂若滿足子句,則子句為1,否則子句為0;

(5)

算法1傳統(tǒng)模擬退火算法

輸入:初始溫度為t0,停止溫度為tf,迭代次數(shù)為n。

輸出:輸出最優(yōu)解。

Step1:初始化溫度t0,初始解x={x1,x2,…,xn},并計(jì)算目標(biāo)函數(shù)E(x)。

Step2:同一溫度下,在解空間產(chǎn)生一個(gè)隨機(jī)的擾動(dòng),生成新解y={y1,y2,…,yn},并計(jì)算目標(biāo)函數(shù)E(y)。

Step3:若E(y)E(x),概率exp[-(Enew-Eold)/T]接受新解。

Step4:若達(dá)到熱平衡,即達(dá)到迭代次數(shù)n,轉(zhuǎn)step5,否則轉(zhuǎn)step2。

Step5:降低溫度tk,若tk

2.2 改進(jìn)的快速模擬退火算法

傳統(tǒng)模擬退火算法在求解Max-SAT實(shí)例時(shí),會(huì)出現(xiàn)效率很低、盲目搜索、收斂慢等問題,為彌補(bǔ)傳統(tǒng)模擬退火算法的不足,進(jìn)行以下3個(gè)方面的策略改進(jìn),優(yōu)化其性能,可更快速高效地求解出最優(yōu)的結(jié)果。

2.2.1變?cè)獧?quán)值計(jì)算 局部搜索算法中,搜索過程占用了整個(gè)算法的大多數(shù)時(shí)間,普遍的隨機(jī)搜索算法的初始解都是隨機(jī)生成的,會(huì)出現(xiàn)一定的隨機(jī)性,當(dāng)初始解比較好時(shí),可以高效地找到有效解,而初始解不好時(shí),會(huì)浪費(fèi)很長(zhǎng)時(shí)間從而降低了算法的性能,同時(shí)還會(huì)重復(fù)訪問一些解。本文提出的變?cè)獧?quán)值計(jì)算,利用變?cè)谡麄€(gè)子句集中出現(xiàn)的次數(shù)來決定對(duì)變?cè)馁x值,從而得到一組有效的初始解。對(duì)于每一個(gè)變?cè)紩?huì)記錄一個(gè)正或負(fù)權(quán)值,根據(jù)該變?cè)?fù)文字出現(xiàn)的差異,變?cè)臋?quán)值代表著變?cè)赡転檎蜇?fù)的程度。如果變?cè)臋?quán)值為正,則代表該變?cè)谡麄€(gè)子句集中出現(xiàn)正文字的次數(shù)較多,反之,若權(quán)值為負(fù),則代表出現(xiàn)負(fù)文字的次數(shù)較多。權(quán)值計(jì)算公式為

(6)

其中:Number(PosLit)代表變?cè)谡麄€(gè)子句集中出現(xiàn)正文字的次數(shù);Number(NegLit)代表變?cè)谡麄€(gè)子句集中出現(xiàn)負(fù)文字的次數(shù);Number(Clausevar)代表變?cè)谡麄€(gè)子句集中出現(xiàn)的次數(shù)。

2.2.2降溫函數(shù) 在傳統(tǒng)的模擬退火算法中,初始溫度和終止溫度的設(shè)置是影響整個(gè)模擬退火算法全局搜索性能中重要的因素之一,初始溫度足夠高,則搜索到全局最優(yōu)解的可能性就越大,但是會(huì)花費(fèi)大量的計(jì)算時(shí)間,反之,則可以節(jié)約時(shí)間,但搜索結(jié)果會(huì)受到影響。傳統(tǒng)模擬退火算法在降溫過程中采用T=T0α的指數(shù)函數(shù)進(jìn)行降溫,其中T0是當(dāng)前溫度,α是退火過程中溫度衰減率,通常取值為0.7<α<1.0。有研究表明,使用傳統(tǒng)的模擬退火算法求解Max-SAT問題,當(dāng)溫度較高時(shí),滿足的子句個(gè)數(shù)較少,而溫度較低時(shí),滿足的子句個(gè)數(shù)越多,其求解效率較高?；诖藛栴},本文提出一種快速分段降溫函數(shù)如式(7)所示,在溫度較高時(shí),采取高溫退火,快速降溫,提高求解時(shí)間,而溫度較低時(shí),采用低溫退火,慢速降溫,在低溫情況下,進(jìn)行充分搜索,尋找其局部最優(yōu)解,使得算法的整體收斂速度加快,從而有效減少求解時(shí)間。

(7)

其中:T0是當(dāng)前溫度;α是退火過程中溫度衰減率;k是迭代次數(shù);1/N通常取值為0.5或1。

上述兩種降溫函數(shù),均是指數(shù)形式。T0>10代表的是高溫退火階段,T0≤10代表的是低溫退火階段。高溫退火階段能夠快速降溫,再利用低溫退火階段進(jìn)行局部搜索。在求解Max-SAT問題時(shí),采用分段降溫的方法能夠快速高效地找到最優(yōu)解。

2.2.3干擾策略 傳統(tǒng)的模擬退火算法具有隨機(jī)性和盲目性,而且容易陷入局部最優(yōu),無法快速有效地找到最優(yōu)解等問題?；诖吮疚淖鞒龈倪M(jìn),在算法剛開始時(shí)溫度很高,目標(biāo)函數(shù)值很大,則對(duì)變?cè)x值進(jìn)行干擾后接受新賦值的概率較大,所以需要在大范圍的空間里對(duì)變量賦值進(jìn)行隨機(jī)擾動(dòng),以防陷入局部最優(yōu)。隨著溫度的降低,則有針對(duì)性對(duì)變?cè)x值進(jìn)行有策略地?cái)_動(dòng)。具體地講,在算法剛開始時(shí),溫度很高,以1-3/T作為選擇不同擾動(dòng)方案的概率,若小于此概率,便進(jìn)行隨機(jī)擾動(dòng),對(duì)解進(jìn)行隨機(jī)生成;若大于此概率,便進(jìn)行有策略擾動(dòng),隨機(jī)挑選一個(gè)變?cè)?對(duì)該變?cè)M(jìn)行翻轉(zhuǎn),從而產(chǎn)生新解。同時(shí),本文在Metropolis接受準(zhǔn)則中加入記憶功能,在同一溫度下,進(jìn)行多次干擾后,會(huì)記錄一個(gè)局部最優(yōu)值,以防丟失。當(dāng)整個(gè)降溫結(jié)束時(shí),在記錄表中直接找到全局最優(yōu)解即可。

改進(jìn)的快速模擬退火算法的流程如算法2,具體步驟如下。

算法2改進(jìn)的快速模擬退火算法(QSA)

輸入:初始溫度t0、停止溫度tf、閾值溫度te、迭代次數(shù)L、衰減函數(shù)α、當(dāng)前迭代次數(shù)k。

輸出: 輸出最優(yōu)解。

Step1:初始化溫度t0,初始解x={x1,x2,…,xn},并計(jì)算目標(biāo)函數(shù)E(x)。

Step2:隨機(jī)取一個(gè)0～1的實(shí)數(shù)rand0。

Step3:IF(rand0<1-3/T) {對(duì)解進(jìn)行重新隨機(jī)生成賦值,從而得到新解y={y1,y2,…,yn},并計(jì)算目標(biāo)函數(shù)E(y)}。

ELSE{隨機(jī)選擇一個(gè)變?cè)M(jìn)行翻轉(zhuǎn),從而得到新解y={y1,y2,…,yn},并計(jì)算目標(biāo)函數(shù)E(y)}。

step4:計(jì)算ΔE=E(y)-E(x)。

IF(ΔE<0) {無條件接受新解y={y1,y2,…,yn}和目標(biāo)函數(shù)E(y)}。

ELSE{隨機(jī)生成一個(gè)0～1的隨機(jī)數(shù)rand1}。

IF(rand1>exp[-(E(y)-E(x))/T]){接受新解y={y1,y2,…,yn}}和目標(biāo)函數(shù)E(y)。

ELSE{接受舊解x={x1,x2,…,xn}和目標(biāo)函數(shù)E(x)}。

step5:將該溫度下最優(yōu)值記錄到記錄表中。

step6:若達(dá)到熱平衡,判斷k>L是否滿足,若是,轉(zhuǎn)step7,否則轉(zhuǎn)step2。

Step7:判斷是否達(dá)到終止條件tk

Step8:判斷溫度是否達(dá)到閾值溫度,若tk>te,采取高溫退火,若tk

3 實(shí)驗(yàn)仿真及分析

為了準(zhǔn)確評(píng)估本文提出的改進(jìn)快速模擬退火算法QSA在解決Max-SAT問題的有效性。分別對(duì)算法QSA、SA、WalkSAT、GA、CCEHC和HS-Greedy進(jìn)行測(cè)試。其中WalkSAT、SA和GA為經(jīng)典的啟發(fā)式算法,CCEHC和HS-Greedy 為2016年Max-SAT Evalution 國(guó)際競(jìng)賽的求解器。本次實(shí)驗(yàn)采用Python語言在AMD R7-4800U,1.80 GHz的64位PC端進(jìn)行。采用的是隨機(jī)生成的3-SAT實(shí)例和2016年Max-SAT Evalution國(guó)際競(jìng)賽中隨機(jī)類的數(shù)據(jù)集,分析其求解精度和求解時(shí)間。

算法QSA設(shè)置的參數(shù)初始溫度t0為100 ℃,終止溫度tf為0.01 ℃,閾值溫度te為10 ℃,馬氏鏈長(zhǎng)度L為300,衰減函數(shù)α為0.95。其中閾值溫度te范圍設(shè)置為5 ℃

對(duì)于隨機(jī)生成3-SAT實(shí)例,生成模型如下。隨機(jī)均勻地從所有可能的子句(子句共有23×(n3)T)中選出m(m=αn)個(gè)子句。選出的子句以合取的方式連接,其中:n代表變?cè)獋€(gè)數(shù);m代表子句個(gè)數(shù),子句長(zhǎng)度為3;約束密度為α=m/n。約束密度α對(duì)CNF公式的可滿足性以及可滿足性判定的難易程度會(huì)產(chǎn)生重要的影響,幾乎所有算法的求解效率均與約束密度α密切相關(guān)。有學(xué)者研究表明,隨著約束密度α的增大,當(dāng)3.52<α<4.48時(shí),會(huì)發(fā)生相變。在相變范圍以外的可滿足性實(shí)例均為易解實(shí)例,高概率是可滿足的;在相變點(diǎn)附近的實(shí)例屬于難解實(shí)例,高概率是不可滿足的。

針對(duì)隨機(jī)生成3-SAT實(shí)例,表1是將本文算法QSA和遺傳算法GA進(jìn)行實(shí)驗(yàn)對(duì)比,采取約束密度α分別為4.5、5、10、15、20,變?cè)獋€(gè)數(shù)為50,子句個(gè)數(shù)分別為225、250、500、750、1 000進(jìn)行數(shù)值實(shí)驗(yàn)分析,比較兩種算法的求解時(shí)間(s)和求解精度(最少不滿足子句個(gè)數(shù)),其中加黑字體為算法對(duì)比當(dāng)前最優(yōu)解。實(shí)驗(yàn)表明,隨著約束密度的增加,不滿足子句個(gè)數(shù)也逐漸增加,同時(shí)兩種算法的求解時(shí)間也在增加,但QSA在求解精度和求解時(shí)間方面均遠(yuǎn)遠(yuǎn)優(yōu)于GA,由此說明QSA算法求解隨機(jī)生成的3-SAT實(shí)例中優(yōu)于傳統(tǒng)啟發(fā)式算法。

表1 隨機(jī)生成實(shí)例中QSA和GA在求解精度和 時(shí)間上對(duì)比Table 1 Comparison between QSA and GA in solving precision and time in randomly generated examples

表2給出QSA、WalkSAT、CCEHC和HS-Greedy四種算法的實(shí)驗(yàn)比較,采用2016年Max-SAT Evalution國(guó)際競(jìng)賽中隨機(jī)類的3種易解數(shù)據(jù)集的17個(gè)實(shí)例(變?cè)獋€(gè)數(shù)分別為70、90和110,子句個(gè)數(shù)分別為700、800、900、1 000、1 200),在最少不滿足子句個(gè)數(shù)上進(jìn)行實(shí)驗(yàn)對(duì)比,其中加黑字體為算法對(duì)比當(dāng)前最優(yōu)解。從表2中可以看出,CCEHC效果最好,17個(gè)實(shí)例中有15個(gè)實(shí)例都取得了最好結(jié)果,而本文提出的QSA算法有14個(gè)實(shí)例效果最好,略差于CCEHC,但相較于WalkSAT和HS-Greedy兩種算法,本文算法QSA在求解精度上遠(yuǎn)遠(yuǎn)優(yōu)于這兩種算法,其原因在于WalkSAT和HS-Greedy算法的搜索具有隨機(jī)性和盲目性,而本文提出的QSA算法使用了新的初始解生成方式,通過降溫函數(shù)和擾動(dòng)策略降低了搜索過程中的隨機(jī)性和盲目性,所以在求解性能上會(huì)有優(yōu)勢(shì)。因此,QSA算法在求解易解實(shí)例問題上具有一定的有效性。

表3是QSA、WalkSAT、CCEHC和HS-Greedy四種算法在難解實(shí)例中的算法對(duì)比,采用的是2016 年 Max-SAT Evalution 國(guó)際競(jìng)賽中隨機(jī)類的HG-3SAT-V250-C1000和HG-3SAT-V300-C1200兩個(gè)難解數(shù)據(jù)集(3-SAT實(shí)例,當(dāng)變?cè)獋€(gè)數(shù)為250時(shí)子句個(gè)數(shù)為1 000,當(dāng)變?cè)獋€(gè)數(shù)為300時(shí),子句個(gè)數(shù)為1 200)。每一類數(shù)據(jù)集中有5組數(shù)據(jù),其中加黑字體為算法對(duì)比當(dāng)前最優(yōu)解,比較四種算法最少不滿足子句個(gè)數(shù)。由表3可以得出CCEHC不滿足子句個(gè)數(shù)最少,10組數(shù)據(jù)中其均是排名第一,而本文提出的QSA算法略差一些,但仍然優(yōu)于WalkSAT和HS-Greedy算法。通過表2～3數(shù)據(jù)可以發(fā)現(xiàn),文本提出的算法QSA在求解易解實(shí)例時(shí)效果很好,但在求解難解實(shí)例時(shí)效果略差一些,其原因在于難解實(shí)例結(jié)構(gòu)特性較復(fù)雜,導(dǎo)致在進(jìn)行局部搜索時(shí),搜索程度不夠深入,搜索策略可能會(huì)陷入局部最優(yōu),從而導(dǎo)致求解性能略差于CCEHC,存在的這些問題也是算法今

表2 QSA、WalkSAT、CCEHC和HS-Greedy在易解實(shí)例中算法對(duì)比Table 2 Algorithm comparison of QSA, walksat, ccehc and HS greedy in easy to understand examples 單位:個(gè)

表3 QSA、WalkSAT、CCEHC和HS-Greedy在難解實(shí)例中算法對(duì)比Table 3 Algorithm comparison of QSA, walksat, ccehc and HS greedy in hard to solve examples 單位:個(gè)

后需要改進(jìn)的地方。

表4是將本文提出的QSA算法和傳統(tǒng)模擬退火算法SA的實(shí)驗(yàn)對(duì)比,采用的是2016 年 Max-SAT Evalution 競(jìng)賽中隨機(jī)類數(shù)據(jù)集在求解精度和求解時(shí)間上進(jìn)行比較,其中精度是指最少不滿足的子句個(gè)數(shù),時(shí)間是算法運(yùn)行時(shí)間,加黑字體為算法對(duì)比當(dāng)前最優(yōu)解。由表4可以看出,在求解精度和求解時(shí)間上,QSA算法的性能都優(yōu)于SA算法。QSA算法加入變?cè)獧?quán)值計(jì)算和干擾策略后,在加快求解速度的同時(shí)求解精度也得到了提高。SA算法在整個(gè)退火過程中,隨機(jī)擾動(dòng)很多,具有收斂慢的特點(diǎn),而QSA算法采用分段降溫的方式,在高溫區(qū)域可以快速降溫,在低溫區(qū)域進(jìn)行局部搜索大大提高了求解效率,從而避免了隨機(jī)擾動(dòng)和搜索的隨機(jī)性。由此可得,改進(jìn)后的模擬退火算法在求解Max-3-SAT問題時(shí)取得了很好的效果,且具有一定的穩(wěn)定性,在求解精度上,QSA也優(yōu)于SA,驗(yàn)證了本文算法的有效性。

表4 QSA和SA在求解精度和時(shí)間上對(duì)比Table 4 Comparison between QSA and SA in solution accuracy and time

4 結(jié)束語

本文提出一種改進(jìn)的快速模擬退火算法,主要是對(duì)算法的初始解進(jìn)行變?cè)獧?quán)值計(jì)算,并在降溫過程中,使用高低溫分段兩種降溫方式,同時(shí)根據(jù)Max-SAT問題的特性,采取不同的擾動(dòng)策略,在Metropolis接受準(zhǔn)則中加入記憶功能,從而提高算法在局部搜索過程中的精準(zhǔn)度,找到當(dāng)前滿足最多子句的個(gè)數(shù),加快整個(gè)算法的求解效率,避免算法陷入局部最優(yōu),實(shí)現(xiàn)精準(zhǔn)高效求解,并利用公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),進(jìn)一步驗(yàn)證算法的有效性。通過實(shí)驗(yàn)對(duì)比發(fā)現(xiàn),本文算法不論在易解實(shí)例還是難解實(shí)例,都表現(xiàn)出優(yōu)異的求解效率,其結(jié)果為以后的理論研究提供了參考價(jià)值。雖然本文提出的算法在求解時(shí)間和精度方面遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)模擬退火算法,但當(dāng)問題規(guī)模進(jìn)一步增大時(shí),整個(gè)算法的計(jì)算復(fù)雜度增加導(dǎo)致花費(fèi)時(shí)間增加,后續(xù)研究可以從利用模擬退火算法的可并行性和與其他智能優(yōu)化算法相結(jié)合的策略來入手,從而提高算法性能。