一種無容量設施選址問題的新穎離散差分演化算法

張發(fā)展，張 潼

(河北地質大學 信息工程學院，河北 石家莊 050031)

0 引言

無容量設施選址問題（UFLP）[1]是由Kuehn和Hamburger于1963年首次提出的一個重要的組合優(yōu)化問題。UFLP不僅對于學校、工廠、倉庫、消防站、醫(yī)院等基礎設施的選址具有重要的應用價值[2-3]，而且在資源配置、資金預算、物流運輸、計算機網(wǎng)絡和計算機視覺等領域具有重要的理論意義[4-7]。

近年來，國內外學者對 UFLP的求解算法進行了廣泛的研究。Galv?o和Raggi[8]提出了一種求解UFLP一般0-1公式的三階段精確方法。Conn和 CornuéJols[9]提出了一種基于凝聚對偶的正交精確解求解超線性規(guī)劃的新方法投影，并用于求解UFLP問題。Charikar和Guha[10]提出了一種簡單的貪婪局部搜索算法，在 (2/ )O n?時間內達到了2.414+?的近似比。Takaya等人[11]和Atta[12]等人先后提出了利用螢火蟲算法（FA）和猴群算法（MA）求解UFLP的方法，但是他們都沒有給出大規(guī)模UFLP實例的計算結果。通過上述文獻可以看出，精確算法在求解大規(guī)模UFLP實例時是非常耗費時間的，而非精確算法尤其是演化算法的求解速度遠遠快于精確算法。目前，如何利用演化算法快速高效地求解UFLP已經成為一個熱點問題。因此，本文研究如何利用DE求解UFLP問題，本文首先提出了一個新型傳遞函數(shù)Ntf，將DE中的個體的實向量轉換為二進制向量，以適用于直接求解二元優(yōu)化問題。然后基于 Ntf給出了一種新的離散差分演化算法（N-DisDE），并利用N-DisDE提出了求解UFLP的一個新的高效方法。

1 UFLP 問題的定義和數(shù)學模型

UFLP的定義一般描述為：給定客戶的集合K= {k1,k2,… ,kn}，其中m為客戶的數(shù)量，ki表示第i個客戶。給定可以開放的設施集合S={s1,s2,… ,sn}，其中n為設施數(shù)量，sj表示第j個設施。給定一個m×n的服務矩陣D= [dij]m×n，其中dij表示當?shù)趇個客戶從第j個設施獲得服務時的服務成本。G= {g1,g2,… ,gn}是設施固定開放成本的集合，其中gj表示第j設施開放所需要的開放成本。

首先定義了兩個二進制變量yij和xj如下：

根據(jù)上述定義，UFLP的數(shù)學模型描述如下：

2 新型傳遞函數(shù)

近年來，傳遞函數(shù)已經成為將連續(xù)型演化算法轉換為離散演化算法的重要方法之一。目前，已有的轉換函數(shù)可以分為兩類：S型傳遞函數(shù)和V型傳遞函數(shù)[13-14]。在表1中給出了8個已有的S型和V型轉換函數(shù)的函數(shù)公式，其中S型轉換函數(shù)分別命名為S1 ～S4，V型轉換函數(shù)分別命名為V1 ～V4。

表1 S型轉換函數(shù)和V型轉換函數(shù)Tab.1 S-shaped conversion function and V-shaped conversion function

book=28,ebook=32本文受S型和V型傳遞函數(shù)的啟發(fā)，提出了一個新型轉換函數(shù)，命名為Ntf。轉換函數(shù)Ntf的計算公式為：

3 利用N-DisDE求解UFLP

3.1 N-DisDE

其中， T∈(0,1) 是一個預先設定的閾值，本文設為0.5。

3.2 利用N-DisDE求解UFLP

輸入：一個UFLP實例，參數(shù)A，N，CR，T，F(xiàn)S和MI；

輸出：最好解B和最好值f( B, Q).

在算法 1中，step（1）的時間復雜度為O(N×n)；step（2）～step（7）的時間復雜度為O(N×m×n2)；step（8）的時間復雜度為O(N)；step（9）～step（18）的時間復雜度為O(MI×N×m×n2)；因此，算法 1的時間復雜度為O(N×n) +O(N×m×n2)+O(N)+O(MI×N×m×n2)。當m（客戶個數(shù)），N，MI是關于n的多項式時，算法1為具有多項式時間復雜度的演化算法。

