基于遺傳算法和禁忌搜索算法的混合策略及其應用.pdf

《基于遺傳算法和禁忌搜索算法的混合策略及其應用.pdf》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、維普資訊http://www.cqvip.com第32卷第3期北京工業(yè)大學學報Vo1．32NO．32006年3月JOURNAIOFBEIJINGUNIVERSITYOFTECHNOLOGYMar．2006基于遺傳算法和禁忌搜索算法的混合策略及其應用孫艷豐(北京工業(yè)大學計算機學院，北京100022)摘要：為了提高遺傳算法的局部搜索能力，根據(jù)遺傳算法和禁忌搜索算法自身的特點，通過分析2者的優(yōu)勢和不足，提出了一種將2者混合使用的求解優(yōu)化問題的方法．本算法用遺傳算法作全局搜索，用禁忌搜索算法作局部搜索，可以加快收斂速度，得到滿意的計算結果．同時，為抑制早熟現(xiàn)象，避免收斂到局

2、部最優(yōu)點，提出了一種應對策略．實驗結果表明，該算法在計算速度和計算結果方面都有改進．關鍵詞：遺傳算法；收斂；全局最優(yōu)中圉分類號：TP301．6文獻標識碼：A文章編號：0254—0037(2006)03—0258—05遺傳算法(geneticalgorithm，簡稱GA)和禁忌搜索(tabusearch，簡稱TS)算法是2種十分有效的全局搜索算法，前者源于生物遺傳學，模擬自然界生物的優(yōu)勝劣汰、適者生存的過程，后者模擬一種智力過程．這2種算法都與問題無關，通用性與優(yōu)化性較好，能處理復雜、大規(guī)模優(yōu)化問題，但并不是對所有問題都適用．文獻[1]根據(jù)2者的特點提出將2者混合使用

3、的策略，但其缺點是調用TS算法過于頻繁，計算量大；而不調用Ts算法又易早熟(群體中的個體過早地收斂到某點附近，不能使搜索轉向解空間的其他區(qū)域)，產生局部最優(yōu)解．作者首先對GA和TS算法進行了分析比較，有效結合它們各自優(yōu)勢，提出混合使用的方法；同時對于早熟現(xiàn)象，提出一種早熟判定與應對策略；最后進行了計算試驗．GA及TS算法簡介1．1GA的特點與不足目前，已經有許多GA的變形，但人們習慣上把1975年Holland提出的GA稱為標準GA[4】．與傳統(tǒng)的優(yōu)化算法相比，標準GA具有如下特點：1)搜索過程不直接作用在變量上，而是作用在將變量編碼后的字符串上；2)搜索過程是從一

4、組解迭代到另一組解，這樣可降低陷入局部最優(yōu)解的概率；3)使用隨機搜索過程而不是確定性搜索過程；4)只利用目標函數(shù)和約束函數(shù)的函數(shù)值信息，不需要導數(shù)等其他輔助信息，因此通用性更大，適用范圍更廣．5)作為一種優(yōu)化算法，尋求最優(yōu)點不是GA的唯一目的，更重要的目的是進步，即它的優(yōu)化過程是一個不斷改進的過程．GA具有并行搜索能力，從解空間中多點出發(fā)搜索問題的最優(yōu)解，能在一定程度上保留歷史信息，適合求解大規(guī)模任意目標函數(shù)的全局優(yōu)化問題．但它也有不足，進行局部搜索能力差，導致發(fā)生早熟．這是因為算法的變異概率太小，引入新染色體的機會少。如果變異概率取大些，傳統(tǒng)的變異算子將導致算法隨

5、機性很大，使搜索過程過于盲目．收稿日期：2004—09—07．基金項目：北京市教育委員會科技發(fā)展計劃資助項目(Km200310005025)作者簡介：孫艷豐(1964一)，女，黑龍江齊齊哈爾人，教授．維普資訊http://www.cqvip.com第3期孫艷豐：基于遺傳塑法莖墾塑窒篁望竺壘墮墮墾苧些壟11．2Ts算法的特點與不足TS算法是由Glover于1986年提出的引，它是一種全局逐步尋優(yōu)的搜索算法，也是一種模擬智力過程的“爬山，，算法，它通過一個靈活的記憶功能和藐視準則達到搜索解空間的目的．算法的基本思想如下：假設給出1個解和1個鄰域，首先在這鄰域中找出1個最

6、好的局部解作為當前解z，令當前最優(yōu)解z：z，然后再在這個當前解的鄰域中搜索最好的局部解．但是，這個最好解有可能與前次的相同，為避免這種循環(huán)的現(xiàn)象，設置1個記憶近期操作的禁止操作表，如果當前操作是記錄在此表中的操作，那么，這一操作就被禁止，否則用z取代z．此時z點的目標函數(shù)值可能劣于點的目標值，所以Ts算法以一定概率接受劣解．但對那些特別有益的操作，如果改善了目前找到的最優(yōu)解，可以忽視被禁止的特性(即此時仍令z=z，z：z)，以便迅速找到更好的解，同時為保證搜索更大的解空間，對每個被禁止的操作，設定1個期限，在下次操作時，這個值被減1．當這個值為0時，該操作可重新變成

7、不被禁止的操作．在搜索過程中有些操作出現(xiàn)的頻率很高，為了不重復這樣的操作，對每個操作再設定1個頻率值，該操作每出現(xiàn)1次，頻率值就加1，當頻率值超過某一設定值時，該操作也被列為禁止操作．重復上述搜索迭代過程，直至滿足停止計算準則．與傳統(tǒng)的優(yōu)化算法相比，TS算法的主要特點是：1)在搜索過程中可以接受劣解，所以具有較強的“爬山”能力；2)新解不是在當前解的鄰域中隨機產生，而是從中選取最好解，即最好解的產生概率遠遠大于其他解．TS算法由于具有靈活的記憶功能和藐視準則，并且在搜索過程中可以接受劣解，所以具有較強的“爬山”能力．這樣，搜索時能跳出局部最優(yōu)解，而轉向解空間的其