The Annealing Algorithm

هدف پژوهشی که این تک نگاری از آن شکل گرفت، تبدیل آنیل تا حد امکان به یک روال بهینه سازی با هدف عمومی بود. در نگاه اول ممکن است این یک کار ساده به نظر برسد، زیرا فرمول بندی مفهوم آن قابلیت کاربرد برای هر مسئله بهینه سازی ترکیبی را پیشنهاد می کند. تنها چیزی که برای اجرای بازپخت روی چنین مشکلی نیاز است یک نمایش منحصر به فرد برای هر پیکربندی، یک روش برای اندازه‌گیری کیفیت آن و یک رابطه همسایه است. با این حال، برای به دست آوردن نتایج قابل قبول به طور مداوم در یک زمان کوتاه معقول، موارد بسیار بیشتری مورد نیاز است. حتی مشکوک است که آیا می توان مسئله را به گونه ای فرموله کرد که بازپخت به یک رویکرد مناسب برای همه نمونه های یک مسئله بهینه سازی تبدیل شود. به سؤالاتی مانند اینکه بهترین فرمول برای یک نمونه مشخص چیست و چگونه باید این فرآیند را کنترل کرد، باید پاسخ داده شود. اگرچه در سال‌های پس از معرفی این مفهوم در حوزه بهینه‌سازی ترکیبی در سال 1981 پیشرفت‌های زیادی صورت گرفته است، اما برخی از سوالات مهم هنوز پاسخ قطعی ندارند. در این کتاب خواننده پایه های بازپخت را در ارائه ای مستقل و منسجم خواهد یافت. اگرچه آنالوگ فیزیکی که این مفهوم از آن نشأت می‌گیرد در فصل اول ذکر شده است، اما تمام نظریه‌ها در چارچوب زنجیره‌های مارکوف توسعه یافته‌اند. برای دستیابی به درجه بالایی از استقلال مثال، استراتژی‌های انطباقی معرفی شده‌اند.

The goal of the research out of which this monograph grew, was to make annealing as much as possible a general purpose optimization routine. At first glance this may seem a straight-forward task, for the formulation of its concept suggests applicability to any combinatorial optimization problem. All that is needed to run annealing on such a problem is a unique representation for each configuration, a procedure for measuring its quality, and a neighbor relation. Much more is needed however for obtaining acceptable results consistently in a reasonably short time. It is even doubtful whether the problem can be formulated such that annealing becomes an adequate approach for all instances of an optimization problem. Questions such as what is the best formulation for a given instance, and how should the process be controlled, have to be answered. Although much progress has been made in the years after the introduction of the concept into the field of combinatorial optimization in 1981, some important questions still do not have a definitive answer. In this book the reader will find the foundations of annealing in a self-contained and consistent presentation. Although the physical analogue from which the con­ cept emanated is mentioned in the first chapter, all theory is developed within the framework of markov chains. To achieve a high degree of instance independence adaptive strategies are introduced.