A bee colony optimization-based approach for binary optimization

Year 2013, Volume: 1 Issue: 4, 47 - 51, 03.10.2013

Mustafa Servet Kıran , Mesut Gündüz

Abstract

The bee colony optimization (BCO) algorithm, one of the swarm intelligence algorithms, is a population based iterative search algorithm. Being inspired by collective bee intelligence, BCO has been proposed for solving discrete optimization problems such as travelling salesman problem. The BCO uses constructive approach for creating a feasible solution for the discrete optimization problems but in this study, we used the solution improvement technique due to nature of the uncapacitated facility location problem (UFLP). In the proposed method named as binBCO, the feasible solutions are generated for the artificial bees in hive of BCO and these solutions are tried to improve by utilizing interaction in the hive. At the end of the each iteration, some of the bees leave self-solutions and the leaving process depends on the loyalty of the bee to the self-solution. After a bee leaves self-solution, a random feasible solution is generated and assigned to this bee. In order to show the performance of binBCO, we examined it on well-known UFLPs, and the experimental studies show that the proposed method produces promising results.

Keywords

Bee colony optimization; binary optimization; uncapacitated facility location problem

References

• Beasley JE. (1990). OR-Library: Distributing Test Problems by Electronic Mail. The Journal of the Operational Research Society 41:1069-1072.
• Davidovic T., Ramljak D., Selmic M., Teodorovic D (2011). Bee colony optimization for the p-center problem. Computers and Operations Research 38:1367-1376.
• Davidovic T., Selmic M., Teodorovic D (2009). Scheduling Independent Tasks: Bee Colony Optimization Approach. In Proc. of the 17th Mediterranean Conference on Control&Automation, Thessaloniki, Greece, 1020-1025.
• Dorigo M., Gambardella L. M (1997). Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1:53–66.
• Dorigo M., Maniezzo V., Colorni A (1996). Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics -Part B 26: 29–41.
• Eberhart RC., Kennedy J (1995). A new optimizer using particle swarm theory. In Proc. of Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 39-43.
• Erlenkotter D (1978). A dual-based procedure for uncapacitated facility location. Operations Research 26: 992–1009.
• Galvao RD., Raggi LA (1989). A method for solving to optimality uncapacitated location problems. Annals of Operations Research 18: 225-244.
• Ghosh D (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research 150: 150-162.
• Guner AR., Sevkli M (2008), A discrete particle swarm optimization algorithm for uncapacitated facility location problem. Journal of Artificial Evolution and Applications 2008: 1-9.
• Karaboga D (2005). An idea based on honey bee swarm for numerical optimization, Erciyes University, Technical Report-TR06, Kayseri/Turkey.
• Kıran MS (2010). Bee Colony-based Driver-Line-Time Optimization. Master Thesis (In Turkish).
• Körkel M (1989). On the exact solution of large-scale simple plant location problems. European Journal of Operational Research 39: 157–73.
• Lucic P., Teodorovic D (2001). Bee System: modeling combinatorial optimization transportation engineering problems by swarm intelligence. In Preprints of the TRISTAN IV Triennial Symposium on Transportation Analysis, Sao Miguel, Azores Islands, Portugal, 441-445.
• Lucic P., Teodorovic D (2003a). Computing with bees: attacking complex transportation engineering problems. International Journal of Artificial Intelligence Tools 12: 375-394.
• Lucic P., Teodorovic D (2002). Transportation Modeling: an artificial life approach. In Proc. of the 14th IEEE International Conference on Tools with Artificial Intelligence, Washington, 216-223.
• Lucic P., Teodorovic D (2003b). Vehicle routing problem with uncertain demand at nodes: the bee system and fuzzy logic approach. Ed.: Verdegay J.L., Fuzzy Sets in Optimization, Springer-Verlag, Heidelberg, Berlin, 67-82.
• Markovic GZ., Teodorovic DB., Raspopovic VSA (2007). Routing and wavelength assignment in all-optical networks based on the bee colony optimization. AI Communications 20: 273-285.
• Resende MGC., Werneck RF (2003). A hybrid multistart heuristic for the uncapacitated facility location problem. European Journal of Operational Research 174: 54-68.
• Sevkli M., Guner AR (2006)., A continuous particle swarm optimization algorithm for uncapacitated facility location problem. In Proc. of the Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence - ANTS 2006, Brussels, Belgium, 316-323.
• Sun M (2006). Solving the uncapacitated facility location problem using tabu search. Computers & Operations Research 33: 2563-2589.
• Tcha D-W., Myung Y-S., Chung K-H (1995). Parametric uncapacitated facility location. European Journal of Operational Research 86: 469-479.
• Tedorovic D (2008). Swarm intelligence systems for transportation engineering: Principles and applications. Transportation Research Part C: Emerging Technogies 16: 651-667
• Teodorovic D (2009). Bee colony optimization (BCO). Eds: Lim C.P., Jain L.C., Dehuri S., Innovations in swarm intelligence, Berlin, Heidelberg, Springer-Verlag, 39-60.
• Teodorovic D., Dell’Orco M (2005). Bee colony optimization-a cooperative learning approach to complex transportation problems. In Proc. of the 10th Meeting Euro Working Group on Transportation, Poznan, Poland, 51-60.
• Teodorovic D., Dell’Orco M (2008). Mitigating traffic congestion: solving the ride matching problem by bee colony optimization. Transportation Planning and Technology 31: 135-152.
• Teodorovic D., Lucic P., Markovic G., Dell’Orco M (2006). Bee colony optimization: Principles and Applications. Eds.: Reljin B., Stankovic S., In Proc. of the 8th Seminar on Neural Network Applications in Electrical Engineering – NEUREL 2006, Belgrade, 151-156.
• Topçuoğlu H., Corut F., Ermiş M., Yılmaz G (2005). Solving the uncapacitated hub location problem using genetic algorithms. Computers & Operations Research 32: 967-984.
• Yiğit V., Aydın ME., Türkbey O (2006). Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing. International Journal of Production Research 44: 4773-4791.