اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOptimization by thermal cycling
63
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
An optimization algorithm is presented which consists of cyclically heating and quenching by Metropolis and local search procedures, respectively. It works particularly well when it is applied to an archive of samples instead of to a single one. We demonstrate for the traveling salesman problem that this algorithm is far more efficient than usual simulated annealing; our implementation can compete concerning speed with recent, very fast genetic local search algorithms.
قيم البحث
اقرأ أيضاً
Optimization plays a significant role in many areas of science and technology. Most of the industrial optimization problems have inordinately complex structures that render finding their global minima a daunting task. Therefore, designing heuristics
that can efficiently solve such problems is of utmost importance. In this paper we benchmark and improve the thermal cycling algorithm [Phys. Rev. Lett. 79, 4297 (1997)] that is designed to overcome energy barriers in nonconvex optimization problems by temperature cycling of a pool of candidate solutions. We perform a comprehensive parameter tuning of the algorithm and demonstrate that it competes closely with other state-of-the-art algorithms such as parallel tempering with isoenergetic cluster moves, while overwhelmingly outperforming more simplistic heuristics such as simulated annealing.
We study numerically the cluster structure of random ensembles of two NP-hard optimization problems originating in computational complexity, the vertex-cover problem and the number partitioning problem. We use branch-and-bound type algorithms to obta
in exact solutions of these problems for moderate system sizes. Using two methods, direct neighborhood-based clustering and hierarchical clustering, we investigate the structure of the solution space. The main result is that the correspondence between solution structure and the phase diagrams of the problems is not unique. Namely, for vertex cover we observe a drastic change of the solution space from large single clusters to multiple nested levels of clusters. In contrast, for the number-partitioning problem, the phase space looks always very simple, similar to a random distribution of the lowest-energy configurations. This holds in the ``easy/solvable phase as well as in the ``hard/unsolvable phase.
A quantum-thermal annealing method using a cluster-flip algorithm is studied in the two-dimensional spin-glass model. The temperature (T) and the transverse field (Gamma) are decreased simultaneously with the same rate along a linear path on the T-Ga
mma plane. We found that the additional pulse of the transverse field to the frozen local spins produces a good approximate solution with a low computational cost.
We study interface thermal resistance (ITR) in a system consisting of two dissimilar anharmonic lattices exemplified by Fermi-Pasta-Ulam (FPU) model and Frenkel-Kontorova (FK) model. It is found that the ITR is asymmetric, namely, it depends on how t
he temperature gradient is applied. The dependence of the ITR on the coupling constant, temperature, temperature difference, and system size are studied. Possible applications in nanoscale heat management and control are discussed.
We consider high dimensional random optimization problems where the dynamical variables are subjected to non-convex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constr
aints are modeled by a perceptron constraint satisfaction problem. We show that depending on the density of constraints, one can have different situations. If the number of constraints is small, one typically has a phase where the ground state of the cost function is unique and sits on the boundary of the island of configurations allowed by the constraints. In this case there is an hypostatic number of constraints that are marginally satisfied. If the number of constraints is increased one enters in a glassy phase where the cost function has many local minima sitting again on the boundary of the regions of allowed configurations. At the phase transition point the total number of constraints that are marginally satisfied becomes equal to the number of degrees of freedom in the problem and therefore we say that these minima are isostatic. We conjecture that increasing further the constraints the system stays isostatic up to the point where the volume of available phase space shrinks to zero. We derive our results using the replica method and we also analyze a dynamical algorithm, the Karush-Kuhn-Tucker algorithm, through dynamical mean field theory and we show how to recover the results of the replica approach in the replica symmetric phase.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