4 計算結果與分析

本文所有計算在配置為（英特爾）Intel(R)Core(TM)i5-7500 CPU@3.40GHz（3401 MHz）和4GB的RAM 2.90ghz的微型計算機上進行，編程語言為C，編譯環(huán)境為Code:Blocks。

4.1 UFLP 實例

我們利用 15個來自 OR-library[15]的 UFLP benchmark實例對EGTOA與上述算法進行比較，這15個benchmark實例根據(jù)它的規(guī)模大小分為4類：第一類是16×50（即16個設施和50個客戶）的小規(guī)模實例，編號分別為cap71～cap74；第二類是25×50（即25個設施和50個客戶）的中等規(guī)模實例，編號分別為 cap101～cap104；第三類是50×50（即50個設施和 50個客戶）的中等規(guī)模實例，編號分別為 cap131～cap134；第四類是100×1000（即100個設施和1000個客戶）的大規(guī)模實例，編號分別為 capA～capC。四類 UFLP實例的規(guī)模大小與最優(yōu)值見表2所示。

表2 UFLP 實例Tab.2 Th e UFLP instances

4.2 計算結果比較與分析

從表3可以看出，N-DisDE，HBDE 和BPSO對于第一類UFLP實例均能100%求得最優(yōu)值。從表4可以看出，對于第二類UFLP實例，N-DisDE和HBDE均能100%求得最優(yōu)值，而BPSO對于實例Cap101和Cap103的求解結果較差，對于實例Cap102和Cap104的求解結果較好。從表5可以看出，對于第三類UFLP實例，HBDE的求解效果最好；N-DisDE對于實例Cap131的計算結果較差，30次獨立運行中有29次可以求得最優(yōu)值；BPSO的計算結果最差，僅對于實例Cap134的計算結果較好。從表5中可以看出，對于第四類大規(guī)模UFLP實例，N-DisDE的計算結果明顯優(yōu)于其他算法，不僅求解質量最好，且魯棒性更佳；其次是BPSO，而HBDE的計算結果最差。

表3 N-DisDE ，HBDE和BPSO求解UFLP實例（16×50）的結果Tab.3 Calculation results of N-DisDE, HBDE and BPSO for solving UFLP instances (16×50)

表4 N-DisDE ，HBDE和BPSO求解UFLP實例（25×50）的結果Tab.4 Calculation results of N-DisDE, HBDE and BPSO for solving UFLP instances (25×50)

表5 N-DisDE ，HBDE和BPSO求解UFLP實例（50×50）的結果Tab.5 Calculation results of N-DisDE, HBDE and BPSO for solving UFLP instances (50×50)

表6 N-DisDE ，HBDE和BPSO求解UFLP實例（100×1 000）的結果Tab.6 Calculation results of N-DisDE, HBDE and BPSO for solving UFLP instances (100×1 000)

5 結論與展望

本文受已有的S型和V型轉換函數(shù)的啟發(fā)，提出了一種新型轉換函數(shù)Ntf，并在此基礎上，給出了一種基于新型轉換函數(shù)的離散差分演化算（N-DisDE）。為了驗證N-DisDE的求解性能，本文通過求解4類不同規(guī)模UFLP實例，驗證了算法的高效性和有效性，并通過與已有算法的計算結果比較表明：NDDE 比HBDE和BPSO的求解結果更優(yōu)，算法的魯棒性更佳，非常適用于求解大規(guī)模UFLP實例。

通過實驗證明，本文提出的基于新型轉換函數(shù)是非常成功的，這為連續(xù)演化算法離散化提供了一種新型函數(shù)。在未來研究中，我們將探索新型轉換函數(shù)對其他算法的影響，如煙花算法（fireworks algorithm, FA）[18]和鴿群優(yōu)化算法（pigeon-inspired optimization algorithm, PIO）[19]等。此外，我們將繼續(xù)嘗試利用 N-DisDE求解其他二元優(yōu)化問題，例如各種背包問題[20-21]，集合覆蓋問題[22]等。