Навигация
Метод поиска с «наказанием случайностью»
17548
знаков
2
таблицы
2
изображения
2. Метод поиска с «наказанием случайностью».
Метод является аналогом метода наискорейшего спуска, только направление локального поиска не градиентное, а случайное. Как и в предыдущем методе, из текущей точки делают случайные шаги до тех пор, пока не будет найдена точка с лучшим значением критерия оптимальности. Затем в этом направлении регулярным методом одномерного поиска ищут оптимум. В точке оптимума по направлению опять случайным образом ищут новое направление и т.д.
Условием окончания обычно является невозможность получения лучшей точки из текущей за предварительно заданное число попыток 
.
3. Метод с «блуждающим поиском».
Данный метод является статистическим расширением градиентного метода и реализуется в соответствии с алгоритмом
где 
– случайный вектор с единичным модулем, 
и 
– коэффициенты, характеризующие вклад случайной составляющей 
и регулярной составляющей () в величину шага.
Чаще в формуле для 
используется не градиент 
, а составляющие направляющие косинусы градиента, что позволяет выдерживать заданное соотношение между регулярной и случайной составляющими шага.
Теоретически доказывается, что данный алгоритм наиболее вероятно приведет к глобальному экстремуму. В алгоритме могут использоваться алгоритмы коррекции шага , свойственные градиентному методу, который включается после неудачных попыток. Условием окончания является малость значения шага 
.
Стратегия поиска может предусматривать не постоянное, а периодическое добавление случайного вектора к градиентному шагу. Частота случайных «скачков» должна уменьшаться по мере приближения к оптимуму и увеличиваться вдали от него. Для этого существуют специальные алгоритмы самообучения, например:
,
где 
– число шагов регулярным градиентным методом без случайной составляющей, т.е. период добавления случайной составляющей;
– заданное целое число (рекомендуется 
, при этом в процессе поиска будет изменяться в диапазоне 
).
Обратно пропорционально частоте «скачков» меняется и доля случайной составляющей в шаге, т.е. 
. Условием окончания поиска будет, как и в регулярном градиентном методе, близость градиента к нулю.
Математическое описание
Метод слепого поискаИдея метода очень проста и наглядна. Случайным образом в допустимой области берется точка, и сравнивается значение критерия в ней с текущим наилучшим. Если новая случайно взятая точка хуже хранящейся в качестве текущей лучшей, то берут другую точку. Если же нашли точку, в которой критерий лучше, то ее запоминают в качестве текущей лучшей. Гарантируется, что при неограниченном возрастании числа попыток мы будем приближаться к глобальному оптимуму, т.е. найденное текущее наилучшее значение будет столь угодно близко к точному решению.
На практике поиск прекращают, когда число неуспешных попыток превышает наперед заданное число .
Данный поиск можно применять для поиска начального приближения, задав сравнительно небольшое число попыток. Метод прост в алгоритмическом плане и не требует примера с конкретными значениями.
Для получения случайных чисел , принадлежащих открытому интервалу (
) используют функцию преобразования
,
если нужны целые числа, используют
.
2. Блок – схема алгоритма моделирования
 | |||
 | |||
Описание ввода – вывода
1 – вводим выбранную нами функцию;
2 – ввод выбранного нами интервала.
3 – вводим число итераций;
4 – основной цикл для вычислений;
5 – реализация случайной величины для получения значений координат точки;
6 – вычисляем значение функции;
7 – первая итерация;
8 – первое вычисляемое значение оптимально;
9 – выбираем следующее более оптимальное значение;
11 – текущее значение является оптимальным;
12 – выводим X1, X2, Y оптимальные, т.е. выводим минимум функции
3. Инструментальные программные средства
Программирование по Windows всегда было достаточно сложной задачей. Интерфейс прикладного программирования (Application Programming Interface – API) Windows предоставляет в распоряжение набор мощных, но не всегда безопасных инструментов для разработки приложений. С появлением Delphi ситуация изменилась. С помощью интерфейса для быстрой разработки приложений (Rapid Application development – RAD) Delphi позволяет быстро и легко разработать приложение очень высокого уровня. Используя Delphi, можно создавать и тестировать приложения со сложным пользовательским интерфейсом без прямого использования функций API. Освобождая программиста от проблем, связанных с применением API, Delphi позволяет сконцентрироваться непосредственно на написании кода программы. Delphi – наиболее мной изученная мощнейшая среда разработки, имеющая все необходимые функции для разработки программной модели численного метода поиска экстремума функции.
Похожие работы
... философии - особенно с методологических позиций материалистического понимания истории и материалистической диалектики с учетом социокультурной обусловленности этого процесса. Однако в западной философии и методологии науки XX в. фактически - особенно в годы «триумфального шествия» логического позитивизма (а у него действительно были немалые успехи) - научное знание исследовалось без учета его ...
... мальне значення показникунадійності, при якому приймається рішення про орєінтованийзвязок назвем порогом показника надійності і позначимо (). Для можливості порівняння результатів у різних парах змінних в одній задачі системного синтезу корисно ввести відносний показник надійності. Відносним показником надійності ηij приняття рішення про напрям звязку між змінними xj → xi (стрілка в ...
... И. Европоцентризм и русское национальное самосознание // Социологические исследования. 1996. № 2. С. 55–62. 24. Зиммель Г. Экскурс по проблеме: как возможно общество? // Вопросы социологии. 1993. Т. 2. № 3. С 16-26. 25. Иванов В.Н. Реформы и будущее России // Социологические исследования. 1996. № 3. С. 21-27. 26. Капусткина Е.В. Социальные реформы в России: история, современное ...
... Замечат. С.: Полемон, Герод Аттик, Аристид, Либаний. Ср. Schmid, "Der Atticismus in seinen Hauptvertretern" (1887-97). 17. Принцип детерминизма в философии. Индетерминизм. Детерминизм (от лат. determino - определяю), философское учение об объективной закономерной взаимосвязи и взаимообусловленности явлений материального и ...
0 комментариев