Kalman-extended genetic algorithm for search in nonstationary environmentswith noisy fitness evaluations

In basic genetic algorithm (GA) applications, the fitness of a solution tak es a value that is certain and unchanging, There are two classes of problem for which this formulation is insufficient. The first consists of ongoing searches for better solutions in a nonstationary environment in which the e xpected fitness of a solution changes with time in unpredictable ways. The second class consists of applications in which fitness evaluations are corr upted by noise. For problems belonging to either or both of these classes, the estimated fitness of a solution will have an associated uncertainty. Bo th the uncertainty due to environmental changes (process noise) and the unc ertainty due to noisy evaluations (observation noise) can be reduced, at le ast temporarily, by re-evaluating existing solutions, The Kalman formulatio n provides a well-developed formal mechanism for treating uncertainty withi n the GA framework. It provides the mechanics for determining the estimated fitness and uncertainty when a new solution is generated and evaluated for the first time. It also provides the mechanics for updating the estimated fitness and uncertainty after an existing solution is re-evaluated and for increasing the uncertainty with the passage of time. A Kalman-extended gene tic algorithm (KGA) is developed to determine when to generate a new indivi dual, when to re-evaluate an existing individual, and which one to re-evalu ate. This KGA is applied to the problem of maintaining a network configurat ion with minimized message loss in which the nodes are mobile and the trans mission over a link is stochastic. As the nodes move, the optimal network c hanges, but information contained within the population of solutions allows efficient discovery of better-adapted solutions. The ability of the. KGA t o continually find near-optimal solutions is demonstrated at several levels of process and observation noise. The sensitivity of the KGA performance t o several control parameters is explored.