Combinatorial optimization based on stochastic relaxation - Revision history

AndreaBonarini at 15:50, 28 April 2011

2011-04-28T15:50:49Z

MatteoMatteucci at 00:54, 16 October 2009

2009-10-16T00:54:59Z

MatteoMatteucci at 00:52, 16 October 2009

2009-10-16T00:52:39Z

MatteoMatteucci: New page: {{ProjectProposal |title=Combinatorial optimization based on stochastic relaxation |image=Stochastic.png |description=The project will focus on the study, implementation, comparison and an...

2009-10-16T00:51:50Z

New page: {{ProjectProposal |title=Combinatorial optimization based on stochastic relaxation |image=Stochastic.png |description=The project will focus on the study, implementation, comparison and an...

New page

{{ProjectProposal
|title=Combinatorial optimization based on stochastic relaxation
|image=Stochastic.png
|description=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
|tutor=MatteoMatteucci; LuigiMalago
|start=2009/10/01
|studmin=1
|studmax=2
|cfumin=5
|cfumax=20
|resarea=Machine Learning
|restopic=Information Geometry; Stochastic Optimization
|level=Ms
|type=Course; Thesis
|status=Active
}}

@@ Line 39: / Line 39: @@
 # 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
 |tutor=MatteoMatteucci; LuigiMalago
 |start=2009/10/01
@@ Line 50: / Line 50: @@
 |level=Ms
 |type=Course; Thesis
-|status=Active
+|status=Closed
 }}

@@ Line 1: / Line 1: @@
 {{ProjectProposal
 |title=Combinatorial optimization based on stochastic relaxation
-|image=Stochastic.png
+|image=Stochastic.jpg
 |description=The project will focus on the study, implementation, comparison and
 analysis of different algorithms for the optimization of pseudo-Boolean

@@ Line 6: / Line 6: @@
 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].
+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
+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
@@ Line 24: / Line 24: @@
 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].
+statistics and MCMC techniques, such as Gibbs and Metropolis samplers (4).
 The project can be extended to master thesis, according to interesting