Метод отжига

пр ктик , ост точно ять n = 24. Äëÿ ìî ëèðî íèÿ òð ó - ìî î N(0; T) ост точно омно ить получи ш ся число н pT . В случ р м рности, ольш й иницы, по к ой и коор ин то ились н исимы о мущ ния с т ким р спр л ни м.

Для мо лиро ния у ы ния т мп р туры исполь о л сь н поср ст нно формул T0= ln k, k = 2; 3; : : :.

4.2.Îò è Êîøè

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

ши с плотностью

1 T g(x) = x2 + T 2 :

Вычислим PfX < yg:

Сл о т льно, сли р ли ция р ном рно р спр л нной н [0; 1] случ йной личины, то личин

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

В случ ч с р м рностью D > 1 исполь о лось прои -ни D о ном рных р спр л ний Коши, т. . носилось о му- щ ни по к ой и коор ин т, ычисл нно по формул (3) ля н исимых i.

Для т мп р туры этом случ исполь у тся формул

T (k) = kT1=D0 ;

ïðè÷ ì ñëó÷ D = 1 он ычислял сь к к T =k, ñëó÷ D = 2

0

ê ê T0=pk ля у лич ния скорости р оты про р мм.

143

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

Для с рх ыстро о от и исполь о л сь т к получ нн я м то ом о р тных функций формул (2). З кон и м н ния т мп - р туры т к им л отличия при D = 1 è D = 2. Åñëè ïðè D = 2

отличи , н ло èчно пр ы ущ му случ ю, с о илось к ычисл - нию k1=2 ê ê pk, òî ïðè D = 1 î ìî í îë ñóù ñò íí ÿ îï-

òèìè öèÿ, ò. ê.

T (k + 1) = e ci=(k+1) = e ci = const:

T (k) e ci=k

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

Для пр от р щ ния л ния н 0 формул х т мп р тур ы- л о р нич н сни у н ч ни м 10 4000.

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

Êðîì ûø îïèñ ííûõ ì òî î , ûëè ñìî ëèðî íû ÷ òûð ì òî òóø íèÿ:

Больцм но ский от и с ум ньш ни м т мп р туры к к м - то Коши,

Больцм но ский от и с экспон нци льным ум ньш ни м т м- п р туры (Tk+1 = cTk, c = 0:99),

м то Коши с экспон нци льным ум ньш ни м т мп р туры (Tk+1 = cTk, c = 0:99),

с рх ыстро туш ни .

С рх ыстро туш ни получ тся и м то с рх ыстро о от-и с исполь о ни м сл ующих формул:

Ti(k) = T(i;0) exp( cikQ=D); ci > 0; ci = mi exp( ni=D);

Q ò ê í û ìûé ìíî èò ëü òóø íèÿ. При т стиро нии мно ит ль туш ния р лся р ным 2.

144

5.Ср н ни сх м от и н ч о н хо нии точки минимум функции со случ йной пом хой

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

30

f(x1; : : : ; x30) = Xx4i + ;

i=1

случ йн я пом х , р спр л нн я р ном рно н [0; 1]. Мно ст о миними ции лось усло иями 1000 xi

1000.

Вы ор п р м тро и н ч льной точки

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

ëèñü mi = 1, ni = 160, ля с рх ыстро о туш ния mi = 1, ni = 80. Т мп р тур по с м коор ин т м со п л , ст рто ын ч ния по ир лись опытным пут м. Ни при о ится т лиц

ñò ðòî ûõ ò ìï ð òóð:

Р ульт ты т стиро ния

К я сх м пуск л сь ух ри нт х кл ссич ском, т к ри нт с ум ньш ни м т мп р туры и посл н у ч ( - ри нт 2.А). Для получи шихся 14 сх м при о ятся р фики н я - ки, получ нной р ульт т уср н ния по 100 пуск м м то .

145

Н п р ом р фик ср ни ются м то ы кл ссич ском ри н- т , н тором ри нт 2.А. Н р фик ото р но и м н ни н я ки по м р ычисл ния н ч ний функции но ых точк х.

146

Íè ïðè î èòñÿ ò ëèö î î í ÷ íèé ëÿ ð ôèêî , ïðè -ííûõ ëÿ ò ñòî :

Àí ëè ð óëüò òî

