一種基于相異因子的最優保存策略*

張 雷 ，常敏慧

(1.運城學院 公共計算機教學部，山西 運城 044000；2.運城學院 應用數學系，山西 運城 044000)

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

1 相關定義

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

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

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

2 基于相異因子的最優保存策略

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

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

(1)設置遺傳算法的基本參數，采用二進制編碼，隨機產生初始種群Chrom；

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

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

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

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

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

(7)gen=：gen+1，若 gen小于最大代數，則轉到(2)繼續執行，否則循環結束。輸出最優值。

3 仿真實驗

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

表1 測試基本參數設置

本文所用測試函數F1、F2、F3選擇參考文獻[9]中的典型測試函數。

F1：一元多峰函數

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

F2：多元單峰函數

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

分別利用DESGA、ESGA和SGA對上述三個函數進行優化測試，測試結果如表2所示。

表2 測試結果比較

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

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

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

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

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

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

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

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

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

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

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