馬娜，王新生

(湖北大學(xué) 資源環(huán)境學(xué)院，湖北 武漢 430062)

設(shè)施定位問題(facility location problem),也稱作多韋伯問題(multi-Weber problem)或p-中位問題(p-median problem)[1], 實(shí)質(zhì)上它既包括用戶的分配，又包括設(shè)施在空間上的定位，所以通常又把設(shè)施定位問題稱為設(shè)施定位一分配問題(facility location-allocation problems).

本文中將設(shè)施定位-分配問題分為用戶分配、設(shè)施定位兩個子問題，提出分別采用遺傳算法來處理.

1 設(shè)施定位問題的數(shù)學(xué)表達(dá)

根據(jù)Miller[2]的研究，設(shè)施定位問題有兩種數(shù)學(xué)表達(dá)形式.

1.1基于平面空間的設(shè)施定位問題的目標(biāo)函數(shù)和變量基于連續(xù)平面空間的設(shè)施定位問題是指在連續(xù)平面空間上確定設(shè)施的空間位置.給定n個用戶對象的集合，設(shè)施定位問題的優(yōu)化目標(biāo)是確定p個沒有限定容量的設(shè)施的空間位置，使設(shè)施與用戶間相互作用費(fèi)用和設(shè)施在選定位置上的固定費(fèi)用之和最小.其數(shù)學(xué)表達(dá)式如下：

(1)

且滿足

(2)

(1)，(2)式中，如果用戶i被分配到設(shè)施j時，zij=1；否則zij=0.wi是對用戶i的需求權(quán)重，Ci描述用戶i的位置，F(xiàn)i描述設(shè)施j的位置，d(Ci,Fj)表示用戶i和設(shè)施j間的距離，S(Fi)指設(shè)施j選定在某一位置上的費(fèi)用，n表示用戶的數(shù)量，p表示設(shè)施的個數(shù)，(2)式表示每個用戶只能接受一個設(shè)施的服務(wù).(1)式中待定的變量有兩個：分配變量z和隱含在Fj中設(shè)施位置的坐標(biāo).

1.2基于離散空間的設(shè)施定位問題的目標(biāo)函數(shù)和變量基于離散空間的設(shè)施定位問題是指在有限個候選設(shè)施中選取若干個設(shè)施，并為這些設(shè)施確定相應(yīng)用戶的問題.假如從m個候選設(shè)施中選取p個設(shè)施，則問題可表示為：

(3)

(3)式除了要滿足(2)式的約束條件外，還應(yīng)服從下面約束：

zij≤zjj,i,j=1,2,…,n

(4)

(5)

(4)，(5)式中，若候選者j被選擇為設(shè)施時，zjj=1；否則zjj=0.(4)式表示除非該設(shè)施是選定設(shè)施，否則不允許將一個用戶分配給候選設(shè)施.(5)式表示從m個候選設(shè)施中選取p個設(shè)施.(3)式中要確定的變量是分配變量z.設(shè)施的位置坐標(biāo)隱含在m個候選設(shè)施中，不是待定的變量.

設(shè)施定位問題中分配子問題是一個一般的指派問題，它是一個已知的NP難問題[1].Miller[2]認(rèn)為，即使對點(diǎn)狀用戶、點(diǎn)狀設(shè)施而言，多設(shè)施定位問題都屬于求解有多個全局最優(yōu)解的目標(biāo)函數(shù)問題.如果考慮到設(shè)施和用戶的空間形狀(configuration)，如設(shè)施和用戶的形狀分別為線狀或面狀，則目標(biāo)函數(shù)更加復(fù)雜，因此必須尋求更有效的枚舉(enumeration)算法或鄰域搜索技術(shù)以求得問題的最好解(或近似最優(yōu)解).

2 遺傳算法在設(shè)施定位問題中的應(yīng)用研究

遺傳算法GA(genetic algorithm)是模擬自然界生物進(jìn)化機(jī)制的一種算法,即遵循適者生存、優(yōu)勝劣汰的法則,即尋優(yōu)過程中有用的保留,無用的去除[3].它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，模擬生物進(jìn)化過程，對群體反復(fù)進(jìn)行遺傳學(xué)的操作(遺傳，交叉和變異)，根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進(jìn)行評價(jià).依據(jù)“適者生存”進(jìn)化規(guī)則，不斷得到更優(yōu)的群體.同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解[4].

由于遺傳算法的通用性、隱含并行性和穩(wěn)健性(robustness),該算法日益引起各方面的廣泛關(guān)注，在實(shí)踐中有許多成功的例子[5-7].

