針對選址問題的一種遺傳算法改進(jìn)探究*

鄒貴祥，張飛舟

(北京大學(xué)地球與空間科學(xué)學(xué)院，北京 100871)

1 引言

選址問題是現(xiàn)代資源配置問題的一個重要分支，涉及城市規(guī)劃、物流供應(yīng)、通信建設(shè)、應(yīng)急優(yōu)化、智能交通等多個方面[1 - 3]。選址問題描述為：在一幅地圖中，尋找若干個設(shè)址點，所選擇的設(shè)址點使得以設(shè)址點為自變量的整體優(yōu)化函數(shù)達(dá)到給定條件下的極值。這里的整體優(yōu)化函數(shù)可以有多種形式，如覆蓋內(nèi)容最大、地圖上每個點到設(shè)址點的總距離最短、施工消耗最小等。一個好的選址可以在降低建設(shè)成本、減少維護(hù)支出的同時提高系統(tǒng)工作效率，對生產(chǎn)生活有著重大的意義。隨著空間信息智能處理技術(shù)的發(fā)展，人們發(fā)明并組合了越來越多的智能算法來解決選址問題，如遺傳算法、蟻群算法、模擬退火算法、微粒群優(yōu)化算法、人工蜂群算法等[4]。而選址問題是一個多變量的整體優(yōu)化問題，通用性強(qiáng)、魯棒性高的遺傳算法適合解決這類問題[5]，Zheng等人[6]利用遺傳算法為航空材料倉庫進(jìn)行選址，Shao等人[7]使用遺傳算法簡化計算幾何尋找供飛船著陸的最大空白圓的過程，Tang等人[8]使用遺傳算法優(yōu)化支持向量機(jī)的參數(shù)在高車輛密度城市區(qū)域內(nèi)為車庫選址，Khorashad等人[9]使用遺傳算法為大學(xué)在省級地圖上進(jìn)行了選址。遺傳算法利用選擇、交叉和變異算子模擬生物種群的進(jìn)化而達(dá)到解決優(yōu)化問題的目的，但標(biāo)準(zhǔn)遺傳算法存在容易陷入早熟的現(xiàn)象，因此人們往往結(jié)合問題特征對標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)[10]。

選址問題有以下兩個特點：地圖坐標(biāo)為自然數(shù)；以地圖坐標(biāo)為自變量時，整體優(yōu)化函數(shù)并不連續(xù)。本文針對這兩個特點，選擇二進(jìn)制編碼的遺傳算法對選址問題進(jìn)行求解。二進(jìn)制的遺傳編碼方式不僅可以完整地表達(dá)地圖坐標(biāo)，定長的編碼序列為交叉操作提供方便，非0即1的編碼方式極大程度地簡化了變異操作[11]。以解決選址過程中遺傳算法陷入早熟的問題為目的，本文在探究的基礎(chǔ)上，提出了結(jié)合小生境技術(shù)和多樣性測度的遺傳算法改進(jìn)方向。

2 算法概述及改進(jìn)

2.1 算法概述

標(biāo)準(zhǔn)遺傳算法解決選址問題的流程如下：(1)將所選地址的坐標(biāo)序列按一定規(guī)則編碼，編碼序列形成單個個體。常見的編碼方式有二進(jìn)制編碼、實數(shù)編碼、大字符集編碼等[10,11]。(2)以流程(1)中的編碼方式重復(fù)編碼，隨機(jī)地生成若干個體，這些個體的集合成為初始種群。(3)反解群體中的個體編碼，得到群體每個個體的坐標(biāo)，并計算以個體坐標(biāo)為自變量時，整體優(yōu)化函數(shù)的值，這個值即為該個體的適應(yīng)值。(4)根據(jù)適應(yīng)值利用選擇算子選出參與交配進(jìn)化的若干個體，放入交配池。選擇算子可以根據(jù)具體需求人工設(shè)計，一般適應(yīng)值高的個體被選擇概率大。(5)利用交叉算子、變異算子完成交配池中若干個體的交配并產(chǎn)生新一代種群。交叉算子按照一定規(guī)律或隨機(jī)產(chǎn)生交叉點，并將參與交叉的兩個個體的交叉點之間的基因序列互換，以此生成新的個體。常見的交叉算子有單點交叉算子、兩點交叉算子和多點交叉算子[10]。變異算子則是以一定的概率對新生群體中隨機(jī)個體的隨機(jī)位上的基因進(jìn)行變異，在二進(jìn)制編碼的遺傳算法中，變異算子將需要變異的基因位變成該基因位的反。(6)重復(fù)選擇、交叉和變異的工作，經(jīng)過標(biāo)準(zhǔn)遺傳算法操作的種群將會出現(xiàn)一種表現(xiàn)型，而對應(yīng)這種表現(xiàn)型的坐標(biāo)序列則是標(biāo)準(zhǔn)遺傳算法對該選址問題的解。

標(biāo)準(zhǔn)遺傳算法容易陷入早熟，是因為經(jīng)過標(biāo)準(zhǔn)遺傳算法的選擇過程后，種群的多樣性逐漸下滑，造成收斂后種群表現(xiàn)型一致的結(jié)果[12]。如果收斂的結(jié)果并不是全局最優(yōu)解，那么就稱為遺傳算法早熟或者收斂至局部最優(yōu)。解決標(biāo)準(zhǔn)遺傳算法陷入早熟的方法有兩大類：一類是在一次遺傳操作之前，保證種群中適應(yīng)值大的個體被選擇概率大的情況下，對選擇算子進(jìn)行改造或者升級[10,12]；第二類是在一次遺傳操作之后引入新的概念或者使用種群的成熟度指標(biāo)來判斷遺傳算法是否早熟，從而改進(jìn)遺傳策略[13]。第一類解決方法中，改造升級選擇算子的方向之一是自適應(yīng)地調(diào)整選擇算子的選擇壓力[14]。此思想以Boltzmann選擇算子、排序選擇算子為代表。為了保證合理的動態(tài)的選擇壓力，設(shè)計這些選擇算子時引入的參數(shù)控制變量，可能需要先驗的實驗數(shù)據(jù)或者重復(fù)的實驗才能獲得[15,16]。改造升級選擇算子的方向之二是調(diào)整選擇算子的操作方法。此思想以聯(lián)賽選擇、精英選擇、穩(wěn)態(tài)選擇算子為代表。這些選擇算子對于所選入交配池的個體的適應(yīng)值有相應(yīng)的要求，設(shè)計這些算子時可能不會引入新的變量，相應(yīng)地，可能會增加種群或者個體之間的比較操作。第二類解決標(biāo)準(zhǔn)遺傳算法陷入早熟困境的方法中，可以引入遺傳模式的概念，在遺傳操作的過程中加入補(bǔ)償算子[17]、再生算子[18]；可以引入?yún)?shù)衰減因子，自適應(yīng)地調(diào)整交叉概率、變異概率[19,20]；可以根據(jù)基因型的構(gòu)成，使用多點一致交叉算子[21]或者致力于當(dāng)2個父代染色體相同時也能產(chǎn)生新的子代的基因序列位移的交叉算子[22]；可以引入表明個體間差異的海明距離概念，采用避免相似個體交叉遺傳策略[23]；還可以對適應(yīng)值函數(shù)進(jìn)行線性尺度變換，在前期縮小高適應(yīng)值個體與低適應(yīng)值個體的適應(yīng)值差，后期加大這個差值[23]。不同的種群成熟度指標(biāo)包括種群個體分布方差、種群的熵、種群個體最佳適應(yīng)度與平均適應(yīng)度的差、基因位的多樣性[24]、種群的多樣度等。其中，群體個體分布方差、種群個體最佳適應(yīng)度與平均適應(yīng)度的差均以個體為單位進(jìn)行計算，反映種群整體的統(tǒng)計狀況；種群的熵、基因位的多樣性和種群的多樣性測度則以每個個體的每位基因為單位進(jìn)行計算，反映種群的基因分布狀況。可以根據(jù)每位基因的多樣性設(shè)計針對每位基因的自適應(yīng)變異算子[25]，也可以采用部分個體重新初始化的遺傳策略[26]。

