Optimization of Functions with Factored Evolutionary Algorithms
- Tuesday, December 13, 2016 from 1:00pm to 2:00pm
- Barnard Hall, Room 323 - view map
Factored Evolutionary Algorithms (FEA) define a relatively new class of evolutionary based optimization algorithms that have been successfully applied to various problems, such as training neural networks and performing abductive inference in graphical models. FEA is unique in that it factors the function being optimized by creating subpopulations that optimize over a subset of dimensions of the function. However, unlike other optimization techniques that subdivide optimization problems, FEA encourages subpopulations to overlap with one another, allowing subpopulations to compete and share information. While FEA has been shown to be very effective at function optimization, there is still little understanding with respect to its general characteristics. In this dissertation, we present seven results exploring theoretical and empirical properties of FEA.
First, we present a formal definition of FEA and demonstrate its relationships to other multiple population algorithms. Second, we demonstrate that for a given problem, there exists an optimal way to generate groups of overlapping subpopulations derived from using the Markov blanket in Bayesian networks. Third, we establish that a class of optimization functions like NK landscapes can be mapped directly to probabilistic graphical models. Additionally, we demonstrate that factor architectures derived from Markov blankets maintain better diversity of their individuals. Fourth, we demonstrate that FEA's success is independent of the underlying optimization algorithm by evaluating the performance of FEA using a wide variety of evolutionary and swarm based algorithms over single population and non-overlapping versions. Fifth, we present a new discrete Particle Swarm Optimization (PSO) algorithm and show its performance as compared to competing approaches. In addition, we analyze the performance of FEA versions of discrete PSO and discover that FEA masks the poor performance of search algorithms. Sixth, we show what conditions are necessary for FEA to converge and scenarios where FEA may become stuck in suboptimal regions in the search space. Finally, we explore the performance of FEA on unitation functions and discover several instances where FEA struggles to outperform single population algorithms. These results allow us to determine which situations are appropriate for FEA when using solving real-world problems.