Жақындыққа негізделген оптимизация және метаэвристикалық әдістер
Simulated annealing
Жасанды қайнату (SA) – жаһандық оңтайландыруға қолданылатын ықтималдық әдіс. Үлкен іздеу кеңістігінде жақсы нәтиже береді, дәл алгоритмдерден артықшылығы бар.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ықтималдық оптимизация техникасы және метаэвристика
Probabilistic optimization technique and metaheuristic
Модельдеу арқылы оттеу (SA) – берілген функцияның жаһандық оптимумын жуықтап табуға арналған ықтималдық техника. Нақтырақ айтқанда, бұл оптимизациялық мәселенің кең іздеу кеңістігінде жаһандық оптимизацияны жуықтап табуға арналған метаэвристика. Көптеген жергілікті оптимумдар болған жағдайда, SA жаһандық оптимумды таба алады. Ол көбінесе іздеу кеңістігі дискретті болған кезде қолданылады (мысалы, сатушының саяхаты мәселесі, бульдік қанағаттандыру мәселесі, белок құрылымын болжау және жұмыс кестесін жоспарлау). Белгілі бір уақыт ішінде нақты жергілікті оптимумды табудан гөрі шамамен жаһандық оптимумды табу маңыздырақ болған мәселелер үшін, градиенттік түсу немесе тармақталу және шектеу сияқты нақты алгоритмдерге қарағанда модельдеу арқылы оттеу әдісі артықшылықты болуы мүмкін. Алгоритмнің атауы металлургиядағы оттеу процесінен алынған, ол материалдың физикалық қасиеттерін өзгерту үшін материалды қыздыру және бақыланатын салқындатуды қамтитын техника. Бұл екеуі де материалдың термодинамикалық еркін энергиясына байланысты қасиеттері. Материалды қыздыру және салқындату температураға да, термодинамикалық еркін энергияға немесе Гиббс энергиясына да әсер етеді. Модельдеу арқылы оттеуді нақты алгоритмдердің сәтсіз аяқталуы мүмкін өте қиын есептеулік оптимизациялық мәселелерде қолдануға болады; әдетте ол жаһандық минимумға жуық шешімге қол жеткізсе де, көптеген практикалық мәселелер үшін бұл жеткілікті болуы мүмкін. SA арқылы шешілетін мәселелер қазіргі уақытта көптеген айнымалылардың объективтік функциясы арқылы формулировкаланады, олар бірнеше математикалық шектеулерге бағынады. Іс жүзінде, шектеулерді объективтік функцияның бір бөлігі ретінде жазалауға болады. Осыған ұқсас техникалар бірнеше рет тәуелсіз түрде ұсынылған, соның ішінде Пинкус (1970), Хачатурян және басқалар (1979, 1981), Киркпатрик, Гелат және Векки (1983) және Серни (1985). 1983 жылы Киркпатрик, Гелат кіші, Векки бұл тәсілді немесе стохастикалық үлгі алу әдісін қолданды. Бұл әдіс – термодинамикалық жүйенің үлгілік күйлерін жасауға арналған Монте-Карло әдісі Metropolis–Hastings алгоритмінің бейімделуі, ол 1953 жылы Н. Метрополис және басқалармен жарияланған.
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete (for example the traveling salesman problem, the boolean satisfiability problem, protein structure prediction, and job shop scheduling). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound. The name of the algorithm comes from annealing in metallurgy, a technique involving heating and controlled cooling of a material to alter its physical properties. Both are attributes of the material that depend on their thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy or Gibbs energy. Simulated annealing can be used for very hard computational optimization problems where exact algorithms fail; even though it usually achieves an approximate solution to the global minimum, it could be enough for many practical problems. The problems solved by SA are currently formulated by an objective function of many variables, subject to several mathematical constraints. In practice, the constraint can be penalized as part of the objective function. Similar techniques have been independently introduced on several occasions, including Pincus (1970), Khachaturyan et al (1979, 1981), Kirkpatrick, Gelatt and Vecchi (1983), and Cerny (1985). In 1983, this approach was used by Kirkpatrick, Gelatt Jr., Vecchi, or by using a stochastic sampling method. The method is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, published by N. Metropolis et al. in 1953.
Шолу
Кейбір физикалық жүйелердің s күйі және E(s) функциясы, сол күйдегі жүйенің ішкі энергиясына ұқсас. Мақсат – жүйені кез келген бастапқы күйден, ең төменгі мүмкін энергияға ие күйге жеткізу.
The state s of some physical systems, and the function E(s) to be minimized, is analogous to the internal energy of the system in that state. The goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.
Негізгі қайталау
Әрбір қадамда, симуляцияланған оттану эвристикасы ағымдағы күйдің s кейбір көршілес күйін s* қарастырады және ықтималдық бойынша жүйені s* күйіне көшіруге немесе s күйінде қалуға шешім қабылдайды. Бұл ықтималдықтар нәтижесінде жүйе төмен энергиялы күйлерге жылжиды. Әдетте, бұл қадам жүйе қолданбаға жеткілікті жақсы күйге жеткенше немесе белгілі бір есептеу шығыны сарланғанша қайталанады.
At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in state s. These probabilities ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.
Мемлекеттің көршілері
Шешімді оңтайландыру – проблеманың күйлерінің көршілерін бағалауды қамтиды, олар берілген күйді консервативті түрде өзгерту арқылы туындайтын жаңа күйлер. Мысалы, саяхатшы сатушысы мәселесінде әр күй әдетте сапарлау қажетті қалалардың орналасу реті ретінде анықталады, ал кез келген күйдің көршілері – осы қалалардың кез келген екеуін ауыстыру арқылы алынған орналасулар жиынтығы болып табылады. Күйлердің көршілес күйлерді жасау үшін өзгеруі "қимыл" деп аталады, ал әртүрлі қимылдар көршілес күйлердің әртүрлі жиынтығын береді. Бұл қимылдар көбінесе соңғы күйде минималды өзгерістерге алып келеді, бұл шешімді оның бөліктерін итеративті түрде жақсарту арқылы (саяхатшы сатушысы мәселесіндегі қала байланыстары сияқты) жақсартуға тырысады. Жақсы көршіні тауып, жақсы көрші болмағанда тоқтайтын, тауға өрлеу сияқты қарапайым эвристикалар, ең жақсы шешімге жетуін кепілдік бере алмайды. Олардың нәтижесі оңай ғана жергілікті оптимум болуы мүмкін, ал нақты ең жақсы шешім – жаһандық оптимум, ол басқаша болуы мүмкін. Метаэвристикалар шешім кеңістігін зерттеу үшін шешімнің көршілерін пайдаланады, және олар жақсы көршілерді қалаумен қатар, жергілікті оптимумдарда тұрып қалудан аулақ болу үшін нашар көршілерді де қабылдайды; олар жеткілікті ұзақ уақыт жұмыс істесе, жаһандық оптимумды таба алады.
Optimization of a solution involves evaluating the neighbors of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the traveling salesman problem each state is typically defined as a permutation of the cities to be visited, and the neighbors of any state are the set of permutations produced by swapping any two of these cities. The well defined way in which the states are altered to produce neighboring states is called a "move", and different moves give different sets of neighboring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem). Simple heuristics like hill climbing, which move by finding better neighbor after better neighbor and stop when they have reached a solution which has no neighbors that are better solutions, cannot guarantee to lead to any of the existing better solutions their outcome may easily be just a local optimum, while the actual best solution would be a global optimum that could be different. Metaheuristics use the neighbors of a solution as a way to explore the solution space, and although they prefer better neighbors, they also accept worse neighbors in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time.
Жарықтау кестесі
Алгоритмнің атауы мен оған түрткі болған идея алгоритмнің жұмыс істеу қасиеттеріне температураның өзгеруімен байланысты қызықты ерекшелікті енгізуді талап етеді. Бұл симуляция жүрген сайын температураны біртіндеп төмендетуді қажет етеді. Алгоритм бастапқыда жоғары мәнге (немесе шексіздікке) орнатылады, содан кейін әр қадамда белгілі бір оттеу кестесі бойынша азаяды – бұл кесте пайдаланушымен анықталуы мүмкін, бірақ бөлінген уақыттың соңына қарай аяқталуы керек. Осылайша, жүйе бастапқыда энергия функциясының ұсақ ерекшеліктерін назарға алмай, жақсы шешімдері бар іздеу кеңістігінің кең аймағына қарай бағытталатыны күтіледі; содан кейін энергиясы төмен аймақтарға қарай қозғалады, олар тарылып, тарылып, ақырында ең тік төмен түсу эвристикасы бойынша төмен қарай жылжиды. Кез келген шекті мәселе үшін, симуляцияланған оттеу алгоритмінің жаһандық оңтайлы шешіммен аяқталу ықтималдығы оттеу кестесі ұзартылғанда 1-ге жақымдасады. Дегенмен, бұл теориялық нәтиже аса пайдалы емес, себебі сәттілік ықтималдығын қамтамасыз ету үшін қажетті уақыт көбінесе шешім кеңістігін толық іздеуге кеткен уақыттан асып түседі.
The name and inspiration of the algorithm demand an interesting feature related to the temperature variation to be embedded in the operational characteristics of the algorithm. This necessitates a gradual reduction of the temperature as the simulation proceeds. The algorithm starts initially with set to a high value (or infinity), and then it is decreased at each step following some annealing schedule—which may be specified by the user but must end with towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low energy regions that become narrower and narrower, and finally move downhill according to the steepest descent heuristic. For any given finite problem, the probability that the simulated annealing algorithm terminates with a global optimal solution approaches 1 as the annealing schedule is extended. This theoretical result, however, is not particularly helpful, since the time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.
Параметрлерді таңдау
Нақты бір мәселеге симуляциялық оттану әдісін қолдану үшін келесі параметрлерді анықтау қажет: күй кеңістігі, энергия (мақсат) функциясы, кандидаттарды жасау процедурасы, қабылдау ықтималдығы функциясы, оттеу кестесі ЖӘНЕ бастапқы температура. Бұл таңдаулар әдістің тиімділігіне маңызды әсер етеді. Анығында, барлық мәселелер үшін жақсы болатын параметрлердің жиынтығы жоқ, сондай-ақ, нақты мәселе үшін ең жақсы таңдауларды табудың жалпы әдісі де жоқ. Келесі бөлімдерде осы мәселені шешуге көмектесетін жалпы ұсыныстар келтіріледі.
In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function , the candidate generator procedure , the acceptance probability function , and the annealing schedule AND initial temperature These choices can have a significant impact on the method's effectiveness. Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem. The following sections give some general guidelines.
Көршіге жеткілікті жақын
Эмоционалды оттепелеуді іздеу графигіндегі кездейсоқ серуендеу ретінде модельдеуге болады, ондағы төбелер барлық мүмкін күйлерді, ал қабырғалар – үміткер амалдарды білдіреді. Функцияның маңызды талабы – бастапқы күйден жаһандық оптимум болуы мүмкін кез келген күйге дейін осы графикте жеткілікті қысқа жол қамтамасыз етуі керек. Іздеу графигінің диаметрі шағын болуы тиіс. Мысалы, жоғарыдағы саяхатшы сатушысы мысалында, n = 20 қала үшін іздеу кеңістігі n! = 2,432,902,008,176,640,000 (2.4 квинтиллион) күйге ие; бірақ әр төбеге байланысты көршілер саны – қабырғалар (n-нен 20 таңдаудан), ал графиктің диаметрі – .
Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is edges (coming from n choose 20), and the diameter of the graph is .
Өтпе ықтималдығы
Белгілі бір проблема бойынша симуляциялық оттепелеудің мінез-құлқын зерттеу үшін, алгоритмді іске асыру кезінде жасалған әртүрлі жобалау шешімдерінен туындайтын ауысу ықтималдықтарын қарастыру пайдалы болуы мүмкін. Іздеу графигінің әрбір қабырғасы үшін ауысу ықтималдығы – бұл симуляциялық оттепелеу алгоритмінің ағымдағы күйінен күйге өту ықтималдығы ретінде анықталады. Бұл ықтималдық , температураға, кандидаттық қозғалыстарды тудыратын функцияның ретіне және қабылдау ықтималдығы функциясына байланысты. (Айта кетсек, ауысу ықтималдығы жай ғана емес, себебі кандидаттар тізбекпен тексеріледі.)
To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the transition probabilities that result from the various design choices made in the implementation of the algorithm. For each edge of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state when its current state is This probability depends on the current temperature as specified by , on the order in which the candidate moves are generated by the function, and on the acceptance probability function (Note that the transition probability is not simply , because the candidates are tested serially.)
Қабылдау ықтималдығы
, , және спецификациясы ішінара қайталауға жатады. Іс жүзінде, көптеген мәселелер үшін бірдей қабылдау функциясын қолдану және қалған екі функцияны нақты мәселеге сәйкес реттеу кең таралған. Киркпатрик және авторлар әдісті жасағанда, қабылдау ықтималдығы функциясы егер 1 болса, ал әйтпесе - ретінде анықталды. Бұл формула физикалық жүйенің өтулерімен салыстыру арқылы негізделген; ол T=1 және Метрополис-Хэстингс ұсыныс таралуы симметриялық болған жағдайда Метрополис-Хэстингс алгоритміне сәйкес келеді. Дегенмен, бұл қабылдау ықтималдығы жиі симуляцияланған оттегілеу үшін қолданылады, тіпті функция, Метрополис-Хэстингстегі ұсыныс таралуына ұқсас, симметриялық болмаса немесе тіпті ықтималдық емес болса да. Нәтижесінде, симуляцияланған оттегілеу алгоритмінің өту ықтималдықтары сол физикалық жүйенің өтулеріне сәйкес келмейді, ал тұрақты температурадағы күйлердің ұзақ мерзімді таралуы кез келген температурада сол физикалық жүйенің күйлері бойынша термодинамикалық тепе-теңдік таралуына ұқсамайды. Дегенмен, симуляцияланған оттегілеудің көптеген сипаттамалары бастапқы қабылдау функциясын қабылдайды, бұл, мүмкін, SA-ның көптеген іске асырылуында қатаң түрде енгізілген. 1990 жылы Москато мен Фонтанари, сондай-ақ тәуелсіз түрде Дьюк пен Шейер, детерминистік жаңарту (яғни, ықтималдық қабылдау ережесіне негізделмеген) оңтайландыру процесін соңғы сапаға әсер етпей үдетуге болатынын ұсынды. Москато мен Фонтанари өз зерттеулерінен алынған "шегілік жаңарту" оттегінің "ерекше жылу" қисығының аналогын қарастырып, "симуляцияланған оттегілеу алгоритміндегі Метрополис жаңартуының стохастикалық сипаты жақын оптималдық минимумдарды іздеуде маңызды рөл атқармайды" деген қорытындыға келді. Оның орнына, олар "жоғары температурадағы құн функциясы ландшафтының тегістелуі және салқындату процесінде минимумдардың біртіндеп қалыптасуы – симуляцияланған оттегілеудің табысқа жетуінің негізгі факторлары" деп ұсынды. Бұл әдіс кейіннен Дьюк пен Шейердің атауымен "шегілік қабылдау" деп танымал болды. 2001 жылы Франц, Хоффман және Саломон детерминистік жаңарту стратегиясы шынымен де құн/энергия ландшафтында кездейсоқ қозғалысты имитациялайтын алгоритмдер класындағы ең оңтайлы стратегия екенін көрсетті.
The specification of , , and is partially redundant. In practice, it's common to use the same acceptance function for many problems and adjust the other two functions according to the specific problem. In the formulation of the method by Kirkpatrick et al., the acceptance probability function was defined as 1 if , and otherwise. This formula was superficially justified by analogy with the transitions of a physical system; it corresponds to the Metropolis–Hastings algorithm, in the case where T=1 and the proposal distribution of Metropolis–Hastings is symmetric. However, this acceptance probability is often used for simulated annealing even when the function, which is analogous to the proposal distribution in Metropolis–Hastings, is not symmetric, or not probabilistic at all. As a result, the transition probabilities of the simulated annealing algorithm do not correspond to the transitions of the analogous physical system, and the long term distribution of states at a constant temperature need not bear any resemblance to the thermodynamic equilibrium distribution over states of that physical system, at any temperature. Nevertheless, most descriptions of simulated annealing assume the original acceptance function, which is probably hard coded in many implementations of SA. In 1990, Moscato and Fontanari, and independently Dueck and Scheuer, proposed that a deterministic update (i. e. one that is not based on the probabilistic acceptance rule) could speed up the optimization process without impacting on the final quality. Moscato and Fontanari conclude from observing the analogous of the "specific heat" curve of the "threshold updating" annealing originating from their study that "the stochasticity of the Metropolis updating in the simulated annealing algorithm does not play a major role in the search of near optimal minima". Instead, they proposed that "the smoothening of the cost function landscape at high temperature and the gradual definition of the minima during the cooling process are the fundamental ingredients for the success of simulated annealing." The method subsequently popularized under the denomination of "threshold accepting" due to Dueck and Scheuer's denomination. In 2001, Franz, Hoffmann and Salamon showed that the deterministic update strategy is indeed the optimal one within the large class of algorithms that simulate a random walk on the cost/energy landscape.
Кандидаттарды тиімді қалыптастыру
Кандидат генераторды таңдағанда, симуляцияланған оттыру алгоритмінің бірнеше итерациясынан кейін ағымдағы күйдің энергиясы кездейсоқ күйге қарағанда әлдеқайда төмен болады деп күтілуі керек. Сондықтан, жалпы ереже бойынша, генераторды баратын күйдің энергиясы ағымдағы күйдің энергиясына ұқсас болуы мүмкін кандидат қозғалыстарға қарай бұру керек. Бұл эвристика (Метрополис-Хестингс алгоритмінің негізгі принципі) өте жақсы кандидат қозғалыстарды, сондай-ақ өте жаман қозғалыстарды да алып тастауға бейім; алайда, біріншісі екіншісіне қарағанда әдетте әлдеқайда сирек кездеседі, сондықтан эвристика әдетте өте тиімді. Жоғарыдағы саяхатшы сатушы мәселесінде, мысалы, төмен энергиялы маршрутта екі қатарлас қаланы ауыстыру оның энергиясына (ұзындығына) шамалы әсер етеді деп күтіледі; ал екі кездейсоқ қаланы ауыстыру оның ұзындығын азайтудан гөрі ұлғайтуы ықтимал. Осылайша, қатарлас ауыстыру көрші генераторы кездейсоқ ауыстыру генераторынан жақсы жұмыс істейді деп күтіледі, тіпті соңғысы оптималға дейін сәл қысқа жолды қамтамасыз ете алады (ауыстырулармен, орнына). Эвристиканың дәлірек тұжырымы – бірінші кандидат күйлерін сынап көру керек, мұнда үлкен. Жоғарыдағы «стандартты» қабылдау функциясы үшін бұл дегеніміз, ол немесе одан кем шамасында. Осылайша, жоғарыдағы саяхатшы сатушы мысалында, екі кездейсоқ қаланы ауыстыратын функцияны қолдануға болады, онда қала жұбын таңдау ықтималдығы олардың арақашықтығы артқан сайын азаяды.
When choosing the candidate generator , one must consider that after a few iterations of the simulated annealing algorithm, the current state is expected to have much lower energy than a random state. Therefore, as a general rule, one should skew the generator towards candidate moves where the energy of the destination state is likely to be similar to that of the current state. This heuristic (which is the main principle of the Metropolis–Hastings algorithm) tends to exclude very good candidate moves as well as very bad ones; however, the former are usually much less common than the latter, so the heuristic is generally quite effective. In the traveling salesman problem above, for example, swapping two consecutive cities in a low energy tour is expected to have a modest effect on its energy (length); whereas swapping two arbitrary cities is far more likely to increase its length than to decrease it. Thus, the consecutive swap neighbor generator is expected to perform better than the arbitrary swap one, even though the latter could provide a somewhat shorter path to the optimum (with swaps, instead of ). A more precise statement of the heuristic is that one should try the first candidate states for which is large. For the "standard" acceptance function above, it means that is on the order of or less. Thus, in the traveling salesman example above, one could use a function that swaps two random cities, where the probability of choosing a city pair vanishes as their distance increases beyond .
Кедергілерден аулақ болу
Кандидат генераторды таңдағанда, сонымен қатар, барлық көршілес күйлерге қарағанда энергиясы әлдеқайда төмен "төмендеу" жергілікті минимумдар (немесе байланысқан күйлер жиынтығы) санын азайтуға тырысу керек. Энергия функциясының мұндай "жабық жинақтаушы алаптары" симуляцияланған қайнату алгоритмін жоғары ықтималдықпен (алаптың күйлер санына шамамен пропорционалды) және өте ұзақ уақыт бойы (айналасындағы күйлер мен алаптың түбі арасындағы энергия айырмашылығына шамамен экспоненциалды түрде байланысты) тұтқындауы мүмкін. Әдетте, осы мақсатты қанағаттандыратын және ұқсас энергиясы бар кандидаттарға басымдық беретін кандидат генераторды жобалау мүмкін емес. Екінші жағынан, генераторды салыстырмалы түрде қарапайым өзгерту арқылы симуляциялық қайнатудың тиімділігін айтарлықтай арттыруға болады. Саяхашының мәселесінде, мысалы, шамамен бірдей ұзындығы бар екі маршрутты көрсету оңай, , мұнда (1) біріншісі оңтайлы, (2) қала жұптарын алмастырудың кез келген тізбегі бірінші маршрутты екіншісіне айналдырғанда, екеуінен де ұзын маршруттардан өтеді, және (3) бірінші маршрутты бірізді қалалардың жиынтығын кері бұру арқылы (реттілігін өзгерту арқылы) екінші маршрутқа түрлендіруге болады. Бұл мысалда, егер генератор тек кездейсоқ жұп алмасуды орындаса, маршруттар әртүрлі "терең алаптарда" болады; бірақ егер генератор кездейсоқ сегменттерді ауыстырса, олар бір алапта болады.
When choosing the candidate generator one must also try to reduce the number of "deep" local minima—states (or sets of connected states) that have much lower energy than all its neighboring states. Such "closed catchment basins" of the energy function may trap the simulated annealing algorithm with high probability (roughly proportional to the number of states in the basin) and for a very long time (roughly exponential on the energy difference between the surrounding states and the bottom of the basin). As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of simulated annealing by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours , , with nearly equal lengths, such that (1) is optimal, (2) every sequence of city pair swaps that converts to goes through tours that are much longer than both, and (3) can be transformed into by flipping (reversing the order of) a set of consecutive cities. In this example, and lie in different "deep basins" if the generator performs only random pair swaps; but they will be in the same basin if the generator performs random segment flips.
Салқындату кестесі
Симуляцияланған оттыртуды негіздеу үшін қолданылатын физикалық аналогия, суыту жылдамдығы ағымдағы күйдің ықтималдық таралымы әрқашан термодинамикалық тепе-теңдікке жақын болуы үшін жеткілікті төмен деп есептейді. Алайда, серпілу уақыты – температура өзгергеннен кейін тепе-теңдіктің қайта орналасуын күтуге қажетті уақыт – энергия функциясының «ландшафтына» және ағымдағы температураға күшті түрде байланысты. Симуляцияланған оттырту алгоритмінде серпілу уақыты кандидатты генераторға да, өте күрделі тәсілмен байланысты. Бұл параметрлердің бәрі әдетте симуляцияланған оттырту алгоритміне «қара жәшік» функциялары ретінде беріледі. Сондықтан, идеалды суыту жылдамдығын алдын ала анықтау мүмкін емес және оны әр мәселе үшін эмпирикалық түрде түзету қажет. Адаптивті симуляцияланған оттырту алгоритмдері бұл мәселені суыту кестесін іздеу прогресімен байланыстыру арқылы шешеді. Термодинамикалық симуляцияланған оттырту сияқты басқа да адаптивті тәсілдер термодинамика заңдарына сәйкес, екі күй арасындағы энергия айырмашылығына негізделіп, әр қадамда температураны автоматты түрде реттейді.
The physical analogy that is used to justify simulated annealing assumes that the cooling rate is low enough for the probability distribution of the current state to be near thermodynamic equilibrium at all times. Unfortunately, the relaxation time—the time one must wait for the equilibrium to be restored after a change in temperature—strongly depends on the "topography" of the energy function and on the current temperature. In the simulated annealing algorithm, the relaxation time also depends on the candidate generator, in a very complicated way. Note that all these parameters are usually provided as black box functions to the simulated annealing algorithm. Therefore, the ideal cooling rate cannot be determined beforehand and should be empirically adjusted for each problem. Adaptive simulated annealing algorithms address this problem by connecting the cooling schedule to the search progress. Other adaptive approaches such as Thermodynamic Simulated Annealing, automatically adjusts the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics.
Қайта бастау
Кейде қазіргі жағдайдан әрқашан өзгешеге көшудің орнына, бұрынғыдан әлдеқайда жақсы болған шешімге қайта оралу тиімдірек. Бұл процеске симуляцияланған оттыртуды қайта іске қосу (restart) дейді. Мұны істеу үшін s және e мәндерін sbest және ebest деп орнатамыз, сондай-ақ, оттырту кестесін де қайта іске қосуға болады. Қайта іске қосу туралы шешім әртүрлі критерийлерге негізделуі мүмкін. Олардың арасында белгілі бір қадамдар санына жеткенде қайта іске қосу, ағымдағы энергияның осы уақытқа дейін алынған ең жақсы энергиядан артық болуы, кездейсоқ түрде қайта іске қосу және тағы да басқалары бар.
Sometimes it is better to move back to a solution that was significantly better rather than always moving from the current state. This process is called restarting of simulated annealing. To do this we set s and e to sbest and ebest and perhaps restart the annealing schedule. The decision to restart could be based on several criteria. Notable among these include restarting based on a fixed number of steps, based on whether the current energy is too high compared to the best energy obtained so far, restarting randomly, etc.