2.2 使用多樣性測度維護(hù)

在遺傳算法的操作過程中，我們引入一個種群成熟度的觀測量——多樣性測度，來輔助算法進(jìn)行遺傳策略的選擇。

多樣性測度的定義如下[10]：

(1)

其中，L為編碼長度，n為群體規(guī)模大小，群體中的每一個個體以如下形式表示：

aj=(a1j,a2j,…,aLj),j=1,2,…,n

(2)

很明顯，多樣性測度滿足m(A)∈[0,1]，遺傳群體的多樣性在多樣性測度m(A)=1時達(dá)到最大，而在多樣性測度m(A)=0時消失[10]。對于t代群體，其多樣性的測度為m(P(t))，P代表迭代次數(shù)為t時的遺傳算法種群。對于二進(jìn)制編碼的遺傳算法而言，其交叉、變異操作均針對每位基因，多樣性測度的計算十分方便。因此，選擇多樣性測度m來描述選址問題的種群成熟度，當(dāng)多樣性測度下降到一定的值時，再對種群進(jìn)行相應(yīng)避免早熟的操作。

相應(yīng)的遺傳策略如下：

(1)每一次選擇、交叉、變異操作后，記錄進(jìn)化過程中種群里(包括父代基因池、子代基因池)出現(xiàn)的適應(yīng)值最高的個體。

(2)完成子代替代父代的操作后，計算種群(指父代基因池)的多樣性測度。

(3)當(dāng)種群的多樣性測度降為0時，表明遺傳算法收斂了，對比當(dāng)前種群的最優(yōu)解個體與記錄的適應(yīng)值最高的個體。

(4)如果當(dāng)前的最優(yōu)解個體的適應(yīng)值低于記錄的最高適應(yīng)值，則重新生成種群(父代基因池)，并把重新生成的父代基因池中的隨機(jī)選擇的一個個體用記錄的適應(yīng)值最高的個體替換，再進(jìn)行選擇、交叉、變異等遺傳操作；如果當(dāng)前種群的最優(yōu)解個體的適應(yīng)值等于記錄的最高適應(yīng)值，則視為遺傳算法收斂至它所認(rèn)為的最優(yōu)解。

(5)由于記錄進(jìn)化過程中種群里出現(xiàn)的適應(yīng)值最高的個體在計算種群的多樣性測度之前，所以此時并不會出現(xiàn)當(dāng)前種群最優(yōu)解個體的適應(yīng)值大于記錄的最高適應(yīng)值的情況。

2.3 預(yù)選機(jī)制的小生境遺傳算法的改進(jìn)

預(yù)選機(jī)制的小生境遺傳算法會在交叉操作(針對兩個父代個體)之后，比較子代個體與產(chǎn)生該子代的父代個體的適應(yīng)值，當(dāng)且僅當(dāng)子代的適應(yīng)值高于父代時，小生境遺傳算法才可以使用子代個體替換父代，完成交叉操作，因而這一“預(yù)選機(jī)制”能夠有效保持群體的多樣性[27]，并讓種群朝著個體擁有高適應(yīng)值的方向進(jìn)化。與預(yù)選機(jī)制的小生境遺傳算法不同：

(1)我們比較完成一次群體地選擇交叉變異之后的父、子代群體最優(yōu)個體的適應(yīng)值大小來判斷進(jìn)化是否成功。因為選址問題全局優(yōu)化函數(shù)的不連續(xù)性，我們不要求每兩個父代個體交叉操作后一定產(chǎn)生更優(yōu)的個體(適應(yīng)值低的個體有產(chǎn)生適應(yīng)值高的子代的可能)，但要求子代群體的最優(yōu)個體適應(yīng)值不低于父代個體(維持群體的進(jìn)化進(jìn)程)。如果新生代的最優(yōu)個體的適應(yīng)值比父代的最優(yōu)個體適應(yīng)值低，那么就視這次進(jìn)化“失敗”，重新進(jìn)化。這種操作的最差情況是，基因池并不會被更新(即無論如何選擇交叉，無法生成比父代適應(yīng)值更高的個體)。

(2)若進(jìn)化成功，將父代和子代的所有個體進(jìn)行排序，選擇適應(yīng)值高且不重復(fù)的若干個體參與下一次進(jìn)化。對于選址問題而言，遺傳算法收斂到一個解，如果這個解不是全局最優(yōu)解，那么這個解在全局最優(yōu)解的附近的概率很大。基于預(yù)選機(jī)制的小生境技術(shù)能讓這個解跳向一個更優(yōu)解，然而更優(yōu)解的方向是不確定的。所以，我們將父子代的全部個體進(jìn)行排序選擇，試圖將最優(yōu)秀的若干個不重復(fù)個體保存下來(保證種群的多樣性)。

Figure 1 Process of combined algorithm圖1 兩種算法結(jié)合后的算法流程圖

