胡承剛，高建瓴，喻明豪，白羽飛，陳 楠

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025）

0 引 言

遺傳算法最早由美國Michigan 大學(xué)的教授John Holland模擬生物遺傳和進(jìn)化提出［1］。二十世紀(jì)80 年代，De Jong 基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行數(shù)值優(yōu)化實(shí)驗(yàn)，歸納總結(jié)形成其基本框架。遺傳算法通過將目標(biāo)函數(shù)的自變量映射為生物遺傳進(jìn)化中的染色體，對染色體編碼來實(shí)現(xiàn)向下進(jìn)化，并找到使目標(biāo)函數(shù)最優(yōu)的染色體；同時，遺傳過程中加入了交叉和變異操作，來優(yōu)化下一代染色體。遺傳算法中染色體的編碼方式有浮點(diǎn)數(shù)編碼和二進(jìn)制編碼兩種方式。不同的染色體編碼方式和采取的變異算子、交叉算子的差異同樣造成了遺傳算法不同［2］。由于遺傳算法是一種全概率搜索優(yōu)化算法，所以其對于目標(biāo)函數(shù)的性質(zhì)沒有要求，比如：可微、連續(xù)等，所以在很多實(shí)際問題中都有應(yīng)用，比如：數(shù)值函數(shù)尋優(yōu)、多目標(biāo)優(yōu)化、機(jī)器學(xué)習(xí)、圖像處理，最優(yōu)路徑規(guī)劃、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練等。

圖像分割是區(qū)分圖像中的對象和背景的過程。對于許多依賴于計(jì)算機(jī)視覺的應(yīng)用，如醫(yī)學(xué)成像、衛(wèi)星圖像中的物體定位、機(jī)器視覺、手指打印和人臉識別等許多應(yīng)用來說，圖像分割是一項(xiàng)必不可少的預(yù)處理任務(wù)。圖像分割的準(zhǔn)確性將對圖像處理的后續(xù)階段的有效性產(chǎn)生很大的影響。圖像分割問題已被研究數(shù)年，但由于圖像的不同模態(tài)直方圖等特征，圖像分割問題仍是一個有待進(jìn)一步研究的問題?；谏疃葘W(xué)習(xí)的圖像分割雖然有不錯的效果，但是需要大量標(biāo)注數(shù)據(jù)來訓(xùn)練神經(jīng)網(wǎng)絡(luò)；基于閾值分割的Otsu 是經(jīng)典的圖像分割算法，在單閾值分割時算法效率很高，但在多閾值分割時算法的速度極低，這是由于算法會遍歷圖像的每個像素點(diǎn)，計(jì)算類內(nèi)方差和類間方差，算法速度慢；基于遺傳算法的閾值分割可以解決多閾值圖像分割效率低的問題。

本文分析遺傳算法及其改進(jìn)算法的性能，提出一種混合改進(jìn)的遺傳算法，并將改進(jìn)的算法先用于數(shù)值函數(shù)尋優(yōu)，以測試比較改進(jìn)算法的性能；對圖像閾值分割進(jìn)行分析，找到最佳的閾值來分割圖像，OTSU 算法遍歷像素的操作在多閾值分割時性能下降嚴(yán)重，通過對閾值分割算法分析，使用遺傳算法來尋找最佳閾值，以分割圖像。

1 混合改進(jìn)的遺傳算法

1.1 自適應(yīng)遺傳算法模型

遺傳算法在多個領(lǐng)域的研究表明其高效性，其性能取決于在迭代的最后是否能夠在函數(shù)優(yōu)化中收斂到局部或者全局最優(yōu)解。標(biāo)準(zhǔn)遺傳算法（SGA）采用固定控制參數(shù)方法，即固定交叉概率和變異概率，缺點(diǎn)明顯，因?yàn)榍昂笃谶m應(yīng)度不同，所以需要的交叉、變異概率也不同。趙大興等人提出基于適應(yīng)度對交叉、變異概率作出改進(jìn)，改進(jìn)的選擇算子會根據(jù)個體適應(yīng)度之間的相似性把種群分為若干組，以組為單位進(jìn)行輪盤賭選擇，在選中的組中產(chǎn)生新的個體［3］；陳璐等人將遺傳算法分解為兩部分，通過第一次尋優(yōu)找到優(yōu)秀個體，將最佳個體再次放入第二個種群中，得到最后的最優(yōu)解［4］；江濤等通過在適應(yīng)度函數(shù)中加入路徑平滑度來改善遺傳算法［5］；陳友青等人提出一種改進(jìn)算子的遺傳算法［6］。雖然這些研究在一定程度上改善了遺傳算法的性能，但是使用固定交叉概率和變異概率的方式固化了參數(shù)，算法前期和后期染色體使用的交叉概率、變異概率一樣，算法收斂速度問題依舊沒有得到很好的解決。

