Метод отжига

Ì òî îò è

Ëîï òèí À. Ñ.

Ñ íêò-Ï ò ð óð ñêèé îñó ðñò ííûé óíè ðñèò ò1

В р от р ссмотр ны р ли ции и с ойст р личных ри нто м -

òî îò è .

1. íè

Ì òî îò è (синонимы: м то о и , м то симуляции от-и , м то мо льной к лки, simulated annealing) это т хник оптими ции, исполь ующ я упоря оч нный случ йный поиск н осно н ло ии с проц ссом о р о ния щ ст крист ллич - ской структуры с миним льной эн р и й при охл нии.

История м то от и н чин тся с 1953 о . В этом о у Н. М трополисом ыл р р от н л оритм симуляции уст но л - ния р но сия сист м с мно ст ом ст п н й с о о ы при -нной т мп р тур [1]. В н ч л 80-х у С. Киркп трик [2] п р ы поя ил сь и я исполь о ть этот л оритм н только ля мо лиро ния фи ич ских сист м, но и ля р ш ния н которых ч оптими ции.

В н стоящ р мя м то от и прим ня тся ля р ш ния мно их оптими ционных ч фин нсо ых (см.[3], [4]), компью- т рной р фики (см. [5], [6]), ком ин торных (см. [7]), т л коммуник ционных с тях (см. [8]), и мно их ру их. З ч стую м то от и исполь уют ля о уч ния н йронных с т й (см. [9], [10]).

Н смотря н т кую широкую о л сть прим н ния, скорость схо-имости м то от и с щ м ло и уч н .

О ромным пр имущ ст ом м то от и я ля тся с ойст о и -

ть ло ушки лок льных минимум х оптими иру мой функции, и про ол ить поиск ло льно о минимум . то ости тсясч т принятия н только и м н ний п р м тро , при о ящих к ум ньш нию н ч ния функции, но и н которых и м н ний, у ли- чи ющих н ч ни , исимости от т. н. ò ìï ð òóðû T х р кт ристики мо лиру мо о проц сс . Ч м ыш т мп р тур , т м ольши уху ш ющи и м н ния ( н ло ичны случ йным

1 c À. Ñ. Ëîï òèí, 2005

133

флукту циям н р том щ ст ) опустимы, и ольш их роятность.

Ещ о ним пр имущ ст ом я ля тся то, что усло иях н х тки ычислит льных р сурсо ля н хо ния ло льно о минимум , м то от и , к к пр ило, ы т сьм н плохо р - ш ни (о ин и лок льных минимумо ).

Л. Ин ром [11] пок но, что м то от и и о мо ифи- к ции я ляются о ним и н и ол эфф кти ных м то о случ й- но о поиск оптим льно о р ш ния ля ольшо о кл сс ч. В [12] Л. Ин ром про н ср нит льный н ли пти но о м - то от и (Adaptive Simulated Annealing, ASA) и н тич скихл оритмо , и которо о сл у т, что н ольшинст ч м то от и н прои ры т н тич ским л оритм м, н мно их иыи ры т.

К н стоящ му р м ни р р от но мно ст о р личных - ри нто м то от и , к к о щих, т к и их сп ци ли ций ля р ш ния конкр тных ч.

В нной р от н ли ируются и стны н н стоящий мо- м нт о щи сх мы от и .

2.Ал оритм м то от и

М то от и слу ит ля поиск ло льно о минимум н которой функции f(x), ííîé ëÿ x и н которо о простр нст S,èñêð òíî î èëè í ïð ðû íî î. ë ì íòû ìíî ñò S пр ст - ляют со ой состояния оо р мой фи ич ской сист мы ( эн р - тич ски уро ни ), н ч ни функции f этих точк х исполь у т- ся к к эн р ия сист мы E = f(x). Â ê ûé ìîì íò ïð ïîë òñÿ