(3)設(shè)置新的遺傳算法收斂條件。小生境遺傳算法中，遺傳算法的收斂條件是完成若干次進(jìn)化操作，本文改進(jìn)的小生境遺傳算法的收斂條件則改為：如果進(jìn)化若干代后，父代基因池最優(yōu)解并未被替換，則視為改進(jìn)的小生境遺傳算法收斂。父代基因池最優(yōu)解重復(fù)代數(shù)越大，算法達(dá)到最優(yōu)解的概率越大，搜索時間也會更長。

2.4 進(jìn)一步改進(jìn)的小生境遺傳算法

基于2.3節(jié)中改進(jìn)的小生境遺傳算法，進(jìn)一步地，我們?nèi)∠啽P賭選擇操作，而使父代內(nèi)的全部個體均參與交叉操作，即每一次選擇操作時，選擇并未參與交叉操作的兩個不同的父代基因序列進(jìn)行交叉，直至父代基因池中的所有個體均參與了交叉操作。

由交叉操作可知，對所選擇的兩個個體使用交叉操作有可能產(chǎn)生與被選擇個體表現(xiàn)型不同的新個體，這也是遺傳算法產(chǎn)生新個體完成搜索的重要操作，但是由公式(1)可知，單純的交叉操作不會導(dǎo)致種群多樣性的減少，選擇操作會導(dǎo)致多樣性的減少，而多樣性的減少是導(dǎo)致遺傳算法陷入早熟或者收斂至局部最優(yōu)解的原因之一。而且，兩個基因序列相同的個體進(jìn)行交叉并不會產(chǎn)生新的個體，輪盤賭選擇方法很有可能會選出兩個基因序列相同的個體參與交叉操作。我們所期盼的選擇、交叉操作的最好結(jié)果是：保證種群多樣性的同時，又產(chǎn)生適應(yīng)值更高的個體。因此，我們?nèi)∠溯啽P賭選擇操作，使得父代內(nèi)的全部個體均參與交叉操作，進(jìn)一步改進(jìn)小生境遺傳算法。

2.5 改進(jìn)算法與多樣性測度結(jié)合

隨著遺傳算法的進(jìn)行，基于預(yù)選機(jī)制小生境算法產(chǎn)生更優(yōu)解的難度會加大，因此我們將進(jìn)一步改進(jìn)的搜索方法安排在求解選址問題的開始階段，來快速產(chǎn)生較高適應(yīng)值的解。在進(jìn)一步改進(jìn)的小生境遺傳算法獲得一個適應(yīng)值較高的認(rèn)為是“可用解”的時候進(jìn)入第二個遺傳算法操作流程，進(jìn)行多樣性測度維護(hù)的遺傳計算。在后期使用多樣性測度維護(hù)的遺傳算法有兩個好處：其一是利用多樣性測度維護(hù)的遺傳算法中的適應(yīng)值比例選擇方法，可以增加算法的選擇壓力；其二是使用多樣性測度維護(hù)的遺傳算法能在一定程度上增加遺傳算法的“變異概率”。

結(jié)合后的算法流程如圖1所示。其中，左半部分表示進(jìn)一步改進(jìn)的小生境遺傳算法，右半部分表示以多樣性測度維護(hù)的遺傳算法。種群初始化后，由于2.4節(jié)中取消了選擇操作，因此左半部分的遺傳算子只包括交叉算子和變異算子，并按2.4節(jié)描述使得父代所有個體均參與交叉操作，按照2.3節(jié)描述進(jìn)行排序判斷選取適應(yīng)值較高的若干個體更新基因池后，判斷是否達(dá)到2.3節(jié)中新設(shè)置的收斂條件：父代基因池最優(yōu)解若干代進(jìn)化都并未被替換。達(dá)到收斂條件后進(jìn)入右半部分的遺傳算法流程，其中標(biāo)準(zhǔn)遺傳操作包括了輪盤賭選擇算子、交叉算子和變異算子，并按照2.2節(jié)描述的遺傳策略完成遺傳算法選址。

3 實驗1

3.1 實驗參數(shù)

地圖：10*10的數(shù)字地圖，地圖的每一格都有一個數(shù)字。

設(shè)址點個數(shù)：2～3個。每個設(shè)址點的覆蓋范圍是以設(shè)址點為中心的3*3的正方形。

優(yōu)化目標(biāo)：2～3個設(shè)址點覆蓋范圍內(nèi)包含的數(shù)字之和最大。覆蓋范圍有重復(fù)的時候，不重復(fù)計算。

編碼：二進(jìn)制編碼。因為23<10<24，因此表達(dá)一個設(shè)址點坐標(biāo)(x,y)的基因二進(jìn)制序列有8位，表達(dá)兩個設(shè)址點坐標(biāo)(x1,y1)，(x2,y2)的基因二進(jìn)制序列有16位，三個設(shè)址點對應(yīng)24位。因為16>10，所以會產(chǎn)生編碼冗余。為了使每個坐標(biāo)被搜索到的概率一致，坐標(biāo)超過地圖范圍的編碼會被隨機(jī)指向一個在地圖內(nèi)的坐標(biāo)。

適應(yīng)值：一個個體的適應(yīng)值即是該個體基因表達(dá)的設(shè)址點覆蓋范圍內(nèi)包含的數(shù)字之和。數(shù)字之和越大，該個體的適應(yīng)值越高。

群體大?。喝后w大小設(shè)置為20[10]，即每一代的種群都由20個個體(20串16/24位的基因二進(jìn)制序列)組成。

選擇算子：對于標(biāo)準(zhǔn)遺傳算法、預(yù)選機(jī)制的小生境遺傳算法、用多樣性測度維護(hù)的遺傳算法和改進(jìn)的小生境遺傳算法，使用適應(yīng)值比例選擇方法中的典型方法：輪盤賭方法。即：對于給定規(guī)模為n的群體P={a1,a2,…,an}，個體aj∈P的適應(yīng)值為f(aj)，其選擇概率為：

(3)

對于進(jìn)一步改進(jìn)的小生境遺傳算法，取消了選擇算子。

交叉算子：兩點交叉算子。隨機(jī)生成交叉點p1,p2，用于交叉的兩個基因二進(jìn)制序列的p1位至p2位的基因序列互換。交叉概率設(shè)置為0.9[10]。

變異算子：變異概率設(shè)置為0.02[10]。以群體中的單個個體為單位，當(dāng)發(fā)生變異時，隨機(jī)生成變異點pm，該個體的基因二進(jìn)制序列的pm位基因變?yōu)樗姆?即1變?yōu)?,0變?yōu)?)。