設(shè)施定位-分配問題可分為用戶分配、設(shè)施定位兩部分.一般來說，離散空間點(diǎn)位的算術(shù)平均中心(mean center)在空間上離中位中心(median center)很近(離散點(diǎn)的數(shù)量較少或空間分布很離散時，偏離較多)，中位中心即是指要確定的設(shè)施空間位置[8-9]，因此首先將算術(shù)平均中心設(shè)定為設(shè)施位置來確定用戶分配子問題，這時問題的目標(biāo)函數(shù)為：

在進(jìn)行遺傳算法的實(shí)際應(yīng)用時，常碰到幾個關(guān)鍵問題：由問題空間到遺傳空間的編碼問題；遺傳算子的技術(shù)設(shè)計(jì)問題；遺傳算法中各項(xiàng)參數(shù)確定和遺傳算法過早收斂問題等.

(1)編碼和適應(yīng)度函數(shù)

采用類似于Dibble和 Densham的遺傳算法編碼方法[10]，由p個整數(shù)組成的染色體碼串表示設(shè)施中用戶分配狀況，如碼串為111122223332的染色體，表示有12個用戶、3個設(shè)施的定位問題的一個可能解，序號為1，2，3，4的用戶分配到編號為1的設(shè)施，序號為5，6，7，8，12的用戶分配到2號設(shè)施，序號為9，10，11的用戶分配到3號設(shè)施.這種編碼方式可以保證染色體長度最短，有效地減少當(dāng)變量過多，碼串過長時，二進(jìn)制編碼出現(xiàn)的“海明懸崖”(hamming cliffs)問題[11].

針對本具體問題，用平均中心來代替設(shè)施空間位置來進(jìn)行遺傳算法的計(jì)算，如上述編碼中是先確定序號為1，2，3，4的用戶的算術(shù)平均中心，計(jì)算該平均中心與這4個用戶的距離和，其余的依次類推，適應(yīng)度函數(shù)即是這些距離的總和.由隨機(jī)法產(chǎn)生的初始群體是由p個整數(shù)組成的，所以變異操作是將當(dāng)前的某個整數(shù)以相等的概率隨機(jī)地轉(zhuǎn)換為其它(p-1)個整數(shù)中的任意一個整數(shù).另外，在計(jì)算個體適應(yīng)度之前，還須對二進(jìn)制碼串進(jìn)行譯碼(decode)，本研究中不是直接將其轉(zhuǎn)換成十進(jìn)制數(shù)，而是轉(zhuǎn)換成各平均中心與其相應(yīng)用戶間距離之和.

(2)遺傳算子的設(shè)計(jì)

在此應(yīng)用中，選擇機(jī)制采用聯(lián)賽選擇方法(tournament selection model)，即從群體中任意選取一定數(shù)目的個體(稱為聯(lián)賽規(guī)模)，本例聯(lián)賽規(guī)模選取為2，其中適應(yīng)度最高的個體保存到下一代.這一過程反復(fù)執(zhí)行，直到保存到下一代的個體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止.

雜交方法采用一致雜交算子(uniform crossover)，即通過設(shè)定屏蔽字(mask)來決定新個體的基因繼承兩個舊個體中哪個個體的對應(yīng)基因.

變異技術(shù)采用基本變異算子，即變異僅以一定的概率(通常很小)對串的某些位作值的變異[6].

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

表1 Cooper 和Rosing的實(shí)例的用戶坐標(biāo)

我們按照上述設(shè)計(jì)編制了相應(yīng)的程序，并進(jìn)行計(jì)算測試.實(shí)驗(yàn)中，我們對遺傳算法中各項(xiàng)參數(shù)進(jìn)行了反復(fù)測試，最后選定群體規(guī)模為100，雜交概率為0.65，變異概率為0.005，初始可行解群體由隨機(jī)法產(chǎn)生，設(shè)定若干代內(nèi)(如100代)適應(yīng)度函數(shù)無變化時運(yùn)行終止.由于本實(shí)驗(yàn)的問題規(guī)模很小，最好結(jié)果都在200代內(nèi)達(dá)到.實(shí)驗(yàn)中僅考慮設(shè)施在連續(xù)平面空間上定位的情況，不考慮設(shè)施在平面上不同地點(diǎn)的固定投資.

用Cooper和Rosing的例子來測試本方法的有效性.這些例子為測試我們提出的方法的有效性提供了一個好的標(biāo)準(zhǔn)，因?yàn)镽osing已經(jīng)計(jì)算出它們的全局最優(yōu)解[1](表3).這些實(shí)例包括30個用戶，其位置坐標(biāo)見表1.用戶需求看作是相同的，并假設(shè)設(shè)施沒有能力約束[1].當(dāng)采用各用戶子集的算術(shù)平均中心為中位中心或設(shè)施空間位置時，計(jì)算得出的用戶分配結(jié)果見表2.

