TL;DR
This paper introduces a novel optimization algorithm, FG-FDA, that uses factor graphs to model complex variable dependencies. By employing symmetric non-negative matrix factorization to learn these factor graphs, FG-FDA efficiently discovers underlying problem structures and generates new solutions, demonstrating strong performance on deceptive and NK landscape problems.
What Problem Does This Paper Address?
Many optimization problems, especially those with "deceptive functions," are challenging for standard genetic algorithms because they fail to learn the underlying structure of variable dependencies (linkage). While Estimation of Distribution Algorithms (EDAs) aim to address this by learning probabilistic models, existing methods often struggle with complex, higher-order interactions or are computationally expensive. The paper highlights that factor graphs are an ideal graphical model for representing these dependencies, but efficient algorithms for learning them have been lacking. This work aims to bridge that gap by proposing a novel factor graph learning algorithm within an EDA framework.
Methods
The core of the proposed Factor Graph based Factorization Distribution Algorithm (FG-FDA) involves three main steps:
- Constructing the Underlying Dependency Graph (UDGP): The algorithm first builds a weighted, undirected graph where vertices represent variables and edge weights signify the strength of pairwise dependencies. Mutual information is used as the metric to quantify these pairwise dependencies. To improve efficiency, weak edges are pruned based on a threshold.
- Factorizing the UDGP into a Factor Graph: This is the most novel part of the approach. The UDGP is transformed into a bipartite graph (a factor graph) using a symmetric non-negative matrix factorization (SNMF) technique. This factorization effectively converts pairwise dependencies into higher-order dependencies represented by factor nodes. The SNMF algorithm is based on minimizing a divergence distance, and its convergence is mathematically proven.
- Generating New Solutions: Once the factor graph is learned, new potential solutions are generated. This involves a "BB-wise crossover" and an "intra-BB search" on the best individual of the population. The intra-BB search aims to find the optimal values for variables within identified building blocks (BBs), and BB-wise crossover then combines these optimized blocks.
Datasets
The paper evaluates FG-FDA on two types of benchmark problems:
- Concatenated Deceptive Functions: These functions are designed to be difficult for standard GAs due to deceptive local optima. The paper uses versions with linkage groups of size 3 and 5.
- Nearest-Neighbor NK Landscapes: These are fitness landscapes known for their complexity, especially with higher values of 'k' (number of neighbors). The paper tests FG-FDA on NK landscapes with k=5.
The paper does not introduce new benchmark datasets.
Key Insights and Ideas
- Factor Graphs as Ideal Models: The paper strongly advocates for factor graphs as the most intuitive and explicit graphical model for representing variable dependencies, offering human-readable insights into problem structure.
- Matrix Factorization for Linkage Learning: The novel application of symmetric non-negative matrix factorization to learn factor graphs from pairwise dependencies is a key contribution, effectively bridging the gap between pairwise metrics and higher-order structural learning.
- Bridging Pairwise to Higher-Order Dependencies: FG-FDA's ability to infer higher-order interactions from pairwise dependency information is crucial for tackling complex problems where direct higher-order measurements might be infeasible.
- Efficiency and Scalability: The algorithm is designed to solve optimization problems in polynomial time with a polynomial number of evaluations, suggesting good scalability.
Key Results
- FG-FDA demonstrated the ability to successfully solve both concatenated deceptive functions and NK landscape problems.
- The algorithm's performance was analyzed in terms of population size and number of fitness evaluations. For concatenated deceptive functions, the population size fit a model of $N \approx a \times m^b \times \ln(m)$, with $b$ values around 1.2-1.5.
- For NK landscapes, the number of fitness evaluations also showed a polynomial relationship with problem size.
- When compared to reference algorithms like BOA and DSMGA on concatenated deceptive functions, FG-FDA generally required a smaller number of fitness evaluations and exhibited slower growth with increasing problem size.
Limitations and Future Work
- Complexity of SNMF: While the SNMF algorithm is proven to converge, its numerical methods for finding local minima might still be computationally intensive for very large-scale problems.
- Hierarchical Problems: The authors suggest that FG-FDA has the potential to solve hierarchical problems by hierarchically factorizing factor nodes, but this is left as a direction for future work.
- Further Analytical Discussions: More in-depth analytical discussions on different problem types and parameter sensitivities, as well as experimental results on explicitly hierarchical problems, are identified as areas for future research.
Summary updated