算法停止條件：對于標(biāo)準(zhǔn)遺傳算法和預(yù)選機(jī)制的小生境遺傳算法，收斂條件設(shè)置為進(jìn)化代數(shù)達(dá)到上限(1 000代)；對于改進(jìn)和進(jìn)一步改進(jìn)的小生境遺傳算法，收斂條件設(shè)置為進(jìn)化代數(shù)達(dá)到相同上限或者連續(xù)10代當(dāng)前最優(yōu)解不被更新。

評價方式：以如下三個指標(biāo)來評價遺傳算法的性能：50輪200次實驗達(dá)到全局最優(yōu)解次數(shù)、在線性能函數(shù)與離線性能函數(shù)。

在線性能函數(shù)的定義如下[10,11,18,28]：

(4)

其中，s為該遺傳算法所選擇的遺傳策略，由編碼長度、群體規(guī)模大小、交叉概率、變異概率等因子決定。T代表該遺傳算法經(jīng)歷過的迭代次數(shù)。在線性能函數(shù)反映的是遺傳群體整體的適應(yīng)值變化及群體進(jìn)化能力，它代表著經(jīng)過平滑處理后的群體平均適應(yīng)值[10,11,18,28]。

離線性能函數(shù)的定義如下[10,11,18,28]：

(5)

其中，s為該遺傳算法所選擇的遺傳策略。

f(a*,t)=max{f(a1,t),f(a2,t),…,f(an,t)}

(6)

指的是迭代次數(shù)為t時，t代群體中適應(yīng)值最高的個體的適應(yīng)值。離線性能函數(shù)反映的是遺傳群體中個體的適應(yīng)值變化以及該遺傳算法對更優(yōu)解的搜索能力，它代表著經(jīng)過了平滑處理后的群體中適應(yīng)值最高的個體的平均適應(yīng)值[10,11,18,28]。

我們隨機(jī)生成每一次實驗的初始種群，同一次實驗中五種算法的初始種群相同。

3.2 實驗結(jié)果及分析

經(jīng)過實驗可以發(fā)現(xiàn)，這五種算法都具有達(dá)到最優(yōu)解的能力，但是達(dá)到最優(yōu)解的效果并不相同(如表1所示)，以改進(jìn)的和進(jìn)一步改進(jìn)的小生境遺傳算法效果最優(yōu)。造成差異的原因是，標(biāo)準(zhǔn)遺傳算法經(jīng)過了遺傳操作之后，種群的多樣性迅速下降，在變異概率不高的情況下，達(dá)到早熟或者收斂到局部最優(yōu)解的概率太大；預(yù)選機(jī)制的小生境遺傳算法進(jìn)化具有一定“方向性”(向著適應(yīng)值更高的子代進(jìn)化)，然而它依舊保留了選擇操作，因此效果比標(biāo)準(zhǔn)遺傳算法好但劣于其他算法；使用多樣性測度來維護(hù)的遺傳算法在多樣性測度達(dá)到0時，對比當(dāng)前最優(yōu)解和進(jìn)化過程中所記錄的最優(yōu)解是否一致后，遺傳算法收斂到局部最優(yōu)解(即早熟)的概率下降，然而它的進(jìn)化不具有“方向性”，因此效果居中；而兩種改進(jìn)的小生境遺傳算法進(jìn)化方向性更強(qiáng)，多樣性下降更慢，因此它們收斂到最優(yōu)解的概率更大；進(jìn)一步改進(jìn)的算法取消了選擇操作，搜索空間會大于改進(jìn)的小生境算法，導(dǎo)致它的效果最優(yōu)。當(dāng)然，種群大小是導(dǎo)致改進(jìn)與進(jìn)一步改進(jìn)的算法并未達(dá)到100%收斂至最優(yōu)解的原因之一，種群變大，兩種改進(jìn)的遺傳算法收斂到全局最優(yōu)解的概率會變大(如表2所示)。

Table 1 Times about algorithms get the max value表1 算法達(dá)到最大次數(shù)的比較

Table 2 Different group population andtimes about algorithms get the max value表2 種群大小與算法性能

從五種算法的隨機(jī)一次實驗的算法性能圖(如圖2所示)的比較中可以看出，在線性能函數(shù)曲線方面，預(yù)選機(jī)制小生境遺傳算法、改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的在線性能函數(shù)曲線上升很快，其數(shù)值與上升速度均超過了剩下的兩種算法，說明這三種算法的種群的平均適應(yīng)值以及平均適應(yīng)值的提高速度優(yōu)于剩下的兩種算法，僅使用多樣性測度維護(hù)的遺傳算法在線性能強(qiáng)于標(biāo)準(zhǔn)遺傳算法；離線性能函數(shù)曲線方面，改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的離線性能函數(shù)曲線上升很快，其數(shù)值與上升速度均超過了剩下的三種算法，說明改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的最優(yōu)個體適應(yīng)值的提高能力和遺傳算法的搜索到更優(yōu)個體的能力優(yōu)于剩下的三種算法，僅使用多樣性測度維護(hù)的遺傳算法離線性能列第三，其更新種群的方式隨機(jī)導(dǎo)致算法向最優(yōu)解收斂的過程隨機(jī)。從圖2中也能看出，雖然這次實驗中預(yù)選機(jī)制小生境遺傳算法前100代中種群的平均適應(yīng)值高，但是最優(yōu)適應(yīng)值卻不高，說明在這次實驗中它已經(jīng)陷入了早熟的狀態(tài)。從表1中可以發(fā)現(xiàn)，進(jìn)一步改進(jìn)的小生境遺傳算法達(dá)到最優(yōu)解的次數(shù)要高于改進(jìn)的小生境遺傳算法，其原因應(yīng)該是取消了選擇操作而導(dǎo)致算法可以搜索的范圍更大，且在圖2所示的這次實驗中，進(jìn)一步改進(jìn)的小生境遺傳算法比改進(jìn)的小生境遺傳算法先找到了它認(rèn)為的最優(yōu)解，因此它的在線、離線性能函數(shù)均高于改進(jìn)的小生境遺傳算法。

Figure 2 Performance comparison of the 5 algorithms圖2 五種算法的性能比較曲線圖

(記錄的)父代基因池最優(yōu)解連續(xù)重復(fù)次數(shù)是改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法中算法收斂條件參數(shù)。我們統(tǒng)計了在不同父代基因池最優(yōu)解連續(xù)重復(fù)次數(shù)下改進(jìn)的小生境遺傳算法的性能。50輪200次10*10數(shù)字地圖選2個地址的實驗結(jié)果如表3所示，其中包括200次實驗中算法達(dá)到最優(yōu)解(正確解)的最低次數(shù)、最高次數(shù)和平均次數(shù)，每完成200次實驗算法的最短用時、最長用時和平均用時。

