相對(duì)于標(biāo)準(zhǔn)約束優(yōu)化問(wèn)題,廣義約束優(yōu)化問(wèn)題（或稱析取優(yōu)化問(wèn)題）的等式或不等式約束條件中不僅包含邏輯"與"關(guān)系,還含有邏輯"或"關(guān)系.單調(diào)速率（RM）優(yōu)化問(wèn)題是廣義約束優(yōu)化問(wèn)題的一個(gè)重要應(yīng)用.目前RM優(yōu)化問(wèn)題已有的解法包括函數(shù)變換、混合整數(shù)規(guī)劃、線性規(guī)劃搜索等算法.隨著任務(wù)數(shù)的增多,這些算法的求解時(shí)間較長(zhǎng).提出一種基于線性規(guī)劃的深度廣度混合搜索算法（LPHS）,將廣義約束優(yōu)化問(wèn)題拆分成若干子問(wèn)題,建立線性規(guī)劃搜索樹,合理選擇搜索順序,利用動(dòng)態(tài)剪枝算法減小子問(wèn)題的規(guī)模,最終求得最優(yōu)解.實(shí)驗(yàn)結(jié)果表明,LPHS算法比其他方法有明顯的效率提升.研究成果與計(jì)算機(jī)基礎(chǔ)理論中的可滿足性模理論的研究相結(jié)合,有助于提高可滿足性模理論問(wèn)題的求解效率,促進(jìn)該理論在程序驗(yàn)證、符號(hào)執(zhí)行等領(lǐng)域的進(jìn)一步應(yīng)用. 

【文章來(lái)源】：軟件學(xué)報(bào). 2017,28(10)北大核心EICSCD

【文章頁(yè)數(shù)】：14 頁(yè)

【部分圖文】：

RM優(yōu)化問(wèn)題約束條件樹

這幾組實(shí)驗(yàn)中均有未解出的問(wèn)題,這表明,LPS方法的有效性并不能得到保證,進(jìn)入局部搜索的陷阱后會(huì)有難以跳出的情況發(fā)生.為了進(jìn)一步比較兩種算法求解時(shí)間的波動(dòng)性,我們統(tǒng)計(jì)了每組任務(wù)中求解時(shí)間的方差,由于計(jì)算結(jié)果的平均時(shí)間數(shù)值差異較大,我們先將每組數(shù)據(jù)均除以該組的平均運(yùn)行時(shí)間(超時(shí)用例統(tǒng)一用1000s計(jì)算),統(tǒng)計(jì)的方差結(jié)果如圖3所示.從圖中可以看出,LPS在求解相同規(guī)模的任務(wù)時(shí),求解時(shí)間的波動(dòng)性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber圖2LPS與LPHS算法求解時(shí)間比較圖3相同問(wèn)題規(guī)模的求解時(shí)間方差LPHS算法比LPS方法效率更高的原因主要包括如下兩點(diǎn).(1)LPS算法在深度優(yōu)先搜索中,沒(méi)有確定同一層可選子問(wèn)題求解的優(yōu)先順序,單純使用了深度優(yōu)先算法.而LPHS算法通過(guò)廣度優(yōu)先搜索,將同一層各子節(jié)點(diǎn)約束下的最優(yōu)值進(jìn)行排序,從最優(yōu)值大的子節(jié)點(diǎn)開始計(jì)算.即對(duì)Node1和Node2兩個(gè)節(jié)點(diǎn),假設(shè)Node1節(jié)點(diǎn)的最優(yōu)值opt1小于Node2節(jié)點(diǎn)的最優(yōu)值opt2,LPHS算法會(huì)先求解Node2的子節(jié)點(diǎn).因?yàn)镹ode2子節(jié)點(diǎn)求出的最優(yōu)值opt有可能大于opt1時(shí),此時(shí)可以將Node1節(jié)點(diǎn)剪掉,避免了對(duì)Node1子節(jié)點(diǎn)的計(jì)算,所以LPHS算法的混合搜索策略比LPS算法的深度優(yōu)先策略更加高效.(2)RM優(yōu)化問(wèn)題在轉(zhuǎn)化為搜索樹后,對(duì)于任一節(jié)點(diǎn)Nodeparent=1111nknnnknnPROBhhh,在它的所有子節(jié)點(diǎn)中,可能存在一個(gè)節(jié)點(diǎn)Nodechild1111nknnnknknnPROBhhhh,使得當(dāng)Nodeparent中約束條件滿足時(shí),Nodechild約束條件也滿足,LPS方法沒(méi)有考慮父子節(jié)點(diǎn)之間存在的上述關(guān)系,而LPHS方法通過(guò)第3.4節(jié)中的動(dòng)態(tài)剪枝算法對(duì)父子節(jié)點(diǎn)關(guān)系進(jìn)行了判斷,若N