針對遺傳算法參數(shù)固定帶來的問題，M.Srinvas和L.M.Patnaik 提出了自適應(yīng)遺傳算法（Adaptive GA，AGA），其思想是在迭代過程中根據(jù)種群適應(yīng)度來自適應(yīng)的調(diào)整交叉概率和變異概率［7］。公式（1）如下：

式中，pc，pm分別表示交叉概率和變異概率；fmax為當(dāng)代種群最大適應(yīng)度值；表示當(dāng)代種群的平均適應(yīng)度值；f表示變異個體的適應(yīng)度值；f ′表示交叉兩個體中較大的適應(yīng)度的值；ki（i＝1，2，3，4）為常數(shù)，取值范圍0＜ki≤1。

AGA 解決了算法前期和后期適應(yīng)度高的個體和適應(yīng)度低個體的交叉概率、變異概率相同的缺點(diǎn)。但自適應(yīng)遺傳算法沒有從全局出發(fā)來控制交叉概率和變異概率，所以在算法后期容易陷入局部收斂，難以找到全局最優(yōu)解。針對這個問題，曲志堅(jiān)等人提出在算法進(jìn)化過程中使用優(yōu)秀個體代替適應(yīng)度差的個體［2］；劉芳等人提出基于種群多樣性的IAGA 來改善算法后期易陷入局部最優(yōu)解的問題［8］；閆春等人使用反正弦函數(shù)自適應(yīng)調(diào)節(jié)變異概率［9］。

通過對遺傳算法以及各種改進(jìn)方式的對比研究，本文提出了混合改進(jìn)遺傳算法：根據(jù)種群密度和進(jìn)化代數(shù)的協(xié)同性，改進(jìn)交叉概率；通過對種群密度的統(tǒng)計(jì)，提出基于種群密度調(diào)整變異概率。

1.2 混合改進(jìn)自適應(yīng)遺傳算法

1.2.1 改進(jìn)交叉概率

評價算法性能指標(biāo)可以用進(jìn)化性來指導(dǎo)，更好的下一代比上一代更能適應(yīng)環(huán)境變化。評價算法進(jìn)化性可以使用種群的密度來衡量，本文算法中計(jì)算每一代群體密度計(jì)算方式（2）如下：

分析每一代種群密度的變化可以掌握算法性能，受改進(jìn)的自適應(yīng)遺傳算法（IAGA）［10］的啟發(fā)，在種群密度的基礎(chǔ)上加上進(jìn)化代數(shù)的因素，從種群迭代次數(shù)以及種群集中程度的考量，改進(jìn)交叉概率，公式（3）如下：

其中，ρ1表示當(dāng)前種群的集中程度，t是當(dāng)前種群的進(jìn)化代數(shù)。

1.2.2 基于種群中心區(qū)域密度改進(jìn)變異概率

在算法進(jìn)化的后期，種群內(nèi)部已經(jīng)趨于相對穩(wěn)定的狀態(tài)，若算法此時得到的解是局部最優(yōu)，由于狀態(tài)穩(wěn)定，算法難以發(fā)生實(shí)質(zhì)進(jìn)化和走出局部最優(yōu)解，如圖1 所示。自然界中的各種生物會經(jīng)歷“天災(zāi)”這樣的自然災(zāi)害，基于這種思考，選擇設(shè)置類似于自然界中的“天災(zāi)”設(shè)定，一定程度上將舊種群初始化為新的種群，從而走出此處局部最優(yōu)解，并試圖尋找下一個可能的局部最優(yōu)解，從而使模型更有希望與能力達(dá)到全局最優(yōu)解。算法遭遇“天災(zāi)”之前，變異概率隨之下降，同時設(shè)置“天災(zāi)”發(fā)生后在正常的種群中心區(qū)域密度ρ2下，密度越高時，變異概率也會隨之上升。

圖1 種群密度變化圖Fig.1 Change of population density

為計(jì)算種群中心區(qū)域的密度ρ2設(shè)定參數(shù)：M表示群體所含的個體數(shù)目；fmax為種群最大適應(yīng)度；fmin表示種群最小適應(yīng)度；favg表示種群平均適應(yīng)度，則t代種群的范圍M（H，t）如式（4）：

