回溯搜索算法的改進及其工程應(yīng)用.pdf

1、優(yōu)化模型是分析與求解科學(xué)和工程問題的基本工具之一，隨著科技的不斷進步，優(yōu)化模型也變得越來越復(fù)雜，經(jīng)常會出現(xiàn)規(guī)模大、離散性、非線性、不可導(dǎo)和非凸性等特點。因此，對該種復(fù)雜模型求解方法的研究一直是本領(lǐng)域國內(nèi)外研究的前沿方向。智能優(yōu)化算法由于在處理這種復(fù)雜模型時表現(xiàn)出來特有的高效性而備受關(guān)注，成為智能計算與工程優(yōu)化鄰域的研究熱點。本文針對一種新型智能優(yōu)化算法——回溯搜索算法（Backtracking Search Algorithm，BSA）

2、開展研究，主要包括算法的詳細分析，算法在約束優(yōu)化問題、組合優(yōu)化問題中的改進，以及其具體的工程實際應(yīng)用等方面。
　　首先介紹了回溯搜索算法的基本原理，詳細介紹了其基本流程和主要操作，并分析了其優(yōu)勢和不足，為后面在相應(yīng)問題上的改進和應(yīng)用提供了理論基礎(chǔ)。
　　其次，針對約束優(yōu)化問題，分析了其求解難點，并在已有研究的基礎(chǔ)上，提出了一種新的約束處理機制——自適應(yīng)ε約束法（Self-adaptationε-constraints，SAε

3、）。通過13個經(jīng)典的約束優(yōu)化函數(shù)的測試，驗證了本文提出約束機制 SAε的高效性，以及基于BSA的約束問題求解算法（BSA-SAε）在收斂速度、搜索精度等方面優(yōu)勢。
　　接著，針對以置換流水車間調(diào)度為代表的組合優(yōu)化問題，通過重構(gòu)解的空間，改進交叉和變異算子，引入模擬退火機制和隨機插入局部搜索等方法，將 BSA用于求解組合優(yōu)化問題，提出了混合回溯搜索算法（Hybrid Backtracking Search Algorithm，HBS

4、A）。通過29個標準測試案例，驗證了隨機插入局部搜索方法的有效性和HBSA在求解組合優(yōu)化問題時的高效性。
　　然后，將前兩章提出的兩種算法BSA-SAε和HBSA分別應(yīng)用于結(jié)構(gòu)設(shè)計參數(shù)優(yōu)化和某汽車發(fā)動機連桿生產(chǎn)車間調(diào)度優(yōu)化工程實例中。結(jié)果表明了 BSA-SAε在處理約束問題時的高效性，和HBSA在處理置換流水車間問題時的有效性，體現(xiàn)了所提出的兩種算法在實際工程中廣泛應(yīng)用前景。
　　最后，對全文進行了總結(jié)，并展望了未來的研究。