XOR-based artificial bee colony algorithm for binary optimization

The artificial bee colony (ABC) algorithm, which was inspired by the foraging and dance behaviors of real honey bee colonies, was first introduced for solving numerical optimization problems. When the solution space of the optimization problem is binary-structured, the basic ABC algorithm should be modified for solving this class of problems. In this study, we propose XOR-based modification for the solution-updating equation of the ABC algorithm in order to solve binary optimization problems. The proposed method, named binary ABC (binABC), is examined on an uncapacitated facility location problem, which is a pure binary optimization problem, and the results obtained by the binABC are compared with results obtained by binary particle swarm optimization (BPSO), the discrete ABC (DisABC) algorithm, and improved BPSO (IBPSO). The experimental results show that binABC is an alternative tool for solving binary optimization problems and is a competitive algorithm when compared with BPSO, DisABC, and IBPSO in terms of solution quality, robustness, and simplicity.

Anahtar Kelimeler:

Swarm intelligence, artificial bee colony, binary optimization, logic operators, uncapacitated facility location

XOR-based artificial bee colony algorithm for binary optimization

Keywords:

Swarm intelligence, artificial bee colony, binary optimization, logic operators, uncapacitated facility location,

PDF

___

D. Karaboga, “An idea based on honey bee swarm for numerical optimization”, Technical Report, Computer Engineering Department, Engineering Faculty, Erciyes University, available at http://mf.erciyes.edu.tr/abc/pub/tr06 2005.pdf, 2005.
D. Karaboga, B. Basturk, “A powerful and efficient algorithm for numerical function optimization”, Journal of Global Optimization, Vol. 39, pp. 459–471, 2007.
D. Karaboga, B. Basturk, “Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems”, Proceedings of the 12th International Fuzzy Systems Association World Congress on Foundations of Fuzzy Logic and Soft Computing, pp. 789–798, 2007.
D. Karaboga, B. Akay, “A modified artificial bee colony (ABC) algorithm for constrained optimization problems”, Applied Soft Computing, Vol. 11, pp. 3021–3031, 2011.
D. Karaboga, B. Basturk, “On the performance of artificial bee colony (ABC) algorithm”, Applied Soft Computing, Vol. 8, pp. 687–697, 2008.
G. Zhu, S. Kwong, “Gbest-guided artificial bee colony algorithm for numerical function algorithm”, Applied Mathematics and Computation, Vol. 217, pp. 3166–3173, 2010.
B. Alatas, “Chaotic bee colony algorithms for global numerical optimization”, Expert Systems with Applications, Vol. 37, pp. 5682–5687, 2010.
M.H. Kashan, N. Nahavandi, A.H. Kashan, “DisABC: a new artificial bee colony algorithm for binary optimization”, Applied Soft Computing, Vol. 12, pp. 342–352, 2011.
D. Karaboga, B. Gorkemli, “A combinatorial artificial bee colony algorithm for traveling salesman problem”, International Symposium on Innovations in Intelligent Systems and Applications, pp. 50–53, 2011.
M.S. Kıran, H. ˙I¸scan, M. G¨ und¨ uz, “The analysis of discrete artificial bee colony algorithm with neighborhood operator on traveling salesman problem”, Neural Computing and Applications, Vol. 23, pp. 9–21, 2012.
M.S. Kıran, M. G¨ und¨ uz, “A novel artificial bee colony-based algorithm for solving the numerical optimization problems”, International Journal of Innovative Computing, Information & Control, Vol. 8, pp. 6107–6122, 2012. B. Akay, D. Karaboga, “A modified artificial bee colony algorithm for real parameter optimization”, Information Sciences, Vol. 192, pp. 120–142, 2012.
D.J. Mala, V. Mohan, M. Kamalapriya, “Automated software test suite optimisation framework – an artificial bee colony optimisation-based approach”, IET Software, Vol. 4, pp. 334–348, 2010.
D. Karaboga, C. Ozturk, “Neural networks training by artificial bee colony algorithm on pattern classification”, Neural Network World, Vol. 19, pp. 279–292, 2009.
D. Karaboga, C. Ozturk, “A novel clustering approach: artificial bee colony (ABC) algorithm”, Applied Soft Computing, Vol. 11, pp. 652–657, 2011.
C. Ozturk, D. Karaboga, B. Gorkemli, “Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm”, Sensors, Vol. 11, pp. 6056–6065, 2011.
C. ¨ Ozt¨ urk, D. Karabo˘ ga, B. G¨ orkemli, “Artificial bee colony algorithm for dynamic deployment of wireless sensor networks”, Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 20, pp. 255–262, 2012.
D. Karaboga, S. Okdem, C. Ozturk, “Cluster based wireless sensor network routing using artificial bee colony algorithm”, Wireless Networks, Vol. 18, pp. 735–747, 2012.
D. Karaboga, C. Ozturk, N. Karaboga, B. Gorkemli, “Artificial bee colony programming for symbolic regression”, Information Sciences, Vol. 209, pp. 1–15, 2012.
A. Singh, “An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem”, Applied Soft Computing, Vol. 9, pp. 625–631, 2009.
N. Karabo˘ ga, M.B. C ¸ etinkaya, “A novel and efficient algorithm for adaptive filtering: artificial bee colony algorithm”, Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 19, pp. 175–190, 2011.
N. Ta¸spınar, D. Karabo˘ ga, M. Yıldırım, B. Akay, “PAPR reduction using artificial bee colony in OFDM systems”, Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 19, pp. 47–58, 2011.
D. Karaboga, B. Gorkemli, C. Ozturk, N. Karaboga, “A comprehensive survey: artificial bee colony (ABC) algorithm and applications”, Artificial Intelligence Review, DOI 10.1007/s10462-012-9328-0, 2012.
A.R. Guner, M. Sevkli, “A discrete particle swarm optimization algorithm for uncapacitated facility location problem”, Journal of Artificial Evolution and Applications, Vol. 2008, pp. 1–9, 2008.
J. Kennedy, R. Eberhart, “A discrete binary version of the particle swarm algorithm”, IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, Vol. 5, pp. 4101–4109, 19
X. Yuan, H. Nie, A. Su, L. Wang, Y. Yuan, “An improved binary particle swarm optimization for unit commitment problem”, Expert System with Applications, Vol. 39, pp. 8049–8055, 2009.
Y. Shi, R.C. Eberhart, “A modified particle swarm optimizer”, Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 69–73, 1998.
R.D. Galvˆ ao, L.A. Raggi, “A method for solving to optimality uncapacitated location problems”, Annals of Operations Research, Vol. 18, pp. 225–244, 1989.
J. Krarup, P.M. Pruzan, “The simple plant location problem: survey and synthesis”, European Journal of Operations Research, Vol. 12, pp. 36–81, 1983.
M.S. Daskin, L.V. Snyder, R.T. Berger, “Facility location in supply chain design”, Lehigh University, Working Paper No.: 03-010, available at http://www.lehigh.edu/ ∼lvs2/Papers/facil-loc-sc.pdf, 2003.
G. Cornu´ ejols, G.L. Nemhauser, L.A Wolsey, “The uncapacitated facility location problem”, Lecture Notes in Artificial Intelligence, Vol. 1865, pp. 119–171, 1990.
K. Holmberg, “Exact solution methods for uncapacitated location problems with convex transportation costs”, European Journal of Operational Research, Vol. 114, pp. 127–140, 1999.
J. Barcelo, ˚ A. Hellfjord, E. Fernandes, K. J¨ ornsten, “Lagrangian relaxation and constraint generation procedures for capacitated plant location problems with single sourcing”, OR Spectrum, Vol. 12, pp. 78–79, 1990.
D. Erlenkotter, “A dual-based procedure for uncapacitated facility location”, Operations Research, Vol. 26, pp. 992–1009, 1978.
J.H. Jaramillo, J. Bhadury, R. Batta, “On the use of genetic algorithms to solve location problems”, Computers & Operations Research, Vol. 29, pp. 761–779, 2002.
K.S. Al-Sultan, M.A. Al-Fawzan, “A tabu search approach to the uncapacitated facility location problem”, Annals of Operations Research, Vol. 86, pp. 91–103, 1999.
M. Sun, “Solving the uncapacitated facility location problem using tabu search”, Computers & Operations Research, Vol. 33, pp. 2563–2589, 2006.
M. Sevkli, A.R. Guner, “A continuous particle swarm optimization algorithm for uncapacitated facility location problem”, Proceedings of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, Brussels, Belgium, pp. 316–323, 2006.
J. Byrka, K. Aardal, “An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem”, SIAM Journal on Computing, Vol. 39 pp. 29–43, 2007.
J.E. Beasley, “OR-Library: distributing test problems by electronic mail”, Journal of the Operational Research Society, Vol. 41, pp. 1069–1072, 1990.
D. Karaboga, B. Akay, “A comparative study of artificial bee colony algorithm”, Applied Mathematics and Computation, Vol. 214, pp. 108–132, 2009.