Оптимизация многомерной нелинейной функции. Слепой поиск

где – случайный вектор с единичным модулем, и – коэффициенты, характеризующие вклад случайной составляющей и регулярной составляющей (g width=13 height=19 src="images/referats/12353/image006.png">) в величину шага.

Чаще в формуле для используется не градиент , а составляющие направляющие косинусы градиента, что позволяет выдерживать заданное соотношение между регулярной и случайной составляющими шага.

Теоретически доказывается, что данный алгоритм наиболее вероятно приведет к глобальному экстремуму. В алгоритме могут использоваться алгоритмы коррекции шага , свойственные градиентному методу, который включается после неудачных попыток. Условием окончания является малость значения шага .

Стратегия поиска может предусматривать не постоянное, а периодическое добавление случайного вектора к градиентному шагу. Частота случайных «скачков» должна уменьшаться по мере приближения к оптимуму и увеличиваться вдали от него. Для этого существуют специальные алгоритмы самообучения, например:

,

где – число шагов регулярным градиентным методом без случайной составляющей, т.е. период добавления случайной составляющей;

– заданное целое число (рекомендуется , при этом в процессе поиска будет изменяться в диапазоне ).

Обратно пропорционально частоте «скачков» меняется и доля случайной составляющей в шаге, т.е. . Условием окончания поиска будет, как и в регулярном градиентном методе, близость градиента к нулю.

Математическое описание

Метод слепого поиска

Идея метода очень проста и наглядна. Случайным образом в допустимой области берется точка, и сравнивается значение критерия в ней с текущим наилучшим. Если новая случайно взятая точка хуже хранящейся в качестве текущей лучшей, то берут другую точку. Если же нашли точку, в которой критерий лучше, то ее запоминают в качестве текущей лучшей. Гарантируется, что при неограниченном возрастании числа попыток мы будем приближаться к глобальному оптимуму, т.е. найденное текущее наилучшее значение будет столь угодно близко к точному решению.

На практике поиск прекращают, когда число неуспешных попыток превышает наперед заданное число .

Данный поиск можно применять для поиска начального приближения, задав сравнительно небольшое число попыток. Метод прост в алгоритмическом плане и не требует примера с конкретными значениями.

Для получения случайных чисел , принадлежащих открытому интервалу () используют функцию преобразования

,

если нужны целые числа, используют

.

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 – наиболее мной изученная мощнейшая среда разработки, имеющая все необходимые функции для разработки программной модели численного метода поиска экстремума функции.

4. Операционная среда моделирования

Windows XP – новая операционная система фирмы Microsoft, непосредственно преемница Windows 2000. В основном повторяя архитектуру своей предшественницы, она делает свою работу на компьютере более эффективно и предоставляет пользователю много дополнительных возможностей, кроме того появился новый интерфейс

Основные задачи, связанные с работой в среде Windows 98:

· Загрузка Windows XP и завершение работы на компьютере

· Получение помощи по ходу работы

· Выбор типа пользовательского интерфейса

· Использование стандартных панелей

· Смена языка

· Управление загрузкой Windows XP

Обладая вытесняющей многозадачностью, способностью исполнять несколько программ одновременно и перераспределять ресурсы компьютера между ними по собственной инициативе.

Имеет высокий уровень совместимости с ранее накопленном программным обеспечением, которое разрабатывалось для MS-DOS и предыдущих версий Windows

 Скачать реферат