International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 6, No. 8, 8 Aug. 2014
Cover page and Table of Contents: PDF (size: 1027KB)
An Improved Chaotic Bat Algorithm for Solving Integer Programming Problems
Full Text (PDF, 1027KB), PP.18-24
Views: 0 Downloads: 0
Author(s)
Osama Abdel-Raouf
1,*
Mohamed Abdel-Baset
2
Ibrahim El-henawy
3
Index Terms
Bat algorithm, meta-heuristics, optimization, chaos, integer programming
Abstract
Bat Algorithm is a recently-developed method in the field of computational intelligence. In this paper is presented an improved version of a Bat Meta-heuristic Algorithm, (IBACH), for solving integer programming problems. The proposed algorithm uses chaotic behaviour to generate a candidate solution in behaviors similar to acoustic monophony. Numerical results show that the IBACH is able to obtain the optimal results in comparison to traditional methods (branch and bound), particle swarm optimization algorithm (PSO), standard Bat algorithm and other harmony search algorithms. However, the benefits of this proposed algorithm is in its ability to obtain the optimal solution within less computation, which save time in comparison with the branch and bound algorithm (exact solution method).
Cite This Paper
Osama Abdel-Raouf, Mohamed Abdel-Baset, Ibrahim El-henawy, "An Improved Chaotic Bat Algorithm for Solving Integer Programming Problems", International Journal of Modern Education and Computer Science (IJMECS), vol.6, no.8, pp.18-24, 2014. DOI:10.5815/ijmecs.2014.08.03
Reference
[1]L. A. Wolsey, "Integer programming," IIE Transactions, vol. 32, pp. 2-58, 2000.
[2]G. B. Dantzig, Linear programming and extensions: Princeton university press, 1998.
[3]G. L. Nemhauser and L. A. Wolsey, Integer and combinatorial optimization vol. 18: Wiley New York, 1988.
[4]E. Beale, "Integer programming," in Computational Mathematical Programming, ed: Springer, 1985, pp. 1-24.
[5]C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity: Courier Dover Publications, 1998.
[6]H. Williams, "Logic and Integer Programming, International Series in Operations Research & Management Science," ed: Springer, 2009.
[7]A. Schrijver, Theory of linear and integer programming: Wiley. com, 1998.
[8]D. Bertsimas and R. Weismantel, Optimization over integers vol. 13: Dynamic Ideas Belmont, 2005.
[9]J. K. Karlof, Integer programming: theory and practice: CRC Press, 2005.
[10]M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, et al., 50 Years of Integer Programming 1958–2008: Springer, Berlin, 2010.
[11]D.-S. Chen, R. G. Batson, and Y. Dang, Applied integer programming: modeling and solution: Wiley. com, 2011.
[12]K. L. Hoffman and M. Padberg, "Solving airline crew scheduling problems by branch-and-cut," Management Science, vol. 39, pp. 657-682, 1993.
[13]J. D. Little, K. G. Murty, D. W. Sweeney, and C. Karel, "An algorithm for the traveling salesman problem," Operations research, vol. 11, pp. 972-989, 1963.
[14]M. Grotschel and L. Lovász, "Combinatorial optimization," Handbook of combinatorics, vol. 2, pp. 1541-1597, 1995.
[15]R. E. Gomory, "Outline of an algorithm for integer solutions to linear programs," Bulletin of the American Mathematical Society, vol. 64, pp. 275-278, 1958.
[16]R. E. Gomory, "An algorithm for integer solutions to linear programs," Recent advances in mathematical programming, vol. 64, pp. 260-302, 1963.
[17]R. E. Gomory, "Early integer programming," Operations Research, pp. 78-81, 2002.
[18]J. Tomlin, "Branch and bound methods for integer and non-convex programming," Integer and Nonlinear Programming, American Elsevier Publishing Company, New York, pp. 437-450, 1970.
[19]S. Rouillon, G. Desaulniers, and F. Soumis, "An extended branch-and-bound method for locomotive assignment," Transportation Research Part B: Methodological, vol. 40, pp. 404-423, 2006.
[20]M. Tuba, "Swarm intelligence algorithms parameter tuning," in Proceedings of the 6th WSEAS international conference on Computer Engineering and Applications, and Proceedings of the 2012 American conference on Applied Mathematics, 2012, pp. 389-394.
[21]R. Jovanovic and M. Tuba, "An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem," Applied Soft Computing, vol. 11, pp. 5360-5366, 2011.
[22]R. Jovanovic and M. Tuba, "Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem," Computer Science and Information Systems, vol. 10, pp. 133-149, 2013.
[23]B. Akay and D. Karaboga, "Solving integer programming problems by using artificial bee colony algorithm," in AI* IA 2009: Emergent Perspectives in Artificial Intelligence, ed: Springer, 2009, pp. 355-364.
[24]M. G. Omran, A. Engelbrecht, and A. Salman, "Barebones particle swarm for integer programming problems," in Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, 2007, pp. 170-175.
[25]G. Rudolph, "An evolutionary algorithm for integer programming," in Parallel Problem Solving from Nature—PPSN III, ed: Springer, 1994, pp. 139-148.
[26]M. G. Omran and A. P. Engelbrecht, "Differential evolution for integer programming problems," in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 2007, pp. 2237-2242.
[27]F. Glover, "Tabu search—part II," ORSA Journal on computing, vol. 2, pp. 4-32, 1990.
[28]X.-S. Yang, "A new metaheuristic bat-inspired algorithm," in Nature inspired cooperative strategies for optimization (NICSO 2010), ed: Springer, 2010, pp. 65-74.
[29]X.-S. Yang, "Bat algorithm for multi-objective optimisation," International Journal of Bio-Inspired Computation, vol. 3, pp. 267-274, 2011.
[30]X.-S. Yang and A. H. Gandomi, "Bat algorithm: a novel approach for global engineering optimization," Engineering Computations, vol. 29, pp. 464-483, 2012.
[31]A. H. Gandomi, X.-S. Yang, A. H. Alavi, and S. Talatahari, "Bat algorithm for constrained optimization tasks," Neural Computing and Applications, pp. 1-17, 2013.
[32]X.-S. Yang, Engineering optimization: an introduction with metaheuristic applications: Wiley. com, 2010.
[33]T. C. Bora, L. d. S. Coelho, and L. Lebensztajn, "Bat-Inspired optimization approach for the brushless DC wheel motor problem," Magnetics, IEEE Transactions on, vol. 48, pp. 947-950, 2012.
[34]L. M. Pecora and T. L. Carroll, "Synchronization in chaotic systems," Physical review letters, vol. 64, pp. 821-824, 1990.
[35]D. Yang, G. Li, and G. Cheng, "On the efficiency of chaos optimization algorithms for global optimization," Chaos, Solitons & Fractals, vol. 34, pp. 1366-1375, 2007.
[36]A. H. Gandomi, G. J. Yun, X.-S. Yang, and S. Talatahari, "Chaos-enhanced accelerated particle swarm optimization," Communications in Nonlinear Science and Numerical Simulation, 2012.
[37]O. Abdel-Raouf, I. El-henawy and M. Abdel-Baset "chaotic Harmony Search Algorithm with Different Chaotic Maps for Solving Assignment Problems "International Journal of Computational Engineering & Management, Vol. 17, pp. 10-15 ,2014.
[38]O. Abdel-Raouf, I. El-henawy and M. Abdel-Baset." A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles", IJMECS, vol.6, no.3, pp.38-44, 2014.
[39]O. Abdel-Raouf, I. El-henawy and M. Abdel-Baset. "Chaotic Firefly Algorithm for Solving Definite Integral", IJITCS, vol.6, no.6, pp.19-24, 2014.
[40]O. Abdel-Raouf, I. El-henawy and M. Abdel-Baset "Improved Harmony Search with Chaos for Solving Linear Assignment Problems", IJISA, vol.6, no.5, pp.55 61, 2014.
[41]J. Mingjun and T. Huanwen, "Application of chaos in simulated annealing," Chaos, Solitons & Fractals, vol. 21, pp. 933-941, 2004.
[42]L. d. S. Coelho and V. C. Mariani, "Use of chaotic sequences in a biologically inspired algorithm for engineering design optimization," Expert Systems with Applications, vol. 34, pp. 1905-1913, 2008.
[43]M. S. Tavazoei and M. Haeri, "Comparison of different one-dimensional maps as chaotic search pattern in chaos optimization algorithms," Applied Mathematics and Computation, vol. 187, pp. 1076-1085, 2007.
[44]R. Hilborn, "Chaos and nonlinear dynamics, 1994," ed: Oxford University Press, New York.
[45]D. He, C. He, L.-G. Jiang, H.-W. Zhu, and G.-R. Hu, "Chaotic characteristics of a one-dimensional iterative map with infinite collapses," Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on, vol. 48, pp. 900-906, 2001.
[46]A. Erramilli, R. Singh, and P. Pruthi, Modeling packet traffic with chaotic maps: Citeseer, 1994.
[47]R. M. May, "Simple mathematical models with very complicated dynamics," Nature, vol. 261, pp. 459-467, 1976.
[48]A. Wolf, "Quantifying chaos with Lyapunov exponents," Chaos, pp. 273-290, 1986.
[49]R. L. Devaney, "An introduction to chaotic dynamical systems," 2003.
[50]R. Barton, "Chaos and fractals," The Mathematics Teacher, vol. 83, pp. 524-529, 1990.
[51]E. Ott, Chaos in dynamical systems: Cambridge university press, 2002.
[52]C. Letellier, Chaos in nature vol. 81: World Scientific Publishing Company, 2013.
[53]Geem, Z.W., Kim, J.H., Loganathan, G.V.: A new heuristic optimization algorithm: Harmony search. Simulation vol. 76, pp. 60–68, 2001.
[54]M. Mahdavi, M. Fesanghary, E. Damangir, An improved harmony search 995 algorithm for solving optimization problems, Applied Mathematics and Computation 188 (2) ,pp. 1567–1579,2007.
[55]M. Mahdavi "Global-best harmony search", Applied Math. Computation vol.198, pp. 643–656, 2008.