A Taxonomy of Hybrid Metaheuristics | Journal of Heuristics
Skip to main content
Springer Nature Link
Log in

A Taxonomy of Hybrid Metaheuristics

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this paper, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms.

As an illustration of the usefulness of the taxonomy an annoted bibliography is given which classifies a large number of hybrid approaches according to the taxonomy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aarts, E.H.L., F.M.I. De Bont, J.H.A. Habers, and P.J.M. Van Laarhoven. (1986). “Parallel Implementations of the Statistical Cooling Algorithms.” Integration 4, 209–238.

    Google Scholar 

  • Abbattista, F., N. Abbattista, and L. Caponetti. (1995). “An Evolutionary and Cooperative Agent Model for Optimization.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 668–671.

  • Abramson, D., P. Logothetis, A. Postula, and M. Randall. (1997). “Application Specific Computers for Combinatorial Optimisation.” In The Australien Computer Architecture Workshop, Sydney, Australia.

  • Abramson, D.A. (1992). “A Very High Speed Architecture to Support Simulated Annealing.” IEEE Computer 25, 27–34.

    Google Scholar 

  • Ackley, D.H. (1987). A Connectionist Machine for Genetic Hillclimbing. Boston, USA: Kluwer Academic Pub.

    Google Scholar 

  • Adamidis, P. and V. Petridis. (1996). “Co-Operating Populations with Different Evolution Behaviours.” In IEEE Int. Conf. on Evolutionary Computation, ICEC'96, Nagoya, Japan, pp. 188–191.

  • Andreatta, A.A. and C.C. Ribeiro. (1994). “A Graph Partitioning Heuristic for the Parallel Pseudo-Exhaustive Logical Test of VLSI Combinatorial Circuits.” Operations Research 50, 1–36.

    Google Scholar 

  • Areibi, S. and A. Vannelli. (1994). “Advanced Search Techniques for Circuit Partitioning.” DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 77–97.

  • Asveren, T. and P. Molitor. (1996). “New Crossover Methods for Sequencing Problems.” In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schewefel (eds.), Parallel Problem Solving from Nature PPSN4, Vol. 1141 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 290–299.

    Google Scholar 

  • Bachelet, V., Z. Hafidi, P. Preux, and E.-G. Talbi. (1998). “Diversifying Tabu Search by Genetic Algorithms.” In INFORMS'98 on Operations Research and Management Sciences Meeting, Montréal, Canada.

  • Bachelet, V., P. Preux, and E.-G. Talbi. (1996). “Parallel Hybrid Meta-heuristics: Application to the Quadratic Assignment Problem.” In Parallel Optimization Colloquium POC96, Versailles, France, pp. 233–242.

  • Badeau, P., M. Gendreau, F. Guertin, J.-Y. Potvin, and E. Taillard. (1995). “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows.” RR CRT-95-84, Centre de Recherche sur les Transports, Universitè de Montréal, Canada.

    Google Scholar 

  • Badeau, P., F. Guertin, M. Gendreau, J.-Y. Potvin, and E.D. Taillard. (1997). “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows.” Transportation Research 5(2), 109–122.

    Google Scholar 

  • Banerjee, P. and M. Jones. (1986). “A Parallel Simulated Annealing Algorithm for Standard Cell Placement on a Hypercube Computer.” In IEEE Int. Conf. on Computer-Aided Design, Santa Clara, California, USA, pp. 34–37.

    Google Scholar 

  • Becker, S. and Y. Le Cun. (1988). “Improving the Convergence of Back-Propagation Learning with Second-Order Methods.” In D. Touretzky, G. Hinton, and T. Sejnowski (eds.), Connectionist Models Summer School, Pittsburgh, USA, Morgan Kaufmann.

    Google Scholar 

  • Belding, T. (1995). “The Distributed Genetic Algorithm Revisted.” In D. Eshelmann (ed.), Sixth Int. Conf. on Genetic Algorithms. San Mateo, CA, Morgan Kaufmann.

    Google Scholar 

  • Belew, R.K., J. McInerny, and N.N. Schraudolph. (1991). “Evolving Networks: Using Genetic Algorithms with Connectionist Learning.” In C.G. Langton, C. Taylor, J.D. Doyne Farmer, and S. Rasmussen (eds.), Second Conf. on Artificial Life, Addison-Wesley, USA, pp. 511–548.

    Google Scholar 

  • Bianchini, R. and C. Brown. (1992). “Parallel Genetic Algorithms on Distributed-Memory Architecturers,” Technical Report 436, University of Rochester, Rochester, NY, USA.

    Google Scholar 

  • Boese, K.D., A.B. Kahng, and S. Muddu. (1994). “NewAdaptive Multi-Start Techniques for Combinatorial Global Optimizations.” Operation Research Letters 16(2), 101–113.

    Google Scholar 

  • Bohnenberger, O., J. Hesser, and R. Manner. (1995). “Automatic Design of Truss Structures Using Evolutionary Algorithms” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 143–147.

  • Braun, H. (1990). “On Solving Traveling Salesman Problems by Genetic Algorithms.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature, Vol 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 129–133.

    Google Scholar 

  • Brown, D.E., C.L. Huntley, and A.R. Spillane. (1989). “A Parallel Genetic Heuristic for the Quadratic Assignment Problem.” In Third Int. Conf. on Genetic Algorithms ICGA'89, San Mateo, California, USA: Morgan Kauffmann, pp. 406–415.

    Google Scholar 

  • Bruns, R. (1995). “Integration of Constraint Solving Techniques in Genetic Algorithms.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 33–38.

  • Bui, T.N. and B.R. Moon. (1994). “A Genetic Algorithm for a Special Class of the Quadratic Assignment Problem.” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Special Issue on Quadratic Assignment and Related Problems 16, 99–116.

  • Calégari, P., G. Coray, A. Hertz, D. Kobler, and P. Kuonen. (1999). “A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization.” Journal of Heuristics 5(2), 145–158.

    Google Scholar 

  • Casotto, A., F. Romeo, and A.L. Sangiovanni-Vincentelli. (1986). “A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells.” In IEEE Int. Conf. on Computer-Aided Design, Santa Clara, California, USA, pp. 30–33.

  • Chak, C.K. and G. Feng. (1995). “Accelerated Genetic Algorithms: Combined with Local Search Techniques for Fast and Accurate Global Search.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 378–383.

  • Chakrapani, J. and J. Skorin-Kapov. (1993). “Massively Parallel Tabu Search for the Quadratic Assignment Problem.” Annals of Operations Research 41, 327–341.

    Google Scholar 

  • Charon, I. and O. Hudry. (1993). “The Noising Method: A New Method for Combinatorial Optimization.” Operations Research Letters 14, 133–137.

    Google Scholar 

  • Chen, H. and N.S. Flann. (1994). “Parallel Simulated Annealing and Genetic Algorithms: A Space of Hybrid Methods.” In Y. Davidor, H.-P. Schwefel, and R. Manner (eds.), Third Conf. on Parallel Problem Solving from Nature. Jerusalem, Israel, Berlin: Springer-Verlag, pp. 428–436.

    Google Scholar 

  • Chu, P.C. (1997). “A Genetic Algorithm Approach for Combinatorial Optimization Problems.” PhD Thesis, University of London, London, UK.

    Google Scholar 

  • Chvatal, V. (1979). “A Greedy Heuristic for the Set Covering Problem.” Mathematics of Operations Research 4(3), 233–235.

    Google Scholar 

  • Cohoon, J., S. Hedge, W. Martin, and D. Richards. (1987). “Punctuated Equilibria: A Parallel Genetic Algorithm” In J.J. Grefenstette (ed.), Second Int. Conf. on Genetic Algorithms. Cambridge, MA, USA: MIT, pp. 148–154.

    Google Scholar 

  • Cohoon, J., S. Hedge, W. Martin, and D. Richards. (1991). “Distributed Genetic Algorithms for the Floorplan Design Problem.” IEEE Trans. on Computer-Aided Design 10(4), 483–492.

    Google Scholar 

  • Cohoon, J.P., W.N. Martin, and D.S. Richards. (1990). “Genetic Algorithms and Punctuated Equilibria.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 134–141.

    Google Scholar 

  • Cohoon, J.P., W.N. Martin, and D.S. Richards. (1991). “A Multi-Population Genetic Algorithm for Solving the k-Partition Problem on Hypercubes.” In R.K. Belew and L.B. Booker (eds.), Fourth Int. Conf. on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, pp. 244–248.

    Google Scholar 

  • Colorni, A., M. Dorigo, and V. Maniezzo. (1991). “Distributed Optimization by Ant Colonies.” In European Conf. on Artificial Life. Elsevier Publishing, pp. 134–142.

  • Crainic, T.D., M. Toulouse, and M. Gendreau. (1993). “Towards a Taxonomy of Parallel Tabu Search Algoithms.” Technical Report CRT-933, Centre de Recherche sur les Transports, Université deMontréal, Montréal, Canada.

    Google Scholar 

  • Crainic, T.G., and M. Gendreau. (1997). “A Cooperative Parallel Tabu Search for Capacitated Network Design,” Technical Report CRT-97-27, Centre de recherche sur les transports, Université de Montréal, Montréal, Canada.

    Google Scholar 

  • Crainic, T.G., A.T. Nguyen, and M. Gendreau. (1997). “Cooperative Multi-Thread Parallel Tabu Search with Evolutionary Adaptive Memory.” In 2nd Int. Conf. on Metaheuristics, Sophia Antipolis, France.

  • Crainic, T.G., M. Toulouse, and M. Gendreau. (1995). “Synchronous Tabu Search Parallelization Strategies for Multi-Commodity Location-Allocation with Balancing Requirements.” OR Spektrum, 17, 113–123.

    Google Scholar 

  • Cung, V-D., T. Mautor, P. Michelon, and A. Tavares. (1997). “A Scatter Search Based Approach for the Quadratic Assignment Problem.” In IEEE Int. Conf. on Evolutionary Computation ICEC'97, Indianapolis, USA.

  • Cung, V.-D., T. Mautor, P. Michelon, and A. Tavares. (1999). “Recherche Dispersée Parallèle.” In Deuxième Congrés de la Socièté Francaise de Recherche Opératinnelle et d'Aide à la décision ROADEF'99, Autrans, France.

  • Davis, L. (1985). “Job-Shop Scheduling with Genetic Algorithms.” In J.J. Grefenstette (ed.), Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, pp. 136–140.

  • Dozier, G., J. Bowen, and D. Bahler. (1995). “Solving Randomly Generated Constraint Satisfaction Problems Using a Micro-Evolutionary Hybrid that Evolves a Population of Hill-Climbers.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 614–619.

  • Duvivier, D., P. Preux, and E.G. Talbi. (1996). “Climbing up NP-Hard Hills.” In The Fourth Int. Conf. on Parallel Problem Solving From Nature. Berlin, Germany: Springer-Verlag, LNCS No. 1141, pp. 574–583.

    Google Scholar 

  • East, I.R. and J. Rowe. (1996). “Effects of Isolation in a Distributed Population Genetic Algorithm.” In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schewefel (eds.), Parallel Problem Solving from Nature PPSN4. Vol. 1141 of LNCS, Dortmund, Germany: Springer-Verlag, pp. 408–419.

    Google Scholar 

  • Fahlman, S.E. (1988). “Faster-Learning Variations on Back-Propagation: An Empirical Study.” In D. Touretzky, G. Hinton, and T. Sejnowsk (eds.), Connectionist Models Summer School, Pittsburgh, PA, USA, San Mateo, CA: Morgan Kaufmann, pp. 38–51.

    Google Scholar 

  • De Falco, I., R. Del Balio, and E. Tarantino. (1994). “Solving the Mapping Problem by Parallel Tabu Search.” In IASTED Conf., Paris, France.

  • De Falco, I., R. Del Balio, and E. Tarantino. (1995). “An Analysis of Parallel Heuristics for Task Allocation in Multicomputers.” Computing 3, 59.

    Google Scholar 

  • De Falco, I., R. Del Balio, E. Tarantino, and R. Vaccaro. (1994). “Improving Search by Incorporating Evolution Principles in Parallel Tabu Search.” In Int. Conf. on Machine Learning, pp. 823–828.

  • Feo, T.A. and M.G.C. Resende. (1995). “Greedy Randomized Adaptive Search Procedures.” Journal of Global Optimization 6, 109–133.

    Google Scholar 

  • Feo, T.A., M.G.C. Resende, and S.H. Smith. (1994). “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, 860–878.

    Google Scholar 

  • Feo, T.A., K. Venkatraman, and J.F. Bard. (1991). “A GRASP for a Difficult Single Machine Scheduling Problem.” Computers and Operations Research 18, 635–643.

    Google Scholar 

  • Fiechter, C.-N. (1994). “A parallel Tabu Search Algorithm for Large Travelling Salesman Problems.” Discrete Applied Mathematics.

  • Fleurent, C. and J.A. Ferland. (1994a). “Genetic Hybrids for the Quardratic Assignment Problem.” DI-MACS Series in Discrete Mathematics and Theoretical Computer Science 16, 173–188.

  • Fleurent, C. and J.A. Ferland. (1994b). “Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique, and Satisfiability.” DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, 619–652.

    Google Scholar 

  • Fleurant, C. and J.A. Ferland. (1996). “Genetic and Hybrid Algorithms for Graph Coloring.” Annals of Operations Research 63.

  • Foo, S.-M. (1991). “An Approach of Combining Simulated Annealing and Genetic Algorithm.” Master's Thesis, University of Illinois, Urbana-Champaign.

    Google Scholar 

  • Fourman, M.P. (1985). “Compaction of Symbolic Layout Using Genetic Algorithms.” In J.J. Grefenstette (ed.), Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, pp. 141–153.

  • Freisleben, B. and P. Merz. (1996). “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems.” In IEEE Int. Conf. on Evolutionary Computation, ICEC'96, Nagoya, Japan, pp. 616–621.

  • Glover, F. (1977). “Heuristics for Integer Programming using Surrogate Constraints.” Decision Sciences 8, 156–166.

    Google Scholar 

  • Glover, F. (1989). “Tabu Search-Part I.” ORSA Journal of Computing 1(3), 190–206.

    Google Scholar 

  • Gorges-Schleuter, M. (1989). “Asparagos, an Asynchronous Parallel Genetic Optimization Strategy.” In 3rd Int. Conf. Genetic Algorithms. Morgan Kaufmann, USA. pp. 422–427.

    Google Scholar 

  • Grefenstette, J.J., (1987). “Incorporating Problem Specific Knowledge into Genetic Algorithms.” In L. Davis (ed.), Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence, San Mateo, CA, USA: Morgan Kaufmann, pp. 42–60.

    Google Scholar 

  • Hancock, P.J.B. and L.S. Smith. (1990). “Gannet: Genetic Design of a Neural Net for Face Recognition.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 292–296.

    Google Scholar 

  • Hart, W.E. (1994). “Adaptive Global Optimization with Local Search.” PhD Thesis, University of California, San Diego.

    Google Scholar 

  • Heijligers, M.J.M. and J.A.G. Jess. (1995). “High-Level Synthesis Scheduling and Allocation Using Genetic Algorithms Based on Conctructive Topological Scheduling Techniques.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 56–61.

  • Hentenryck, V.P. (1989). Constraint Satisfaction in Logic Programming. MIT Press.

  • Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: Michigan Press University.

    Google Scholar 

  • Huntley, C.L. and D.E. Brown. (1991a). “Parallel Genetic Algorithms with Local Search.” Technical Report IPC-TR-90-006, University of Virginia, Charlottesvile, VA, USA.

    Google Scholar 

  • Huntley, C.L. and D.E. Brown. (1991b). “A Parallel Heuristic for Quadratic Assignment Problems.” Computers and Operations Research 18, 275–289.

    Google Scholar 

  • Husbands, P., F. Mill, and S. Warrington. (1990). “Genetic Algorithms, Production Plan Optimisation and Scheduling.” In H.-P. Schewefel and R. Manner (eds.), Parallel Problem Solving From Nature, Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 80–84.

    Google Scholar 

  • Iba, H. (1996). “Emergent Cooperation for Multiple Agents Using Genetic Programming.” In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schewefel (eds.), Parallel Problem Solving from Nature PPSN4, Vol. 1141 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 32–41.

    Google Scholar 

  • Ishibuchi, H. and T. Murata. (1996). “Multi-Objective Genetic Local Search Algorithm.” In IEEE Int. Conf. on Evolutionary Computation, ICEC'96, Nagoya, Japan, pp. 119–124.

  • Jog, P., J.Y. Suh, and D. Van Gucht. (1989). “The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Traveling Salesman Problem.” In 3rd Int. Conf. Genetic Algorithms, Morgan Kaufmann, USA.

    Google Scholar 

  • Kim, H., Y. Hayashi, and K. Nara. (1995). “The Performance of Hybridized Algorithm of Genetic Algorithm Simulated Annealing and Tabu Search for Thermal Unit Maintenance Scheduling.” In 2nd IEEE Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 114–119.

  • Kirkpatrick, S., C.D. Gelatt, and M.P. Vecchi. (1983). “Optimization by Simulated Annealing.” Science 220(4598), 671–680.

    Google Scholar 

  • Kirkpatrick, S., and G. Toulouse. (1985). “Configuration Space Analysis of the Travelling Salesman Problem.” J. Phys. 46(1277).

  • Koza, J. and D. Andre. (1995). “Parallel Genetic Programming on a Network of Transputers.” Technical Report CS-TR-95-1542, Stanford University.

  • Koza, J.R. (1992). Genetic Programming. Cambridge, USA: MIT Press.

    Google Scholar 

  • Kragelund, L.V. (1997). “Solving a Timetabling Problem Using Hybrid Genetic Algorithms.” Software Practice and Experience 27(10), 1121–1134.

    Google Scholar 

  • Kroger, B., P. Schwenderling, and O. Vornberger. (1990). “Parallel Genetic Packing of Rectangles.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany. Springer-Verlag, pp. 160–164.

    Google Scholar 

  • Kroger, B., P. Schwenderling, and O. Vornberger. (1991). “Genetic Packing of Rectangles on Transputers.” In P. Welch et al. (eds.), Transputing 91. IOS Press.

  • Krueger, M. (1993). “Méthodes d'analyse d'algorithmes d'optimisation stochastiques à l'aide d'algorithmes génétiques.” Ph.D. Thesis, Ecole Nationale Supèrieure des Télécommunications, Paris, France.

    Google Scholar 

  • Lawler, E.L. (1976). Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, USA.

    Google Scholar 

  • Lee, K.-G. and S.-Y. Lee. (1992). “Efficient Parallelization of Simulated Annealing Using Multiple Markov Chains: An Application to Graph Partitioning.” In T.N. Mudge (ed.), Int. Conf. on Parallel Processing. CRC Press, pp. 177–180.

  • Levine, D. (1994). “AParallel Genetic Algorithm for the Set Partitioning Problem.” Ph.D. Thesis, Argonne National Laboratory, Illinois Institute of Technology, Argonne, USA.

    Google Scholar 

  • Liepins, G.E. and M.R. Hilliard. (1987). “Greedy Genetics.” In 2nd Int. Conf. on Genetic Algorithms: Genetic Algorithms and Their Applications, Hillsdale, NJ, USA, Lawrence Erlbaum, pp. 90–99.

    Google Scholar 

  • Lin, F.T., C.Y. Kao, and C.C. Hsu. (1991). “Incorporating Genetic Algorithms into Simulated Annealing.” Proc. of the Fourth Int. Symp. on AI. pp. 290–297.

  • Lohmann, R. (1990). “Application of Evolution Strategy in Parallel Populations.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature.Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 198–208.

    Google Scholar 

  • Mahfoud, S.W. and D.E. Goldberg. (1995). “Parallel Recombinative Simulated Annealing: A Genetic Algorithm.” Parallel Computing 21, 1–28.

    Google Scholar 

  • Malek, M., M. Guruswamy, M. Pandya, and H. Owens. (1989). “Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem.” Annals of Operations Research 21, 59–84.

    Google Scholar 

  • Mariano, C.E. and E. Morales. (1998). “A Multiple Objective Ant-q Algorithm for the Design of Water Distribution Irrigation Networks.” In First International Workshop on Ant Colony Optimization ANTS'98, Bruxelles, Belgique.

  • Martin, O.C. and S.W. Otto. (1996). “Combining Simulated Annealing with Local Search Heuristics.” Annals of Operations Research 63, 57–75.

    Google Scholar 

  • Martin, O.C., S.W. Otto, and E.W. Felten. (1992). “Large-Step Markoy Chains for the TSP: Incorporating Local Search Heuristics.” Operation Research Letters 11, 219–224.

    Google Scholar 

  • Muhlenbein, H., M. Georges-Schleuter, and M. Kramer. (1998). “Evolution Algorithms in Combinatorial Optimization.” Parallel Computing 7, 65–85.

    Google Scholar 

  • Muhlenbein, H., M. Schomisch, and J. Born. (1991). “The Parallel Genetic Algorithm as Function Optimizer.” Parallel Computing 17, 619–632.

    Google Scholar 

  • Niar, S. and A. Freville. (1997). “A Parallel Tabu Search Algorithm for the 0-1 Multidimensional Knapsack Problem.” In Int. Parallel Processing Symposium, Geneva, Switzerland. IEEE Society.

    Google Scholar 

  • Nissen, V. (1994). “Solving the Quadratic Assignment problem with Clues from Nature.” IEEE Transactions on Neural Networks 5(1), 66–72.

    Google Scholar 

  • O'Reilly, U.-M. and F. Oppacher. (1995). “Hybridized Crossover-Based Techniques for Program Discovery.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 573–578.

  • Osman, I.H. and G. Laporte. (1996). “Metaheuristics: A Bibliography.” Annals of Operations Research 63, 513–628.

    Google Scholar 

  • Papadimitriou, C.H. and K. Steiglitz. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall.

  • Petty, C.B., M.R. Leuze, and J.J. Grefenstette. (1987). “A Parallel Genetic Algorithm.” In Proc. of the Second Int. Conf. on Genetic Algorithms. Cambridge: MIT, pp. 155–161.

    Google Scholar 

  • Piramuthu, S. (1990). “Feature Construction for Back-Propagation.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature, Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 264–268.

    Google Scholar 

  • Porto, S.C.S. and C. Ribeiro. (1996). “Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling Under Precedence Constraints.” Journal of Heuristics 1(2), 207–223.

    Google Scholar 

  • Potter, W.D., J.A. Miller, B.E. Tonn, R.V. Gandham, and C.N. Lapena. (1992). “Improving the Reliability of Heuristic Multiple Fault Diagnosis via the Ec-based Genetic Algorithm.” Int. J. Artificial Intell., Neural Networks, Complex Problem-Solving Technol. 2, 5–23.

    Google Scholar 

  • Potter, W.D., J.A. Miller, and O.R. Weyrich. (1990). “A Comparison of Methods for Diagnostic Decision Making.” Expert Syst. Applicat. Int. J. 1, 425–436.

    Google Scholar 

  • Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer systeme nach prizipien der biologischen evolution. Formann-Holzboog Verlag, Stuttgart, Germany.

    Google Scholar 

  • Reeves, C.R. (1993). Modern Heuristic Techniques for Combinatorial Problems. Oxford, UK: Black Scientific Publications.

    Google Scholar 

  • Rego, C. and C. Roucairol. (1996). “A Parallel Tabu Search Algorithm for the Vehicle Routing Problem.” In I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory and Applications. Kluwer, Norwell, MA, USA, pp. 253–295.

    Google Scholar 

  • Rose, J.S., D.R. Blythe, W.M. Snelgrove, and Z.G. Vranecic. (1986). “Fast, High Quality VLSI Placement on a MIMD Multiprocessor.” In IEEE Int. Conf. on Computer-Aided Design, Santa Clara, pp. 42–45.

  • Rudolph, G. “Global Optimization by Means of Distributed Evolution Strategies.” (1990). In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 209–213.

    Google Scholar 

  • Rumelhart, D.E., G.E. Hinton, and R.J. Williams. (1986). “Learning Internal Representations by Error Propagation.” In D.E. Rumelhart and J.L. McClelland (eds.), Parallel Distributed Processing, Vol. 1, MIT Press, USA, pp. 318–362.

    Google Scholar 

  • Salami, M. and G. Cain. (1996). “Genetic Algorithm Processor on Reprogrammable Architectures.” In Fifth Annual Conference on Evolutionary Programming EP'96, San Diego, California, USA, MIT Press.

    Google Scholar 

  • Shahookar, K. and P. Mazumder. (1990). “A Genetic Approach to Standard Cell Placement Using Metagenetic Parameter Optimization.” IEEE Trans. Computer-Aided Design 9(5), 500–511.

    Google Scholar 

  • Shoukry, A. and M. Aboutabl. (1996). “Neural Network Approach for Solving the Maximal Common Subgraph Problem.” IEEE Trans. on Systems, Man, and Cybernetics 26(5), 785–790.

    Google Scholar 

  • Sloot, P.M., J.A. Kandorp, and A. Schoneveld. (1995). “Dynamic Complex Systems: A New Approach to Parallel Computing in Computational Physics.” Technical Report TR-CS-95-08, University of Amsterdam, Netherlands.

    Google Scholar 

  • Sprave, J. (1999). “A Unified Model of Non-panmictic Population Structures in Evolutionary Algorithms.” In Proc. of the 1999 Congress on Evolutionary Computation, Vol. 2, Piscataway, NJ, IEEE Press, pp. 1384–1391.

    Google Scholar 

  • Stutzle, T. and H.H. Hoos. (1997). “The MAX-MIN Ant System and Local Search for Combinatorial Optimization Problems: Towards Adaptive Tools for Global Optimization.” In 2nd Int. Conf. on Metaheuristics, Sophia Antipolis, France, INRIA, pp. 191–193.

    Google Scholar 

  • Suh, J.Y. and D. Van Gucht. (1987). “Incorporating Heuristic Information into Genetic Search.” In 2nd Int. Conf. Genetic Algorithms, Lawrence Erlbaum Associates, USA, pp. 100–107.

    Google Scholar 

  • Sun, Z. and Q. Wan. (1995). “A Modified Genetic Algorithm: Meta-leval Control of Migration in Distributed Ga.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 312–316.

  • Taillard, E. (1993). “Parallel Iterative Search Methods for Vehicle Routing Problem.” Networks 23, 661–673.

    Google Scholar 

  • Taillard, E.D. and L.M. Gambardella. (1997). “An Ant Approach for Structured Quadratic Assignment Problems.” In C. Roucairol, I.H. Osman, S. Martello, and S. Voss (eds.), 2nd Int. Conf. on Metaheuristics, Sophia Antipolis, France, INRIA, pp. 217–222.

    Google Scholar 

  • Talbi, E.G., T. Muntean, and I. Samarandache. (1994). “Hybridation des AlgorithmesGénétiquesAvec la Recherche Tabou.” In Evolution Artificielle EA94, Toulouse, France.

  • Tanese, R. (1987). “Parallel genetic Algorithms for a Hypercube.” In Proc. of the Second Int. Conf. on Genetic Algorithms, MIT, Cambridge, MA, USA, pp. 177–183.

    Google Scholar 

  • Thiel, J. and S. Voss. (1994). “Some Experiences on Solving Multiconstraint Zero-one Knapsack Problems with Genetic Algorithms.” INFOR 32(4), 226–242.

    Google Scholar 

  • Ulder, N.L.J., E.H.L. Aarts, H.-J. Bandelt, P.J.M. Van Laarhoven, and E. Pesch. (1990). “Genetic Local Search Algorithms for the Traveling Salesman Problem.” In H.-P. Schewefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 109–116.

    Google Scholar 

  • Vaessens, R., E. Aarts, and J. Lenstra. (1992). “A Local Search Template.” In R. Manner and B. Manderick (eds.), Parallel Problem Solving From Nature. Belgique, pp. 67–76.

  • Voigt, H.-M., J. Born, and I. Santibanez-Koref. (1990). “Modelling and Simulation of Distributed Evolutionary Search Processes for Function Optimization.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany, Springer-Verlag, pp. 373–380.

    Google Scholar 

  • Von Laszewski, G. and H. Muhlenbein. (1990). “Partitioning a Graph with Parallel Genetic Algorithm.” In H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature. Vol. 496 of LNCS, Dortmund, Germany. Springer-Verlag, pp. 165–169.

    Google Scholar 

  • Voss, S. (1993). “Tabu Search: Applications and Prospects.” In Network Optimization Problems, World Scientific, USA, pp. 333–353.

    Google Scholar 

  • Wang, L.-H., C.-Y. Kao, M. Ouh-Young, and W.-C. Chen, (1995). “Molecular Binding: A Case Study of the Population-Based annealing Genetic Algorithms.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 50–55.

  • Yang, S.Y., L.-J. Park, C.H. Park, and J.W. Ra. (1995). “A Hybrid Algorithm Using Genetic Algorithm and Gradient-Based Algorithm for Iterative Microwave Inverse Scattering.” In IEEE Int. Conf. on Evolutionary Computation ICEC'95, Perth, Australia, pp. 450–455.

Download references

Author information

Authors and Affiliations

  1. Laboratoire d'Informatique Fondamentale de Lille, URA CNRS 369, Cité scientifique, 59655, Villeneuve d'Ascq Cedex, France

    E.-G. Talbi

Authors
  1. E.-G. Talbi
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Talbi, EG. A Taxonomy of Hybrid Metaheuristics. Journal of Heuristics 8, 541–564 (2002). https://doi.org/10.1023/A:1016540724870

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1016540724870

Search

Navigation