Abstract
We present a state-of-the-art survey of parallel meta-heuristic developments and results, discuss general design and implementation principles that apply to most meta-heuristic classes, instantiate these principles for the three meta-heuristic classes currently most extensively used—genetic methods, simulated annealing, and tabu search, and identify a number of trends and promising research directions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, E. and Korst, J. (2002) Selected topics in simulated annealing. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 1–57.
Aarts, E.H.L, de Bont, F.M.J., Habers, J.H.A. and van Laarhoven, P.J.M. (1986) Parallel implementations of statistical cooling algorithms. Integration, The VLSI Journal, 3, 209–238.
Aarts, E.H.L. and Korst, J.H.M. (1989) Simulated Annealing and Boltzmann Machines. John Wiley & Sons, New York, NY.
Abramson, D. and Abela, J. (1992) A parallel genetic algorithm for solving the school timetabling problem. In: G. Gupta and C. Keen (eds.), 15th Australian Computer Science Conference. Department of Computer Science, University of Tasmania, pp. 1–11.
Abramson, D., Mills, G. and Perkins, S. (1993) Parallelization of a genetic algorithm for the computation of efficient train schedules. In: D. Arnold, R. Christie, J. Day and P. Roe (eds.), Proceedings of the 1993 Parallel Computing and Transputers Conference. IOS Press, pp. 139–149.
Aiex, R.M., Martins, S.L., Ribeiro, C.C. and Rodriguez, N.R. (1996) Asynchronous parallel strategies for tabu search applied to the partitioning of VLSI circuits. Monografias em ciência da computação, Pontifícia Universidade Católica de Rio de Janeiro.
Andreatta, A. A. and Ribeiro C.C. (1994) A graph partitioning heuristic for the parallel pseudo-exhaustive logical test of VLSI combinational circuits. Annals of Operations Research, 50, 1–36.
Azencott, R. (1992) Simulated Annealing Parallelization Techniques. John Wiley & Sons, New York, NY.
Badeau, P., Guertin, F., Gendreau, M., Potvin, J.-Y. and Taillard, É.D. (1997) A parallel tabu search heuristic for the vehicle routing problem with time windows. Transportation Research C: Emerging Technologies, 5(2), 109–122.
Baluja, S. (1993) Structure and performance of fine-grain parallelism in genetic algorithms. In: S. Forrest (ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 155–162.
Barr, R.S. and Hickman, B.L. (1993) Reporting computational experiments with parallel algorithms: issues, measures, and experts opinions. ORSA Journal on Computing, 5(1), 2–18.
Battiti, R. and Tecchiolli, G. (1992) Parallel based search for combinatorial optimization: genetic algorithms and TABU. Microprocessors and Microsystems, 16(7), 351–367.
Bhandarkar, S.M. and Chirravuri, S. (1996) A study of massively parallel simulated annealing algorithms for chromosome reconstruction via clone ordering. Parallel Algorithms and Applications, 9, 67–89.
Bonabeau, E., Dorigo, M. and Theraulaz, G. (eds.) (1999) Swarm Intelligence—From Natural to Artificial Systems. Oxford University Press, New York, NY.
Cantú-Paz, E. (1995) A summary of research on parallel genetic algorithms. Report 95007, University of Illinois at Urbana-Champain.
Cantú-Paz, E. (1998) A survey of parallel genetic algorithms. Calculateurs Parallèles, Réseaux et Systèmes répartis, 10(2), 141–170.
Cavalcante, C.B.C., Cavalcante, V.F., Ribeiro, C.C. and de Souza, C.C. (2002) Parallel cooperative approaches for the labor constrained scheduling problem. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 201–225.
Chakrapani, J. and Skorin-Kapov, J. (1992) A connectionist approach to the quadratic assignment problem. Computers & Operations Research, 19(3/4), 287–295.
Chakrapani, J. and Skorin-Kapov, J. (1993) Massively parallel tabu search for the quadratic assignment problem. Annals of Operations Research, 41, 327–341.
Chakrapani, J. and Skorin-Kapov, J. (1993a) Connection machine implementation of a tabu search algorithm for the traveling salesman problem. Journal of Computing and Information Technology, 1(1), 29–36.
Chakrapani, J. and Skorin-Kapov, J. (1995) Mapping tasks to processors to minimize communication time in a multiprocessor system. In: The Impact of Emerging Technologies of Computer Science and Operations Research. Kluwer Academic Publishers, Norwell, MA, pp. 45–64.
Chen, Y.-W., Nakao, Z. and Fang, X. (1996) Parallelization of a genetic algorithm for image restoration and its performance analysis. In: IEEE International Conference on Evolutionary Computation, pp. 463–468.
Christofides, N., Mingozzi A. and Toth, P. (1979) The vehicle routing problem. In: N. Christofides, A. Mingozzi, P. Toth and C. Sandi (eds.), Combinatorial Optimization. John Wiley, New York, pp. 315–338.
Chu, K., Deng, Y. and Reinitz, J. (1999) Parallel simulated annealing algorithms by mixing states. Journal of Computational Physics, 148, 646–662.
Cohoon, J., Hedge, S., Martin, W. and Richards, D. (1987) Punctuated equilibria: a parallel genetic algorithm. In: J. Grefenstette (ed.), Proceedings of the Second International Conference on Genetic Algorithms and their Applications. Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 148–154.
Cohoon, J., Martin, W. and Richards, D. (1991a) Genetic algorithm and punctuated equilibria in VLSI. In: H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496. Springer-Verlag, Berlin, pp. 134–144.
Cohoon, J., Martin, W. and Richards, D. (1991b) A multi-population genetic algorithm for solving the k-partition problem on hyper-cubes. In: R. Belew and L. Booker (eds.), Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 134–144.
Colorni, A., Dorigo, M. and Maniezzo, V. (1991) Distributed optimization by ant colonies. In: Proceedings of the 1991 European Conference on Artificial Life. North-Holland, Amsterdam, pp. 134–142.
Crainic, T.G. (2002) Parallel computation, co-operation, tabu search. In: C. Rego and B. Alidaee (eds.), Adaptive Memory and Evolution: Tabu Search and Scatter Search. Kluwer Academic Publishers, Norwell, MA (forthcoming).
Crainic, T.G. and Gendreau, M. (1999) Towards an evolutionary method—cooperating multi-thread parallel tabu search hybrid. In: S. Voß, S. Martello, C. Roucairol and I.H. Osman (eds.), Mela-Heuristics 98: Theory & Applications. Kluwer Academic Publishers, Norwell, MA, pp. 331–344.
Crainic, T.G. and Gendreau, M. (2001) Cooperative parallel tabu search for capacitated network design. Journal of Heuristics (forthcoming).
Crainic, T.G. and Toulouse, M. (1998) Parallel metaheuristics. In: T.G. Crainic and G. Laporte (eds.), Fleet Management and Logistics. Kluwer Academic Publishers, Norwell, MA, pp. 205–251.
Crainic, T.G., Toulouse, M. and Gendreau, M. (1995a) Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements. Annals of Operations Research, 63, 277–299.
Crainic, T.G., Toulouse, M. and Gendreau, M. (1995b) Synchronous tabu search parallelization strategies for multicommodity location-allocation with balancing requirements. OR Spektrum, 17(2/3), 113–123.
Crainic, T.G., Toulouse, M. and Gendreau, M. (1997) Towards a taxonomy of parallel tabu search algorithms. INFORMS Journal on Computing, 9(1), 61–72.
Cung, V.-D., Martins, S.L., Ribeiro, C.C. and Roucairol, C. (2002) Strategies for the parallel implementations of metaheuristics. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 263–308.
Darema, F., Kirkpatrick, S. and Norton, V.A. (1987) Parallel algorithms for chip placement by simulated annealing. IBM Journal of Research and Development, 31, 391–102.
De Falco, I., Del Balio, R. and Tarantino, E. (1995) Solving the mapping problem by parallel tabu search. Report, Istituto per la Ricerca sui Sistemi Informatici Paralleli-CNR.
De Falco, I., Del Balio, R., Tarantino, E. and Vaccaro, R. (1994) Improving search by incorporating evolution principles in parallel tabu search. In: Proceedings International Conference on Machine Learning, pp. 823–828.
Dorigo, M., Maniezzo, V. and Colorni, A. (1996) The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B, 26(1), 29–41.
Du, Z., Li, S., Li, S., Wu, M. and Zhu, J. (1999) Massively parallel simulated annealing embedded with downhill—a SPMD algorithm for cluster computing. In: Proceedings of the 1st IEEE Computer Society International Workshop on Cluster Computing. IEEE Computer Society Press, Washington, DC.
Durand, M.D. (1989) Parallel simulated annealing: accuracy vs. speed in placement. IEEE Design & Test of Computers, 6(3), 8–34.
Durand, M.D. (1989a) Cost function error in asynchronous parallel simulated annealing algorithms. Technical Report CUCS-423-89, University of Columbia.
Felten, E., Karlin, S. and Otto, S. W. (1985) The traveling salesman problem on a hypercube, MIMD computer. In Proceedings 1985 of the International Conference on Parallel Processing, pp. 6–10.
Feo, T.A. and Resende, M.G.C. (1995) Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109–133.
Festa, P. and Resende, M.G.C. (2002) GRASP: an annotated bibliography. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 325–367.
Fiechter, C.-N. (1994) A parallel tabu search algorithm for large travelling salesman problems. Discrete Applied Mathematics, 51(3), 243–267.
Fogarty, T.C. and Huang, R. (1990) Implementing the genetic algorithm on transputer based parallel systems. In: H.-P. Schwefel and R. Männer (eds.), Proceedings of the 1st Workshop on Parallel Problem Solving from Nature. Springer-Verlag, Berlin, pp. 145–149.
Fogel, D.B. (1994) Evolutionary programming: an introduction and some current directions. Statistics and Computing, 4, 113–130.
Garcia, B.L., Potvin, J.-Y. and Rousseau, J.M. (1994) A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints. Computers & Operations Research, 21(9), 1025–1033.
Gendreau, M. (2002) Recent advances in tabu search. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 369–377.
Gendreau, M., Guertin, F., Potvin, J.-Y. and Taillard, É.D. (1999) Tabu search for real-time vehicle routing and dispatching. Transportation Science, 33(4), 381–390.
Glover, F. (1986) Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 1(3), 533–549.
Glover, F. (1989) Tabu search—part I. ORSA Journal on Computing, 1(3), 190–206.
Glover, F. (1990) Tabu search—part II. ORSA Journal on Computing, 2(1), 4–32.
Glover, F. (1994) Genetic algorithms and scatter search: unsuspected potentials. Statistics and Computing, 4, 131–140.
Glover, F. (1996) Tabu search and adaptive memory programming—advances, applications and challenges. In: R. Barr, R. Helgason and J. Kennington (eds.), Interfaces in Computer Science and Operations Research. Kluwer Academic Publishers, Norwell, MA, pp. 1–75.
Glover, F. and Laguna, M. (1993) Tabu search. In: C. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications, Oxford, pp. 70–150.
Glover, F. and Laguna, M. (1997) Tabu Search. Kluwer Academic Publishers, Norwell, MA.
Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA.
Graffigne, C. (1992) Parallel annealing by periodically interacting multiple searches: an experimental study. In: R. Azencott (ed.), Simulated Annealing Parallelization Techniques. John Wiley & Sons, New York, NY, pp. 47–79.
Greening, D.R. (1990) Parallel simulated annealing techniques. Physica D, 42, 293–306.
Grefenstette, J. (1981) Parallel adaptive algorithms for function optimization. Technical Report CS-81-19, Vanderbilt University, Nashville.
Hansen, P. and Mladenovic, N. (1997) Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.
Hansen, P. and Mladenovic, N. (1999) An introduction to variable neighborhood search. In: S. Voß, S. Martello, C. Roucairol and I.H. Osman (eds.), Meta-Heuristics 98: Theory & Applications. Kluwer, Norwell, MA, pp. 433–458.
Hansen, P. and Mladenovic, N. (2002) Developments of variable neighborhood search. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 415–439.
Hauser, R. and Männer, R. (1994) Implementation of standard genetic algorithm on MIMD machines. In: Y. Davidor, H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature III, Lecture Notes in Computer Science 866. Springer-Verlag, Berlin, pp. 504–514.
Herdy, M. (1992) Reproductive isolation as strategy parameter in hierarchical organized evolution strategies. In: R. Männer and B. Manderick (eds.), Parallel Problem Solving from Nature, 2. North-Holland, Amsterdam, pp. 207–217.
Hillis, D.W. (1992) Co-evolving parasites improve simulated evolution as an optimization procedure. In: C.E.A. Langton (ed.), Artificial Life II. Addison-Wesley, pp. 313–324.
Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
Holmqvist, K. and Migdalas, A. and Pardalos, P.M. (1997) Parallelized heuristics for combinatorial search. In: A. Migdalas, P. Pardalos and S. Storoy (eds.), Parallel Computing in Optimization. Kluwer Academic Publishers, Norwell, MA, pp. 269–294.
Jayaraman, R. and Darema, F. (1988) Error tolerance in parallel simulated techniques. In: Proceedings of the IEEE International Conference on Computer-Aided Design: ICCAD-88. IEEE Computer Society Press, Washington, DC, pp. 545–548.
Kindervater, G.A.P, Lenstra, J.K. and Savelsberg, M.W.P. (1993) Sequential and parallel local search for the time constrained traveling salesman problem. Discrete Applied Mathematics, 42, 211–225.
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983) Optimization by simulated annealing. Science, 220, 671–680.
Kliewer, G. and Tschoke, S. (2000) A general parallel simulated annealing library and its application in airline industry. In: Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS 2000). Cancun, Mexico, pp. 55–61.
Kohlmorgen, U., Schmeck, H. and Haase, K. (1999) Experiences with fine-grained parallel genetic algorithms. Annals of Operations Research, 90, 203–219.
Kurbel, K., Schneider, B. and Singh, K. (1995) VLSI standard cell placement by parallel hybrid simulated annealing and genetic algorithm. In: D.W. Pearson, N.C. Steele and R. F. Albrecht (eds.), Proceedings of the Second International Conference on Artificial Neural Networks and Genetic Algorithms. Springer-Verlag, Berlin, pp. 491–494.
Laarhoven, P. and Aarts, E.H.L. (1987) Simulated Annealing: Theory and Applications. Reidel, Dordrecht.
Laursen, P.S. (1994) Problem-independent parallel simulated annealing using selection and migration. In: Y. Davidor, H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature III, Lecture Notes in Computer Science 866. Springer-Verlag, Berlin, pp. 408–417.
Laursen, P.S. (1996) Parallel heuristic search—introductions and a new approach. In: A. Ferreira and P. Pardalos (eds.), Solving Combinatorial Optimization Problems in Parallel, Lecture Notes in Computer Science 1054. Springer-Verlag, Berlin, pp. 248–274.
Le Bouthillier, A. and Crainic, T.G. (2001) Parallel co-operative multi-thread meta-heuristic for the vehicle routing problem with time window constraints. Publication, Centre de recherche sur les transports, Université de Montréal, Montréal, QC, Canada.
Lee, F.-H.A. (1995) Parallel Simulated Annealing on a Message-Passing Multi-Computer. Ph.D. thesis, Utah State University.
Lee, K.-G. and Lee, S.-Y. (1992a) Efficient parallelization of simulated annealing using multiple markov chains: an application to graph partitioning. In: T. Mudge (ed.), Proceedings of the International Conference on Parallel Processing, volume III: Algorithms and Applications. CRC Press, pp. 177–180.
Lee, K.-G. and Lee, S.-Y. (1995) Synchronous and asynchronous parallel simulated annealing with multiple markov chains. Lecture Notes in Computer Science 1027, pp. 396–408.
Lin, S.-C., Punch, W. and Goodman, E. (1994) Coarse-grain parallel genetic algorithms: categorization and new approach. In: Sixth IEEE Symposium on Parallel and Distributed Processing. IEEE Computer Society Press, pp. 28–37.
Lis, J. (1996) Parallel genetic algorithm with the dynamic control parameter. In: IEEE 1996 International Conference on Evolutionary Computation, pp. 324–328.
Mahfoud, S.W. and Goldberg, D.E. (1995) Parallel recombinative simulated annealing: a genetic algorithm. Parallel Computing, 21, 1–28.
Malek, M., Guruswamy, M., Pandya, M. and Owens, H. (1989) Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Annals of Operations Research, 21, 59–84.
Maniezzo, V. and Carbonaro, A. (2002) Ant colony optimization: an overview. In: C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, Norwell, MA, pp. 469–492.
Martins, S.L., Ribeiro, C.C. and Rodriguez, N.R. (1996) Parallel programming tools for distributed memory environments. Monografias em Ciência da Computação 01/96, Pontifícia Universidade Católica de Rio de Janeiro.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E. (1953) Equation of state calculation by fast computing machines. Journal of Chemical Physics, 21, 1087–1092.
Michalewicz, Z. (1992) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin.
Michalewicz, Z. and Fogel, D.B. (2000) How to Solve It: Modern Heuristics. Springer-Verlag, Berlin.
Moscato, P. (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Publication Report 790, Caltech Concurrent Computation Program.
Moscato, P. and Norman, M.G. (1992) A “memetic” approach for the traveling salesman problem. Implementation of a computational ecology for combinatorial optimization on message-passing systems. In: M. Valero, E. Onate, M. Jane, J. Larriba and B. Suarez (eds.), Parallel Computing and Transputer Applications. IOS Press, Amsterdam, pp. 187–194.
Mühlenbein, H. (1991) Evolution in time and space—the parallel genetic algorithm. In: G. Rawlins (ed.), Foundations of Genetic Algorithm & Classifier Systems. Morgan Kaufman, San Mateo, CA, pp. 316–338.
Mühlenbein, H. (1992) Parallel genetic algorithms in combinatorial optimization. In: O. Balci, R. Sharda and S. Zenios (eds.), Computer Science and Operations Research. Pergamon Press, New York, NY, pp. 441–56.
Mühlenbein, H. (1992a) How genetic algorithms really work: mutation and hillclimbing. In: R. Manner and B. Manderick (eds.), Parallel Problem Solving from Nature, 2. North-Holland, Amsterdam, pp. 15–26.
Muhlenbein, H., Gorges-Schleuter, M. and Krämer, O. (1987) New solutions to the mapping problem of parallel systems—the evolution approach. Parallel Computing, 6, 269–279.
Mühlenbein, H., Gorges-Schleuter, M. and Krämer, O. (1988) Evolution algorithms in combinatorial optimization. Parallel Computing, 7(1), 65–85.
Mühlenbein, H. and Schlierkamp-Voosen, D. (1994) The science of breeding and its application to the breeder genetic algorithm BGA. Evolutionary Computation, 1(4), 335–360.
Ouyang, M., Toulouse, M., Thulasiraman, K., Glover, F. and Deogun, J.S. (2000a) Multi-level cooperative search: application to the netlist/hypergraph partitioning problem. In: Proceedings of International Symposium on Physical Design. ACM Press, pp. 192–198.
Ouyang, M., Toulouse, M., Thulasiraman, K., Glover, F. and Deogun, J.S. (2000b) Multilevel cooperative search for the circuit/hypergraph partitioning problem. IEEE Transactions on Computer-Aided Design, (to appear).
Pardalos, P.M., Pitsoulis, L., Mavridou, T., and Resende, M.G.C. (1995) Parallel search for combinatorial optimization: genetic algorithms, simulated annealing, tabu search and GRASP. In: A. Ferreira and J. Rolim (eds.), Proceedings of Workshop on Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Computer Science 980. Springer-Verlag, Berlin, pp. 317–331.
Pardalos, P.M., Pitsoulis, L. and Resende, M.G.C. (1995) A parallel GRASP implementation for the quadratic assignment problem. In: A. Ferreira and J. Rolim (eds.), Solving Irregular Problems in Parallel: State of the Art. Kluwer Academic Publishers, Norwell, MA.
Porto, S.C.S. and Ribeiro, C.C. (1995) A tabu search approach to task scheduling on heteregenous processors under precedence constraints. International Journal of High-Speed Computing, 7, 45–71.
Porto, S.C.S. and Ribeiro, C.C. (1996) Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints. Journal of Heuristics, 1(2), 207–223.
Potter, M. and De Jong, K. (1994) A cooperative coevolutionary approach to function optimization. In: Y. Davidor, H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature III, Lecture Notes in Computer Science 866. Springer-Verlag, Berlin, pp. 249–257.
Ram, D.J., Sreenivas, T.H. and Subramaniam, K.G. (1996) Parallel simulated annealing algorithms. Journal of Parallel and Distributed Computing, 37, 207–212.
Rego, C. and Roucairol, C. (1996) A parallel tabu search algorithm using ejection chains for the VRP. In: I. Osman and J. Kelly (eds.), Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, Norwell, MA, pp. 253–295.
Rochat, Y. and Taillard, É.D. (1995) Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147–167.
Schlierkamp-Voosen, D. and Mühlenbein, H. (1994) Strategy adaptation by competing subpopulations. In: Y. Davidor, H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature III, Lecture Notes in Computer Science 866. Springer-Verlag, Berlin, pp. 199–208.
Schnecke, V. and Vornberger, O. (1996) An adaptive parallel genetic algorithm for VLSI-layout optimization. In: Y. Davidor, H.-P. Schwefel and R. Manner (eds.), Parallel Problem Solving from Nature III, Lecture Notes in Computer Science 866. Springer-Verlag, Berlin, pp. 859–868.
Schulze, J. and Fahle, T. (1999) A parallel algorithm for the vehicle routing problem with time window constraints. Annals of Operations Reseach, 86, 585–607.
Schwehm, M. (1992) Implementation of genetic algorithms on various interconnection networks. In: M. Valero, E. Onate, M. Jane, J. Larriba and B. Suarez (eds.), Parallel Computing and Transputers Applications. IOS Press, Amsterdam, pp. 195–203.
Shonkwiler, R. (1993) Parallel genetic algorithms. In: S. Forrest (ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 199–205.
Sondergeld, L. and Voß, S. (1999) Cooperative intelligent search using adaptive memory techniques. In: S. Voß, S. Martello, C. Roucairol and I.H. Osman (eds.), Meta-Heuristics 98: Theory & Applications. Kluwer, Norwell, MA, pp. 297–312.
Starkweather, T., Whitley, D. and Mathias, K. (1991) Optimization using distributed genetic algorithms. In: H.-P. Schwefel and R. Männer (eds.), Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496. Springer-Verlag, Berlin, pp. 176–185.
Taillard, É.D. (1991) Robust taboo search for the quadratic assignment problem. Parallel Computing, 17, 443–455.
Taillard, É.D. (1993a) Parallel iterative search methods for vehicle routing problems. Networks, 23, 661–673.
Taillard, É.D. (1993b) Recherches itératives dirigées parallèles. Ph.D. thesis, École Polytechnique Fédérate de Lausanne.
Taillard, É.D. (1994) Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6(2), 108–117.
Taillard, É.D., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J.-Y. (1997) A tabu Search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31, 170–186.
ten Eikelder, H.M.M., Aarts, B.J.M., Verhoeven, M.G.A. and Aarts, E.H.L. (1999) Sequential and parallel local search for job shop scheduling. In: S. Voß, S. Martello, C. Roucairol and I.H. Osman (eds.), Meta-Heuristics 98: Theory & Applications. Kluwer, Norwell, MA, Montréal, QC, Canada, pp. 359–371.
Toulouse, M., Crainic, T.G. and Gendreau, M. (1996) Communication issues in designing cooperative multi thread parallel searches. In: I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, Norwell, MA, pp. 501–522.
Toulouse, M., Crainic, T.G. and Sansó, B. (1997) Systemic behavior of cooperative search algorithms. Publication CRT-97-55, Centre de recherche sur les transports, Université de Montréal, Montréal, QC, Canada.
Toulouse, M., Crainic, T.G. and Sansó, B. (1999a) An experimental study of systemic behavior of cooperative search algorithms. In: S. Voß, S. Martello, C. Roucairol and I.H. Osman (eds.), Meta-Heuristics 98: Theory & Applications. Kluwer Academic Publishers, Norwell, MA, pp. 373–392.
Toulouse, M., Crainic, T.G., Sansó, B. and Thulasiraman, K. (1998a) Self-organization in cooperative search algorithms. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics. Omnipress, pp. 2379–2385.
Toulouse, M., Crainic, T.G. and Thulasiraman, K. (2000) Global optimization properties of parallel cooperative search algorithms: a simulation study. Parallel Computing, 26(1), 91–112.
Toulouse, M., Glover, F. and Thulasiraman, K. (1998b) A multi-scale cooperative search with an application to graph partitioning. Report, School of Computer Science, University of Oklahoma, Norman, OK.
Toulouse, M., Thulasiraman, K. and Glover, F. (1999b) Multi-level cooperative search. In: P. Amestoy, P. Berger, M. Daydé, I. Duff, V. Frayssé, L. Giraud and D. Ruiz (eds.), 5th International Euro-Par Parallel Processing Conference, volume 1685 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, pp. 533–542.
Verhoeven, M.G.A. and Severens, M.M.M. (1999) Parallel local search for steiner trees in graphs. Annals of Operations Research, 90, 185–202.
Verhoeven, M.G.A. and Aarts, E.H.L (1995) Parallel local search. Journal of Heuristics, 1(1), 43–65.
Voß, S. (1993) Tabu search: applications and prospects. In: D.-Z. Du and P. Pardalos (eds.), Network Optimization Problems. World Scientific Publishing Co., Singapore, pp. 333–353.
Whitley, D. (1993) Cellular genetic algorithms. In: S. Forrest (eds.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 658–658.
Whitley, D. and Starkweather, T. (1990a) Optimizing small neural networks using a distributed genetic algorithm. In: Proceedings of the International Conference on Neural Networks. IEEE Press, pp. 206–209.
Whitley, D. and Starkweather, T. (1990b) GENITORII: a distributed genetic algorithm. Journal of Experimental and Theoretical Artificial Intelligence, 2(3), 189–214.
Whitley, L.D. (1994) A genetic algorithm tutorial. Statistics and Computing, 4, 65–85.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Kluwer Academic Publishers
About this chapter
Cite this chapter
Crainic, T.G., Toulouse, M. (2003). Parallel Strategies for Meta-Heuristics. In: Glover, F., Kochenberger, G.A. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 57. Springer, Boston, MA. https://doi.org/10.1007/0-306-48056-5_17
Download citation
DOI: https://doi.org/10.1007/0-306-48056-5_17
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4020-7263-5
Online ISBN: 978-0-306-48056-0
eBook Packages: Springer Book Archive