Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects
Parekh, Pratik Mayur
Loading…
Permalink
https://hdl.handle.net/2142/78688
Description
Title
Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects
Author(s)
Parekh, Pratik Mayur
Issue Date
2015-04-30
Department of Study
Mechanical Sci & Engineering
Discipline
Mechanical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Deterministic Annealing Algorithm
Computational Aspects
Abstract
The deterministic annealing (DA) method, used for the solution of several nonconvex problems, offers the ability to avoid shallow local minima of a given cost surface and the ability to minimize the cost function even when there are many local minima. The method is established in a probabilistic framework through basic information-theoretic techniques such as maximum entropy and random coding. It arises naturally in the context of statistical mechanics by the emulation of a physical process whereby a solid is slowly cooled and at zero temperature assumes its minimum energy configuration. We start with the introduction to DA method and then present a tutorial to describe the algorithm steps. Also, we discuss the connections of DA method with Statistical Mechanics and Rate-Distortion Theory. Next, we present the application of DA method to pickup and deliver scheduling problem with time windows. Finally, a computational complexity analysis for DA is presented for a given temperature schedule. The case study focuses on the geometric cooling law $T(t)=\rho T(t-1), 0<\rho<1$, where $T(t)$ is the temperature at time $t$.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
