Главная
Главная

Поиск по сайту:
Russian version         English version Главная -> Наука -> Вычислительные методы ->

Оптимизация функции нескольких переменных методом комплексов

Выберите файл с исходными данными:



Выполнено   387
успешных оптимизаций.

Общие сведения

Методы нелинейного программирования используются для поиска минимумов и максимумов функций нескольких переменных с учетом ограничений. Нелинейный характер задачи делает возможным достижение максимального или минимального значения не только на границе области поиска, но и внутри этой области. Одним из распространенных подходов к оптимизации функций нескольких переменных является метод комплексов (или комплекс-метод), относящийся к группе стохастических. В окрестности начальной точки поиска генерируется множество случайных точек (комплекс), "худшая" вершина которого затем заменяется на более "хорошую" путем отражения относительно центра тяжести или сжатия комплекса. При сходимости к минимуму или максимуму функции комплекс в пределе стягивается в точку. На практике поиск заканчивают при достижении некоторого условия - например, достаточно малого среднеквадратичного отклонения значений функции в вершинах комплекса.

На данной странице сайта представлена он-лайн реализация метода комплексов. Оптимизация может осуществляться как с ограничениями в виде неравенств по каждой из координат (в N-мерном параллелепипеде, где N-количество переменных), так и с частичными ограничениями или без ограничений (безусловный поиск локального экстремума от заданной начальной точки). Исходные данные подготавливаются пользователем в виде текстового файла - например, в редакторе Блокнот. Затем этот файл отправляется с помощью формы на сервер. Оптимизация длится не более 20 секунд, после чего в браузере пользователя отобразятся результаты и информация о том, достигнуто ли условие сходимости.

Структура файла исходных данных

Файл с исходными данными содержит три обязательных блока строк. Каждый из блоков начинается со служебной строки, первым символом которой является # (решетка). За служебной строкой следуют строки данных. Первый блок содержит код оптимизируемой функции. Во втором блоке задается тип оптимизации (поиск минимума или максимума). В третьем блоке указываются координаты начальной точки и границы области поиска. Перед первым блоком может помещаться неограниченное количество строк комментариев. Ни одна из них не должна начинаться с символа #. Кроме того, комментарий может располагаться в служебной строке сразу за первым символом #. Такой комментарий нельзя переносить на следующую строку. В содержимом каждого из трех блоков пустые строки игнорируются.

Блок кода оптимизируемой функции

Кодируется только правая часть выражения функции, т.е. без "F=" или "Y=". Переменные нумеруются, начиная с 1, и кодируются цифрой в фигурных скобках. Например, X1 и X2 кодируются как {1} и {2} соответственно (буква X не указывается). Так, функция F = 5X12 + X2 - 3.4 записывается в виде строки 5*{1}*{1}+{2}-3.4

Внутри кода оптимизируемой функции допускается использовать следующие имена наиболее распространенных математических функций.
   sin(), cos(), tan() - стандартные тригонометрические функции (синус, косинус, тангенс). Аргумент указывается в радианах.
   asin(), acos(), atan() - обратные тригонометрические функции (арксинус, арккосинус, арктангенс). Значение вычисляется в радианах.
   exp() - экспонента.
   log() - натуральный логарифм.
   sqrt() - квадратный корень.
   abs() - абсолютное значение.
   ceil() - значение, округленное до ближайшего большего целого.
   floor() - значение, округленное до ближайшего меньшего целого.
   pow(<Число>, <Степень>) - возведение <Числа> в <Степень>.
Например, выражение X13 можно закодировать как {1}*{1}*{1} или pow({1},3), а код pow({10},1/3) соответствует кубическому корню из X10. Число π задается двумя буквами: pi. Так, косинус от 60o кодируется в виде cos(pi/3).

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

Пример файла исходных данных Rosenbrock.txt для функции Розенброка f(X1, X2) = (1 - X1)2 + 100(X2 - X12)2 содержит все необходимые блоки, а также комментарии и дополнительный блок, о котором пойдет речь ниже. Этот файл следует использовать в качестве шаблона для формулирования собственных задач оптимизации.

Блок типа оптимизации

Этот блок является самым коротким и состоит из единственной строки данных с числом -1 или 1, которые соответствуют поиску минимума или максимума соответственно. Пример для поиска минимума функции приведен в Rosenbrock.txt.

Блок координат начальной точки и границ области поиска

