基于改進算子的遺傳算法

《基于改進算子的遺傳算法 》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于改進算子的遺傳算法孫秀娟濰坊科技學(xué)院山東壽光262700【文章】為提高算法收斂速度，本文提出一種改進算法來解決遺傳算法存在的問題。在選擇運算中引入一種抗早熟機制，防止算法陷入局部最優(yōu)解；在交叉運算中，通過動態(tài)調(diào)整交叉算子保證父代的優(yōu)良模式遺傳到下一代，加快算法的收斂速度。實驗證明，兩種改進算子的有效結(jié)合保證算法能以較快速度收斂于全局最優(yōu)解。【關(guān)鍵詞】遺傳算法；交叉算子：TP301.6：A0引言遺傳算法是一種全局隨機搜索算法，它有三種基本遺傳算子：選擇算子、交叉算子和變異算子，這些參數(shù)將直接影響算法的性能和收斂速度?；具z傳算法存在收斂速度慢、運行時間長、過早陷入局部最

2、優(yōu)解等問題。本文針對傳統(tǒng)遺傳算法存在的問題，提出一種改進算法。在選擇運算中引入一種抗早熟機制來防止算法陷入局部最優(yōu)解；在交叉運算中引入一種自識別交叉算子以加快算法收斂速度，減少運行時間。1改進的遺傳算法1.1選擇操作選擇運算是根據(jù)個體的適應(yīng)度，按照一定的規(guī)則，從第t代群體中選擇一些優(yōu)良個體保留到下一代群體中。本文引入一種抗早熟機制，即個體被選中的概率與適應(yīng)度大小存在一種函數(shù)關(guān)系。個體被中的概率與適應(yīng)度的關(guān)系如下：（1）（2）其中，為常數(shù)，。式（1）的概率需經(jīng)過歸一化后再進行輪盤賭選擇。用式（2）進行歸一化，m為群體規(guī)模。當個體的適應(yīng)度值大于1時，根據(jù)式（1），概率大于個體

3、的適應(yīng)度，當參數(shù)越小，這種關(guān)系越明顯。該方法可有效地預(yù)防算法提早陷于局部最優(yōu)解。1.2交叉算子交叉算子對遺傳算法的收斂速度有著重要影響。根據(jù)兩個個體的相似性，遺傳算法采用固定的交叉率對兩個個體進行交叉操作，導(dǎo)致父個體中的優(yōu)良模式不能被遺傳到下一代，進而降低了算法收斂速度。為提高父個體的優(yōu)良模式遺傳到下一代機率，本文提出一種自識別交叉算子，該算子根據(jù)個體間的相似度大小確定是否進行交叉操作。定義兩個串A和B的相似度如下：（3）其中l(wèi)是A和B的最長公共子串的長度，n為染色體串長度。下面定義一閾值p:其中大Z為進化代數(shù)，小z為當前進化代數(shù)。只有當兩個個體相似度小s小于大S時，兩個

4、個體才可以進行單點交叉。2實驗為了評估新算法的性能，使用1個Benchmark函數(shù)進行測試：本文分別采用傳統(tǒng)遺傳算法和改進算法對上述函數(shù)進行測試，種群規(guī)模取200，獨立運行50次，并記錄函數(shù)的最優(yōu)平均值和標準差。將本文算法運行的結(jié)果和傳統(tǒng)的遺傳算法進行比較，結(jié)果如表1示。由表1以看出，對于測試函數(shù)f1，本文算法得到的標準差雖然大于傳統(tǒng)算法，即本文算法得到的最優(yōu)解的波動性比傳統(tǒng)算法大，說明本文算法的收斂速度和搜索精度明顯優(yōu)于傳統(tǒng)算法。測試函數(shù)f1存在多個局部極值點，搜索過程易陷入局部最優(yōu)。因此，本文算法具有較強的多峰搜索能力。3結(jié)論本文提出一種改進遺傳算法，該算法在加快算法

5、收斂速度的同時，防止算法陷入局部最優(yōu)解?！?/p>