Abstract
Algorithms based on the variational approach, as used in statistical physics, are developed. For constraint satisfaction problems a novel cost function, based on information-theoretic arguments, is introduced, and an algorithm similar to the mean-field annealing algorithm is proposed. It outperforms the conventional mean-field algorithm, and its performance is comparable to good problem-dedicated heuristics for KSAT and graph coloring. For nonlinear assignment problems, improvements to mean-field annealing algorithms based on Potts spins are suggested, and confirmed for TSP. Also a more proper variational approach to assignment problems is proposed and analysed. A novel variational approximation to maximum likelihood is introduced and applied to phylogeny reconstruction. In tests on artificial and real DNA-sequences, the performance is seen to be comparable to that of standard maximum likelihood for reasonably similar sequences.
Original language | English |
---|---|
Qualification | Doctor |
Awarding Institution | |
Supervisors/Advisors |
|
Award date | 2001 Dec 14 |
Publisher | |
ISBN (Print) | 91-7874-161-1 |
Publication status | Published - 2001 |
Bibliographical note
Defence detailsDate: 2001-12-14
Time: 10:15
Place: Lecture hall F, Department of Theoretical Physics
External reviewer(s)
Name: Monasson, Remi
Title: [unknown]
Affiliation: [unknown]
---
Subject classification (UKÄ)
- Biophysics
Free keywords
- statistical physics
- gravitation
- relativity
- annealing
- variational
- mean-field
- phylogeny
- constraint satisfaction
- combinatorial optimization
- maximum likelihood
- Physics
- Fysik
- Mathematical and general theoretical physics
- quantum mechanics
- classical mechanics
- klassisk mekanik
- kvantmekanik
- relativitet
- statistisk fysik
- termodynamik
- Fysicumarkivet A:2001:Jönsson
- Matematisk och allmän teoretisk fysik
- thermodynamics