<<
>>

МЕТОДЫ СЛУЧАЙНОГО ПОИСКА

Постановка задачи

Требуется найти безусловный минимум функции /(*) многих переменных,

т.е. найти такую точку х* е Rn, что /(**) = min /(*).

' ' xeRn

5.6.1. Адаптивный метод случайного поиска

Стратегия поиска

Задается начальная точка х°.

Каждая последующая точка находится по формуле

„fc+l _ „Л , и к к X -X + tk $ ,

из текущей точки достигает некоторого числа М , дальнейший поиск продолжа­ется из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше

где tk gt; 0 - величина шага; - случайный вектор единичной длины, опреде­ляющий направление поиска; к - номер итерации. На текущей итерации при по­мощи генерирования случайных векторов получаются точки, лежащие на ги­персфере радиуса tk с центром в точке хк (рис. 5.19). Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным (точки у1,у2 при поиске из х°; у1,у3 при поиске из х1). Если число неудачных шагов

Рис. 5.19

заранее заданной величины Я . Если же значение функции в полученной точке меньше, чем в центре, шаг считается удачным и в найденном направлении дела­ется увеличенный шаг, играющий роль ускоряющего шага (как при поиске по образцу в методе конфигураций). Если при этом значение функции снова мень­ше, чем в центре, направление считается удачным и дальнейший поиск продол­жается из этой точки (точки г3 = х1 при поиске из х°, г4 = х2 при поиске из х1). Если же значение функции стало не меньше, чем в центре, направление считается неудачным и поиск продолжается из старого центра (в точке у2 при поиске из х1 функция меньше, чем в х1, а в точке I2 уже не меньше, поэтому направление (г2 -х^ неудачное).

Алгоритм

Шаг 1. Задать начальную точку х°, коэффициенты расширения а pound; 1 и сжатия 0 lt; р lt; 1, М - максимальное число неудачно выполненных испытаний на текущей итерации, /0 = 1 - начальную величину шага, Я - минимальную величи­ну шага, N - максимальное число итераций. Положить к = 0, у = 1.

Шаг 2. Получить случайный вектор =^1У,...,pound;,/|Г, где - случайная величина, равномерно распределенная на интервале [—1,1].

. у)

Шаг 3. Вычислить у} = хК + tk тр-пг

Шаг 4. Проверить выполнение условий:

а) если /(У) lt;/(**), шаг удачный. Положить г* = хк + а -х*|. Опре­делить, является ли текущее направление у* - хк удачным:

- если /(^) lt; /(**)» направление поиска удачное. Положить

