智能優(yōu)化算法的性能及搜索空間研究.pdf

1、優(yōu)化作為一個重要的科學(xué)分支，一直受到人們的廣泛重視，它對多個學(xué)科產(chǎn)生了重大影響，并在諸多工程領(lǐng)域得到迅速推廣和應(yīng)用，己成為不同領(lǐng)域中很多工作不可或缺的工具。 優(yōu)化算法基于某種思想和機(jī)制，通過一定的途徑來得到滿足用戶要求的解?，F(xiàn)在，求解線性規(guī)劃、非線性規(guī)劃以及隨機(jī)規(guī)劃、幾何規(guī)劃、整數(shù)規(guī)劃等各種最優(yōu)化問題的理論研究發(fā)展迅速，新方法不斷出現(xiàn)，實(shí)際應(yīng)用日益廣泛。在計(jì)算機(jī)技術(shù)的推動下，最優(yōu)化理論與方法在經(jīng)濟(jì)計(jì)劃、工程設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)

2、輸?shù)确矫娴玫搅藦V泛應(yīng)用，成為一門十分活躍的學(xué)科。 很多優(yōu)化問題如旅行商問題、設(shè)備布局問題、生產(chǎn)調(diào)度問題等等，已被證明是NP完全問題，至今沒有有效的多項(xiàng)式時間解法，用傳統(tǒng)的最優(yōu)化方法求解，需要的計(jì)算時間與問題的規(guī)模成指數(shù)關(guān)系。因此，人們轉(zhuǎn)而求其次，發(fā)展了很多隨機(jī)性搜索算法，希望在有限的時間內(nèi)求得問題的次優(yōu)解或近優(yōu)解，如蒙特卡羅模擬、模擬退火、遺傳算法、禁忌搜索及其混合優(yōu)化策略等。 智能優(yōu)化算法作為新興的搜索算法，一般是指利

3、用自然界的生物系統(tǒng)與優(yōu)化過程的某些相似性而逐步發(fā)展起來的優(yōu)化算法，如遺傳算法、粒子群算法、蟻群算法等，它們通過對搜索空間中的一組解按某些概率規(guī)則操作得到下一組解。因此算法本身的搜索機(jī)制決定算法對空間的全局搜索能力和局部尋優(yōu)能力，從而決定算法的搜索性能，即是否能較快地收斂于全局最優(yōu)解。同時，由于變量取值、約束復(fù)雜等使得搜索空間中可行解與不可行解交叉分布，空間結(jié)構(gòu)很不規(guī)則，往往造成智能優(yōu)化算法得到不可行解的無效搜索過多，極大地影響搜索速度，

4、且算法不能很好地收斂到最優(yōu)解。因此，本論文主要圍繞智能優(yōu)化算法的空間搜索能力，從算法搜索機(jī)制和搜索空間結(jié)構(gòu)兩個方面，研究增強(qiáng)算法的全局搜索能力的方法，同時兼顧局部尋優(yōu)能力，以避免算法陷入局部最優(yōu)，提高搜索性能。 此前的智能優(yōu)化算法，在搜索過程中不斷繁殖好解并擇優(yōu)保留個體，導(dǎo)致有效成分缺失，群體多樣性降低，從而使算法失去了探索新空間區(qū)域的能力，易于陷入局部最優(yōu)。而算法運(yùn)行后期局部搜索能力不強(qiáng)，收斂速度過慢，得到的解的質(zhì)量不高。權(quán)衡

5、算法的空間探測和開發(fā)能力，即大范圍全局搜索和小范圍局部尋優(yōu)能力，并且在算法運(yùn)行過程中有效控制搜索的進(jìn)行，才能使算法具有較好的搜索性能，提高收斂速度和解的質(zhì)量。 1．針對算法種群多樣性減小導(dǎo)致的算法失去空間探索能力的問題，在算法迭代過程中以合理的方式接受劣解，以增加種群的多樣性，可以避免算法陷入局部最優(yōu)，從而提高算法的搜索性能。 變異操作是產(chǎn)生種群多樣性的根本，交叉(包括信息交互或傳遞)起加速作用。因此選用僅包含變異操作的進(jìn)化規(guī)劃