ííîé ò ìï ð òóð ñèñò ìû T , к к пр ило, ум ньш ющ яся с т ч ни м р м ни. Посл поп ния состояни x ïðè ò ìï ð - òóð T , сл ующ состояни сист мы ы ир тся соот тст ии с

ííûì поро ющим с м йст ом роятностных р спр л - ний G(x; T ), которо при фиксиро нных x è T ò ñëó÷ éíûé ýë ì íò G(x; T ) со н ч ниями простр нст S. Посл н р ции но о о состояния x0 = G(x; T ), сист м с роятностью h( E; T ) п р хо ит к сл ующ му ш у состояни x0, проти ном случ проц сс н р ции x0 ïî òîðÿ òñÿ. Ç ñü E о о н ч т прир щ - ни функции эн р ии f(x0) f(x). В личин h( E; T ) í û òñÿ

но о о состояния.

134

К к пр ило, к ч ст функции h( E; T ) ы ир тся ли о точно н ч ни соот тст ующ й фи ич ской личины

1

h( E; T ) = 1 + exp( E=T );

ëè î ïðè ëè ííî í ÷ íè

h( E; T ) = exp( E=T ):

Втор я формул исполь у тся н и ол ч сто. При исполь-о нии h( E; T ) ок ы тся ольш иницы случ E < 0, и то соот тст ующ я роятность счит тся р ной 1. Т ким

о р ом, сли но о состояни т лучш н ч ни оптими и- ру мой функции, то п р хо это состояни прои ой т лю ом случ .

Ит к, конкр тн я сх м м то от и тся сл ующими п р м тр ми:

Âû îðîì êîí è ì í íèÿ ò ìï ð òóðû T (k), k íîì ð ø .

Âû îðîì ïîðî þù î ñ ì éñò ð ñïð ë íèé G(x; T ).

Вы ором функции роятности принятия h( E; T ).

Ал оритм:

1)Ñëó÷ éíûì î ð îì û èð òñÿ í ÷ ëüí ÿ òî÷ê x = x0, x0 2 S. Ò êóù í ÷ íè ýí ð èè E óñò í ëè òñÿ í ÷ íè f(x0).

2)k-я ит р ция осно но о цикл состоит и сл ующих ш о :

(a)Ñð íèòü ýí ð èþ ñèñò ìû E состоянии x с н й н- ным н т кущий мом нт ло льным минимумом. Если E = f(x) м ньш , то и м нить н ч ни ло льно о минимум .

(b)С н риро ть но ую точку x0 = G(x; T (k)).

(c)Вычислить н ч ни функции н й E0 = f(x0).

(d)С н риро ть случ йно число и инт р л [0; 1]

135

(e) Åñëè < h(E0 E; T (k)), òî óñò íî èòü x x0; E E0 и п р йти к сл ующ й ит р ции. Ин ч по торить ш (b), пок н у т н й н по хо ящ я точк x0.

И стны сл ующи мо ифик ции это о л оритм :

Мо ифик ция A. Н ш 2e п р хо к сл ующ й ит р ции происхо ит и том случ , сли точк x0 н я лял сь по хо-ящ й. При этом сл ующ я ит р ция н чин тся с точки x, íî ó ñ íî ûì í ÷ íè ì ò ìï ð òóðû.

Мо ифик ция Б. В к ч ст оц нки точки минимум о р - щ тся посл н н ч ни x. то мо т н н чит льно ускорить л оритм случ ольшой р м рности S, но с н ольшой роятностью мо т при сти к тому, что у т полу- ч но ху ш р ш ни (осо нно, сли т мп р тур к мом нту

рш ния л оритм ост ¸тся н чит льно ольш нуля).

Ìî èôèê öèÿ Â. Í ø 2b x0 ычисля тся р курр нтно с исполь о ни м формулы x0 = G(x0; T (k)). È í ÷ ëüíî í ø

