﻿ 求解P中位问题的混合蝙蝠算法
 上海理工大学学报  2019, Vol. 41 Issue (4): 344-349 PDF

Hybrid Bat Algorithm for Solving a P-Median Problem
Wang Tingting, Zhang Huizhen
Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Based on the mathematical model and specific features of a P-median problem, the subtraction operator between the location and the location of bats, the addition operator between the velocity and location as well as the feasible function were redefined. The idea of crossover in genetic algorithm was introduced in order to perform a local search on the current solution and a hybrid bat algorithm (HBA) was proposed for the problem. By some tests on the P-median problem and comparisons with other algorithms, the computational results show that the hybrid bat algorithm is feasible and efficient for solving P-median problems.
Key words: P-median problem     bat algorithm     feasible function     crossover

1 P中位问题

 $\min \;z = \mathop \sum \limits_{i = 1}^m \mathop \sum \limits_{j = 1}^n {d_{ij}}{x_{ij}}$ (1)
 $\mathop \sum \limits_{i = 1}^m {x_{ij}} = 1,\quad \forall j \in N$ (2)
 ${x_{ij}} \leqslant {y_i},\quad\forall i \in M,j \in N$ (3)
 $\mathop \sum \limits_{i = 1}^m {y_i} = p,\quad\forall i \in M$ (4)
 ${x_{ij}} \in \left\{ {0,1} \right\},\forall i \in M,j \in N$ (5)
 ${y_i} \in \left\{ {0,1} \right\},\forall i \in M$ (6)

2 基本蝙蝠算法

2.1 基本蝙蝠的搜索过程

BA的搜索过程实质上是通过频率的变化实现对蝙蝠速度的控制，从而更新蝙蝠的位置。假设在d维空间中，蝙蝠it时刻下的速度和位置分别为vitxit，则该蝙蝠通过改变频率fi来调整自身位置与当前所处位置最好的蝙蝠之间的距离，从而更新自身新位置xit+1，向当前求解的最好解靠拢，则蝙蝠it+1时刻下的速度和位置更新公式定义为

 ${f_i} = {f_{\min}} + \left( {{f_{\max}} - {f_{\min}}} \right)\beta$ (7)
 $v_i^{t + 1} = v_i^t + \left( {x_i^t - {x^*}} \right){f_i}$ (8)
 $x_i^{t + 1} = x_i^t + v_i^{t + 1}$ (9)

2.2 基本蝙蝠的优化过程

 ${x_{\rm new}} = {x_{\rm old}} + {\varepsilon} {A^t}$ (10)

 $A_i^{t + 1} = \alpha A_i^t$ (11)
 $r_i^{t + 1} = r_i^0\left[ {1 - {\rm exp}\left( { - \gamma t} \right)} \right]$ (12)

3 混合蝙蝠算法

BA与蚁群算法、粒子群算法等其他群体智能算法类似，是利用蝙蝠的回声定位特性来模拟蝙蝠的捕食猎物行为而建立的仿生算法。它的速度和位置更新步骤有些类似于标准粒子群优化，在一定程度上，BA可以看作是标准粒子群优化和强化的局部搜索的平衡结合，其平衡受音量和脉冲发生率的控制。BA的提出是用来求解连续域的函数优化问题，不能直接用来求解组合优化问题，因此，本文根据PMP的具体特征和BA的基本思想，提出了一种适用于求解PMP的混合蝙蝠算法。

3.1 编码方式

PMP的主要任务是在m个候选位置点中选择p个位置作为中位点，以这些中位点来服务客户，而仅当每个客户都被分配到离其最近的中位点时才能保证总距离最小，则可认为PMP的求解是通过搜索不同组合的p个中位点来寻找问题最优解。因而本文采用基于中位数的方式对个体进行编码，每只蝙蝠对应一个p维向量，每个维度上的值为[1，m]内的随机整数，该p维向量内每一维度上的值都是唯一的，且没有大小顺序。例如，对于一个m=5，p=3的PMP，与蝙蝠i对应的编码为 $x_i=(5\;2\;3)$ ，即设施2，3，5为中位点。

3.2 相关定义

 ${{D }}=\left[ {\begin{array}{*{20}{c}} {{0}}&{{{424}}}&{{{569}}}&{{{254}}}&{{{275}}}\\ {{{424}}}&{{0}}&{{{391}}}&{{{452}}}&{{{298}}}\\ {{{569}}}&{{{391}}}&{{0}}&{{{167}}}&{{{528}}}\\ {{{254}}}&{{{452}}}&{{{167}}}&{{0}}&{{{456}}}\\ {{{275}}}&{{{298}}}&{{{528}}}&{{{456}}}&{{0}} \end{array}} \right]$