Table 3 Different repetition times of optimum solutionand performance of improved GA with niche technique表3 最優(yōu)解重復(fù)代數(shù)與改進(jìn)的小生境遺傳算法性能

考慮到算法準(zhǔn)確性和算法用時，我們折衷選擇了父代基因池最優(yōu)解連續(xù)重復(fù)10次作為改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的收斂條件。

在2.93 GHz英特爾i3處理器4 GB內(nèi)存32位Windows 7操作系統(tǒng)的實驗環(huán)境下，小生境遺傳算法平均每次迭代用時0.069 ms，改進(jìn)的小生境遺傳算法平均每次迭代用時0.898 ms，進(jìn)一步改進(jìn)的小生境遺傳算法平均每次迭代用時0.538 ms。算法每迭代一次將更新一次種群，不斷迭代完成一次實驗。兩種改進(jìn)算法以一定的時間代價換取了更優(yōu)的種群單次更新效果。

對于改進(jìn)小生境算法與多樣性測度維護(hù)結(jié)合的實驗(流程如圖1所示)，從算法性能曲線(如圖3所示)中可以看出，第一個流程中使用進(jìn)一步改進(jìn)的小生境遺傳算法獲得一個被認(rèn)為是“可用解”的過程中，在線性能函數(shù)和離線性能函數(shù)都快速增長。而之后再進(jìn)行多樣性測度維護(hù)后，種群中開始混入適應(yīng)值較低的個體，形成較大的“變異概率”，所以在線性能函數(shù)的值(描述種群平均適應(yīng)值變化)會降低，之后在線函數(shù)的變化由于搜索的隨機(jī)性而無法預(yù)測。在多樣性測度達(dá)到0之前進(jìn)行的都是標(biāo)準(zhǔn)遺傳操作，當(dāng)“可用解”適應(yīng)值很高時，離線性能函數(shù)會下降。但是，在多樣性測度達(dá)到0的時候，因為種群中的最高適應(yīng)值個體與記錄的最優(yōu)個體相比較和替換(見2.2節(jié))，算法的離線性能函數(shù)(描述種群最優(yōu)個體適應(yīng)值變化)并不會降低太多。最終我們選取的結(jié)果也是維護(hù)過程中出現(xiàn)的最優(yōu)記錄個體。

4 實驗2

4.1 實驗參數(shù)

地圖：制作70*70的數(shù)字地圖，包括北至北京市北四環(huán)西路，南至阜成路，西至西四環(huán)北路，東至西直門北大街的近49 km2的海淀區(qū)，涉及到八里莊街道、甘家口街道、曙光街道、紫竹院街道、北下關(guān)街道、北太平莊街道、海淀街道、中關(guān)村街道、花園路街道等社區(qū)。地圖的每一格都有一個數(shù)字，表示實驗區(qū)內(nèi)海淀區(qū)各街道社區(qū)的人口密度，人口密度數(shù)據(jù)由2010年第六次人口普查[29]的數(shù)據(jù)進(jìn)行計算而得。

設(shè)址點個數(shù)：模擬設(shè)置20個快遞點。每個設(shè)址點的覆蓋范圍是以設(shè)址點為中心的5*5的正方形。

優(yōu)化目標(biāo)：20個設(shè)址點覆蓋范圍內(nèi)包含的數(shù)字之和最大，即覆蓋到的人口最多。覆蓋范圍有重復(fù)的時候，不重復(fù)計算。

Figure 3 Performance of genetic algorithm combined with 2 algorithms圖3 兩種算法結(jié)合后的遺傳算法性能曲線圖

算法選擇：選擇預(yù)選機(jī)制小生境遺傳算法、進(jìn)一步改進(jìn)的小生境算法、多樣性測度維護(hù)與進(jìn)一步改進(jìn)的小生境算法結(jié)合算法、排擠小生境遺傳算法和人工蜂群算法進(jìn)行實驗比較。

排擠小生境遺傳算法會隨機(jī)選擇群體中的若干個體，計算群體中的個體與所選個體的相似性，并降低與所選個體相似的個體的適應(yīng)值，之后參與進(jìn)化，以保證遺傳算法中的群體多樣性[30]。

人工蜂群算法同樣作為優(yōu)化算法[4,31 - 34]，它先隨機(jī)生成若干個蜜源，每個蜜源以20個設(shè)址點的坐標(biāo)表示。使用引領(lǐng)蜂和跟隨蜂對蜜源進(jìn)行優(yōu)化。與蜜源一一對應(yīng)的引領(lǐng)蜂在蜜源附近搜索，如果一只引領(lǐng)蜂發(fā)現(xiàn)附近的解適應(yīng)值較高，則更換蜜源。跟隨蜂以一定規(guī)則選擇引領(lǐng)蜂發(fā)現(xiàn)的蜜源，并在所選擇的蜜源附近進(jìn)行搜索，如果一只跟隨蜂發(fā)現(xiàn)附近的解適應(yīng)值較高，則更換蜜源。記錄下引領(lǐng)蜂和跟隨蜂發(fā)現(xiàn)的適應(yīng)值最高的蜜源。如此循環(huán)兩種蜜蜂的操作。如果某只引領(lǐng)蜂所在蜜源若干次循環(huán)并未被更換，則放棄當(dāng)前蜜源，隨機(jī)生成新的蜜源。人工蜂群算法的重點是由蜜源產(chǎn)生附近蜜源坐標(biāo)的方法，一般使用的方法是：

(7)

