Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Achieving Fast Annealing Convergence by the Quantized Mean Field Annealing Algorithm

IP.com Disclosure Number: IPCOM000110270D
Original Publication Date: 1992-Nov-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 3 page(s) / 126K

Publishing Venue

IBM

Related People

Nobakht, RA: AUTHOR

Abstract

In this article, a new annealing algorithm, based on the mean field annealing algorithm and the projections onto convex sets technique, is derived. Emphasis is placed on the set of a priori information, which we project onto, in order to increase the efficiency and the speed of the optimization process.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Achieving Fast Annealing Convergence by the Quantized Mean Field Annealing Algorithm

       In this article, a new annealing algorithm, based on the
mean field annealing algorithm and the projections onto convex sets
technique, is derived.  Emphasis is placed on the set of a priori
information, which we project onto, in order to increase the
efficiency and the speed of the optimization process.

      A central objective in engineering is to develop optimal
solutions to problems.  Unfortunately, many problems of practical
value are difficult to solve due to their combinatorial nature, i.e.,
the quality of their solutions is affected by a large number
(possibly millions) of interacting decisions or degrees of freedom.
Expressed mathematically, a vector a = [a1, a2, ..., aN]T must be
found, which minimizes some function of interest, H(a), that depends
on a in some complex, non-linear way.  Adjustments are made to a
based only upon knowledge of the previous and present H(a); no other
information concerning the system is used.  However, an optimization
problem is always accompanied with some a priori knowledge, which we
shall represent by a collection of propositions {Ka}aeb, where b is a
nonempty index set.  The amount of a priori knowledge depends on our
ingenuity, and the extent of our theoretical and practical
understanding of the physical system under study.  Each piece of a
priori information Ka narrows our ignorance of the true object and
is, therefore, valuable in increasing objectively the efficiency and
speed of the estimate.  Hence, it is sensible to adopt consistency
with all pieces of a priori knowledge, rather than optimality with
respect to some arbitrary standard, as an optimization criterion.
The estimates produced, according to this principal, are constrained
to satisfy only those properties which the true object is known to
possess.

      In the quantized mean field annealing algorithm (QMFA), the
amplitude range for the N parameters of the system are divided into a
contiguous set of M bins {A1,A2,...AM}.  At each temperature, a
randomly selected parameter is stepped through the entire set of M
quantized amplitudes (while leaving the other parameters unchanged),
and the performance measure at each amplitude, Hj (1 & j & M), is
determined either analytically or by simulation.  The selected
parameter is then set to weighted average of the quantized amplitudes
                                                       (1)

                       ...