Ви но, что р личны м то ы от и хорошо р от ют с функциями с пом хой, исключ ни м н которых м то о туш ния. И -стно, что скорость схо имости лю о о м то , осно нно о только н н ч ниях функции с н ыро нными н у ы ющими по- м х ми, н мо т ыть по поря ку ыстр , ч м кор нь и чис- л ит р ций. Ни при о ится т лиц н я ки при исполь о - нии м то с рх ыстро о от и исимости от числ ы о о функций:

При т стиро нии исполь о лось уср н ни по сяти пус- к м.

Н поср ст нно и при ¸нной т лицы и но, что скорость у ы ния н я ки ост точно ысок , и, скор с о, со п т с оптим льной т ор тич ской оц нкой. К со л нию, ок т льст о это о ф кт ля м то от и о сих пор н н й но.

6.Ç êëþ÷ íè

М то от и я ля тся сьм эфф кти ным л оритмом слу- ч йно о поиск ло льно о минимум . В рсия л оритм с рх ы-

147

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

Пок м ло и уч ны о мо ности м то от и ля р ш нияру их ч, с о ящихся к оптими ционным. Н юсь, что ли-йш р мя у ут получ ны т ор тич ски р ульт ты относи- т льно скорости схо имости м то от и . К со л нию, н н - стоящий мом нт инст нны и стны р ульт ты к с ются ст - тистич ской р нтии схо имости (см. [13], [14], [15], [18]).

Список лит р туры

by Fast Computer Machines // J. Chemical Physics. 21. 6. June. 1953. P. 1087 1092.

[2]Kirkpatrick S., Gelatt Jr. C. D., and Vecchi M. P. Optimization by Simulated Annealing // Science. 220. 1983. P. 671 680.

[3]Ingber L., Mondescu R. P. Optimization of Trading Physics Models of Markets // IEEE Trans. Neural Networks. 12(4). 2001. P. 776 790.

Mathematical Computer Modelling. 31(8/9). 2000. P. 167 192.

[5]Forman M. C. , Aggoun A., McCormick M. Simulated Annealing for Optimisation and Characterisation of Quantisation Parameters in Integral 3D Image Compression // The Institute of Mathematics and its Applications. Horwood. 2000. P. 393 413.

[6]Forman M. C. Compression of Integral Three Dimensional Television Pictures / Ph. D. Thesis at De Montfort University Leicester. 2000. United Kingdom.

[7]Jeong C., Kim M. Fast Parallel Simulated Annealing for Traveling Salesman Problem on SIMD Machines with Linear Interconnections // Parallel Computing. 17. 1991. P. 221 228.

148

[8]Yao X. Call Routing by Simulated Annealing // International Journal of Electronics. Oct. 1995.

[9]Cohen B. Training Synaptic Delays in a Recurrent Neural Network / Thesis submitted towards the degree Master of Science at Tel-Aviv University. 1994.

[10]Óîññ ðì í Ô. Н йрокомпьют рн я т хник : Т ория и пр к- тик / П р о н русский я ык, . А. Зу , В. А. Точ но . 1992.

[11]Ingber L. Simulated Annealing: Practice versus theory // Mathematical and Computer Modelling. 18(11). 1993. P. 29 57.

[12]Ingber L., Rosen B. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison // Mathematical and Computer Modelling. 16(11). 1992. P. 87 100.

[13]Geman S., Geman D. Stochastic relaxation, Gibbs distribution and the Bayesian restoration in images // IEEE Trans. Patt. Anal. Mac. Int. 6(6). 1984. P. 721 741.

[14]Szu H. H., Hartley R. L. Fast Simulated Annealing // Physical Letters A. 122. 1987. P. 157 162.

[15]Ingber L. Very fast simulated re-annealing // Mathematical and Computer Modelling. 12. 1989. P. 967 973.

[16]Yao X. A New Simulated Annealing Algorithm // International Journal of Computer Mathematics. 56. 1995. P. 161 168.

[17]Ingber L. Adaptive simulated annealing (ASA): Lessons learned

//Journal Control and Cybernetics . 1995.

[18]Yao X. Simulated Annealing with Extended Neighbourhood

//International Journal of Computer Mathematics. 40. 1991. P. 169 189.

149