Preference Disaggregation
- PDF / 12,592,618 Bytes
- 143 Pages / 594 x 828 pts Page_size
- 21 Downloads / 183 Views
pB(T;R) = f exp[-ZY(R)] dR' where ~ _= 1/ksT is the inverse temperature (ks is Boltzmann's constant which relates the energy and temperature scales). As T -+ 0, all probability is concentrated in the vicinity of the global minimum, Rg, of V. Simulated annealing attempts to find Rg by following PB(~; R) as the system is cooled using the Metropolis [5] or other (e.g., molecular dynamics) search procedures to simultaneously search the entire space. In contrast, during cooling, packet annealing recursively subdivides conformation space into a sequence of compact macrostate regions which are separated from each other by potential energy barri-
ers that are large compared to the current T. By this means, the space is subdivided into a growing number of smaller and smaller macrostates which are searched in parallel. The hierarchical relationships between the macrostates are represented in tree-like macrostate trajectory diagrams which describe the thermodynamic properties of the macrostates as functions of temperature. This allows computational effort to be focussed on the most promising subregions of conformation space. A key feature is that both the characteristic energetic and spatial scales of each macrostate are computed during the search process so that each macrostate can be searched using appropriately coarse-grained energetic and spatial variables. The nature of the linkage between these scales, the scaling properties of the system, determines the difficulty of finding the minimum. For illustration, consider the problem of finding the global minimum of the two-dimensional potential shown in Fig. la. At a high temperature where kBT exceeds the internal energy barriers (right panel, Fig. lb), the probability distribution is spread fairly smoothly over a compact region and can be coarsely approximated by a single Gaussian characteristic packet ¢0a (right panel, Fig. lc) which is characterized by its centroid (vector R °) and root-mean-square size (tensor A°a) (Fig. ld). As T is reduced to the point where the central energy barrier becomes larger than kBT, the distribution bifurcates into two lobes ~ and which can be approximated by two child packets (center panels, Fig. lb, Fig. lc, Fig. ld). As temperature is further decreased, ~ bifurcates into two children 5 and e (left panels). By this tern-
Packet annealing perature it is evident that the peak within the ¢~ packet corresponds to the global m i n i m u m of V. While this could be found by a random search (as in simulated annealing), it is clear that it would be more efficient to use the hierarchically coarsegrained structure manifested by the characteristic packet analysis to direct the search.
4B
a
b
Ps C
¢0
o®
©o A%
EQ
e
.y /
e
i
Tlo
Treed > Tlo. C) Superposition of the Gaussian packets that are solutions of the characteristic packet equations at the three tem
Data Loading...