6、算法，引入退火概率的選擇方式，每次迭代以退火概率接受劣解，形成退火進(jìn)化規(guī)劃算法。經(jīng)證明這種算法是全局收斂的，可有效地避免局部最優(yōu)，較快地達(dá)到最優(yōu)解。通過估計(jì)算法種群以概率1包含最優(yōu)解的速度和達(dá)到收斂的最大時間，發(fā)現(xiàn)退火因子會影響算法的收斂速度，通過選擇合適的退火因子，可以提高算法的收斂速度。 2．在算法的搜索過程中以當(dāng)前信息為基礎(chǔ)不斷產(chǎn)生新解，在犧牲部分時間性能的條件下，也可以擴(kuò)展搜索范圍。本文利用組合優(yōu)化問題的解的模式概念，通

7、過比較種群中的解包含的相同模式，在迭代過程中產(chǎn)生新解來提高算法的全局搜索能力和解的質(zhì)量。 (1)首先改變利用極值操作的個體解的變量適應(yīng)度定義，使其與目標(biāo)函數(shù)相關(guān)。經(jīng)實(shí)驗(yàn)證實(shí)，新的目標(biāo)函數(shù)適應(yīng)度可較大程度提高個體的搜索能力。應(yīng)用新的變量適應(yīng)度定義，設(shè)計(jì)了基于模式的極值進(jìn)化算法。解的模式信息的利用增強(qiáng)了算法的局部搜索能力，較好地改善了解的質(zhì)量。最后證明了算法的收斂性。 (2)基于新的目標(biāo)函數(shù)適應(yīng)度，分析迭代過程中產(chǎn)生的新解對

8、搜索的影響作用。然后以拓?fù)溥M(jìn)化網(wǎng)絡(luò)描述的生物進(jìn)化模型為結(jié)構(gòu)，設(shè)計(jì)具有可變種群規(guī)模的網(wǎng)絡(luò)拓?fù)溥M(jìn)化算法。經(jīng)過對比，該算法明顯擴(kuò)展了搜索的范圍。由于網(wǎng)絡(luò)拓?fù)溥M(jìn)化算法不設(shè)定解的變異方式，因而可以采用各種現(xiàn)有的變異方法，具有廣泛的可結(jié)合性。該算法主要用于離散優(yōu)化問題，然而通過將連續(xù)變量轉(zhuǎn)換成二進(jìn)制編碼，以相同取值的二進(jìn)制“位”表示解的相同部分，算法也可應(yīng)用于連續(xù)函數(shù)優(yōu)化。 優(yōu)化問題搜索空間龐大、算法搜索的隨機(jī)性與搜索速度之間的矛盾，也在很

9、大程度上影響了算法性能。大部分智能優(yōu)化算法屬于全局搜索算法，都是在問題的全空間上進(jìn)行搜索，當(dāng)問題規(guī)模變大時，搜索空間迅速膨脹。此前的智能優(yōu)化算法都是在不明確空間結(jié)構(gòu)的情況下進(jìn)行尋優(yōu)，所以其盲目性很大，隨著優(yōu)化問題規(guī)模的增大，算法的搜索時間往往以指數(shù)速度增長。目前所研究的確定型模型，一般都有確定的空間結(jié)構(gòu)，但是算法在搜索過程中不了解最優(yōu)解和空間結(jié)構(gòu)的關(guān)系，因此要改善算法的性能，除了設(shè)計(jì)更為合理的搜索機(jī)制，研究問題的搜索空間也有重要意義。

