Back to Search
Start Over
Performance Analysis of Evolutionary Optimization for the Bank Account Location Problem
- Source :
- IEEE Access, Vol 6, Pp 17756-17767 (2018)
- Publication Year :
- 2018
- Publisher :
- IEEE, 2018.
-
Abstract
- 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^{2} \log n+nk^{2})$ , 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.
- Subjects :
- Polynomial
General Computer Science
Bank account location
Evolutionary algorithm
performance guarantee
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Evolutionary computation
Simple (abstract algebra)
0202 electrical engineering, electronic engineering, information engineering
General Materials Science
Local search (optimization)
multiobjective optimization
evolutionary algorithms
runtime analysis
Discrete mathematics
Fitness function
business.industry
General Engineering
Approximation algorithm
Binary logarithm
010201 computation theory & mathematics
020201 artificial intelligence & image processing
lcsh:Electrical engineering. Electronics. Nuclear engineering
business
lcsh:TK1-9971
Subjects
Details
- Language :
- English
- ISSN :
- 21693536
- Volume :
- 6
- Database :
- OpenAIRE
- Journal :
- IEEE Access
- Accession number :
- edsair.doi.dedup.....740acf9cdd2f52004751d5df6a1a6c5c