Performance Analysis of Evolutionary Optimization for the Bank Account Location Problem

The bank account location (BAL) problem is an NP-hard discrete optimization problem. A few experimental studies have shown that evolutionary algorithms are efficient methods for the BAL problem. However, from theoretical point of view, we know little about the performance of evolutionary algorithms (EAs) on the BAL problem. In this paper, we contribute to theoretical understanding of EAs on the BAL problem. The worst-case bounds on a simple evolutionary algorithm called (1 + 1) EA and a global simple multiobjective evolutionary algorithm called GSEMO for the BAL problem is presented. We reveal that the (1 + 1) EA can find a (k/(2k - 1)) approximation solution for the BAL problem. We also find that GSEMO can obtain an approximate solution on the BAL problem with value not less than (1-(1/e))OPT in expected polynomial runtime O(n² log n + nk²), where OPT is the optimal fitness function value, n is the number of banks that can open accounts, and k is the maximum number of accounts that can be maintained. Meanwhile, we demonstrate that the (1+1) EA and GSEMO are superior to some local search algorithms with interchange neighborhood on an instance, and we also show that GSEMO can efficiently optimize another instance while the (1 + 1) EA may be inefficient.