zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Bees algorithm for generalized assignment problem. (English) Zbl 1181.90167
Summary: Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.
MSC:
90B80Discrete location and assignment
90C59Approximation methods and heuristics
90C10Integer programming
References:
[1]D.T. Pham, E. Koç, A. Ghanbarzadeh, S. Otri, S. Rahim, M. Zaidi, The bees algorithm – a novel tool for complex optimisation problems, in: Proceedings of the Second International Virtual Conference on Intelligent Production Machines and Systems, 2006a, pp. 454 – 461.
[2]Martello, S.; Toth, P.: An algorithm for the generalized assignment problems, Operational research, 589-603 (1981) · Zbl 0473.90047
[3]Martello, S.; Toth, P.: Knapsack problems: algorithms and computer implementations, (1990) · Zbl 0708.68002
[4]D. Cattrysse, Set partitioning approaches to combinatorial optimization problems, Ph.D. Dissertation, Katholieke Universiteit Leuven, Centrum Industrieel Beleid, Belgium, 1990.
[5]Cattrysse, D.; Salomon, M.; Van Wassenhove, L. N.: A set partitioning heuristic for the generalized assignment problem, European journal of operational research 72, 167-174 (1994) · Zbl 0798.90107 · doi:10.1016/0377-2217(94)90338-7
[6]Ross, G. T.; Soland, P. M.: A branch and bound based algorithm for the generalized assignment problem, Mathematical programming 8, 91-103 (1975) · Zbl 0308.90028 · doi:10.1007/BF01580430
[7]Fisher, M. L.; Jaikumar, R.; Van Wassenhove, L. N.: A multiplier adjustment method for the generalized assignment problem, Management science 32, 1095-1103 (1986) · Zbl 0626.90036 · doi:10.1287/mnsc.32.9.1095
[8]Savelsbergh, M.: A branch-and-price algorithm for the generalized assignment problem, Operations research 45, 831-841 (1997) · Zbl 0895.90161 · doi:10.1287/opre.45.6.831
[9]Nauss, R. M.: Solving the generalized assignment problem: an optimizing and heuristic approach, Informs journal of computing 15, 249-266 (2003)
[10]Osman, I. H.: Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches, OR spektrum 17, 211-225 (1995) · Zbl 0841.90098 · doi:10.1007/BF01720977
[11]Chu, P. C.; Beasley, J. E.: A genetic algorithm for the generalized assignment problem, Computers and operations research 24, 17-23 (1997) · Zbl 0881.90070 · doi:10.1016/S0305-0548(96)00032-9
[12]Racer, M.; Amini, M. M.: A robust heuristic for the generalized assignment problem, Annals of operations research 50, 487-503 (1994) · Zbl 0812.90097 · doi:10.1007/BF02085655
[13]Yagiura, M.; Yamaguchi, T.; Ibaraki, T.: A variable-depth search algorithm with branching search for the generalized assignment problem, Optimization methods and software 10, 419-441 (1998) · Zbl 0947.90070 · doi:10.1080/10556789808805722
[14]Yagiura, M.; Yamaguchi, T.; Ibaraki, T.: A variable-depth search algorithm for the generalized assignment problem, Meta-heuristics: advances and trends in local search paradigms for optimization, 459-471 (1999) · Zbl 0985.90079
[15]Laguna, M.; Kelly, J. P.; Gonzalez-Velarde, J. L.; Glover, F.: Tabu search for the multilevel generalized assignment problem, European journal of operational research 82, 176-189 (1995) · Zbl 0905.90122 · doi:10.1016/0377-2217(93)E0174-V
[16]Diaz, J. A.; Fernandez, E.: A tabu search heuristic for the generalized assignment problem, European journal operational research 132, 22-38 (2001) · Zbl 0980.90045 · doi:10.1016/S0377-2217(00)00108-9
[17]Yagiura, M.; Ibaraki, T.; Glover, F.: An ejection chain approach for the generalized assignment problem, Informs journal of computing 16, 131-151 (2004)
[18]Lourenço, H. R.; Serra, D.: Adaptive search heuristics for the generalized assignment problem, Mathware and soft computing 9, 209-234 (2002) · Zbl 1031.68056
[19]L. Alfandari, A. Plateau, P. Tolla, A two-phase path relinking algorithm for the generalized assignment problem, in: Proceedings of the Fourth Metaheuristic International Conference, Porto, Portugal, July 16 – 20, 2001, pp. 175 – 179.
[20]L. Alfandari, A. Plateau, P. Tolla, A two-phase path relinking algorithm for the generalized assignment problem, Technical Report No.: 378, CEDRIC, CNAM, 2002.
[21]Alfandari, L.; Plateau, A.; Tolla, P.: A path relinking algorithm for the generalized assignment problem, Metaheuristics: computer decision-making, 1-17 (2004)
[22]M. Yagiura, T. Ibaraki, F. Glover, An effective metaheuristic algorithm for the generalized assignment problem, in: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Tucson, Arizona, USA, 2001.
[23]M. Yagiura, T. Ibaraki, F. Glover, A path relinking approach for the generalized assignment problem, in: Proceedings of International Symposium on Scheduling, Hamamatsu, Japan, 2002, pp. 105 – 108.
[24]Yagiura, M.; Ibaraki, T.; Glover, F.: A path relinking approach with ejection chains for the generalized assignment problem, European journal of operational research 169, 548-569 (2006) · Zbl 1079.90119 · doi:10.1016/j.ejor.2004.08.015
[25]M. Randall, Heuristics for ant colony optimisation using the generalised assignment problem, in: Proceedings of IEEE Congress on Evolutionary Computation, Portland, Oregon, USA, 2004, pp. 1916 – 1923.
[26]H. Feltl, G.R. Raidl, An improved hybrid genetic algorithm for the generalized assignment problem, in: Proceedings of the 2004 ACM Symposium on Applied Computing, Nicosia, Cyprus, 2004, pp. 990 – 995.
[27]A. Baykasogbreve;lu, L. Özbakır, P. Tapkan, Artificial bee colony algorithm and its application to generalized assignment problem, in: F.T.S. Chan, M.K. Tiwari (Eds.), Swarm Intelligence: Focus on Ant and Particle Swarm Optimization, I-Tech Education and Publishing, Vienna, Austria, 2007, pp. 113 – 144.
[28]Seeley, T. D.: The wisdom of the hive, (1995)
[29]P. Lucic, D. Teodorovic, Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence, in: Proceedings of Triennial Symposium on Transportation Analysis, Sao Miguel, Azores Islands, 2001, pp. 441 – 445.
[30]P. Lucic, D. Teodorovic, Transportation modeling: an artificial life approach, in: Proceedings of the 14th International Conference on Tools with Artificial Intelligence, 4 – 6 November 2002, Washington, DC, USA, 2002, pp. 216 – 223.
[31]Lucic, P.; Teodorovic, D.: Computing with bees: attacking complex transportation engineering problems, International journal on artificial intelligence tools 12, No. 3, 375-394 (2003)
[32]P. Lucic, Modeling transportation problems using concepts of swarm intelligence and soft computing, Ph.D. Dissertation, Civil Engineering, Faculty of the Virginia Polytechnic Institute and State University, 2002.
[33]Lucic, P.; Teodorovic, D.: Vehicle routing problem with uncertain demand at nodes: the bee system and fuzzy logic approach, Fuzzy sets in optimization, 67-82 (2003) · Zbl 1051.90009
[34]D. Teodorovic, M. Dell’Orco, Bee colony optimization – a cooperative learning approach to complex transportation problems, in: Proceedings of the 10th EWGT Meeting, Poznan, 13 – 16 September 2005, pp. 51 – 60.
[35]Markovic, G. Z.; Teodorovic, D.; Acimovic-Raspopovic, V. S.: Routing and wavelength assignment in all-optical networks based on the bee colony optimization, AI communications 20, No. 4, 273-285 (2007) · Zbl 1185.90174
[36]S. Nakrani, C. Tovey, On honey bees and dynamic allocation in an internet server Colony, in: Proceedings of Second International Workshop Mathematics and Algorithms of Social Insects, Atlanta, Georgia, USA , 2003.
[37]Wedde, H. F.; Farooq, M.; Zhang, Y.: Beehive: an efficient fault-tolerant routing algorithm inspired by honey bee behavior, Lecture notes in computer science 3172, 83-94 (2004)
[38]G.M. Bianco, Getting inspired from bees to perform large scale visual precise navigation, in: Proceedings of International Conference on Intelligent Robots and Systems (IEEE/RSJ’2004), Sendai, Japan, 2004, pp. 619 – 624.
[39]C.S. Chong, M.Y.H. Low, A.I. Sivakumar, K.Y. Gay, A bee colony optimization algorithm to job shop scheduling, in; Proceedings of the 37th Conference on Winter Simulation, Monterey, California, 2006, pp. 1954 – 1961.
[40]Drias, H.; Sadeg, S.; Yahi, S.: Cooperative bees swarm for solving the maximum weighted satisfiability problem, Lecture notes in computer science 3512, 318-325 (2005)
[41]N. Quijano, K.M. Passino, Honey bee social foraging algorithms for resource allocation theory and application, Submitted for publication, available on lt;http://wwwprof.uniandes.edu.co/ nquijano/Publications.htmlgt;.
[42]B. Baştürk, D. Karabogbreve;a, An artificial bee colony (ABC) algorithm for numeric function optimization, in: IEEE Swarm Intelligence Symposium, Indianapolis, Indiana, USA, May 12 – 14, 2006.
[43]Karabo&gbreve, D.; A; Baştürk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of global optimization 39, 459-471 (2007)
[44]Yang, X. S.: Engineering optimizations via nature-inspired virtual bee algorithms, Lecture notes in computer science 3562, 317-323 (2005)
[45]D.T. Pham, S. Otri, A. Ghanbarzadeh, E. Koç, Application of the bees algorithm to the training of learning vector quantisation networks for control chart pattern recognition, in: Proceedings of International Conference on Information and Communication Technologies, 24 – 28 April 2006, Umayyad Palace, Damascus, Syria, 2006, pp. 1624 – 1629.
[46]D.T. Pham, E. Koç, A. Ghanbarzadeh, S. Otri, Optimisation of the weights of multi-layered perceptrons using the bees algorithm, in: Proceedings of the Fifth International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, 2006, pp. 38 – 46.
[47]D.T. Pham, A.J. Soroka, A. Ghanbarzadeh, E. Koç, S. Otri, M. Packianather, Optimising neural networks for identification of wood defects using the bees algorithm, in: Proceedings of IEEE International Conference on Industrial Informatics, August 16 – 18, 2006, Singapore, 2006, pp. 1346 – 1351.
[48]D.T. Pham, A. Ghanbarzadeh, E. Koç, S. Otri, Application of the bees algorithm to the training of radial basis function networks for control chart pattern recognition, in: Proceedings of the Fifth CIRP International Seminar on Intelligent Computation in Manufacturing Engineering, Ischia, Italy, 2006, pp. 711 – 716.
[49]D.T. Pham, Z. Muhamad, M. Mahmuddin, A. Ghanbarzadeh, E. Koç, S. Otri, Using the bees algorithm to optimise a support vector machine for wood defect classification, in: Proceedings of Innovative Production Machines and Systems Virtual Conference, Cardiff, UK, 2007.
[50]D.T. Pham, A. Afify, E. Koç, Manufacturing cell formation using the bees algorithm, in: Proceedings of Innovative Production Machines and Systems Virtual Conference, Cardiff, UK, 2007.
[51]D.T. Pham, E. Koç, J.Y. Lee, J. Phrueksanant, Using the bees algorithm to schedule jobs for a machine, in: Proceedings of the Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, Euspen, UK, 2007, pp. 430 – 439.
[52]D.T. Pham, M. Castellani, A. Ghanbarzadeh, Preliminary design using the bees algorithm, in: Proceedings of the Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, Euspen, UK, 2007, pp. 420 – 429.
[53]D.T. Pham, S. Otri, A. Afify, M. Mahmuddin, H. Al-Jabbouli, Data clustering using the bees algorithm, in; Proceedings of the 40th CIRP International Manufacturing Systems Seminar, Liverpool, UK, 2007.
[54]D.T. Pham, A.J. Soroka, E. Koç, A. Ghanbarzadeh, S. Otri, Some applications of the bees algorithm in engineering design and manufacture, in: Proceedings of International Conference on Manufacturing Automation, 28 – 30 May 2007, Singapore, 2007.
[55]D.T. Pham, A. Ghanbarzadeh, Multi-objective optimisation using the bees algorithm, in: Proceedings of Innovative Production Machines and Systems Virtual Conference, Cardiff, UK, 2007.
[56]D.T. Pham, A.H. Darwish, E.E. Eldukhri, S. Otri, Using the bees algorithm to tune a fuzzy logic controller for a robot gymnast, in: Proceedings of International Conference on Manufacturing Automation, 28 – 30 May 2007, Singapore, 2007.
[57]L.A.N. Lorena, M.G. Narciso, J.E. Beasley, A constructive genetic algorithm for the generalized assignment problem, Evolutionary Optimization, Submitted for publication, Available from: lt;http://www.lac.inpe.br/ lorena/public.htmlgt;.