一種基于相異因子的最優(yōu)保存策略*

張 雷 ，常敏慧

(1.運城學(xué)院 公共計算機(jī)教學(xué)部，山西 運城 044000；2.運城學(xué)院 應(yīng)用數(shù)學(xué)系，山西 運城 044000)

遺傳算法(GA)是根據(jù)生物進(jìn)化理論和遺傳變異理論提出的一種基于種群搜索的優(yōu)化算法，其思想是通過選擇復(fù)制和遺傳算子的共同作用使種群不斷進(jìn)化，最終收斂到優(yōu)化解[1]。在機(jī)器人控制、函數(shù)優(yōu)化、參數(shù)辨別等方面得到了廣泛的應(yīng)用，但簡單的遺傳算法(SGA)具有一些固有的弊端，如局部收斂性、早熟等。參考文獻(xiàn)[2]對交換和變異操作進(jìn)行了改進(jìn)，提出一種防止近親繁殖的交換策略，有效地避免了基因缺失。但由于海明距離下限不隨進(jìn)化代數(shù)和本代平均海明距離變化，因而不利于產(chǎn)生種群多樣性。參考文獻(xiàn)[3]利用構(gòu)造新選擇算子，通過按親緣關(guān)系放棄一個解而獲得另一個解來保證算法在最優(yōu)解的領(lǐng)域內(nèi)的有效搜索，提高全局最優(yōu)解的搜索能力和收斂速度。參考文獻(xiàn)[4]采用混沌變異算子的進(jìn)化算法，并提出“尺度收縮”的變異策略，從一定程度上提高了收斂速度。但由于采用線性交叉算子，在進(jìn)行交叉之前不進(jìn)行近親判斷和回避，因此交叉操作的效率不高。此外，許多文獻(xiàn)還對遺傳算法中的最優(yōu)個體保存策略進(jìn)行了研究[5～8]，其中最優(yōu)保存遺傳算法(ESGA)直接將最優(yōu)個體保存到下一代，具有全局收斂性，但是使得下一代中的某些個體缺乏活力，協(xié)作能力差。本文提出一種基于相異因子的最優(yōu)保存策略，用于最優(yōu)個體相異因子較大，但目標(biāo)值相近的個體，依次將種群中與最劣個體相似因子較大且目標(biāo)值相近的個體替換。既可以通過新添加的個體來保證種群多樣性，又可以保證全局收斂性。從而加快收斂速度，提高收斂性能。

1 相關(guān)定義

為了方便描述，引入以下定義：

定義 2 假設(shè) n維空間的任意兩個個體 M1=(x1，x2，…，xn)，M2=(y1，y2，…，yn)，每個分量的編碼長度不同，其中編碼采用m進(jìn)制編碼， 即xi=(xi1xi2…xij…xili)，yi=(yi1yi2… yij…yili)， 將第i個分量中對應(yīng)位置相同的位數(shù)記為Ci(i=1，2，…，n)，則定義這兩個個體間的相似因子為：

定義 3 假設(shè) n維空間的任意兩個個體 M1=(x1，x2，…，xn)，M2=(y1，y2，…，yn)，每個分量的編碼長度不同，其中編碼采用m進(jìn)制編碼， 即xi=(xi1xi2…xij…xili)，yi=(yi1yi2… yij… yili)，定義這兩個個體間的相異因子為[8]：

2 基于相異因子的最優(yōu)保存策略

在遺傳操作過程中，首先從種群中找出最優(yōu)個體ChromMaxHao和最劣個體ChromMaxBad，產(chǎn)生一個與最優(yōu)個體相異因子μ較大的個體ChromFan，為了既能夠保證種群多樣性，又能加快收斂速度，再隨機(jī)產(chǎn)生一個新個體ChromNew，比較ChromFan和ChromNew的目標(biāo)值，找出與ChromMaxHao最接近的個體并記為ChromFind。依次計算種群中的個體與最劣個體ChromMaxBad之間的相似因子v。當(dāng)v較大時，比較當(dāng)前個體與ChromFind的目標(biāo)值，如果當(dāng)前個體的目標(biāo)值小于ChromFind的目標(biāo)值，則用ChromFind替換當(dāng)前個體，這樣不僅保證了種群的多樣性，而且將種群中的最劣個體以及與其極其相似的個體都用較好的個體進(jìn)行替換，加快了收斂速度。

采用基于相異因子的最優(yōu)保存策略的遺傳算法(DESGA)描述如下：

