鄒貴祥，張飛舟

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

1 引言

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

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

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

2.1 算法概述

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

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

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

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

多樣性測(cè)度的定義如下[10]：

(1)

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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)解的概率越大，搜索時(shí)間也會(huì)更長(zhǎng)。

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

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

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

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

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

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

3 實(shí)驗(yàn)1

3.1 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

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

(3)

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

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

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

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

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

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

(4)

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

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

(5)

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

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

(6)

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

經(jīng)過(guò)實(shí)驗(yàn)可以發(fā)現(xiàn)，這五種算法都具有達(dá)到最優(yōu)解的能力，但是達(dá)到最優(yōu)解的效果并不相同(如表1所示)，以改進(jìn)的和進(jìn)一步改進(jìn)的小生境遺傳算法效果最優(yōu)。造成差異的原因是，標(biāo)準(zhǔn)遺傳算法經(jīng)過(guò)了遺傳操作之后，種群的多樣性迅速下降，在變異概率不高的情況下，達(dá)到早熟或者收斂到局部最優(yōu)解的概率太大；預(yù)選機(jī)制的小生境遺傳算法進(jìn)化具有一定“方向性”(向著適應(yīng)值更高的子代進(jìn)化)，然而它依舊保留了選擇操作，因此效果比標(biāo)準(zhǔn)遺傳算法好但劣于其他算法；使用多樣性測(cè)度來(lái)維護(hù)的遺傳算法在多樣性測(cè)度達(dá)到0時(shí)，對(duì)比當(dāng)前最優(yōu)解和進(jìn)化過(guò)程中所記錄的最優(yōu)解是否一致后，遺傳算法收斂到局部最優(yōu)解(即早熟)的概率下降，然而它的進(jìn)化不具有“方向性”，因此效果居中；而兩種改進(jìn)的小生境遺傳算法進(jìn)化方向性更強(qiáng)，多樣性下降更慢，因此它們收斂到最優(yōu)解的概率更大；進(jìn)一步改進(jìn)的算法取消了選擇操作，搜索空間會(huì)大于改進(jìn)的小生境算法，導(dǎo)致它的效果最優(yōu)。當(dāng)然，種群大小是導(dǎo)致改進(jìn)與進(jìn)一步改進(jìn)的算法并未達(dá)到100%收斂至最優(yōu)解的原因之一，種群變大，兩種改進(jìn)的遺傳算法收斂到全局最優(yōu)解的概率會(huì)變大(如表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ī)一次實(shí)驗(yàn)的算法性能圖(如圖2所示)的比較中可以看出，在線(xiàn)性能函數(shù)曲線(xiàn)方面，預(yù)選機(jī)制小生境遺傳算法、改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的在線(xiàn)性能函數(shù)曲線(xiàn)上升很快，其數(shù)值與上升速度均超過(guò)了剩下的兩種算法，說(shuō)明這三種算法的種群的平均適應(yīng)值以及平均適應(yīng)值的提高速度優(yōu)于剩下的兩種算法，僅使用多樣性測(cè)度維護(hù)的遺傳算法在線(xiàn)性能強(qiáng)于標(biāo)準(zhǔn)遺傳算法；離線(xiàn)性能函數(shù)曲線(xiàn)方面，改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的離線(xiàn)性能函數(shù)曲線(xiàn)上升很快，其數(shù)值與上升速度均超過(guò)了剩下的三種算法，說(shuō)明改進(jìn)與進(jìn)一步改進(jìn)的小生境遺傳算法的最優(yōu)個(gè)體適應(yīng)值的提高能力和遺傳算法的搜索到更優(yōu)個(gè)體的能力優(yōu)于剩下的三種算法，僅使用多樣性測(cè)度維護(hù)的遺傳算法離線(xiàn)性能列第三，其更新種群的方式隨機(jī)導(dǎo)致算法向最優(yōu)解收斂的過(guò)程隨機(jī)。從圖2中也能看出，雖然這次實(shí)驗(yàn)中預(yù)選機(jī)制小生境遺傳算法前100代中種群的平均適應(yīng)值高，但是最優(yōu)適應(yīng)值卻不高，說(shuō)明在這次實(shí)驗(yàn)中它已經(jīng)陷入了早熟的狀態(tài)。從表1中可以發(fā)現(xiàn)，進(jìn)一步改進(jìn)的小生境遺傳算法達(dá)到最優(yōu)解的次數(shù)要高于改進(jìn)的小生境遺傳算法，其原因應(yīng)該是取消了選擇操作而導(dǎo)致算法可以搜索的范圍更大，且在圖2所示的這次實(shí)驗(yàn)中，進(jìn)一步改進(jìn)的小生境遺傳算法比改進(jìn)的小生境遺傳算法先找到了它認(rèn)為的最優(yōu)解，因此它的在線(xiàn)、離線(xiàn)性能函數(shù)均高于改進(jìn)的小生境遺傳算法。

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

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

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

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

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

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

4 實(shí)驗(yàn)2

4.1 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

人工蜂群算法同樣作為優(yōu)化算法[4,31 - 34]，它先隨機(jī)生成若干個(gè)蜜源，每個(gè)蜜源以20個(gè)設(shè)址點(diǎn)的坐標(biāo)表示。使用引領(lǐng)蜂和跟隨蜂對(duì)蜜源進(jìn)行優(yōu)化。與蜜源一一對(duì)應(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ī)生成新的蜜源。人工蜂群算法的重點(diǎn)是由蜜源產(chǎn)生附近蜜源坐標(biāo)的方法，一般使用的方法是：

(7)

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

4.2 實(shí)驗(yàn)結(jié)果

我們比較200次實(shí)驗(yàn)中，進(jìn)一步改進(jìn)的小生境遺傳算法的解適應(yīng)值優(yōu)于預(yù)選機(jī)制小生境遺傳算法的次數(shù)(A)，其優(yōu)于排擠小生境遺傳算法的次數(shù)(B)，使用多樣性測(cè)度維護(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é)果比較

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

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

4.3 討論

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

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

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

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

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

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

(2)實(shí)驗(yàn)結(jié)果方面。

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

(3)與實(shí)際情況對(duì)比方面。

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

[5] 徐愛(ài)功,徐濤,張明月,等.GPS動(dòng)態(tài)單點(diǎn)定位的遺傳算法探究[J].測(cè)繪科學(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] 汪民樂(lè),高曉光,劉剛.遺傳算法早熟問(wèn)題的定量分析及其預(yù)防策略[J].系統(tǒng)工程與電子技術(shù),2006,28(8):1249-1251.

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

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

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

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

[18] 賴(lài)志柱.長(zhǎng)模式遺傳算法及其應(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)急物資配送車(chē)輛調(diào)度優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(10):2928-2932.

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

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

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

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

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

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

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

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