A study of the effectiveness of detailed balance in avoiding convergence in PBIL

Correa, ES and Shapiro, JL 2004, 'A study of the effectiveness of detailed balance in avoiding convergence in PBIL' , in: Applications and Science in Soft Computing , Advances in Soft Computing, 24 , Springer Berlin Heidelberg, pp. 255-260.

[img] PDF - Draft Version
Restricted to Repository staff only

Download (284kB)

Abstract

Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that use statistical information to guide the exploration of the search space. A prominent problem in EDAs is the loss of variability as the search progresses. This occurs because at each iteration the probabilistic model reinforces the probability of generating the best solutions found in the previous populations. This process may accelerate convergence to local optima. This paper investigates a method to diminish this convergence pressure by applying “detailed balance” to the Population Based Incremental Learning (PBIL) algorithm [4]. Detailed balance is a well-known condition in Markov chains. Basically, it says that, on a flat fitness landscape, the probability of going from a state i to a state j must be the same as the probability of going backwards from state j to state i. This condition slows the rate of convergence of the probability parameters when the landscape is flat. As a result, the algorithm requires more evidence from the fitness function to drive the search to a single point in the search space and maintains variability for longer.

Item Type: Book Section
Editors: Lotfi, A and Garibaldi, JM
Schools: Schools > School of Computing, Science and Engineering > Salford Innovation Research Centre (SIRC)
Publisher: Springer Berlin Heidelberg
Series Name: Advances in Soft Computing
ISBN: 9783540408567
Depositing User: Dr Elon Correa
Date Deposited: 10 Feb 2017 15:26
Last Modified: 08 Aug 2017 22:38
URI: http://usir.salford.ac.uk/id/eprint/41387

Actions (login required)

Edit record (repository staff only) Edit record (repository staff only)

Downloads

Downloads per month over past year