1 óñò í ëè òñÿ x0 x0. то по оля т и ть стр - ния л оритм , о н ко т к я р ли ция т ря т мно ст о пр имущ ст м то от и , т. к. н оч нь сильно отлич т- ся от о ычно о случ йно о поиск (осо нно, сли это ком и- ниру тся с ри нтом 1 этом случ про рку h( E; T )оо щ мо но исключить).

В сл ующ м р л у ут р ссмотр ны осно ны сх мы ы-ор п р м тро м то от и .

3.Î ùè ñõ ìû ì òî îò è

3.1.Больцм но ский от и

Историч ски п р ой сх мой м то от и я ля тся т.н. сх - м Больцм но ско о от и . Им нно эт сх м исполь о л сь Н. М трополисом и р. [1] ля ычисл ния мно ом рных инт -р ло пути ч х ст тистич ской фи ики, т к С. Кирк- п триком и р. [2] ля р ш ния чи н хо ния оптим льной

136

р о ки микросх м. В Больцм но ском от и и м н ни т мп - р туры ¸тся формулой

Ñ ì éñò î ð ñïð ë íèé G(x; T ) ы ир тся к к с м йст о нор- м льных р спр л ний с м т м тич ским о и ни м x è èñï ð- ñè é T , т. . ¸тся плотностью

g(x0; x; T ) = (2 T ) D=2 exp( jx0 xj2=(2T ));

D р м рность простр нст состояний. Простр нст о состояний пр пол тся м трич ским.

Для Больцм но ской сх мы ок но (см. [1]), что при ост -

точно ольших T0 и о щ м колич ст ш о K, ы ор т ко о с - м йст р спр л ний р нтиру т н хо ни ло льно о минимум .

3.2.От и Коши ( ыстрый от и )

Осно ным н ост тком Больцм но ско о от и я ля тся оч нь

ì ë ííî ó û íè ò ìï ð òóðû. Í ïðèì ð, ëÿ òî î, ÷òî û ïîíè èòü èñõî íóþ ò ìï ð òóðó 40 ð , òð ó òñÿ e40 2:35 1017

ит р ций, что у ря ли при мл мо при р ш нии к ких-ли о -ч. В и у это о Цу и Х ртли [14] пр ло или л оритм, который по оля т исполь о ть ля и м н ния т мп р туры сх му

пот ри р нтии н хо ния ло льно о минимум . то о- сти тся сч т исполь о ния к ч ст G р спр л ний Коши с плотностью

g(x0; x; T ) = (jx0 xj2 +TT 2)(D+1)=2) ;

соот тст ующим о р ом нормиро нных. Н прим р, случ D = 1 прихо им к плотности

137

Êñî ë íèþ, ýòî ð ñïð ë íè í î÷ íü ó î íî ìî ëèðî òü

простр нст р м рности ольш 1. то о мо но и ть, н - прим р, с помощью п р мно ния D î íîì ðíûõ ð ñïð ë íèé

но этом случ н хо ни ло льно о минимум р нтиру тся только при кон и м н ния т мп р туры н ыстр ч м:

T (k) = kT1=D0 ;

÷òî îð î ì ë íí ñõ ìû (1).

3.3.С рх ыстрый от и

Н ост тки ух пр ы ущих м то о при ли к тому, что 1989 о у м рик нским иссл о т л м Л. Ин ром ыл р р -от н м то с рх ыстро о от и (Very Fast Annealing) [15]. В н м простр нст о S счит тся состоящим и D-м рных кторо

 ê ÷ ñò y ля получ ния плотности р спр л ний G исполь-

ó òñÿ x , ò êèì î ð îì, íî î í ÷ íè xi0 ычисля тся по

Bi Ai

формул xi0 = xi + zi(Bi Ai), zi случ йн я личин с плот-

ностью g(i;T) í [ 1; 1]. При этом ыхо ящи р ницы инт р - л н ч ния п р м тр н рируются но о (пок н прои ой т

поп ни инт р л) или прир ни ются соот тст ующим р - ниц м.

