Probability Model Based Heuristics maintained by Qingfu Zhang and Jianyong Sun.

 

 

 

Home
Research Groups
Publications
News

 

Please inform me of  your algorithms and any other algorithms that should go into this page.  Thanks.

 

Probability model based heuristics for optimisation and search problems have become popular recently, particularly in the community of evolutionary computation. These heuristics  use probability models to guide their search.

From my point of view, the following algorithms can be classified as probability model based heuristics. 

bullet

Estimation of Distribution Algorithms (EDAs)

A probability model is built based on global statistical information extracted from selected promising solutions. New offspring are then sampled from the model thus built.

EDA homepage maintained by
P. Larraņaga, et. al
 

bullet

Evolution Strategies (ES)

At each generation, new solutions are sampled from a probability model (sampling is often called mutation). The well-known rule to update the model is the 1/5-rule.

ES homepage maintained by I. Rechenberg.

bullet

Ant Colony Optimisation (ACO)

Ant Colony Optimization simulates the behaviour of real ant colonies. Pheromone values define a probability model.

ACO homepge maintained by
M. Dorigo, et. al
 

bullet

Cross Entropy Method (CE)

CE treats an optimisation problem as the estimation of probabilities of "rare events" in complex stochastic networks.

CE homepage maintained by Pieter-Tjerk de Boer

bullet

Monte Carlo Methods for Optimisation Problem (MCM)

The most famous instance of this class is simulated annealing. Based on Monte Carlo strategies, these algorithms try to sample from the target probability distribution which characterizes the best area (points). 

bullet

Learning Automata (LA)

Learning automata have been used for solving noisy optimisation problems in machine learning. A simple version of this algorithm maintains a probability vector at each iteration. An action is randomly taken based on this probability vector. Then it receives a stochastic reward from the environment, which is used to update the probability vector.  

bullet

Global Optimisation Methods Based on Response Surface (RS)

Surrogates for the objective function and constraint functions are built at each iteration for guiding the further search. Often, a probability of improvement is also used in the search.

bullet

Adaptive Multiresolution Search

Regions of high average fitness are sampled on average more than other areas by making the sampling range dependent on the fitness function of the last sample.

 


Last updated: 02/13/04.