3.3 混合蝙蝠算法的设计

4 数值实验

 图 1 HBA求解pmed14的最优迭代图 Fig. 1 Optimal iterative graph of pmed14 solved by HBA

 图 2 HBA求解pmed15的最优迭代图 Fig. 2 Optimal iterative graph of pmed15 solved by HBA
5 结　论

 [1] HAKIMI S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research, 1964, 12(3): 450-459. DOI:10.1287/opre.12.3.450 [2] HAKIMI S L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J]. Operations Research, 1965, 13(3): 462-475. DOI:10.1287/opre.13.3.462 [3] HRIBAR M, DASKIN M S. A dynamic programming heuristic for the p-median problem[J]. European Journal of Operational Research, 1997, 101(3): 499-508. DOI:10.1016/S0377-2217(96)00218-4 [4] SENNE E L F, LORENA L A N. Lagrangean/surrogate heuristics for p-median problems[M]//LAGUNA M, GONZÁLEZ VELARDE J L. Computing Tools for Modeling, Optimization and Simulation. Boston: Springer, 2000: 115-130. [5] BELTRAN C, TADONKI C, VIAL J P. Solving the p-median problem with a semi-lagrangian relaxation[J]. Computational Optimization and Applications, 2006, 35(2): 239-260. DOI:10.1007/s10589-006-6513-6 [6] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco: W. H. Freeman, 1979: 45-76. [7] YURI K, TATYANA L, EKATERINA A, et al. Large neighborhood local search for the p-median problem[J]. Yugoslav Journal of Operations Research, 2005, 15(1): 53-63. DOI:10.2298/YJOR0501053K [8] RESENDE M G C, WERNECK R F F. On the implementation of a swap-based local search procedure for the p-median problem[C]//Proceedings of the 5th Workshop on Algorithm Engineering and Experiments. Baltimore: SIAM, 2003: 119-127. [9] ANTAMOSHKIN A N, KAZAKOVTSEV L A. Random search algorithm for the p-median problem[J]. Informatica, 2013, 37(3): 267-278. [10] AL-KHEDHAIRI A. Simulated annealing metaheuristic for solving p-median problem[J]. International Journal of Contemporary Mathematical Sciences, 2008, 3(25/28): 1357-1365. [11] ALP O, ERKUT E, DREZNER Z. An efficient genetic algorithm for the p-median problem[J]. Annals of Operations Research, 2003, 122(1/4): 21-42. DOI:10.1023/A:1026130003508 [12] LI X, XIAO N C, CLARAMUNT C, et al. Initialization strategies to enhancing the performance of genetic algorithms for the p-median problem[J]. Computers & Industrial Engineering, 2011, 61(4): 1024-1034. [13] KRÖMER P, PLATOŠ J. New genetic algorithm for the p-median problem[M]//PAN J S, SNASEL V, CORCHADO E S, et al. Intelligent Data analysis and Its Applications, Volume II. Cham: Springer, 2014: 35-44. [14] SEVKLI M, MAMEDSAIDOV R, CAMCI F. A novel discrete particle swarm optimization for p-median problem[J]. Journal of King Saud University:Engineering Sciences, 2014, 26(1): 11-19. DOI:10.1016/j.jksues.2012.09.002 [15] YANG X S. A new metaheuristic bat-inspired algorithm[M]//GONZÁLEZ J R, PELTA D A, CRUZ C, et al. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010). Berlin, Heidelberg: Springer, 2010: 65-74. [16] NAKAMURA R Y M, PEREIRA L A M, COSTA K A, et al. BBA: a binary bat algorithm for feature selection[C]//Proceedings of the 2012 25th SIBGRAPI Conference on Graphics, Patterns and Images. Ouro Preto, Brazil: IEEE, 2012: 291-297. [17] 李枝勇, 马良, 张惠珍. 0-1规划问题的元胞蝙蝠算法[J]. 计算机应用研究, 2013, 30(10): 2903-2906. DOI:10.3969/j.issn.1001-3695.2013.10.005 [18] RIZK-ALLAH R M, HASSANIEN A E. New binary bat algorithm for solving 0-1 knapsack problem[J]. Complex & Intelligent Systems, 2018, 4(1): 31-53.