138

i н исимы случ йны личины, р спр л нны р - ном рно н [0; 1].

Äîê íî (ñì. [15]), ÷òî êîí è ì í íèÿ ò ìï ð òóðû

Ti(k) = T(i;0) exp( cik1=D); ci > 0

eт ст тистич скую р нтию н хо ния ло льно о минимум . Для роятности принятия т к исполь у тся от льн я шк л т мп р туры, и м няющ яся по т кому кону. К к пр ило, при р ли ции это о м то ci óïð ëÿ òñÿ óìÿ ï ð ì òð ìè:

ci = mi exp( ni=D):

Пр имущ ст т ко о м то оч и ны. Во-п р ых, экспон н- ци льно у ы ни т мп р туры ор о ыстр ости имо о пр ы ущих м то х. Воторых, р л ни р м рност й мо тть ольшой ыи рыш, к к и л о ря от льным т мп р тур м (т. к. сп цифик конкр тной чи мо т сильно р лич ть п - р м тры), т к и л о ря ускор нию проц сс , случ , сли н ну но м нять с коор ин ты о но р м нно.

Кром то о, отличи от от и Коши, с рх ыстрый от и , к к ыло пок но, опуск т оч нь ыстро мо лиро ни р с- пр л ния G н исимо от р м рности S.

Ср и н ост тко это о м то мо но н ть то, что и уольшо о колич ст п р м тро ино тр у тся н сколько м ся- ц , что ы хорошо н строить о ля р ш ния конкр тной чи.

3.4.Ал оритм Ксин о

Ал оритм Ксин о [16] ыл получ н по торным прим н ни м и и пр ы ущ о л оритм . В к ч ст gT (y) û èð òñÿ

139

ости тся ст тистич ск я р нтия н хо ния ло льно о минимум .

О н ко, к к пок но [16], у лич ни скорости у ы ния т м- п р туры о с н о н ч т ускор ния р ш нии чи. Бол то о, р м нность р спр л ния при о ит к тому, что м тон риру т о ромно число линных п р хо о , которы от р - ются силу ни кой роятности их принятия.

Т ким о р ом, н смотря н то, что этот проц сс мо но ит риро ть о скон чности, получ я коны и м н ния т мп р турыро

Ti(k) = T(i;0) exp( exp(exp(: : : exp(bik1=D) : : :)));

ц нность т ких улучш ний пр ст ля тся сомнит льной. Бол то о, л ко и ть, что пр л это при о ит к три и льному м - то у случ йно о поиск , которым я ля тся м то от и при T = 0.

то н ольшой ст п ни прим нимо и к м то у с рх ыстро о от и , т к что опрос о скорости схо имости этих м то о , т к-о ру их м то х, о сп чи ющих н т ко ыстро у ы ни т мп р туры, но ольшую скорость схо имости, ост тся открытым.

Сл о т льно, р оту [16] мо но р ссм три ть и к к н кую скрытую критику м то с рх ыстро о от и . О н ко, полно мо ны чи, н которых тор я ит р ция ыш опис нно о проц сс мо т ть н плохи р ульт ты, поэтому этот м то и р ссмотр н н стоящ й р от .

3.5.Ì òî û òóø íèÿ

Д л ко н с х т т ычислит льных р сурсо н поискло льно о минимум . Кром то о, ч стую ост точно ости - нуть н ло льно оптим льно о р ш ния чи, ост точно ли - ко о к н му. М то ы туш ния (simulated quenching) н р нтируют н хо ния ло льно о минимум , но, к к пр ило, ыстро н хо ят ли ко р ш ни , н пр ктик ч стую и с м оптимум.

Îñíî í ÿ è ÿ ýòèõ ì òî î êëþ÷ òñÿ òîì, ÷òî û ñêîì è- íèðî òü ñ ì éñò î ð ñïð ë íèé G о но о и пр ы ущих ч ты- р х м то о с ол ыстрым коном у ы ния т мп р туры.