這幾組實(shí)驗(yàn)中均有未解出的問(wèn)題,這表明,LPS方法的有效性并不能得到保證,進(jìn)入局部搜索的陷阱后會(huì)有難以跳出的情況發(fā)生.為了進(jìn)一步比較兩種算法求解時(shí)間的波動(dòng)性,我們統(tǒng)計(jì)了每組任務(wù)中求解時(shí)間的方差,由于計(jì)算結(jié)果的平均時(shí)間數(shù)值差異較大,我們先將每組數(shù)據(jù)均除以該組的平均運(yùn)行時(shí)間(超時(shí)用例統(tǒng)一用1000s計(jì)算),統(tǒng)計(jì)的方差結(jié)果如圖3所示.從圖中可以看出,LPS在求解相同規(guī)模的任務(wù)時(shí),求解時(shí)間的波動(dòng)性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber圖2LPS與LPHS算法求解時(shí)間比較圖3相同問(wèn)題規(guī)模的求解時(shí)間方差LPHS算法比LPS方法效率更高的原因主要包括如下兩點(diǎn).(1)LPS算法在深度優(yōu)先搜索中,沒(méi)有確定同一層可選子問(wèn)題求解的優(yōu)先順序,單純使用了深度優(yōu)先算法.而LPHS算法通過(guò)廣度優(yōu)先搜索,將同一層各子節(jié)點(diǎn)約束下的最優(yōu)值進(jìn)行排序,從最優(yōu)值大的子節(jié)點(diǎn)開始計(jì)算.即對(duì)Node1和Node2兩個(gè)節(jié)點(diǎn),假設(shè)Node1節(jié)點(diǎn)的最優(yōu)值opt1小于Node2節(jié)點(diǎn)的最優(yōu)值opt2,LPHS算法會(huì)先求解Node2的子節(jié)點(diǎn).因?yàn)镹ode2子節(jié)點(diǎn)求出的最優(yōu)值opt有可能大于opt1時(shí),此時(shí)可以將Node1節(jié)點(diǎn)剪掉,避免了對(duì)Node1子節(jié)點(diǎn)的計(jì)算,所以LPHS算法的混合搜索策略比LPS算法的深度優(yōu)先策略更加高效.(2)RM優(yōu)化問(wèn)題在轉(zhuǎn)化為搜索樹后,對(duì)于任一節(jié)點(diǎn)Nodeparent=1111nknnnknnPROBhhh,在它的所有子節(jié)點(diǎn)中,可能存在一個(gè)節(jié)點(diǎn)Nodechild1111nknnnknknnPROBhhhh,使得當(dāng)Nodeparent中約束條件滿足時(shí),Nodechild約束條件也滿足,LPS方法沒(méi)有考慮父子節(jié)點(diǎn)之間存在的上述關(guān)系,而LPHS方法通過(guò)第3.4節(jié)中的動(dòng)態(tài)剪枝算法對(duì)父子節(jié)點(diǎn)關(guān)系進(jìn)行了判斷,若N

【參考文獻(xiàn)】：
期刊論文
[1]基于樹狀線性規(guī)劃搜索的單調(diào)速率優(yōu)化設(shè)計(jì)[J]. 陳力,王永吉,吳敬征,呂蔭潤(rùn).  軟件學(xué)報(bào). 2015(12)
[2]基于邏輯“或”約束優(yōu)化的實(shí)時(shí)系統(tǒng)設(shè)計(jì)[J]. 劉軍祥,王永吉,王源,邢建生,曾海濤.  軟件學(xué)報(bào). 2006(07)
[3]單調(diào)速率及其擴(kuò)展算法的可調(diào)度性判定[J]. 王永吉,陳秋萍.  軟件學(xué)報(bào). 2004(06)



本文編號(hào)：3283216