人工蜂群算法直接以坐標(biāo)作為蜜源的編碼方式，而其余算法與實驗1相似，以二進(jìn)制編碼作為編碼方式；以覆蓋范圍內(nèi)數(shù)字總和為適應(yīng)值函數(shù)；以輪盤賭選擇方法作為預(yù)選機(jī)制小生境遺傳算法、排擠小生境遺傳算法[30]和人工蜂群算法的選擇算子；以兩點交叉算子作為交叉算子；以單點變異方式為變異算子。對于排擠小生境遺傳算法，群體大小設(shè)置為30，選取前20個個體遺傳到下一代，排擠因子設(shè)為3，排擠海明長度設(shè)置為0。因為適應(yīng)值函數(shù)的不連續(xù)性，并未進(jìn)行如文獻(xiàn)[30]中提到的個體優(yōu)化，并且全程保持較高的交叉概率以求更大的搜索范圍。對于預(yù)選機(jī)制小生境遺傳算法、排擠小生境遺傳算法和人工蜂群算法，收斂條件為迭代次數(shù)達(dá)到迭代上限。對于進(jìn)一步改進(jìn)的小生境遺傳算法，設(shè)置更苛刻的收斂條件為：交叉操作次數(shù)與預(yù)選機(jī)制小生境遺傳算法交叉操作次數(shù)相等(此時迭代次數(shù)一般都未達(dá)到迭代上限。在這里，預(yù)選機(jī)制小生境遺傳算法的一次交叉操作指對于種群的一次交叉操作，相當(dāng)于完成了一次種群的迭代)，或者連續(xù)10代當(dāng)前最優(yōu)解不被更新。我們進(jìn)行預(yù)選機(jī)制小生境遺傳算法、進(jìn)一步改進(jìn)的小生境遺傳算法、兩種算法(進(jìn)一步改進(jìn)的小生境遺傳算法和多樣性測度維護(hù))結(jié)合的方法、排擠小生境遺傳算法和人工蜂群算法對選址問題進(jìn)行求解。我們隨機(jī)生成每一次實驗的初始種群，同一次實驗中五種算法的初始種群相同(排擠小生境算法中有20個個體與剩下的三種遺傳算法相同，剩余10個個體隨機(jī)生成；人工蜂群算法中初始20個蜜源的坐標(biāo)與其他算法相同)。

4.2 實驗結(jié)果

我們比較200次實驗中，進(jìn)一步改進(jìn)的小生境遺傳算法的解適應(yīng)值優(yōu)于預(yù)選機(jī)制小生境遺傳算法的次數(shù)(A)，其優(yōu)于排擠小生境遺傳算法的次數(shù)(B)，使用多樣性測度維護(hù)的進(jìn)一步改進(jìn)的小生境遺傳算法的解適應(yīng)值優(yōu)于進(jìn)一步改進(jìn)的小生境遺傳算法的次數(shù)(C)，其優(yōu)于排擠小生境遺傳算法的次數(shù)(D)，和人工蜂群算法的次數(shù)(E)。其結(jié)果如表4所示。

Table 4 Performance comparison of the 4 algorithms表4 五種算法的結(jié)果比較

我們選取使用多樣性測度維護(hù)的進(jìn)一步改進(jìn)算法的隨機(jī)一次結(jié)果，制作了實驗所得的快遞點選址分布圖(如圖4所示)。其中，‘+’表示實驗選址，‘o’表示由百度地圖(搜索關(guān)鍵詞為“海淀區(qū)順豐快遞”)得出的實驗區(qū)域內(nèi)的19個快遞點。

Figure 4 Result of site selection圖4 選址結(jié)果圖

4.3 討論

(1)算法改進(jìn)方面。

迭代次數(shù)相同時，200次實驗中，進(jìn)一步改進(jìn)的小生境遺傳算法均有近70%的概率產(chǎn)生比小生境遺傳算法更優(yōu)的解。說明本文提出的進(jìn)一步改進(jìn)的小生境遺傳算法是有效的；在多樣性測度的維護(hù)下，進(jìn)一步改進(jìn)的小生境遺傳算法也產(chǎn)生過若干次更優(yōu)解，說明以多樣性測度對進(jìn)一步改進(jìn)的小生境遺傳算法維護(hù)的改進(jìn)遺傳算法也是有效的。

隨著迭代次數(shù)的增加，多樣性測度對進(jìn)一步改進(jìn)的小生境遺傳算法的優(yōu)化效率降低，這說明隨著迭代次數(shù)的增加，進(jìn)一步改進(jìn)的小生境遺傳算法產(chǎn)生的適應(yīng)值較高的解的效果提升。

迭代次數(shù)相同時，進(jìn)一步改進(jìn)的小生境遺傳算法與排擠小生境遺傳算法效果相近，但是增加了多樣性測度維護(hù)之后，進(jìn)一步改進(jìn)的小生境遺傳算法比排擠小生境遺傳算法效果要好，這說明了多樣性測度維護(hù)操作的有效性。而兩種算法結(jié)合的算法性能并未完全優(yōu)于人工蜂群算法，主要的原因是人工蜂群算法操作的對象是實際坐標(biāo)，而遺傳算法的

變異手段操作的對象是基因序列。在突變概率低的情況下，通過單個基因位變異而達(dá)到選址點坐標(biāo)微小位移的概率太低，而人工蜂群算法卻有較大的概率完成坐標(biāo)微小的位移(公式(7))，這體現(xiàn)出針對基因序列的遺傳算法變異操作的局限性。

算法效果的比較也為深入優(yōu)化遺傳算法提供了方向。由于使用多樣性維護(hù)的遺傳算法中采用了適應(yīng)值比例選擇算子擔(dān)任選擇方法，多樣性測度為0時新種群的生成方式為隨機(jī)生成，因此，可以通過改進(jìn)選擇算子、改進(jìn)新種群生成方式的方法進(jìn)一步提高多樣性測度維護(hù)與改進(jìn)小生境算法結(jié)合的遺傳算法的計算效率。如可以通過多次實驗獲得的數(shù)據(jù)，計算退火溫度的初值T，利用Boltzmann選擇法自適應(yīng)地改變選擇壓力；也可以根據(jù)遺傳算法的計算進(jìn)度，在種群多樣性測度為0時以所記錄的最優(yōu)個體為中心，以隨算法進(jìn)度改變的不同漢明距離為半徑，生成新的種群。一方面可以增大遺傳算法達(dá)到全局最優(yōu)解的概率，另一方面，在多樣性測度降為0時進(jìn)行有范圍控制的變異操作，以減少新的種群生成的隨機(jī)性，相比隨機(jī)生成的新的種群而言更具有“方向性”，因此可以減少算法到達(dá)收斂所需要的進(jìn)化代數(shù)，從而提高算法效率。還可以考慮設(shè)計針對坐標(biāo)的變異算子應(yīng)用于遺傳算法的收尾階段，使得一次變異操作的結(jié)果能夠限制在變異前坐標(biāo)的一定范圍內(nèi)。

(2)實驗結(jié)果方面。

在人口稠密的地區(qū)實驗選址結(jié)果分布得多，而稀薄的地區(qū)分布得少。與我們預(yù)期的實驗結(jié)果是相符合的。

(3)與實際情況對比方面。

不巧的是，所選實驗區(qū)人口密度最大、次大的區(qū)域恰巧沒有實際的快遞點(北太平莊區(qū)域)，此區(qū)域的快遞點位于所選實驗區(qū)外，這一點并不利于與實際數(shù)據(jù)的吻合對照。

