Abstract
In this paper the optimization of additively decomposed discrete functions is investigated. For these functions genetic algorithms have exhibited a poor performance. First the schema theory of genetic algorithms is reformulated in probability theory terms. A schema defines the structure of a marginal distribution. Then the conceptual algorithm BEDA is introduced. BEDA uses a Boltzmann distribution to generate search points. From BEDA a new algorithm, FDA, is derived. FDA uses a factorization of the distribution. The factorization captures the structure of the given function. The factorization problem is closely connected to the theory of conditional independence graphs. For the test functions considered, the performance of FDA—in number of generations till convergence—is similar to that of a genetic algorithm for the OneMax function. This result is theoretically explained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts, E.H., H.M. Korst, and P.J. van Laarhoven. (1997). “Simulated Annealing.” In E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization. Chichester: Wiley, pp 121–136.
Baluja, S. and S. Davies. (1997). “Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space,” Carnegie Mellon Report CMU-CS-97-107.
De Bonet, J.S., Ch.L. Isbell, and P. Viola. (1997). “MIMIC: Finding Optima by Estimating Probability Densities.” In M. Mozer, M. Jordan, and Th. Petsche (eds.), Advances in Neural Information Processing Systems, vol. 9.
Dechter, R., A. Dechter, and J. Pearl. (1990). “Optimization in Constraint Networks.” In Oliver R.M. and J.Q. Smith (eds.), Influence Diagrams, Belief Nets and Decision Analysis. New York: Wiley, pp. 411–426.
de la Maza, M. and B. Tidor. (1993). “An Analysis of Selection Procedures with Particular Attention Paid to Proportional and Boltzmann Selection.” In S. Forrest (ed.), Proc. of the Fifth Int. Conf. on Genetic Algorithms. San Mateo, CA: Morgan Kaufman, pp. 124–131.
Forrest, S. and M. Mitchell. (1993). “What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation,” Machine Learning 13, 285–319.
Frey, B.J. (1998). Graphical Models for Machine Learning and Digital Communication. Cambridge: MIT Press.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison-Wesley.
Goldberg, D.E., K. Deb, H. Kargupta, and G. Harik. (1993). “Rapid, Accurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms. In S. Forrest (ed.), Proc. of the Fifth Int. Conf. on Genetic Algorithms. San Mateo, CA: Morgan Kaufman, pp. 56–64.
Holland, J. (1992). Adaptation in Natural And Artificial Systems. Cambridge: MIT Press.
Kargupta, H. and D.E. Goldberg. (1997). “SEARCH, Blackbox Optimization, and Sample Complexity.” In R.K. Belew and M. Vose (eds.), Foundations of Genetic Algorithms 4. San Mateo, CA: Morgan Kaufman.
Kargupta, H. (1997). Revisiting the GEMGA: Scalable Evolutionary Optimization Through Linkage Learning. Personal Communication.
Lauritzen, S.L. (1996). Graphical Models. Oxford: Clarendon Press.
Lawler, E.L. (1976). Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston.
Mühlenbein, H. and D. Schlierkamp-Voosen. (1993a). “Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter Optimization,” Evolutionary Computation 1, 25–49.
Mühlenbein, H. and D. Schlierkamp-Voosen. (1993b). “The Science of Breeding and its Application to the Breeder Genetic Algorithm,” Evolutionary Computation 1, 335–360.
Mühlenbein, H. (1998). “The Equation for Response to Selection and its Use for Prediction, Evolutionary Computation 5, 303–346.
Mühenbein, H. and Th. Mahnig. (1999a). “Convergence Theory and Applications of the Factorized Distribution Algorithm, Journal of Computing and Information Technology, to appear.
Mühlenbein, H. and Th. Mahnig. (1999b). FDA—A Scalable Evolutionary Algorithm for the Optimization of Additively Decomposed Discrete Functions, Evolutionary Compilation, to appear.
Mühlenbein, H. and G. Paaß. (1996). “From Recombination of Genes to the Estimation of Distributions I. Binary Parameters.” In Voigt, H.-M. et al. (eds.), Lecture Notes in Computer Science 1141: Parallel Problem Solving from Nature—PPSN IV. Berlin: Springer, pp. 178–187.
Pelikan, M. and H. Mühlenbein. (1999). “The Bivariate Marginal Distribution Algorithm.” In R. Roy, T. Furuhashi, and P.K. Chawdhry (eds.), Advances in Soft Computing—Engineering Design and Manufacturing. Berlin: Springer-Verlag, pp. 521–535.
Tanese, R. (1989). “Distributed Genetic Algorithms for Function Optimization.” Unpublished doctoral dissertation, University of Michigan, Ann Arbor.
Toulouse, G. (1977). “Optimal Graph Matching for 2D Ising Models,” Commun. Phys. 2, 115–119.
Whitley, D., R. Beveridge, C. Graves, and K. Mathias. (1995). “Test Driving Three 1995 Genetic Algorithms: New Test Functions and Geometric Matching,” Journal of Heuristics 1, 77–104.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mühlenbein, H., Mahnig, T. & Rodriguez, A.O. Schemata, Distributions and Graphical Models in Evolutionary Optimization. Journal of Heuristics 5, 215–247 (1999). https://doi.org/10.1023/A:1009689913453
Issue Date:
DOI: https://doi.org/10.1023/A:1009689913453