(1)設(shè)置遺傳算法的基本參數(shù)，采用二進(jìn)制編碼，隨機(jī)產(chǎn)生初始種群Chrom；

(2)計算Chrom中各個體適應(yīng)度值FitnV；

(3)根據(jù)計算出的適應(yīng)度值FitnV將種群Chrom依次進(jìn)行選擇、交叉和變異操作，得到種群SelCh；

(4)在種群SelCh中找出最優(yōu)個體ChromMaxHao和最劣個體ChromMaxBad，根據(jù)相異因子μ計算得到ChromFind；

(5)根據(jù)相似因子依次用ChromFind替換與ChromMaxBad相似的個體；

(6)將 Chrom和 SelCh合并，得到新的Chrom；

(7)gen=：gen+1，若 gen小于最大代數(shù)，則轉(zhuǎn)到(2)繼續(xù)執(zhí)行，否則循環(huán)結(jié)束。輸出最優(yōu)值。

3 仿真實驗

為了驗證本文提出的基于相異因子的最優(yōu)保存策略的遺傳算法(DESGA)的有效性，將該策略和算法分別應(yīng)用到多個典型優(yōu)化測試函數(shù)中，分別與最優(yōu)保存遺傳算法(ESGA)和簡單遺傳算法(SGA)進(jìn)行分析和比較。其中，測試的基本參數(shù)設(shè)置如表1所示。染色體編碼采用二進(jìn)制編碼。

表1 測試基本參數(shù)設(shè)置

本文所用測試函數(shù)F1、F2、F3選擇參考文獻(xiàn)[9]中的典型測試函數(shù)。

F1：一元多峰函數(shù)

maxf(x)=xsin(10π·x)+2.0，x∈[-1，2]，該函數(shù)具有多個極值點，全局最大值為：x=1.850 5，f(x)=3.850 3

F2：多元單峰函數(shù)

F3：多元多峰函數(shù)-10≤x1，x2≤10，該函數(shù)具有多個極值點，全局最小值為(x1，x2)=(-1.434 2，-0.800 3)，f(x1，x2)=-186.730 9

分別利用DESGA、ESGA和SGA對上述三個函數(shù)進(jìn)行優(yōu)化測試，測試結(jié)果如表2所示。

表2 測試結(jié)果比較

從表2可以看出，ESGA只是簡單地將每一代產(chǎn)生的最優(yōu)個體直接保留，有可能使得下一代中的某些個體缺乏活力，協(xié)作能力差，DESGA利用相異因子產(chǎn)生與最優(yōu)個體目標(biāo)值相近的個體，并且利用該個體將種群中與最劣個體相似因子較大且目標(biāo)值相近的個體依次替換，這樣不僅可以保證種群多樣性，而且可以大大提高收斂速度。

本文提出了一種基于相異因子的最優(yōu)個體保存策略的遺傳算法(DESGA)，該算法相對于最優(yōu)保存遺傳算法(ESGA)和簡單遺傳算法(SGA)有更好的全局收斂性能。

[1]HOLLAND J H.Adaptation in natural and artificial systems[M].The University of Michigan Press，1975.

[2]邊潤強(qiáng)，陳增強(qiáng)，袁著祉.一種改進(jìn)的遺傳算法及其在系統(tǒng)辨識中的應(yīng)用[J].控制與決策，2000，15(5)：623-625.

[3]楊世達(dá)，單志勇，李慶華.基于親緣選擇的遺傳算法[J].計算機(jī)工程，2009，35(15)：10-12.

[4]駱晨鐘，邵惠鶴.采用混沌變異的進(jìn)化算法[J].控制與決策，2000，15(5)：557-560.

[5]孔春海，張志涌.基于最優(yōu)保存并行混合遺傳算法的直接盲信號檢測[J].西安郵電學(xué)院學(xué)報，2007，12(1)：71-75.

[6]王秀坤，赫然，張曉峰.一種改進(jìn)的最優(yōu)保存遺傳算法[J].小型微型計算機(jī)系統(tǒng)，2005，26(5)：833-835.

[7]尉宇，孫德寶.自適應(yīng)最優(yōu)保存的模擬退火遺傳算法及應(yīng)用[J].華中科技大學(xué)學(xué)報，2001，29(9)：46-47.

[8]畢惟紅，任紅民，吳慶標(biāo).一種新的遺傳算法最優(yōu)保存策略[J].浙江大學(xué)學(xué)報(理學(xué)版)，2006，33(1)：32-35.

[9]雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.