基于SAT的規(guī)劃理論與算法研究.pdf

1、本文研究了經(jīng)典規(guī)劃形式化、SAT規(guī)劃形式化、SAT問(wèn)題求解算法和領(lǐng)域知識(shí)表示與使用等方面，主要的內(nèi)容有：在研究智能規(guī)劃概念模型、經(jīng)典規(guī)劃模型和因果理論規(guī)劃模型的理論的基礎(chǔ)上，重點(diǎn)論述了基于情景演算、基于規(guī)劃圖和基于因果規(guī)劃的三種主要的SAT規(guī)劃形式化方法，以及編碼復(fù)雜性與優(yōu)化編碼的技術(shù)。回顧了SAT問(wèn)題已有的主要算法及存在的問(wèn)題，總結(jié)了提高算法性能和跳出局部陷井所用的策略或機(jī)制。提出了SAT問(wèn)題的子句權(quán)重多項(xiàng)式轉(zhuǎn)換等方法和相應(yīng)的求解算法

2、SAT-GA。給出了與GSAT和WSAT對(duì)比和觀察早熟現(xiàn)象的實(shí)驗(yàn)結(jié)果。為了解決早熟問(wèn)題，進(jìn)行了一般遺傳算法的可視化實(shí)驗(yàn)，說(shuō)明了局部最優(yōu)解的吸引作用與早熟的關(guān)系，提出了利用吸引作用和強(qiáng)化最優(yōu)解的吸引作用解決早熟問(wèn)題策略，并在分析了經(jīng)典遺傳算法框架的一些局限性的基礎(chǔ)上，引進(jìn)了函數(shù)逆優(yōu)化問(wèn)題、幾何相似性、幾何相似變換、平臺(tái)早熟學(xué)準(zhǔn)則和學(xué)習(xí)算子等概念，描述了我們提出的基于學(xué)習(xí)機(jī)制的遺傳算法理論，擴(kuò)展了經(jīng)典遺傳算法框架。結(jié)合SAT問(wèn)題特殊知識(shí)，提

3、出了子句權(quán)重表示啟發(fā)知識(shí)和約束強(qiáng)弱的量化表示方法和基于子句權(quán)重學(xué)習(xí)的SAT-WAGA算法，描述了子句權(quán)重學(xué)習(xí)算子的策略設(shè)計(jì)和算法描述，提供了性能比較、參數(shù)優(yōu)化和解決早熟效果等等多種目的的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果表明SAT-WAGA算法能有效解決早熟問(wèn)題和顯著提高性能。提出了領(lǐng)域知識(shí)表示和應(yīng)用策略和在SAT規(guī)劃器中SAT-WAGA算法與其它算法結(jié)合方式。在領(lǐng)域知識(shí)的挖掘研究中，提出了并實(shí)現(xiàn)了不確定性規(guī)劃領(lǐng)域的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)遺傳算法和物流問(wèn)題中求