某個體的適應(yīng)度到群體適應(yīng)度均值之間的距離m（h），式（5）：

群體中心區(qū)域的半徑σ可以表示為式（6）：

某染色體適應(yīng)度到當(dāng)代群體適應(yīng)度均值的距離小于σ的染色體數(shù)目N（δ，f），則群體中心的密度ρ2為式（7）：

通過對種群中心區(qū)域密度的分析，對變異概率改進(jìn)如式（8）：

式中，T表示最大進(jìn)化次數(shù)；t表示當(dāng)前進(jìn)化次數(shù)；tm是經(jīng)歷“天災(zāi)”的某代種群。

文中設(shè)定當(dāng)中心區(qū)域密度達(dá)到0.5 時，種群經(jīng)歷“天災(zāi)”，之后變異概率會逐漸上升，如圖2 所示。

圖2 變異概率變化曲線Fig.2 Variation curve of mutation probability

2 仿真實(shí)驗(yàn)結(jié)果

本文仿真實(shí)驗(yàn)基于Windows 10（x64）操作系統(tǒng)，Intel（R）Core（TM）i5－7500 CPU 3.40 GHz主頻，RAM8G內(nèi)存。編譯環(huán)境采用MATLAB R2018a。12 個函數(shù)的形式，尋優(yōu)范圍和函數(shù)最優(yōu)值見表1。使用12 個測試函數(shù)來對本文改進(jìn)后的算法進(jìn)行仿真測試，其中函數(shù)F2、F3、F5、F7－ F11 擁有許多局部極小值，F(xiàn)1、F4、F6、F12 用于多維空間測試。

表1 測試函數(shù)Tab.1 Test functions

實(shí)驗(yàn)對表1 中的函數(shù)在搜索空間中進(jìn)行優(yōu)化測試，對比算法選擇SGA 以及IAGA，SGA 參數(shù)設(shè)置：pc＝0.7、pm＝0.01；IAGA 參數(shù)設(shè)置：pc1＝0.9，pc2＝0.6，pm1＝0.1，pm2＝0.001。使用12 個函數(shù)對算法進(jìn)行2 維尋優(yōu)性能測試分析，函數(shù)F1、F6、F10、F12 進(jìn)行30 維測試。

2.1 改進(jìn)算法性能測試

在2 維情況下，將SGA，IAGA與本文算法在12個測試函數(shù)上進(jìn)行試驗(yàn)，3 種算法獨(dú)立求解測試函數(shù)所得收斂曲線如圖3 所示，從F1～F5 函數(shù)在算法迭代50 次尋優(yōu)的曲線，可以看出本文算法在函數(shù)F1～F5 上都能近似到最優(yōu)效果；同時圖3 還給出了F6～F12 函數(shù)迭代200 次的尋優(yōu)效果，可以看出本文算法收斂速度明顯快于SGA 和IAGA。由圖3 可以看出，通過種群密度和迭代次數(shù)的全局考慮，以及加入類似“天災(zāi)”設(shè)置的情況下，算法收斂速度快，易跳出局部最優(yōu)值，而其余兩種算法則出現(xiàn)收斂速度慢或陷入局部最優(yōu)解等問題。雖然本文算法在前期函數(shù)F3 收斂速度略劣于前兩種算法，但是在中后期收斂速度明顯高于前兩種算法，對比來看本文算法更具優(yōu)勢。

圖3 測試函數(shù)適應(yīng)度變化曲線Fig.3 Fitness curve of test function

2.2 收斂精度與收斂率分析

實(shí)驗(yàn)使用了表1 中測試函數(shù)F1～F6，進(jìn)行了50 次獨(dú)立測試，測試結(jié)果見表2?？梢钥闯霰疚乃惴ㄔ?0 次獨(dú)立實(shí)驗(yàn)中收斂精度上優(yōu)于其余兩種算法，收斂率（在50 多次獨(dú)立實(shí)驗(yàn)中的收斂次數(shù)）也明顯高于其余兩種算法，函數(shù)F3在50 次實(shí)驗(yàn)中收斂次數(shù)也高于前兩種。30 維搜索空間優(yōu)化實(shí)驗(yàn)中改進(jìn)算法對比SGA 和IAGA在收斂速度和跳出局部最優(yōu)解能力更有優(yōu)勢，收斂曲線如圖4 所示。

圖4 30 維搜索空間測試結(jié)果Fig.4 Test results of 30－dimensional search space

表2 函數(shù)F1～F6在50 次獨(dú)立實(shí)驗(yàn)的200 代平均值以及收斂率對比Tab.2 Comparison of average and convergence rate of function F1～F6 in 50 independent experiments with 200 generations

