Browse wiki

Jump to: navigation, search
Combinatorial optimization based on stochastic relaxation
PrjCFUMax 20  +
PrjCFUMin 5  +
PrjDescription The project will focus on the study, imple The project will focus on the study, implementation, comparison and analysis of different algorithms for the optimization of pseudo-Boolean functions, i.e., functions defined over binary variables with values in R. These functions have been studied a lot in the mathematical programming literature, and different algorithms have been proposed (1). More recently, the same problems have been faced in evolutionary computations, with the use of genetic algorithms, and in particular estimation of distribution algorithms (2,3). Estimation of distribution algorithms are a recent meta-heuristic, where classical crossover and mutation operators used in genetic algorithms are replaced with operators that come from statistics, such as sampling and estimation. The focus will be on the implementation of a new algorithm able to combine different approaches (estimation and sampling, from one side, and exploitation of prior knowledge about the structure of problem, on the other), together with the comparison of the results with existing techniques that historically appear in different (and often separated) communities. Good coding (C/C++) abilities are required. Since the approach will be based on statistical models, the student is supposed to be comfortable with notions that come from probability and statistics courses. The project could require some extra effort in order to build and consolidate some background in math, especially in Bayesian statistics and MCMC techniques, such as Gibbs and Metropolis samplers (4). The project can be extended to master thesis, according to interesting and novel directions of research that will emerge in the first part of the work. Possible ideas may concern the proposal of new algorithms able to learn existing dependencies among the variables in the function to be optimized, and exploit them in order to increase the probability to converge to the global optimum. Picture taken from http://www.ra.cs.uni-tuebingen.de/ Bibliography # Boros, Endre and Boros, Endre and Hammer, Peter L. (2002) Pseudo-boolean optimization. Discrete Applied Mathematics. # Pelikan, Martin; Goldberg, David; Lobo, Fernando (1999), A Survey of Optimization by Building and Using Probabilistic Models, Illinois: Illinois Genetic Algorithms Laboratory (IlliGAL), University of Illinois at Urbana-Champaign. # Larrañga, Pedro; & Lozano, Jose A. (Eds.). Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers, Boston, 2002. # Image Analysis, Random Fields Markov Chain Monte Carlo Methods om Fields Markov Chain Monte Carlo Methods
PrjImage Image:Stochastic.jpg  +
PrjLevel Master of Science +
PrjResArea Machine Learning +
PrjResTopic Information Geometry + , Stochastic Optimization +
PrjStarts 1 October 2009  +
PrjStatus Closed  +
PrjStudMax 2  +
PrjStudMin 1  +
PrjTitle Combinatorial optimization based on stochastic relaxation  +
PrjTutor User:MatteoMatteucci + , User:LuigiMalago +
PrjType Course + , Thesis +
Categories ProjectProposal  +
Modification dateThis property is a special property in this wiki. 28 April 2011 15:50:49  +
hide properties that link here 
  No properties link to this page.
 

 

Enter the name of the page to start browsing from.