表3中的誤差百分比計(jì)算如為：(實(shí)際計(jì)算值-最優(yōu)值)/最優(yōu)值×100%.當(dāng)p=3時，我們計(jì)算的目標(biāo)函數(shù)值為306.399 7，這比Rosing方法計(jì)算的全局最優(yōu)解307.372還要低，認(rèn)為我們的結(jié)果是正確的，我們得到的3個設(shè)施的坐標(biāo)分別為(6.889 7,16.598 5)、(21.359 3,44.304 2)、(39.086 1,15.993 5).或許Rosing方法的計(jì)算結(jié)果有精度誤差.從表2、表3可以看出，如果將算術(shù)平均中心作為設(shè)施位置(即中位中心)，計(jì)算的目標(biāo)函數(shù)值就已十分接近問題的最優(yōu)解，這也說明算術(shù)平均中心在空間上與中位中心很近.當(dāng)用戶分配子問題確定以后，多設(shè)施定位問題變?yōu)閱卧O(shè)施定位問題，再經(jīng)過遺傳算法求解，計(jì)算結(jié)果較Cooper的ALA方法效果好，與已知的全局最優(yōu)解誤差不大.這說明了本研究中所采取的解決問題方法的有效性.

另外，需要說明的是，我們也對本方法進(jìn)行了較大規(guī)模的設(shè)施定位問題(用戶達(dá)到數(shù)百個，設(shè)施十余個)的試驗(yàn)，從遺傳算法的設(shè)計(jì)上完全可以處理這種規(guī)模的問題，但是即使我們對基本遺傳算法(simple genetic algorithms)作一些改進(jìn)，如采用自適應(yīng)雜交、變異[12]、遺傳-災(zāi)變算法[13]和重新起動[14]等策略，在有限的時間內(nèi)還是不能收斂到全局最優(yōu)解，我們正在進(jìn)一步尋求其它的改進(jìn)方法.

表2 基于遺傳算法的用戶分配結(jié)果

表3 與Cooper 和 Rosing實(shí)例的結(jié)果比較

3 結(jié)語

由于遺傳算法的主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換，操作是根據(jù)優(yōu)勝劣汰的原則，算法在收斂性、全局優(yōu)化方面都較傳統(tǒng)搜索方法優(yōu)越.正如前面所述，設(shè)施定位問題是一個NP難問題，對解決此類遺傳問題算法是有效的.

參考文獻(xiàn)：

[1] Gen M,Cheng R. Genetic algorithms and engineering design[M].New York:John Wiley and Sons,Inc,1997.

[2] Miller H J. GIS and geometric representation in facility location problems[J]. International Journal of Geographical Information Systems,1996,10(7):791-816.

[3] 李華昌,謝淑蘭,易忠勝.遺傳算法的原理與應(yīng)用[J].礦業(yè),2005,14(1):87-90.

[4] 喬均儉,付麗君,徐雅玲.應(yīng)用遺傳算法原理確定函數(shù)的最優(yōu)解[J].微計(jì)算機(jī)信息,2007,23(6):240-241.

[5] 王春水,肖學(xué)柱,陳漢明.遺傳算法的應(yīng)用舉例[J].計(jì)算機(jī)仿真.2005,22(6):155-157.

[6] Rubenstein-Montano B,Zandi I. Application of a genetic algorithm to policy planning:the case of solid waste[J].Environment and Planning B:Planning and Design,1999,26(6):893-907.

[7] richard J B,John T T,Michael R B, et al. Multiobjective urban planning usinggenetic algorithm[J]. Journal of Urban and Development,1999,125(2):86-99.

[8] 郭仁忠.空間分析[M].武漢:武漢測繪科技大學(xué)出版社,1997:191-201.

[9] Robert G C.Digital cartography[M].Prentice Hall:New Jersey,1991:165-176.

[10] Dibble C,Densham P J.Generating interesting alternatives in GIS and SDSS using genetic algorithms[M].In Proceeding of GIS/LIS’93(Bethesda:American Society of Photogrammetry and Remote Sensing and American Congress on Surveying and Mapping),1993:180-189.

[11] Zbigniew M.Genetic algorithms + data structures=evolution programs[M].Berlin Heidelberg:springer-Verlag,1996.

[12] 徐勇.一種基于自適應(yīng)遺傳算法的聚類分析方法[J].系統(tǒng)工程與電子技術(shù).1997,19(9):39-43.

[13] 孟祥萍,張化光,何巍.一種基于二進(jìn)制編碼的改進(jìn)遺傳算法[J].吉林工業(yè)大學(xué):自然科學(xué)學(xué)報(bào),1999,29(3):79-83.

[14] 孟祥萍,張化光.一種快速綜合性的遺傳算法[J].東北師大學(xué)報(bào):自然科學(xué)版,1998,4:13-17.