140

Í ïðèì ð, ìî íî ð ññì òðè òü íîðì ëüíû ð ñïð ë íèÿ G и Больцм но ско о от и , но при этом ум ньш ть т мп р туру по кону

Tk+1 = cTk:

Ê ê ïð èëî, ýòîì ñëó÷ c û èð òñÿ ì ó 0:7 è 0:99. Т - кой м то оч нь ыстро схо ится, и ля конкр тных ч мо т

ть сьм н плохо р ш ни , ли ко к оптим льному, усло-иях р льно о р м ни.

Н которы и м то о туш ния р ссмотр ны [11] и [17]. З - ч стую они осно ны ли о н норм льном р спр л нии, ли о н р спр л нии ля с рх ыстро о от и . Кром то о, стр ч ются сп ци льны р спр л ния, по о р нны опытным пут м ля р ш ния конкр тных ч.

3.6.Ì ñøò èðî íè õî îò è

З ч стую при р ли ции с рх ыстро о от и ч х сольшой р м рностью исполь у тся т хноло ия ì ñøò èðî íèÿ îò è (reannealing), ино т к прим ня м я и к ру им - ри нт м от и . При исполь о нии этой т хноло ии п рио ич скио р мя от и прои о ится сл ующ я оп р ция. О о н чим si н ч ни н которой оц нки прои о ной ц л ой функции по i-й коор ин т точк т кущ о минимум :

ы мый этом л оритм ð ì í ì îò è (annealing-time)) и т мп р тур ля к ой р м рности и м няются сл ующим о - р ом:

Ti0 = Ti(ki)(smax=si); ki0 = (ln(T(i;0)=Ti0)=ci)D:

Ò êèì î ð îì, í ÷ íè T(i;0) сохр ня тся, р мя от и (которо т п рь мо т приним ть н только ц лы н ч ния) м сшт и-

ðó òñÿ ñî ë ñíî ò ìï ð òóð .

141

Т мп р тур , исполь у м я ля р сч т роятности принятия, т к м сшт иру тся. Спосо м сшт иро ния исит от - чи, но, к к пр ило, коэффици нт м сшт иро ния опр ля тсян ч ни м ц л ой функции точк т кущ о минимум (ч м м нь- ш н ч ни функции, т м м ньш т мп р тур ). Вр мя от и ля п р сч т т мп р туры принятия т к и м ня тся н ло ичным о р ом.

Кром при нно о, о мо ны ру и спосо ы м сшт иро - ния, исящи от конкр тной чи. К к пр ило, они с о ятся кру ому ы ору коэффици нто чу ст ит льности si. При н- ный ыш спосо ы ор si исполь у тся ля н лин йных фи ич - ских ч ольшой р м рности.

Ал оритм с рх ыстро о от и с исполь о ни м этой т хноло ии опис н [11], [15] и [17], и носит н ни ïòè íî î ì -

(adaptive simulated annealing).

4.Ìî ëèðî íè ñõ ì îò è

Для ср н ния р личных сх м м то от и мо лиро лось по ни их оц нок. Вопрос мо лиро ния р личных сх м от-и р и тся н ч сти:

промо лиро ть соот тст ующ р спр л ни ,

промо лиро ть сх му и м н ния т мп р туры.

4.1.Больцм но ский от и

Норм льно р спр л ни мо лиро лось с помощью ц нтр льной пр льной т ор мы. О о н чим i н исимы р ли ции р ном рно о р спр л ния н [0; 1]. То E i = 0, D i = 1=12 è

n

iP i

=1

pn=12 n!!1

Ò êèì î ð îì, ìî íî ñëî èòü n н исимых р ли ций i, и р ли их сумму н pn=12, мы у м им ть ост точно хоро- ш при ли ни к норм льному р спр л нию. К к пок ы т

142