10、 1．智能優(yōu)化算法通過在空間的搜索來尋找問題的最優(yōu)解，因此了解搜索空間結(jié)構(gòu)有助于理解問題求解的難度，從而設(shè)計(jì)合適的搜索策略以提高求解效率。 (1)傳統(tǒng)的遺傳算法等智能優(yōu)化算法基本不使用搜索空間的知識，從而影響了算法的搜索效率。已經(jīng)搜索到的解能夠反映空間的部分信息，利用這些信息可以對算法進(jìn)行指導(dǎo)，實(shí)現(xiàn)算法的自適應(yīng)搜索，在此思想基礎(chǔ)上設(shè)計(jì)了具有信息指導(dǎo)的退火進(jìn)化規(guī)劃算法。經(jīng)過仿真比較，算法具有更快的收斂速度：對于較大規(guī)模的優(yōu)化

11、問題，解的精度誤差百分比仍然可以控制在3﹪以內(nèi)。 (2)雖然智能優(yōu)化算法的共同特點(diǎn)是對優(yōu)化問題的依賴性小，但都具有隨機(jī)性，且都是在問題的全空間尋優(yōu)。實(shí)現(xiàn)尋優(yōu)空間的簡約，可以提高算法的搜索速度和解的質(zhì)量。此前的空間收縮和劃分方法，缺乏針對性，難處理離散優(yōu)化問題，且需要人為設(shè)定劃分的子空間個數(shù)。這里用不完全演化的智能優(yōu)化算法獲得好解信息收縮空間后，利用組合優(yōu)化的解的模式將搜索空間自動地劃分為一個或多個最優(yōu)解域，然后再進(jìn)行局部優(yōu)化。經(jīng)

12、車間作業(yè)調(diào)度問題仿真驗(yàn)證，該方法可快速獲得多個高質(zhì)量的解。 2．對于具體的優(yōu)化問題，問題的空間結(jié)構(gòu)或某些性質(zhì)是已知的，如能充分利用，必能提高算法效率，從而減少搜索的不確定性，提高解的質(zhì)量。 混合整數(shù)規(guī)劃模型(MIP)的空間，可由整數(shù)變量自然地劃分為多個分散的子空間，將搜索限制在可行解的子空間可降低優(yōu)化算法的搜索工作量。在生產(chǎn)調(diào)度形成的MIP模型中存在任務(wù)加工所用設(shè)備之間的競爭約束，我們將這個性質(zhì)融合到算法中，可以實(shí)現(xiàn)空間

13、的進(jìn)一步簡約，從而將搜索限制在可行的子空間。通過分析間歇過程生產(chǎn)調(diào)度形成的0-1MIP模型中的0-1變量間及其與實(shí)數(shù)變量之間的關(guān)系，設(shè)計(jì)基于空間劃分的分解算法，并對分解算法所適用的問題規(guī)模進(jìn)行分析。結(jié)果表明：當(dāng)求解算法的復(fù)雜度O(f(·))的函數(shù)增長速度大于2”的增長速度，且連續(xù)變量個數(shù)m、0-1變量個數(shù)n均大于閾值ξ時，分解算法可以極大地降低求解的計(jì)算量。綜上所述，經(jīng)過對智能優(yōu)化算法的搜索機(jī)制和搜索空間的分析，本文從算法搜索機(jī)制和空間

14、結(jié)構(gòu)兩方面對提高求解性能的方法做了系統(tǒng)的研究工作。一方面，在算法迭代過程中以合理的方式接受劣解或產(chǎn)生新解，擴(kuò)展了算法的搜索范圍，從而增強(qiáng)了算法的全局搜索能力，使其能獲得高質(zhì)量的解。另一方面，利用搜索空間的信息來指導(dǎo)搜索或估計(jì)空間結(jié)構(gòu)，提高了算法的效率和求解質(zhì)量。基于模型的已知空間結(jié)構(gòu)和問題的性質(zhì)簡約空間，可以設(shè)計(jì)更合適的求解策略，降低求解的復(fù)雜性。將智能優(yōu)化算法與問題空間結(jié)構(gòu)結(jié)合的優(yōu)化方式，是很有發(fā)展前途的研究方向，正受到越來越多優(yōu)化研