Examining the performance of population-based incremental learning and island model population-based incremental learning on a GA-hard problem with a very large search space.

摘要

The performance characteristics of both Population-Based Incremental Learning and Island Model Population-Based Incremental Learning in navigating very large and complex fitness landscapes is explored. A modified solution representation for the knapsack problem designed to increase epistatic effects is used in this research in order to examine the performance of both algorithms. The results demonstrate that for search spaces larger than 2 4000, neither algorithm is a suitable candidate for a system being used to solve binary encoded stationary optimization problems, and that a genetic algorithm producing one-twentieth the solutions per generation can converge to a more optimal solution in a smaller number of generations. However, Island Model Population-Based Incremental Learning is shown to produce higher quality solutions in reduced-round experiments (the number of generations is limited to 100) for all search-space sizes examined.Keywords: Population-based Incremental Learning, Genetic Algorithm, Stationary Optimization Problem, Island Model Population-Based Incremental Learning, Evolutionary Computation, Machine Learning, Genetic Recombination, Knapsack Problem, GA-Hard Problem, Epistasis