# A factor graph based genetic algorithm

B. Hoda Helmi; Adel T. Rahmani; Martin Pelikan

International Journal of Applied Mathematics and Computer Science (2014)

- Volume: 24, Issue: 3, page 621-633
- ISSN: 1641-876X

## Access Full Article

top## Abstract

top## How to cite

topB. Hoda Helmi, Adel T. Rahmani, and Martin Pelikan. "A factor graph based genetic algorithm." International Journal of Applied Mathematics and Computer Science 24.3 (2014): 621-633. <http://eudml.org/doc/271878>.

@article{B2014,

abstract = {We propose a new linkage learning genetic algorithm called the Factor Graph based Genetic Algorithm (FGGA). In the FGGA, a factor graph is used to encode the underlying dependencies between variables of the problem. In order to learn the factor graph from a population of potential solutions, a symmetric non-negative matrix factorization is employed to factorize the matrix of pair-wise dependencies. To show the performance of the FGGA, encouraging experimental results on different separable problems are provided as support for the mathematical analysis of the approach. The experiments show that FGGA is capable of learning linkages and solving the optimization problems in polynomial time with a polynomial number of evaluations.},

author = {B. Hoda Helmi, Adel T. Rahmani, Martin Pelikan},

journal = {International Journal of Applied Mathematics and Computer Science},

keywords = {optimization problems; genetic algorithms; estimation of distribution algorithms; factor graph; matrix factorization},

language = {eng},

number = {3},

pages = {621-633},

title = {A factor graph based genetic algorithm},

url = {http://eudml.org/doc/271878},

volume = {24},

year = {2014},

}

TY - JOUR

AU - B. Hoda Helmi

AU - Adel T. Rahmani

AU - Martin Pelikan

TI - A factor graph based genetic algorithm

JO - International Journal of Applied Mathematics and Computer Science

PY - 2014

VL - 24

IS - 3

SP - 621

EP - 633

AB - We propose a new linkage learning genetic algorithm called the Factor Graph based Genetic Algorithm (FGGA). In the FGGA, a factor graph is used to encode the underlying dependencies between variables of the problem. In order to learn the factor graph from a population of potential solutions, a symmetric non-negative matrix factorization is employed to factorize the matrix of pair-wise dependencies. To show the performance of the FGGA, encouraging experimental results on different separable problems are provided as support for the mathematical analysis of the approach. The experiments show that FGGA is capable of learning linkages and solving the optimization problems in polynomial time with a polynomial number of evaluations.

LA - eng

KW - optimization problems; genetic algorithms; estimation of distribution algorithms; factor graph; matrix factorization

UR - http://eudml.org/doc/271878

ER -

## References

top- Abbeel, P., Koller, D. and Ng, A.Y. (2006). Learning factor graphs in polynomial time and sample complexity, Journal of Machine Learning Research 7: 1743-1788. Zbl1222.68128
- Gámez, J.A., Mateo, J.L. and Puerta, J.M. (2008). Improved EDNA (estimation of dependency networks algorithm) using combining function with bivariate probability distributions, Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO'08, Atlanta, GA, USA, pp. 407-414.
- Kschischang, F.R., Frey, B.J. and Loeliger, H.A. (2001). Factor graphs and the sum-product algorithm, IEEE Transactions on Information Theory 47(2): 498-519. Zbl0998.68234
- Kuang, D., Park, H. and Ding, C.H.Q. (2012). Symmetric nonnegative matrix factorization for graph clustering, Proceedings of the 12 SIAM International Conference on Data Mining, Anaheim, CA, USA, pp. 106-117.
- Larrañaga, P. and Lozano, J.A. (2001). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA. Zbl0979.00024
- Lee, D.D. and Seung, H.S. (2001). Algorithms for non-negative matrix factorization, in T.K. Leen, T.G. Dietterich and V. Tresp (Eds.), Advances in Neural Information Processing Systems 13, MIT Press, Cambridge, MA, pp. 556-562.
- Mahnig, T. and Mühlenbein, H. (1999). FDA-a scalable evolutionary algorithm for the optimization of additively decomposed functions, Evolutionary Computation, 7(4): 353-376.
- Mendiburu, A., Santana, R. and Lozano, J.A. (2007). Introducing belief propagation in estimation of distribution algorithms: A parallel approach, Technical Report EHUKAT-IK-11-07, University of the Basque Country, Bilbao. Zbl1251.68211
- Miquelez, T., Bengoetxea, E. and Larrañaga, P. (2004). Evolutionary computation based on Bayesian classifiers, International Journal of Applied Mathematics and Computer Science 14(3): 335-349. Zbl1084.90538
- Mühlenbein, H. (2008). Convergence of estimation of distribution algorithms for finite samples, Technical report, Fraunhofer Institute for Autonomous Intelligent Systems, Sankt Augustin.
- Mühlenbein, H. (2012). Convergence theorems of estimation of distribution algorithms, in S. Shakya and R. Santana (Eds.), Markov Networks in Evolutionary Computation, Adaptation, Learning, and Optimization, Vol. 14, Springer, Berlin/Heidelberg, pp. 91-108. Zbl1251.68212
- Mühlenbein, H. and Paaß, G. (1996). From recombination of genes to the estimation of distributions, I: Binary parameters, in H.M. Voigt, W. Ebeling, I. Rechenberger and H.P. Schwefel (Eds.), Parallel Problem Solving from Nature IV, Vol. 1141, Lecture Notes in Computer Science, Springer-Verlag, London, pp. 178-187.
- Munetomo, M. and Goldberg, D.E. (1999). Identifying linkage groups by nonlinearity/nonmonotonicity detection, Genetic and Evolutionary Computation Conference (GECCO-99), Orlando, FL, USA, pp. 433-440.
- Pelikan, M. (2005). Hierarchical Bayesian Optimization Algorithm, Springer-Verlag, Berlin/Heidelberg. Zbl1107.68084
- Pelikan, M., Goldberg, D.E. and Lobo, F.G. (2002). A survey of optimization by building and using probabilistic models, Computational Optimization and Applications 21(1): 5-20. Zbl0988.90052
- Pelikan, M., Hauschild, M., and Thierens, D. (2011). Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm, MEDAL Report No. 2011001, University of Missouri at St. Louis, St. Louis, MO.
- Santana, R., Larraaga, P. and Lozano, J. (2008). Adaptive estimation of distribution algorithms, in C. Cotta, M. Sevaux and K. Srensen (Eds.), Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence, Vol. 136, Springer, Berlin/Heidelberg, pp. 177-197.
- Sastry, K. and Goldberg, D. (2004). Designing competent mutation operators via probabilistic model building of neighborhoods, in K. Deb (Ed.), Genetic and Evolutionary Computation, GECCO 2004, Lecture Notes in Computer Science, Vol. 3103, Springer, Berlin/Heidelberg, pp. 114-125.
- Sastry, K. and Goldberg, D. E. (2000). On extended compact genetic algorithm, IlliGAL Report No. 2000026, University of Illinois at Urbana-Champaign, Urbana, IL.
- Thierens, D. (2010). Linkage tree genetic algorithm: First results, Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO'10), Portland, OR, USA, pp. 1953-1958.
- Yu, K., Yu, S. and Tresp, V. (2006). Soft clustering on graphs, in Y. Weiss, B. Schölkopf and J. Platt (Eds.), Advances in Neural Information Processing Systems 18, MIT Press, Cambridge, MA, pp. 1553-1560.
- Yu, T.-L. (2006). A Matrix Approach for Finding Extrema: Problems with Modularity, Hierarchy, and Overlap, Ph.D. thesis, University of Illinois at Urbana-Champaign, Champaign, IL.
- Yu, T.-L. and Goldberg, D.E. (2006). Conquering hierarchical difficulty by explicit chunking: Substructural chromosome compression, 8th Annual Conference on Genetic and Evolutionary Computation, (GECCO-2006), Seattle, WA, USA, pp. 1385-1392.
- Yu, T.-L., Sastry, K., Goldberg, D. E. and Pelikan, M. (2007). Population sizing for entropy-based model building in discrete estimation of distribution algorithms, Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO '07, London, UK, pp. 601-608.
- Zhou, D., Schölkopf, B. and Hofmann, T. (2005). Semi-supervised learning on directed graphs, in L.K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in Neural Information Processing Systems 17, MIT Press, Cambridge, MA, pp. 1633-1640.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.