хк+[ = I*, /*+1 = а /*, к = к + \ и проверить условие окончания. Если к lt; N, положить у = 1 и перейти к шагу 2. Если к = N, поиск завершить: х* = х*;

- если /(гу ) ^ /(**)» направление поиска неудачное, перейти к шагу 5;

б) если /(У) 2: /(**), шаг неудачный и перейти к шагу 5.

Шаг 5. Оценить число неудачных шагов из текущей точки:

а) если у lt; М , следует положить у = у +1 и перейти к шагу 2;

б) если у = М, проверить условие окончания:

- если ** pound; Я, процесс закончить: х* = х*,/(х*| г /(х*);

- если tкgt; Я, положить Г* = р**,у = 1 и перейти к шагу 2

Замечания 5.13.

1. Величина 4/, равномерно распределенная на интервале [-1,1], генери­руется обычно с помошью датчиков псевдослучайных чисел на ЭВМ. Вырабаты-

вается случайная величина ц/, равномерно распределенная на [0,1], а затем ис­пользуется линейное преобразование: pound;/ = 2г|/ -1.

2. Шумер и Стейглиц [8сЬишег М.А., 81ещИ1г К.] рекомендуют следующие параметры алгоритма: а = 1,618; р = 0,618; М = Зл. При а = 1 точка г* на шаге 4 совпадает с у7, т.е. аналог поиска по образцу не производится. Начальный шаг /0 gt; Я можно задать произвольно [36] .

3. Если выполнено условие окончания tk lt;, Я , то в качестве ответа можно использовать любую точку внутри шара с радиусом и центром в точке хк.

4. Многочисленные варианты случайного поиска изложены в [8] и могут включать элементы обучения, при котором направления убывания функции ста­новятся более вероятными, а другие направления - менее вероятными.

Пример 5.18. Найти минимум функции /(*) = - 5)2 +(х2 - 6)2 методом

адаптивного случайного поиска.

? 1°. Зададим начальную точку х°=(8,9)г, а = 1,618; р = 0,618; N = 10; Я = 0,8; /0 = 1; М = 3. Положим к -0J = \.

2°. Получаем =(0,843; 0Г374)Г.

4°. Так как /(у1) = 72,83 gt; /(*°) = 45, шаг неудачен.

5°. Имеем у = 1 lt; М = 3. Положим у = у +1 = 2 и перейдем к шагу 2. 2*. Получаем =(0,239; 0,954)г.

41. Так как /(з'2) = 57,75 gt; /(х°) = 45 , шаг неудачен.

51. Имеем у = 2 lt; АГ = 3. Положим у = у +1 = 3 и перейдем к шагу 2. 22. Получаем = (-0,159;-0,402)г.

З2. Вычисляем у3 = х° + /0 —-------- (8, ЭУ + ^ = 8,07)г.

/1 = а*0 = 1,618-1 = 1,618, к = к + 1 = 1. Так как к = 1 lt; N = 10, положим у=1 и перейдем к шагу 2.

0,432

23. Получаем г2 = (0Д68;-0,727)Г.

З3. Вычисляем

У = *' *lt;|1^-(7,4;7,4»(г «),«18^’168’_°'727)Г = (7,67; 5.82)г.

И °'747

43. Так как /(У) = 29Д9 gt; /(*!) = 25,26, шаг неудачный.

52. Имеем у = 1 lt; АГ = 3. Положим у = у +1 = 2 и перейдем к шагу 2.

24. Получаем pound;2 = (-0,478;-0,214)г.

З4. Вычисляем

44. Так как /(у2) = 07 lt; /(**) = 25,26, шаг удачный. Положим

I2 = X1 + а(у2 -х1) = (7,4;7,49)Г +1,618[(5)92;6,83)7’ -(7,4;7,49)Г] = (5,005;6,42)Г,

/(г2) = 0,176 lt; /(х1) = 25,26, направление удачное.

Положим х2 = г2 =(5,005; 6,42)Г, /2 = а/1 = 2,618, pound; = pound; + 1 = 2. Так как

к = 2 lt; N = 10, положим У = 1 и перейдем к шагу 2.

25. Получаем 41 = (-0,361;0,112)г.

35. Вычисляем

У1 = х2 + Н рц= (5.005; 6,42)г + 2,618ЬМ!1М2Е1 = (2,93; 7,19)г.

45. Так как /(У) = 18,55 gt; /(*2) = 0,176, шаг неудачен.

53. Имеем У = 1 lt; М = 3. Положим у = у +1 = 2 и перейдем к шагу 2.

26. Получаем pound;2 = (0,674; 0,551)Г.

36. Вычисляем

У2 =х2+‘2Щ = ^005; 6,42^Г + 2,618amp;—^’551)Г = (7,03; 8,08)г.

46. Так как /(у1) = 20,81 gt; /(х2) = 0,176, шаг неудачен.

54. Имеем У = 2 lt; М = 3. Положим у = у +1 = 3 и перейдем к шагу 2.

27. Получаем pound;3 = (0,789;- 0,742)7.

37. Вычисляем

= (5,005; 6,42)г + 2,618 (°’789gt; = (6,91; 4,63)г.

4 7. Так как /(у3) = 14,73 gt; /(*2) = 0,176, шаг неудачен.

55. Имеем у = 3 = М. Так как г2 = 2,618 gt;Я = 03, положим /2 = 0,618 /2 = 0,618 • 2,618 = 1,618, у = 1 и перейдем к шагу 2.

2 8. Получаем = (- 0,824; - 0Д93)7.

3 8. Вычисляем

У'=Х2+*2Щ = (5,005; 6,42)Г +1)618^'’82084б’193^ = (3,43; 6,°5)Г-

4 8. Так как /(у1) = 9,86 gt; /(*2) = 0,176, шаг неудачен.

56. Имеем у = 1 lt; М = 3. Положим У = 7 + 1 = 2 и перейдем к шагу 2.

2 9. Получаем pound;2 = (-0,08; 0,917)г.

3 9. Вычисляем

У2 = х2 + lt;2 Д = (5,005; 6,42)г +1,618 ^0’08;^917)Г = (4,86; 8,03/.

4 9. Так как /(у2) = 4,19 gt; /(*2) = 0,176, шаг неудачен.

5 7. Имеем У = 2 lt; Л/ = 3. Положим У = у +1 = 3 и перейдем к шагу 2.

2 10. Получаем pound;3 = (0,05; 0,171)г.

З10. Вычисляем

У3 = х2 + /2= (5,005; 6,42/ +1,618 = (5,46; 7,97/.

4 10. Так как /(у3) = 4,73 gt; /(*2) = 0,176, шаг неудачен.

5 8. Имеем у = 3 = М. Так как г2 = 1,618 gt; Я = 0,8, положим /2 = 0,618 /2 = 0,618 • 1,618 = 1, у = 1 и перейдем к шагу 2.

2 11. Получаем = (0,251;-0,447)г.

3й. Вычисляем

у =х2+/2|^| = (5,005; 6,42/ + ^О.251^447)7' = (5gt;5; 5,54/.

4 11. Так как /(у1) = 1,21 gt; /(*2) = 0,176, шаг неудачен.

5 9. Имеем у = 1 lt; М = 3. Положим у = у +1 = 2 и перейдем к шагу 2.

2 12. Получаем pound; = (-0,812;0Д02)Г.

З12. Вычисляем

у2=х2+‘2Щ=(5,005; 6,42)Г'+1' ^~°,8ош102^ = (4,01; 6,54)Г •

412. Так как /(.У2) = 4Д2 gt; /(*2) = ОД76, шаг неудачен.

510. Имеем у = 2 lt; М = 3. Положим у = у +1 = 3 и перейдем к шагу 2.

213. Получаем pound;3 = (0,507; 0,537)г.

313. Вычисляем

gt;-3=*2+/2|г б°°5; 6gt;42)г+!^ГГ- amp;69; 7gt;15)г •

413. Так как /(gt;'3) = 3,23 gt; /(*2) = 0,176, шаг неудачен.

5й. Имеем у = 3 = М . Так как *2 = 1 gt; Я = 0,8, то положим /2 = 0,618*2 = 0,618, у = 1 и перейдем к шагу 2.

214. Получаем ^ = (-0,587; 0,461)Г.

314. Вычисляем

уХ=+М=(5,lt;Ю5; 6,42)Г+0|618^^quot;=(4,52; 6,8)Г #9632;

414. Так как /(у1) = 1,56 gt; /(х2) = ОД 76, шаг неудачен.

512. Имеем у = 1 lt; М = 3. Положим у = у +1 = 2 и перейдем к шагу 2.

215. Получаем pound;2 = (0,911; 0,018)Г.

315. Вычисляем

gt;quot;2=*2+'2^| = (5,005; 6,42)Г + 0,618 = (5,62;6,43)Г.

415. Так как /(.У2) = 1,72 gt; /(*2) = 0Д76, шаг неудачен.

513. Имеем у = 2 lt; М = 3. Положим у = у +1 = 3 и перейдем к шагу 2.

216. Получаем pound; = (-0,07;-0,971)Г.

316. Вычисляем

у3 = X2 + /21pound;| = (5,005; 6у42У + 0,618 И’07^971)! = (4,96; 5,803)г.

416. Так как /(у3) = 0,046 lt; /(х2) = 0,176, шаг удачен. Положим

г3 = х2 + а (у3 - х2) = (5,005;6,42)Г +1,618 [(4,96; 5,803)Г - (5,005;6,42)Г] =

= (4,93;5,42)г,/[г3| = 0,356gt;/(х2) = 0,176, направление неудачное. Перейдем к шагу 5.

514. Имеему = 3 = М, /2 = 0,618 lt; Я = 0,8. Поэтому х* = х2 = (5,005; 6,42)^, /(**) = 0,176 или, более точно, результат содержится в круге с радиусом *2 = 0,618 и центром в точке X2. Ш

Пример 5.19. Найти минимум функции /(х) = їх2 +х{х2+ х\ методом адаптивного случайного поиска.

? 1°. Зададим начальную точку х°= (0,5;1)Г; а = 1;Р = 0,5;Л/ = Ъ\Ы = 100; Я = 0,5; /о = 1 • Положим к = 0, у* = 1. Так как а = 1, согласно п. 2 замечаний 5.13 7 точка на шаге 4 не вычисляется.

2°. Получаем ^ = (- 0,875; - 0,436)^.

3°. Вычисляем

ЛГ

lt;0 Й = (0gt;5; 1)Г+1 ^0,870,977,436) = (quot; °,395; °’553)Г •

4°. Так как /{у11 = 0,399 lt;/(х°) = 2, шаг удачный. Так как а = 1, то Zl = у1, /(г1) lt; /(*°) * Положим х1 = I1 = у1 = (-0,395; 0,553)Г, А: = к +1 = 1,

/, = а /0 = *о = 1, у = 1 и перейдем к шагу 2.

21. Получаем = (0,199; 0,369)^.

31. Вычисляем

0,395; 0,553)г +1 • ^р^’369^ = (0,08; 1,43/.

41. Так как /(У) = 2,17 gt; /(я1) = 0,399, шаг неудачный.

5°. Имеем у = 1 lt; М = 3, поэтому У = У +1 = 2 и перейдем к шагу 2.

22. Получаем %2 = (0,287; 0,763)Г.

32. Вычисляем

у2=х' +,,р|=(quot; °gt;395; °’553)г +1 = (- 0.04; - 0,38)г.

42. Так как /(gt;'2) = 0,16 lt;/(я1) = 0,399, шаг удачный. Так как а-1, то

12=у29 /^2) lt;/(х1). Положим х2 = т} = у1 = (-0,04;-0,38)г, к = к +1 = 2,

/2 = а /, = /! = 1, у = 1 и перейдем к шагу 2.

23. Получаем ^ = (-0,937; 0,831)г.

3 3. Вычисляем

У = *2 + '2I = (- 0.04; -0,38)г +1 • Иgt;937’^831)1 = (_ о,79; 0,28)г.

4 3. Так как /(У) = М gt; /(*2) = 0Д6, шаг неудачный.

51. Имеем у = 1 lt; Л/ = 3, поэтому у = у +1 = 2 и перейдем к шагу 2.

2 [8]. Получаем 42 = (0,692;-ОДП)Т.

3 4. Вычисляем

у2 = х2 + /2 |^| = (- °gt;04; - О-38)7- +1 • ^6~|'7Н~^Г = lt;°gt;929; - °-63)г •

4 4. Так как /(у2) = 1.54 gt; /(*2) = ОД 6, шаг неудачный.

52. Имеем у = 2 lt; М = 3, поэтому у = у +1 = 3 и перейдем к шагу 2.

2 [9]. Получаем pound;3 = (0,596;-0,05)Г.

3 5. Вычисляем

= х2 + /2 ^ = (- 0,04; - 0,38^ +1 • = (0,956; 0,463)г.

4 5. Так как /(у3) = 2,48 gt; /(*2) = ОД6, шаг неудачный.

5 3. Имеем у = 3 = Л/, но t2=lgt;R = 0J5. Положим /2 = Р*2 = ОД у -1 и

перейдем к шагу 2.

2 6. Получаем = (0,08; 0,971)г.

3 6. Вычисляем

У = X2 + н = (- 0,04; - 0,38)г +1 • = (0,08; 0,118)г.

4 6. Так как /(у1) = 0,036 lt; /|х2| = 0Д6, шаг удачный. Так как а = 1, то

Положим х3 = г1 = у1 = (0,08;0Д18)Г,pound; = к +1 = 3, /3 = а(2 = 0,5; у = 1 и пе­рейдем к шагу 2.

2 7. Получаем %1 = (0,343; 0,512)Г.

3 7. Вычисляем

У = х3 + /31^| = (0,08; 0,118)г + 0,5^-6”’р^ = (0,358; 0,53)г.

28. Получаем \2 =(-0,218;-0,491)7'.

38. Вычисляем

у2 = х3+4 Щ= (0,08; 0,1 + 0,5 0,2 ^'ззу491^ = (- °-123; - °.34)г •

48. Так как /(у2) = 0,187 gt; /(*3) = 0,036, шаг неудачный.

55. Имеем у = 2 lt; М = 3, поэтому у = у +1 = 3 и перейдем к шагу 2.

29. Получаем pound;3 = (— 0,715;0Д52)Г.

39. Вычисляем

З'3 = *3 + /3 Р1 = (0,08; ОД 18)7quot; + 0,5 = (- 0,391; 0,284)г.

49. Так как /(у3) = 0,275 gt; /(*3) = 0,036, шаг неудачный.

56. Имеем у = 3 = Л/, *з = 0,5 = Я. Поэтому процесс завершается: х* г я3 = (0,08;0,118)Г; /(х*) г 0,036. #9632;

5.6.2. Метод случайного поиска с возвратом при неудачном шаге

Стратегия поиска

Задается начальная точка х°. Каждая последующая точка находится по формуле

ъ-к+1 _ * к к

X = X + pound; ,

где г* gt; 0 - величина шага; - случайный вектор единичной длины, опреде­ляющий направление поиска; к - номер итерации. На текущей итерации при по­мощи генерирования случайных векторов получаются точки, лежащие на ги­персфере радиуса ** с центром в точке хк (рис. 5.20). Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным (точки у1,у2 при поиске из х°; у1,у2,у3 при поиске из х1) , происходит возврат в текущий центр и поиск продолжается. Если число неудачных шагов из текущей точки достигает некоторого числа М , дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины Я . Если же значение функции в полученной точке меньше, чем в центре, шаг считается удачным и дальнейший поиск продолжается из этой точки.

Рис. 5.20 Алгоритм

Шаг 1. Задать начальную точку х°, коэффициент сжатия 0 lt; р lt; 1, М - максимальное число неудачно выполненных испытаний на текущей итера­ции, /0 - начальную величину шага, Я - минимальную величину шага, N - мак­симальное число итераций. Положить к = 0,у = 1.

Шаг 2. Получить случайный вектор =^1У,...,4Я^| , где - случайная

величина, равномерно распределенная на интервале [—1,1].

. pound;./

Шаг 3. Вычислить у] = хК + |у|'

Шаг 4. Проверить выполнение условий:

а) если /(у7) lt; /(**)gt; шаг Удачный. Положить х*+1 = у*, ^+1 = /*,

к = к +1 и проверить условие окончания. Если к lt; N, положить у = 1 и пе­рейти к шагу 2. Если к = N, поиск завершить: х* = х*;

б) если /(у7) ^ /(**)» шаг неудачный и перейти к шагу 5.

Шаг 5. Оценить число неудачных шагов из текущей точки:

а) если у lt; М , следует положить у = у +1 и перейти к шагу 2;

б) если у = А/, проверить условие окончания:

- если pound; Л, процесс закончить: х* = х*,/(х*| =

- если tk gt; Я, положить tk = Р**,у = 1 и перейти к шагу 2.

5.6.3. Метод наилучшей пробы

Стратегия поиска

Задается начальная точка х°. Каждая последующая точка находится по формуле

~Л+1 _ .Д , * с к X = X + ,

где tk gt; 0 - величина шага; - случайный вектор единичной длины, опреде­ляющий направление поиска; к - номер итерации. На текущей итерации при по­мощи генерирования случайных векторов получается М точек у1,...,ум,

лежащих на гиперсфере радиуса tk: с центром в точке хк (рис. 5.21). Среди по­лученных точек выбирается точка ут, в которой значение функции наименьшее. Если в выбранной точке значение функции меньше, чем в центре, то дальней­ший поиск продолжается из этой точки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины Я.

4 lt;

*2

ч

у1 Х...

Рис. 5.21

Алгоритм

Шаг 1. Задать начальную точку х°, коэффициент сжатия 0 lt; р lt; 1, М - число испытаний на текущей итерации, /0 =1 quot; начальную величину шага, Я - минимальную величину шага, N - максимальное число итераций. Положить к = 0, у = 1.

Шаг 2. Получить М реализаций случайного вектора = ^,-Ап^.

j = 1,..., М , где S,/ - случайная величина, равномерно распределенная на интер­вале [—1,1].

Шаг 3. Вычислить

yJ = хк +**тг®7|[gt; 7 = 1..... Л/.

И

Шаг 4. Найти /” из условия /(/”) = min /(у-').

1 uuml;juuml;M

Проверить выполнение условий:

а) если /(/quot;)lt; /(**), шаг удачный. Положить x*+1 = /*+1 = /*, А: = Л +1 и проверить условие окончания. Если к lt;N, положить У = 1 и перейти к шагу

2. Если к = N, поиск завершить: х* =хк \

б) если /(yw)^ /(**), шаг неудачный и перейти к шагу 5.

Шаг 5. Проверить условие окончания:

- если tk lt; R, процесс закончить: х* = = f\xkJ;

- если tkgt; R, положить tk = p,у = 1 и перейти к шагу 2.

Замечания 5.14.

1. Существуют варианты данного метода, в которых на шаге 4 полагают хк+1 _ ут szlig; этом случае становятся возможными шаги в направлении возраста­ния функции. Они могут позволить преодолевать локальные минимумы при по­иске глобального экстремума.

2. Недостатком метода является учет только наилучшей пробной точки. В отбрасываемых точках содержится полезная информация о поведении целевой функции.

3. Одним из методов учета информации, содержащейся во всех сгенериро­ванных точках, является алгоритм статистического градиента. Для каждой из М

реализаций pound;1,...,\м случайного вектора pound; , полученных в точке хк, вычисляют­ся разности

Дfi = f(xk + /прД*) - f(xk) , где /пр - пробное значение шага. В качестве направления поиска используется

1 м #9632; i dk

вектор статистического антиградиента dK или вектор трттг. Далее

Vy-1 г II

алгоритм решения совпадает с описанным выше.

Задачи для самостоятельного решения

1. Решить задачу

/(х) = Х[3 + х22 - Ъхх - 2х2 + 2-gt; min

методами конфигураций, деформированного многогранника, сопряженных направлений.

Ответ: точное решение х* = (1Д)Г.

2. Решить задачу

/(х) = (х{ - 2)2 + (х2 - 5)2 + (х3 + 2)2 min

методами конфигураций, деформированного многогранника, сопряженных на­правлений, Розенброка.

Ответ: точное решение х* = (2,5,- 2)Т.

3. Решить задачу

/(х) = х\ + х24 + 2х\Х2 - 4х{ + 3 min

методами конфигураций, деформированного многогранника, сопряженных

направлений.

Ответ: точное решение х* = (1,0)^.

4. Решить задачу

/(х) = (Х|2 + х2 -11)2 + (ху + х22 - 7)2 min

методами конфигураций, деформированного многогранника, сопряженных

направлений.

Ответ: точное решение х* = (3,2)Т.

5. Решить задачу

/(х) = 1 - 2xt - 2х2 - 4х!Х2 + lOxj2 + 2х22 min

методами конфигураций, деформированного многогранника, сопряженных

направлений, Розенброка.

Ответ, точное решение х* = (0Д5;0,75)Г.

6. Методом Свенна найти начальный интервал неопределенности для ре­шения задачи

/(х) = х2 - 6х +14 -#9658; min

при х° = 0; t = 1; t = ОД; t = 0,01.

Ответ: L0 = [1,7] при / = 1 ; L0 = [1,5;6,3] при / = ОД ; Lq = [1,27;5,11] при t = 0,01.

7. Методом Свенна найти начальный интервал неопределенности для решения задачи

/(х) = х2 + 6х +12 min.

Ответ:Lq = [-8; 4] при х° = -10, / = 2; Lq =[-5,1] при х° = 1, t = 2;

L0 = [—6;0] при х° = 1,/ = 1; Lq = [-7;-1] при х° = 0, t = 1.

8. Методами равномерного поиска, деления интервала пополам, дихотомии решить задачу

/(х) = х2 - 6х + 14 -gt; min,/о = [-2,4].

Ответ : метод равномерного поиска при N = 10 - х* е [2,364; 3,455]; метод деления интервала пополам: при / = 1 х* е [2,50; 3,25]; при / = ОД х* е [2,969; 3,063]; метод дихотомии: при / = 1, е = 0,2 х* е L6 = [2,35; 3,275], при / = 1,6 = 0,1 X* eL6 =[2,425;3,263]; при / = ОД ,s = 0,01 х* eLl4 = [2,960;3,017].

9. Методами равномерного поиска, деления интервала пополам, дихото­мии, золотого сечения, Фибоначчи решить задачу

/(х) = х2 + 6х +12 -gt; min, Lq = [-4Д].

Ответ: метод равномерного поиска при N = 10 : х* е L = [-3,545;- 2,636]; метод деления интервала пополам: при / = 1 х* е L6 = [-3,375;- 2,750]; метод дихотомии: при / = 1 ,е = 0,2 х* е 16 = [—3,4; — 2,6]; метод золотого сечения: при / = 1 х* е L5 = [-3,271; - 2,541]; при / = ОД х* € Ll0 = [-3,033; - 2,967]; метод Фибоначчи: при N = 5,6 = ОД х* е L5 = [—3375;— 2,650]; при N = 5, 6 = 0,01 х* е L5 = [-3,375;- 2,740]. Точное решение х* = -3.

10. Сделать 3 итерации методом конфигураций в задаче

/(х) = 4(xj - 5)2 + (х2 - 6)2 -gt; min

при х° = (1,2)г, е = 0,1 , A j = А 2 = 0,5 , а = 1^ , Я. = 1.

Ответ: полученные точки (1,5;2)г,(1^;2^)г, х1 = (2;3)г,(2^;3)г,(2^;3,5)г, х2 = (33;43)Г,(4;43)Г, (4;5)г, х3 =(5,5;6,5)г. Точное решение х* =(5,6)г.

11. Сделать 4 итерации методом деформируемого много1ранника в задаче

/(х) = 4(х! - 5)2 + (х2 - 6)2 min при е = 0Д;а = 1;у = 2 и следующих вершинах начального много1ранника:

(4,7)г, (3,2)г, (6,7)г.

Ответ: в результате трех последовательных редукций получены треуголь­ники, заданные своими вершинами. Первый треугольник: (4,7)г, (5,7)г,

(33;43)г; второй треугольник: (4,5;7)7, (5,7)7, (4,25;5,75)7; третий треуголь­ник: (4,75;7)7, (5,7)7, (4,625;6,375)7. В результате четвертой итерации -

растяжения - получен треугольник (4,938;6,063)7, (5,7)7, (4,625;6,375)7.

12. Решить задачу методом сопряженных направлений

/(х) = 4(х! - 5)2 + (х2 - 6)2 min

при х° = (1,2)7, 8 = ОД.

Ответ: решение получено за две итерации: tQ* = 4,001; (1,000; 6,001)7;

/1* = 4,000; х* = (5,000; 6,001)7. Точное решение х* = (5,6)7.

<< | >>
Источник: Пантелеев А. В., Летова Т. А.. Методы оптимизации в примерах и задачах: Учеб. посо- бие/А. В. Пантелеев, Т. А. Летова. — 2-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме МЕТОДЫ СЛУЧАЙНОГО ПОИСКА:

  1. 2. Классификация методов прогнозирования
  2. 5.5. Структура «поиска» рабочих мест в российской переходной экономике
  3. Расчетные методы и приемы анализа
  4. Эвристические методы анализа
  5. Общая характеристика математических методов анализа
  6. § 2. Метод экономической теории
  7. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА
  8. 14.4. Вопрос о методе раскрытия и расследования преступлений
  9. 4.2. Методы и средства собирания доказательств
  10. 2.1. Основные методы обучения праву
  11. 6.6. Оптимизация инвестиционного портфеля по методу Марковица
  12. ДЕТЕРМИНИРОВАННЫЙ МЕТОД ВЫБОРКИ
  13. 7.2. Моделирование ситуаций
  14. 14.2. Отбор и окончательный выбор консультанта