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

張發展，張 潼

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

0 引言

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

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

1 UFLP 問題的定義和數學模型

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

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

根據上述定義，UFLP的數學模型描述如下：

2 新型傳遞函數

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

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

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

3 利用N-DisDE求解UFLP

3.1 N-DisDE

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

3.2 利用N-DisDE求解UFLP

輸入：一個UFLP實例，參數A，N，CR，T，FS和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（客戶個數），N，MI是關于n的多項式時，算法1為具有多項式時間復雜度的演化算法。

4 計算結果與分析

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

4.1 UFLP 實例

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

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

4.2 計算結果比較與分析

從表3可以看出，N-DisDE，HBDE 和BPSO對于第一類UFLP實例均能100%求得最優值。從表4可以看出，對于第二類UFLP實例，N-DisDE和HBDE均能100%求得最優值，而BPSO對于實例Cap101和Cap103的求解結果較差，對于實例Cap102和Cap104的求解結果較好。從表5可以看出，對于第三類UFLP實例，HBDE的求解效果最好；N-DisDE對于實例Cap131的計算結果較差，30次獨立運行中有29次可以求得最優值；BPSO的計算結果最差，僅對于實例Cap134的計算結果較好。從表5中可以看出，對于第四類大規模UFLP實例，N-DisDE的計算結果明顯優于其他算法，不僅求解質量最好，且魯棒性更佳；其次是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型轉換函數的啟發，提出了一種新型轉換函數Ntf，并在此基礎上，給出了一種基于新型轉換函數的離散差分演化算（N-DisDE）。為了驗證N-DisDE的求解性能，本文通過求解4類不同規模UFLP實例，驗證了算法的高效性和有效性，并通過與已有算法的計算結果比較表明：NDDE 比HBDE和BPSO的求解結果更優，算法的魯棒性更佳，非常適用于求解大規模UFLP實例。

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