遺傳算法在設施定位問題中的應用研究

馬娜，王新生

(湖北大學 資源環境學院，湖北 武漢 430062)

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

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

1 設施定位問題的數學表達

根據Miller[2]的研究，設施定位問題有兩種數學表達形式.

1.1基于平面空間的設施定位問題的目標函數和變量基于連續平面空間的設施定位問題是指在連續平面空間上確定設施的空間位置.給定n個用戶對象的集合，設施定位問題的優化目標是確定p個沒有限定容量的設施的空間位置，使設施與用戶間相互作用費用和設施在選定位置上的固定費用之和最小.其數學表達式如下：

(1)

且滿足

(2)

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

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

(3)

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

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

(4)

(5)

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

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

2 遺傳算法在設施定位問題中的應用研究

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

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

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

在進行遺傳算法的實際應用時，常碰到幾個關鍵問題：由問題空間到遺傳空間的編碼問題；遺傳算子的技術設計問題；遺傳算法中各項參數確定和遺傳算法過早收斂問題等.

(1)編碼和適應度函數

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

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

(2)遺傳算子的設計

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

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

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

(3)實驗結果

表1 Cooper 和Rosing的實例的用戶坐標

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

用Cooper和Rosing的例子來測試本方法的有效性.這些例子為測試我們提出的方法的有效性提供了一個好的標準，因為Rosing已經計算出它們的全局最優解[1](表3).這些實例包括30個用戶，其位置坐標見表1.用戶需求看作是相同的，并假設設施沒有能力約束[1].當采用各用戶子集的算術平均中心為中位中心或設施空間位置時，計算得出的用戶分配結果見表2.

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

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

表2 基于遺傳算法的用戶分配結果

表3 與Cooper 和 Rosing實例的結果比較

3 結語

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

參考文獻：

[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] 李華昌,謝淑蘭,易忠勝.遺傳算法的原理與應用[J].礦業,2005,14(1):87-90.

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

[5] 王春水,肖學柱,陳漢明.遺傳算法的應用舉例[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].武漢:武漢測繪科技大學出版社,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] 徐勇.一種基于自適應遺傳算法的聚類分析方法[J].系統工程與電子技術.1997,19(9):39-43.

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

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