|
Поиск по сайту: |
Главная -> Наука -> Вычислительные методы -> |
Общие сведенияМетоды нелинейного программирования используются для поиска минимумов и максимумов функций нескольких переменных с учетом ограничений. Нелинейный характер задачи делает возможным достижение максимального или минимального значения не только на границе области поиска, но и внутри этой области. Одним из распространенных подходов к оптимизации функций нескольких переменных является метод комплексов (или комплекс-метод), относящийся к группе стохастических. В окрестности начальной точки поиска генерируется множество случайных точек (комплекс), "худшая" вершина которого затем заменяется на более "хорошую" путем отражения относительно центра тяжести или сжатия комплекса. При сходимости к минимуму или максимуму функции комплекс в пределе стягивается в точку. На практике поиск заканчивают при достижении некоторого условия - например, достаточно малого среднеквадратичного отклонения значений функции в вершинах комплекса. На данной странице сайта представлена он-лайн реализация метода комплексов. Оптимизация может осуществляться как с ограничениями в виде неравенств по каждой из координат (в N-мерном параллелепипеде, где N-количество переменных), так и с частичными ограничениями или без ограничений (безусловный поиск локального экстремума от заданной начальной точки). Исходные данные подготавливаются пользователем в виде текстового файла - например, в редакторе Блокнот. Затем этот файл отправляется с помощью формы на сервер. Оптимизация длится не более 20 секунд, после чего в браузере пользователя отобразятся результаты и информация о том, достигнуто ли условие сходимости. Структура файла исходных данныхФайл с исходными данными содержит три обязательных блока строк. Каждый из блоков начинается со служебной строки, первым символом которой является # (решетка). За служебной строкой следуют строки данных. Первый блок содержит код оптимизируемой функции. Во втором блоке задается тип оптимизации (поиск минимума или максимума). В третьем блоке указываются координаты начальной точки и границы области поиска. Перед первым блоком может помещаться неограниченное количество строк комментариев. Ни одна из них не должна начинаться с символа #. Кроме того, комментарий может располагаться в служебной строке сразу за первым символом #. Такой комментарий нельзя переносить на следующую строку. В содержимом каждого из трех блоков пустые строки игнорируются. Блок кода оптимизируемой функцииКодируется только правая часть выражения функции, т.е. без "F=" или "Y=". Переменные нумеруются, начиная с 1, и кодируются цифрой в фигурных скобках. Например, X1 и X2 кодируются как {1} и {2} соответственно (буква X не указывается). Так, функция F = 5X12 + X2 - 3.4 записывается в виде строки 5*{1}*{1}+{2}-3.4
Внутри кода оптимизируемой функции допускается использовать следующие имена наиболее распространенных математических функций. Код функции может занимать несколько строк и переноситься в любом месте без разрыва чисел или имен функций. Пробелы внутри кода игнорируются. Пример файла исходных данных 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.
Примеры файлов исходных данных для других тестовых функций: Некоторые особенности выполнения оптимизацииПодготовленный файл исходных данных сохраняется пользователем на локальном компьютере, а затем отправляется на сервер с помощью формы, приведенной выше на данной странице. Через несколько секунд в браузере появится результат выполнения оптимизации. Большинство типичных ошибок, в том числе допущенных при кодировании функции, распознаются программой с выдачей соответствующих сообщений в браузер пользователя. Однако необходимо учитывать, что код функции интерпретируется на сервере во временный PHP-скрипт, и если затем в этом скрипте возникнут синтаксические ошибки языка PHP, то пользователь увидит "белый экран". Например, такое произойдет, когда вместо десятичной точки в числе поставлена запятая или в исходном коде функции переменная указана как X{5} вместо {5}. Если Вы наблюдаете "белый экран" более 20 секунд (предельное время, отведенное для оптимизации), то необходимо внимательно проверить код функции, исправить ошибки в файле исходных данных и повторить расчет. Отзывы о работе программы онлайн-оптимизации можно направлять по адресу a.k@ngs.ru |