在實驗區(qū)人口密度較大的區(qū)域，實驗所選的快遞點與實際存在的快遞點有較好的重合。

在實驗區(qū)人口密度較小的區(qū)域，實驗所選的快遞點與實際存在的快遞點重合較差。

進(jìn)一步分析發(fā)現(xiàn)，在實驗區(qū)人口密度較大的區(qū)域，實驗所選的快遞點分布大致在地鐵、高級道路的沿線，而地鐵、高級道路往往是街道社區(qū)劃分的邊界線，這個區(qū)域的人口密度介于被分開的兩個街道社區(qū)之間，所以會有較大的人口密度；同時，因為接近地鐵、高級道路，方便快遞公司與市民取、寄快遞，因此快遞公司在這些區(qū)域設(shè)置快遞點的概率更大。如中關(guān)村街道與北下關(guān)街道分界的北三環(huán)西路、中關(guān)村街道與北太平莊街道、北下關(guān)街道與北太平莊街道分界的地鐵十三號線沿線上的快遞點分布吻合得較好。

再者，快遞點選址不只涉及人口因素，還需考慮小區(qū)位置、交通、地價等因素，如果加上這些因素對適應(yīng)值函數(shù)進(jìn)行修改，應(yīng)該可以產(chǎn)生更吻合實際情況的實驗結(jié)果。本文的重點在于對選址問題中遺傳算法的改進(jìn)，在算法對照表格中已經(jīng)可以看到本文算法的改進(jìn)效果了。

5 結(jié)束語

二進(jìn)制編碼的遺傳算法可以有效求解優(yōu)化選址問題。為克服遺傳算法在選址過程中陷入早熟的缺點，本文發(fā)現(xiàn)使用多樣性測度維護(hù)的遺傳算法可以有效地使遺傳算法跳出早熟的結(jié)果，同時，針對選址問題的特點，本文改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法可以啟發(fā)式地產(chǎn)生適應(yīng)值較高的解，并且減少遺傳算法達(dá)到收斂的代數(shù)。因此，本文將進(jìn)一步改進(jìn)的小生境遺傳算法與使用多樣性測度維護(hù)的遺傳算法相結(jié)合，先產(chǎn)生適應(yīng)值較高的可能解，再以較大變異概率判斷是否早熟，使得二者互補(bǔ)，提高遺傳算法的計算性能，并通過地圖選址實驗進(jìn)行驗證，同時指出設(shè)計自適應(yīng)的選擇、變異算子和針對坐標(biāo)的變異算子將會作為我們深入優(yōu)化遺傳算法的方向。

參考文獻(xiàn):

[1] Weng Ke-rui,Xu Zi-hao.Facility location problem with coverings demands limitation[J].Mathematics in Practice and Theory,2014,44(11):191-195.(in Chinese)

[2] Liu Cheng,Chen Ze-hui,Gong Yu-yan.Emergency material storages location problem based on time-satisfaction[J].Mathematics in Practice and Theory,2014,44(17):8-14.(in Chinese)

[3] Wang Ji-guang,Li Jing-feng.Discrete facility location problem in the presence of random disruption[J].Computer Engineering and Applications,2015,51(17):1-7.(in Chinese)

[4] Wang Zhi-gang,Wang Ming-gang,Shang Xu-dong.Solving location problem of distribution centre based on artificial bee colony algorithm[J].Mathematics in Practice and Theory,2014,44(17):170-175.(in Chinese)

[5] Xu Ai-gong,Xu Tao,Zhang Ming-yue,et al.GPS real time point positioning based on genetic algorithm[J].Science of Surveying and Mapping,2009,34(S2):18-20.(in Chinese)

[6] Zheng J,Xu K,Xin Y,et al.The study of selection of air material storehouse based on second generation of genetic algorithm in site[C]∥Proc of International Conference on Information Sciences,Machinery,Materials and Energy,2015:748-751.

[7] Shao W,Cui P,Zhou W.Safe landing site selection based on computational geometry and genetic algorithm[C]∥Proc of International Conference on Natural Computation,2008:660-664.

[8] Tang M,Ren E.Site selection of mechanical parking garage in high density vehicle urban area based on genetic algorithm-support vector machine[C]∥Proc of 2009 2nd International Symposium on Knowledge Acquisition and Modeling,2009:100-102.

[9] Khorashad A K, Kianoosh Z H. Application of genetic algorithm in regional planning (case study:site selection for comprehensive universities)[J].Journal of Basic and Applied Scientific Research,2012,2(11):11428-11433.

[10] Li Min-qiang,Kou Ji-song,Lin Dan,et al.The basic theory and application of genetic algorithm[M].Beijing:Science Press,2002.(in Chinese)

[11] Tian Xin.Study on the hybrid crossover strategy genetic algorithm and its application[D].Baoding:North China Electric Power University,2009.(in Chinese)

[12] Chen Jun-hong.Research on genetic algorithm application in distribution network optimal planning[D].Baoding:Agricultural University of Hebei,2006.(in Chinese)

[13] Wang Min-le,Gao Xiao-guang,Liu Gang.Quantitative analysis and prevention of genetic algorithm premature convergence[J].Systems Engineering and Electronics,2006,28(8):1249-1251.(in Chinese)

[14] Wang Guo-rui.Genetic algorithm with applications in image mosaic[D].Wuhan:Huazhong University of Science and Technology,2006.(in Chinese)

[15] Zhang Yu-hu.The research and implement of classification based on simulated annealing algorithm[D].Qingdao:Qingdao University,2013.(in Chinese)

[16] Wang Xiao-feng, Shang Xu-jing. GA solution of 3-SAT based on clustering ranking selection[J].Journal of Dalian Nationalities University,2009,11(3):267-271.(in Chinese)

[17] Xiong Wei-qing,Wei Ping,Zhao Jie-yu.Research on the premature convergence of genetic algorithms[J].Application Research of Computers,2001,18(9):12-14.(in Chinese)

[18] Lai Zhi-zhu.Long schema genetic algorithms and its applications[D].Chongqing:Chongqing University,2008.(in Chinese)

[19] Xu Yan,Zhi Jing.Optimal PMU configuration based on improved adaptive genetic algorithm[J].Power System Protection and Control,2015,43(2):55-62.(in Chinese)

[20] Aldallal A S.Avoiding premature convergence of genetic algorithm in informational retrieval systems[J].International Journal of Intelligent Systems & Applications in Engineering,2015,2(4):80-85.

[21] Hu Fei-hu,Ma Bei-long,Yang Li,et al.Research on vehicle scheduling optimization in emergency material distribution based on improved genetic algorithm[J].Application Research of Computers,2014,31(10):2928-2932.(in Chinese)