3 改進(jìn)遺傳算法圖像分割

3.1 Otsu 圖像分割

圖像分割是計(jì)算機(jī)視覺中一個重要的研究內(nèi)容，在很多領(lǐng)域中都是一項(xiàng)必不可少的圖像預(yù)處理任務(wù)。基于閾值分割的大律法（Otsu）是經(jīng)典的圖像分割算法，但是在多閾值分割任務(wù)上性能很差，處理圖像時間長，所以本文使用改進(jìn)遺傳算法用于閾值圖像分割。圖像閾值分割經(jīng)典算法是Otsu 算法，通過尋找灰度圖像中的最佳閾值來分割圖像，雖然在單閾值分割時Otsu 算法表現(xiàn)不錯，但是多閾值分割時一張圖像需要處理的時間過長，算法效率太低。使用改進(jìn)的遺傳算法用于圖像分割，流程圖如圖5。

圖5 改進(jìn)算法用于圖像分割流程圖Fig.5 Flow chart of improved algorithm for image segmentation

單個閾值把圖像像素分為兩類，Otsu 算法通過遍歷每個像素點(diǎn)尋找能最大化類間方差的點(diǎn)，這個像素點(diǎn)就是最佳閾值。多閾值是在單閾值的基礎(chǔ)上推廣而來。若有M個閾值（t1，t2…tM）將圖像分為M＋1 類（C0，C1…CM），分割標(biāo)準(zhǔn)的度量可以使用類間方差和類內(nèi)方差共同決定。類內(nèi)方差盡可能小，類間方差盡可能大，衡量標(biāo)準(zhǔn)則是類間方差和類內(nèi)方差比值，式（9）：

其中，Sbb是類間方差，Swo是類內(nèi)方差。

選取公式（9）為適應(yīng)度函數(shù)，轉(zhuǎn)換為函數(shù)尋優(yōu)中的求最大值問題?；叶葓D像的像素級在［0，255］之間，閾值就是灰度值，將染色體編碼為比特向量，每一個向量都有L ×M位，L是log（灰度級數(shù)），M是閾值數(shù)，則每L位表示一個染色體，如圖6 所示。

圖6 像素編碼為染色體Fig.6 The pixels are encoded as chromosomes

3.2 圖像分割實(shí)驗(yàn)

Otsu 算法在多閾值分割時出現(xiàn)分割速度慢、抗噪性能差的缺點(diǎn)，采用改進(jìn)的遺傳算法優(yōu)化Otsu 多閾值分割，能在一定程度上克服這些不足之處，實(shí)驗(yàn)結(jié)果見表3、如圖7 所示。使用原Otsu 算法、SGA、IAGA 以及本文改進(jìn)的算法對圖像進(jìn)行分割，傳統(tǒng)Otsu 算法分割效率低；遺傳算法的加入解決效率低的問題，但由圖7 的實(shí)驗(yàn)結(jié)果來看，SGA、IAGA 算法還有明顯的噪聲，在細(xì)小部分分割效果差。使用遺傳算法分割圖像在單閾值和多閾值時所用時間對比見表3。

圖7 圖像分割結(jié)果Fig.7 Image segmentation results

表3 四種方法分割時間對比Tab.3 Comparison among the four methods on time consumption

4 結(jié)束語

針對標(biāo)準(zhǔn)遺傳算法在進(jìn)化過程難以跳出局部最優(yōu)解、收斂率較低和收斂速度慢等問題，本文通過以下兩種方式改進(jìn)遺傳算法：首先，考慮種群密度和進(jìn)化代數(shù)的協(xié)同性，改進(jìn)交叉概率，以增強(qiáng)交叉概率自適應(yīng)性；其次，在進(jìn)化過程中又設(shè)定類似于“天災(zāi)”設(shè)置，結(jié)合進(jìn)化代數(shù)改進(jìn)變異概率，增強(qiáng)種群跳出局部最優(yōu)解的能力。相較于簡單遺傳算法和自適應(yīng)遺傳算法，本文算法在收斂速度和收斂率上有明顯優(yōu)勢，在跳出局部最優(yōu)解的能力上也優(yōu)于SGA 和IAGA。通過改進(jìn)算法分割圖像也達(dá)到不錯的效果，相較于傳統(tǒng)的Otsu 算法，結(jié)合遺傳算法優(yōu)化之后效果更好，在與IAGA、SGA 優(yōu)化對比中，本文改進(jìn)算法更具有魯棒性，抗噪能力更強(qiáng)。