Третий обязательный блок должен содержать не менее N непустых строк данных. Каждая строка относится к одной из переменных оптимизируемой функции в порядке их нумерации (первая непустая строка - к X1, вторая - к X2 и т.д.). В строке приводятся три числа, разделенных запятыми. Первое число задает нижнюю границу поиска по данной переменной, второе - координату начальной точки, третье - верхнюю границу поиска. Например, строка "4 , 7.8 , 20" указывает, что поиск ведется из точки с координатой 7.8 по данной переменной, и эта координата при поиске не выйдет за пределы 4...20. Координату начальной точки задавать обязательно, а любая из границ или обе сразу могут отсутствовать. В этом случае запятые с каждой из сторон от значения начальной координаты должны сохраняться. Так, строка " , 7.8 , 20" означает, что переменная будет неограничена снизу, но ограничена сверху, т.е. изменяться от - до 20. При наличии строки вида " , 7.8 , " поиск по данной координате будет осуществляться без ограничений. В примере файла исходных данных задан неограниченный поиск по обеим переменным.

Дополнительный блок параметров поиска

Это необязательный блок, он может отсутствовать. Основными параметрами комплекс-метода являются размер L области, в которой генерируется начальный комплекс из 2N случайных точек, и условие сходимости ε (среднеквадратичное отклонение значений функции в вершинах комплекса, при достижении которого процесс оптимизации считается завершенным). По умолчанию величина L равна 0.02, т.е. исходный комплекс будет построен внутри гиперкуба с ребром 0.02 по каждой координате. Начальная точка поиска находится в центре этого гиперкуба. Значение ε по умолчанию равно 10-6. Для большинства практических случаев значения параметров по умолчанию обеспечивают достаточную точность решения задачи нелинейного программирования. Однако иногда бывает необходимо использовать другие значения L или ε.

Дополнительный блок параметров содержит две строки данных, в первой из которых указывается значение L, а во второй - величина ε.

Например, при ε = 10-6 (точность по умолчанию) поиск минимума функции Розенброка не доходит до экстремума, поскольку он находится в очень узком и пологом овраге (см. рисунок). Можно убедиться в недостаточной сходимости, если удалить необязательный блок из файла Rosenbrock.txt и провести оптимизацию с оставшимися обязательными блоками. Тем не менее, указав значение ε = 10-9 в блоке дополнительных параметров, можно уверенно найти минимум тестовой функции Розенброка, имеющий координаты X1=1, X2=1.

Следует отметить, что в оригинальной публикации М. Дж. Бокса (M.J. Box, A new method of constrained optimization and a comparison with other methods. Computer J. 1965, Vol.8, P.42-52) предлагается генерировать исходный комплекс во всей области поиска (в параллелепипеде). При этом одна из вершин комплекса совпадает с точкой начального приближения. Тогда значение L не используется. Такой подход позволяет естественным образом учесть различия в масштабах по координатам, но не слишком подходит для функций с большим количеством оптимумов в области поиска. Вариант, предложенный Боксом, можно реализовать, если в блоке дополнительных параметров указать отрицательное значение L. В этом случае верхние и нижние границы для всех переменных должны быть определены, иначе будет установлено значение L по умолчанию, и исходный комплекс будет генерироваться внутри гиперкуба с ребром L=0.02.

Примеры файлов исходных данных для других тестовых функций:
Функция Химмельблау  f(X1,X2) = (X12 + X2 - 11)2 + (X1 + X22 - 7)2  (см. график)
Сферическая функция  f(X1,X2, ..., Xn) = Σ Xi2
Сферическая функция с ограничением
Функция Исома (Easom function)  f(X1,X2) = - cos(X1) cos(X2) exp [ -(X1-π)2 - (X2-π)2]  (см. график)

Некоторые особенности выполнения оптимизации

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

Большинство типичных ошибок, в том числе допущенных при кодировании функции, распознаются программой с выдачей соответствующих сообщений в браузер пользователя. Однако необходимо учитывать, что код функции интерпретируется на сервере во временный PHP-скрипт, и если затем в этом скрипте возникнут синтаксические ошибки языка PHP, то пользователь увидит "белый экран". Например, такое произойдет, когда вместо десятичной точки в числе поставлена запятая или в исходном коде функции переменная указана как X{5} вместо {5}. Если Вы наблюдаете "белый экран" более 20 секунд (предельное время, отведенное для оптимизации), то необходимо внимательно проверить код функции, исправить ошибки в файле исходных данных и повторить расчет.

Отзывы о работе программы онлайн-оптимизации можно направлять по адресу a.k@ngs.ru

© А.И. Хлебников


  

Рейтинг@Mail.ru