Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning - Robotics Institute Carnegie Mellon University

Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning

Shumeet Baluja
Tech. Report, CMU-CS-94-163, Computer Science Department, Carnegie Mellon University, June, 1994

Abstract

Genetic algorithms (GAS) are biologically motivated adaptive systems which have been used, with varying degrees of success, for function optimization. In this study, an abstraction of the basic genetic algorithm, the Equilibrium Genetic Algorithm (EGA), and the GA in turn, are reconsidered within the framework of competitive learning. This new perspective reveals a number of different possibilities for performance improvements. This paper explores population-based incremental learning (PBIL), a method of combining the mechanisms of a generational genetic algorithm with simple competitive learning. The combination of these two methods reveals a tool which is far simpler than a GA, and which out-performs a GA on large set of optimization problems in terms of both speed and accuracy. This paper presents an empirical analysis of where the proposed technique will outperform genetic algorithms, and describes a class of problems in which a genetic algorithm may be able to perform better. Extensions to this algorithm are discussed and analyzed. PBE and extensions are compared with a standard GA on twelve problems, including standard numerical optimization functions, traditional GA test suite problems, and NP-complete problems.

BibTeX

@techreport{Baluja-1994-15981,
author = {Shumeet Baluja},
title = {Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning},
year = {1994},
month = {June},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-CS-94-163},
}