A factor graph based genetic algorithm

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.

• Publication year

  2014

• Venue

  International Journal of Applied Mathematics and Computer Sciences

• Publication date

  2014-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.2478/amcs-2014-0045
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Symmetric Nonnegative Matrix Factorization for Graph Clustering

  2012cited by this paper
• Convergence Theorems of Estimation of Distribution Algorithms

  2012cited by this paper
• Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm

  2011cited by this paper
• Linkage tree genetic algorithm: first results

  2010cited by this paper
• Adaptive Estimation of Distribution Algorithms

  2008cited by this paper
• Improved EDNA (estimation of dependency networks algorithm) using combining function with bivariate probability distributions

  2008cited by this paper
• Convergence of Estimation of Distribution Algorithms for Finite Samples

  2007cited by this paper
• Population sizing for entropy-based model building in discrete estimation of distribution algorithms

  2007cited by this paper
• Hierarchical Bayesian Optimization Algorithm

  2006cited by this paper
• Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression

  2006influential reference
• Learning Factor Graphs in Polynomial Time and Sample Complexity

  2006influential reference
• A Matrix Approach for Finding Extrema: Problems With Modularity, Hierarchy, and Overlap

  2006cited by this paper
• Soft Clustering on Graphs

  2005cited by this paper
• Evolutionary computation based on Bayesian classifiers

  2004cited by this paper
• Extended Compact Genetic Algorithm

  2004cited by this paper
• Semi-supervised Learning on Directed Graphs

  2004cited by this paper
• Designing Competent Mutation Operators Via Probabilistic Model Building of Neighborhoods

  2004influential reference
• Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation

  2001cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• A Survey of Optimization by Building and Using Probabilistic Models

  2000cited by this paper
• Algorithms for Non-negative Matrix Factorization

  2000cited by this paper
• Identifying Linkage Groups by Nonlinearity/Non-monotonicity Detection

  1999cited by this paper
• FDA -A Scalable Evolutionary Algorithm for the Optimization of Additively Decomposed Functions

  1999cited by this paper
• From Recombination of Genes to the Estimation of Distributions I. Binary Parameters

  1996cited by this paper

• Gray-box optimization and factorized distribution algorithms: where two worlds collide

  2017cites this paper
• A comprehensive survey on formal concept analysis, its research trends and applications

  2016cites this paper
• A review of message passing algorithms in estimation of distribution algorithms

  2016cites this paper
• Genetic and combinatorial algorithms for optimal sizing and placement of active power filters

  2015cites this paper
• A Probabilistic Evolutionary Optimization Approach to Compute Quasiparticle Braids

  2014cites this paper