[22] Zhang Qing-hua,Zhang Xi.Application of improved genetic algorithm in vehicle routing problem[J].Journal of Transport Information and Safety,2012,30(5):81-86.(in Chinese)

[23] Jiang J,Meng L D.The strategy of improving convergence of genetic algorithm[J].Telkomnika Indonesian Journal of Electrical Engineering,2012,10(8):2063-2068.

[24] Liu Li,Jing Ping.A mutation strategy dealing with premature convergence of genetic algorithm[J].Electronic Technology & Software Engineering,2015(23):179.(in Chinese)

[25] Liu J,Fu J,Bai X.A new genetic algorithm considering diversity of gene locus[C]∥Prof of the 2nd International Workshop on Materials Engineering and Computer Sciences,2015:764-768.

[26] Nicoar? E S. Mechanisms to avoid the premature convergence of genetic algorithms[J].Petroleum-Gas University of Ploiesti Bulletin,Mathematics-I,2009,41(1):87-96.

[27] Zhao Yue,Ru Ting-ting.Comparison and analysis of basic theory and performance on typical genetic algorithms based on niche technique[J].Journal of Tonghua Normal University,2014,35(2):38-39.(in Chinese)

[28] Wang Tong.Research on schema characters in genetic algorithm[D].Zhengzhou:PLA Information Engineering University,2009.(in Chinese)

[29] Census Office of the State Council,Department of population and employment statistics,National Bureau of Statistics.China’s 2010 census information of township,town and street[M].Beijing:China Statistics Press,2012:256-259.(in Chinese)

[30] Hua Jie,Cui Du-wu.Adaptive niche genetic algorithm based on individual optimization[J].Computer Engineering,2010,36(1):194-196.(in Chinese)

[31] He D X,Jia R M.Cloud model-based artificial bee colony algorithm's application in the logistics location problem[C]∥Proc of 2012 International Conference on Information Management,Innovation Management and Industrial Engineering,2012:256-259.

[32] Basti M,Sevkli M.An artificial bee colony algorithm for the p-median facility location problem[J].International Journal of Metaheuristics,2015,4(1):91-113.

[33] Zhang S Z.Optimization of facility location problem in reverse logistics network using artificial bee colony algorithm[C]∥Proc of the 2013 IEEE IEEM,2013:1348-1352.

[34] Yin Jian-xia.Research on artificial bee colony algorithm and its application[D].Xi’an:Xidian University,2012.(in Chinese)

附中文參考文獻(xiàn):

[1] 翁克瑞,許自豪.帶覆蓋需求約束的設(shè)施選址問題[J].數(shù)學(xué)的實踐與認(rèn)知,2014,44(11):191-195.

[2] 劉誠,陳則輝,龔玉燕.基于時間滿意度的應(yīng)急物資儲備庫選址問題[J].數(shù)學(xué)的實踐與認(rèn)知,2014,44(17):8-14.

[3] 王繼光,李景峰.隨機(jī)中斷情境下的離散型設(shè)施選址問題研究[J].計算機(jī)工程與應(yīng)用,2015,51(17):1-7.

[4] 王志剛,王明剛,尚旭東.基于人工蜂群算法的配送中心選址問題求解[J].數(shù)學(xué)的實踐與認(rèn)知,2014,44(17):170-175.

[5] 徐愛功,徐濤,張明月,等.GPS動態(tài)單點定位的遺傳算法探究[J].測繪科學(xué),2009,34(S2):18-20.

[10] 李敏強(qiáng),寇紀(jì)淞,林丹,等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,2002.

[11] 田欣.混合交叉策略遺傳算法及其應(yīng)用研究[D].保定:華北電力大學(xué),2009.

[12] 陳俊紅.遺傳算法在配電網(wǎng)優(yōu)化規(guī)劃中的應(yīng)用研究[D].保定:河北農(nóng)業(yè)大學(xué),2006.

[13] 汪民樂,高曉光,劉剛.遺傳算法早熟問題的定量分析及其預(yù)防策略[J].系統(tǒng)工程與電子技術(shù),2006,28(8):1249-1251.

[14] 王國銳.遺傳算法及其在圖象拼接中的應(yīng)用[D].武漢:華中科技大學(xué),2006.

[15] 張玉虎.基于模擬退火的分類算法研究與實現(xiàn)[D].青島:青島大學(xué),2013.

[16] 王曉峰,尚旭靜.基于聚類排序選擇方法求解3-SAT問題的遺傳算法[J].大連民族學(xué)院學(xué)報,2009,11(3):267-271.

[17] 熊偉清,魏平,趙杰煜.遺傳算法的早熟現(xiàn)象研究[J].計算機(jī)應(yīng)用研究,2001,18(9):12-14.

[18] 賴志柱.長模式遺傳算法及其應(yīng)用[D].重慶:重慶大學(xué),2008.

[19] 徐巖,郅靜.基于改進(jìn)自適應(yīng)遺傳算法的PMU優(yōu)化配置[J].電力系統(tǒng)保護(hù)與控制,2015,43(2):55-62.

[21] 胡飛虎,馬貝龍,楊麗,等.基于改進(jìn)遺傳算法的應(yīng)急物資配送車輛調(diào)度優(yōu)化問題研究[J].計算機(jī)應(yīng)用研究,2014,31(10):2928-2932.

[22] 張華慶,張喜.改進(jìn)遺傳算法在車輛路徑問題中的應(yīng)用[J].

交通信息與安全,2012,30(5):81-86.

[24] 劉麗,景萍.一種抑制遺傳算法早熟的變異策略[J].電子技術(shù)與軟件工程,2015(23):179.

[27] 趙越,茹婷婷.典型小生境遺傳算法原理與性能比較分析[J].通化師范學(xué)院學(xué)報,2014,35(2):38-39.

[28] 汪彤.遺傳算法中模式性質(zhì)研究[D].鄭州:解放軍信息工程大學(xué),2009.

[29] 國務(wù)院人口普查辦公室,國家統(tǒng)計局人口和就業(yè)統(tǒng)計司.中國2010年人口普查分鄉(xiāng)、鎮(zhèn)、街道資料[M].北京:中國統(tǒng)計出版社,2012：256-259.

[30] 華潔,崔杜武.基于個體優(yōu)化的自適應(yīng)小生境遺傳算法[J].計算機(jī)工程,2010,36(1):194-196.

[34] 銀建霞.人工蜂群算法的研究及其應(yīng)用[D].西安：西安電子科技大學(xué),2012.