|
| |
|
Слаботочка Книги ним тогда, когда целевая функция мультимодальиа или имеет узкие гребни, извилистые овраги и т. д. По мере того как стоимость вычислений падает, а скорость пх растет, метод случайного поиска становится все более привлекательным с прикладной точки зрения. К сожалению, метод случайного поиска имеет один серьезный недостаток - большое число попыток. Предположим, что имеются п входных характеристик jyXi, 7X2, ..NXn, которые могут изменяться в пределах от О Гфдделы поисиа  Контуры урсЗней иеледой фунщаи Рис. 8.1. Случайное размещение входных леременных по внутренней области поиска. ДО 1. Пусть максимальное значение целевой функции находится в подобласти заранее выбранного размера а по -отношению ко всей области поиска. Другими словами, а является вероятностью того, что случайно выбранная точка попадает в желаемую подобласть. Вероятность противоположного события составит 1-а, а та же вероятность для М независимых экспериментов, связанных с выбором точки, составит (1-а)-. Отсюда следует, что вероятность попадания точки в желаемую область в результате по крайней мере одного из экспериментов составит -(1-а); из последнего соотношения можно записать, что log {1-й) т. е., другими словами, Р представляет вероятность успешного исхода эксперимента, или вероятность того, что по крайней мере одна попытка поиска будет осуществлена в подобласти, содержащей максимум. Напри-.мер, если требуемая вероятность успешного исхода рав-13* 195 на Р=:95% и размер подобласти составляет а=Ь%, то число попыток поиска будет достаточно велико: М=59. Важно отметить, что число пробных шагов поиска не зависит от числа входных переменных п эксперимента. Как было установлено (Уайлд и Бейтлер, 1967), многомерность исследуемого пространства в задачах оптимизации ведет к существенному уменьшению эффективности любого метода, для которого область неопределенности стремятся установить как фгшсированную долю полного объема пространства поиска. Например, если Натуры постоянных роЗнди целеВоа функции Рнс. 8.2. Ползущий случайный поиск в двух направлениях.  число входных переменных равно 50, то гиперкуб, содержащий лишь 10% полного объема (а=0Л), будет по каждой переменной (одной из своих сторон) давать 0,1=0,91. При малом /г, например, /г8, оказывается возможным использовать случайный поиск для отыскания глобального оптимума (Хилл, 1969). Еще один недостаток метода случайного поиска состоит в том, что сохраняется информация только о наибольшем значении целевой функции; информация о максимуме, содержащаяся в остальных М.-1 значениях целевой функции, теряется. В связи с этим был предложен более удобный вариант метода случайного поиска (Брукс, 1958), названный методом ползущего случайного поиска (рис. 8.2). Согласно этому методу, начиная с пробной точки, изменяют jvXi и Л-Х2 иа случайную по-лохительную или отрицательную величину Дл-Х1, AnXi. Если У(л-Х1, ;уХг) не увеличивается, то дают новое случайное изменение, пока не будет достигнуто увеличение У. Точки (ivA:i-f Д л-xi, 1уХ2+ДлгХ2) используют затем 196 как основание для нового случайного изменения. Каждый десятый шаг, например, можно сделать достаточно большим, чтобы избежать так называемого зависания> на локальном: оптимуме, если исследуемая поверхность отклика мультимодальиа. В качестве другого усовершенствования можно ввести корреляцию между случайными изменениями, т. е. сделать изменения в направлении предыдущих успешных шагов более вероятными, чем изменения просто в двух направлениях (Корн, 1966). 8.2.1.2. Метод вращающихся координат Метод вращающихся координат, первоначально описанный Розенброком в 1960 г., оказался особенно эффективным тогда, когда поверхность отклика имеет извилистые овраги, как показано на рис. 8.3 (Розен-брок, 1960). Начиная с некоторой начальной, или пробной, точки, локально исследуют поверхность отклика вокруг этой точки и находят наилучшее направление поиска. Затем координатную систему поворачивают так, чтобы одна ось располагалась в направлении гребня.  д0(м(1иимум} Л5 Рис. 8.S. Задача Розенброка с извилистым оврагом : г/=100Х 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 [63] 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |