Skip to main content
SpringerLink
Log in

Embedding Branch and Bound within Evolutionary Algorithms

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

A framework for hybridizing evolutionary algorithms with the branch-and-bound algorithm (B&B) is presented in this paper. This framework is based on using B&B as an operator embedded in the evolutionary algorithm. The resulting hybrid operator will intelligently explore the dynastic potential (possible children) of the solutions being recombined, providing the best combination of formae (generalized schemata) that can be constructed without introducing implicit mutation. As a basis for studying this operator, the general functioning of transmitting recombination is considered. Two important concepts are introduced, compatibility sets, and granularity of the representation. These concepts are studied in the context of different kinds of representation: orthogonal, non-orthogonal separable, and non-separable.

The results of an extensive experimental evaluation are reported. It is shown that this model can be useful when problem knowledge is available in the form of an optimistic evaluation function. Scalability issues are also considered. A control mechanism is proposed to alleviate the increasing computational cost of the algorithm for highly multidimensional problems.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. T. Bäck, D. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Oxford University Press: New York, NY, 1997.

    Google Scholar 

  2. L. Fogel, A. Owens, and M. Walsh, Artificial Intelligence through Simulated Evolution, Wiley: New York, NY, 1966.

    Google Scholar 

  3. J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press: Ann Harbor, 1975.

    Google Scholar 

  4. H.-P. Schwefel, “Evolution strategies: A family of non-linear optimization techniques based on imitating some principles of natural evolution,” Annals of Operations Research, vol. 1, pp. 165–167, 1984.

    Google Scholar 

  5. A. Eiben, P.-E. Raue, and Z. Ruttkay, “Genetic algorithms with multi-parent recombination,” in Parallel Problem Solving from Nature III, edited by Y. Davidor, H.-P. Schwefel, and R. Männer, vol. 866 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, pp. 78–87, 1994.

    Google Scholar 

  6. D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley: Reading, MA, 1989.

    Google Scholar 

  7. N. Radcliffe, “Equivalence class analysis of genetic algorithms,” Complex Systems, vol. 5, pp. 183–205, 1991.

    Google Scholar 

  8. N. Radcliffe, “The algebra of genetic algorithms,” Annals of Mathematics and Artificial Intelligence, vol. 10, pp. 339–384, 1994.

    Google Scholar 

  9. R. Tanese, “Distributed genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, edited by J. Schaffer, Morgan Kaufmann: San Mateo, CA, 434–439, 1989.

    Google Scholar 

  10. P. Spiessens and B. Manderick, “A massively parallel genetic algorithm,” in Proceedings of the 4th International Conference on Genetic Algorithms, edited by R. Belew and L. Booker, Morgan Kauffman: San Mateo, CA, 1991, pp. 279–286.

    Google Scholar 

  11. W. Hart and R. Belew, “Optimizing an arbitrary function is hard for the genetic algorithm,” in Proceedings of the 4th International Conference on Genetic Algorithms, edited by R. Belew and L. Booker, Morgan Kaufmann: San Mateo, CA, 1991, pp. 190–195.

    Google Scholar 

  12. D. Wolpert and W. Macready, “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, vol. 1, no.1, pp. 67–82, 1997.

    Google Scholar 

  13. J. Culberson, “On the futility of blind search: An algorithmic view of no free lunch,” Evolutionary Computation, vol. 6, no.2, pp. 109–128, 1998.

    Google Scholar 

  14. L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold: New York, NY, 1991.

    Google Scholar 

  15. C. Cotta, “A study of hybridisation techniques and their application to the design of evolutionary algorithms,” AI Communications, vol. 11, nos.3/4, pp. 223–224, 1998.

    Google Scholar 

  16. P. Moscato, “Memetic algorithms: A short introduction,” in New Ideas in Optimization, edited by D. Corne, M. Dorigo, and F. Glover, McGraw-Hill, 1999, pp. 219–234

  17. N. Radcliffe and P. Surry, “Fitness variance of formae and performance prediction,” in Foundations of Genetic Algorithms III, edited by L. Whitley and M. Vose, Morgan Kauffman: San Mateo, CA, 1994, pp. 51–72.

    Google Scholar 

  18. C. Cotta and J. Troya, “Genetic forma recombination in permutation flowshop problems,” Evolutionary Computation, vol. 6, no.1, pp. 25–44, 1998.

    Google Scholar 

  19. C. Cotta, E. Alba, and J. Troya, “Utilising dynastically optimal forma recombination in hybrid genetic algorithms,” in Parallel Problem Solving From Nature V, vol. 1498 of Lecture Notes in Computer Science, edited by A. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, Springer-Verlag: Berlin, pp. 305–314, 1998.

    Google Scholar 

  20. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag: Berlin, 1992.

    Google Scholar 

  21. T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, and C. Whitley, “A comparison of genetic sequencing operators,” in Proceedings of the 4th International Conference on Genetic Algorithms, edited by R. Belew and L. Booker, Morgan Kauffman: San Mateo, CA, 1991, pp. 69–76.

    Google Scholar 

  22. I. Oliver, D. Smith, and J. Holland, “A study of permutation crossover operators on the traveling salesman problem,” in Proceedings of the 2nd International Conference on Genetic Algorithms, edited by J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, 1987, pp. 224–230.

    Google Scholar 

  23. C. Cotta and J. Troya, “On the influence of the representation granularity in heuristic forma recombination,” in ACM Symposium on Applied Computing 2000, edited by J. Carroll, E. Damiani, H. Haddad, and D. Oppenheim, ACM Press, 2000, pp. 433–439.

  24. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman and Co.: San Francisco, CA, 1979.

    Google Scholar 

  25. C. Cotta, J. Aldana, A. Nebro, and J. Troya, “Hybridizing genetic algorithms with branch and bound techniques for the resolution of the TSP,” in Artificial Neural Nets and Genetic Algorithms 2, edited by D. Pearson, N. Steele, and R. Albrecht, Springer-Verlag: Wien New York, 1995, pp. 277–280.

    Google Scholar 

  26. G. Syswerda, “Uniform crossover in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, edited by J. Schaffer, Morgan Kaufmann: San Mateo, CA, pp. 2–9, 1989.

    Google Scholar 

  27. C. Cotta and J. Troya, “Tackling epistatic problems using dynastically optimal recombination,” in Computational Intelligence. Theory and Applications, Vol. 1625 of Lecture Notes in Computer Science, edited by B. Reusch, Springer-Verlag: Berlin Heidelberg, 1999, pp. 197–205.

    Google Scholar 

  28. E. Lawler and D. Wood, “Branch and bounds methods: A survey,” Operations Research, vol. 4, no.4, pp. 669–719, 1966.

    Google Scholar 

  29. T. Bäck, “Selective pressure in evolutionary algorithms: A characterization of selection mechanisms,” in Proceedings of the 1st IEEE Conference on Evolutionary Computation, IEEE Press: Piscataway, NJ, 1994, pp. 57–62.

    Google Scholar 

  30. N. Radcliffe, “Forma analysis and random respectful recombination,” in Proceedings of the 4th International Conference on Genetic Algorithms, edited by R. Belew and L. Booker, Morgan Kaufmann: San Mateo, CA, 1991, pp. 222–229.

    Google Scholar 

  31. C. Cotta and J. Troya, “Using a hybrid evolutionary-A* approach for learning reactive behaviors,” in Real-World Applications of Evolutionary Computation, vol. 1803 of Lecture Notes in Computer Science, edited by S. Cagnoni et al., Edinburgh, Springer-Verlag, 2000, pp. 347–356.

  32. T. Bäck, Evolutionary Algorithms in Theory and Practice, Oxford University Press: New York, NY, 1996.

    Google Scholar 

  33. D. Goldberg and R.J. Lingle, “Alleles, loci, and the travelling salesman problem,” in Proceedings of an International Conference on Genetic Algorithms, edited by J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, 1985, pp. 154–159.

    Google Scholar 

  34. L. Davis, “Applying adaptive algorithms to epistatic domains,” in Proceedings of the 9th International Joint Conference on Artiicial Intelligence, Morgan Kaufmann: Los Angeles, CA, 1985, pp. 162–164.

    Google Scholar 

  35. G. Syswerda, “Schedule optimization using genetic algorithms,” in Handbook of Genetic Algorithms, edited by L. Davis, Van Nostrand Reinhold: New York, NY, 1991, pp. 335–349.

    Google Scholar 

  36. P. Moscato and C. Cotta, “A gentle introduction to memetic algorithms,” in Handbook of Metaheuristics, edited by F. Glover and G. Kochenberger, Kluwer Academic Publishers: Boston, MA, 2002.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. Lenguajes y Ciencias de la Computación, University of Málaga, ETSI Informática (3.2.49), Campus de Teatinos, 29071, Málaga, Spain

    Carlos Cotta & José M. Troya

Authors
  1. Carlos Cotta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José M. Troya
    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

Cotta, C., Troya, J.M. Embedding Branch and Bound within Evolutionary Algorithms. Applied Intelligence 18, 137–153 (2003). https://doi.org/10.1023/A:1021934325079

Download citation

  • Issue Date:

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

Search

Navigation