|
|
Здесь нет описаний конкретных алгоритмов и программ.
Скорее - общие рассуждения на заданную тему...
Параметрическая оптимизация - тема,
которой я увлеченно занимался в начале
своей программистской деятельности и к
которой не раз возвращался в тех или
иных обстоятельствах.
От самой первой своей уже "инженерной" задачи, оказавшейся, ни много, ни мало - решением
системы нелинейных алгебраических уравнений методом - только не надо смеяться,
была проявлена инженерная смекалка! - дихотомии. Здесь я впервые на собственной шкуре узнал,
как важно знать, где искать. И как полезно правильно
определить интервал унимодальности
при одномерном поиске. А заодно, с цифрами, то бишь, с
распечатками в руках показал своим
теоретикам, что их задача имеет в общем случае два решения. В результате родилось выдающееся
открытие: оказывается прямоугольный лист можно свернуть в трубку, как по длинной, так и по
короткой стороне!
До самой последней: поиска максимального замкнутого пути в связанном ориентированном графе,
с последующим разбиением оного на связанные же подграфы, максимизируя суммарную длину таких подграфов.
Клиринговые расчеты во вселенской клиринговой системе!
Между этими двумя точками несколько лет в разных вариантах решалась классическая задача параметрической
оптимизации:
-
найти экстремум функции нескольких (в моем случае до 15..20) переменных, описываемой системой нелинейных
алгебраических уравнений, при наличии ограничений (числом до 30), заданных функционалами, определяемых из решения
нескольких (от 2 до 6) систем нелинейных дифференциальных уравнений (порядок систем 7..20).
Очень научно!
Пакостность математического описания функции качества как-то сразу заставила обратиться к методам
"случайного поиска с самообучением". Несколько книжек Леонарда Андреевича Расстригина были
зачитаны до дыр. В результате появилась программа PSK578, в которой были скомбинированы
два, предложенных Расстригиным метода: адаптированный поиск по направляющему конусу и стохастический
градиентный поиск.
Идея комбинированного алгоритма состоит в том, что информация, получаемая при поиске очередного
направления по конусу, накапливается и, если поиск по конусу не удался, используется для вычисления
статистической оценки градиента. По которой проводится исследующий поиск перед очередным уменьшением
радиуса направляющего конуса и увеличением угла его раскрытия.
Примерно для 8..10% таких попыток новое направление поиска оказывалось удачным, что для решавшейся
задачи было не плохо.
Помимо всего, в программе было заложено несколько хитрых приемов для борьбы с застреванием
на границах ограничений и учета "физически не реализуемых сочетаний варьируемых переменных".
Худо-бедно, но пару задач из предметной области, которой я в ту пору занимался, удалось
"соптимизировать". Программа даже
приобрела определенную популярность, по меньшей мере, еще в четырех
работах из смежных областей ее использовали. Правда, увы, не всегда указывалось авторство.
Исходная задача была связана с попытками улучшить характеристики изделия, уже принятого на ... э-э-э
в массовое производство. Поэтому
пространство допустимых (по ограничениям) решений было чрезвычайно
мало. Это заставило искать методы исследования пространства параметров, позволяющие определять области
возможного расположения экстремума.
Первоначально, для определения "начальной точки" поиска использовался алгоритм изменения распределений случайных значений управляемых переменных. Случайные значения управляемых переменных с большей вероятностью генерируются в некоторой β-окрестности предполагаемого оптимума. Замечательное свойство алгоритма - исключительно просто реализуется анализ на "физическую реализуемость сочетания параметров" - очередная проба попросту объявляется несуществующей. При невысоких требованиях к определению оптимума алгоритм успешно реализовался как самостоятельный алгоритм оптимизации. Например, - редкий случай, когда могу явно назвать объект оптимизации, - для оптимизации параметров компрессора бытового холодильника (см. работы М.Ю.Елагина.) (К сожалению, авторов алгоритма указать не могу - был опубликован в закрытом источнике. А вот программа, его реализующая, спустя 12 лет нашлась, есть повод для разговора...)
Но появилась следующая книжка, так же, до дыр, зачитанная. Соболь И.М., Статников Р.Б.
"Выбор оптимальных параметров в задачах со многими критериями". Авторы придумали "ЛП-τ" распределение, "более представительное, чем равномерное".
Нетривиальный механизм генерации пробных точек в пространстве параметров использовался ими для решения
многокритериальных оптимизационных задач (точнее - использовался способ интерпретации результатов исследования в ЛПτ точках). На мой взгляд, любые попытки формализовать решение подобных задач, должны сводиться скорее к предоставлению Лицу, Принимающему Решению некой дополнительной информации для принятия решения, не больше. Поэтому, алгоритм ЛПτ-поиска был использован как метод поиска начальной точки для применения программа PSK578. Попутно, накопленная информация использовалась для решения принципиально новой задачи, но об этом, если руки дойдут, потом...
Так у меня зафиксировался на некоторое время подход к оптимизационным задачам: ЛПτ-поиск для исследования пространства параметров и определения начальной точки поиска, затем - использование алгоритма самообучаемого поиска PSK578.
В самом начале 90-х, когда востребованным стало программирование уже совсем других задач, неожиданно предложили мне по старой памяти порешать одну новую задачку. Сводилась она, в конечном счете, снова к решению небольшой нелинейной системы алгебраических уравнений. Система имела достаточно мерзкую структуру, чтобы решать ее, как задачу минимизации "невязки правых частей".
И порядок действий уже привычный: ЛПτ-поиск плюс что-нибудь самообучаемое...
Очень удачно было отпущено время на работу - с января по июнь, как раз семестр. Решил, поиграю-ка я в руководителя проекта, и раздал куски задачи студентам в виде курсовых работ. А сам зачитался какой-то книжкой по численным методам и... призадумался. Призадумался на тему, а почему это я никогда классические методы оптимизации не использую?
Пишут же умные люди, дескать, градиентные методы за n+1, что ли, шагов экстремум дают... А переменных у меня сегодня не так много... Ну да, ну да. Выражения для производных здесь не выведешь. Но ведь можно попробовать производные и численно вычислять. И, пока студиозы корпели над реализацией, настучал безыскусную процедуру численного определения градиента и градиентного поиска.
Студентов я муштровал жестко и, когда они получили вожделенные пятерки, получил работающую систему. Объединил со своим градиентным поиском, запустил супер персоналку типа ДВК-3... и пошел к Заказчику объясняться. "Такой точности не бывает". Заказчик сравнил
результаты со своими представлениями о счастье. И понял - счастье есть. А я отправился уже для собственного удовольствия играть в "что будет, если".
Для этой конкретной задачи получилось вот что (все цифры по памяти и применительно к упомянутой "ЭВМ").
ЛПτ-поиск занимал 20-30% общего времени решения, случайный поиск с самообучением улучшал решение после ЛПτ-поиска на 2-3 порядка.
Градиентная подсистема, требовала дополнительно процентов 10 времени, точность решения увеличивалась еще на 3-5 порядков. Условимся эти результаты считать эталонными.
Попытки добиться такой же точности без применения градиентной процедуры за счет ужесточения условий останова самообучающегося случайного поиска эффекта не дали. Поиск вырождался и останавливался.
Отказ от предварительного этапа ЛПτ-поиска увеличивал время решения в 1.5-2 раза.
Отказ от промежуточного этапа случайного поиска увеличивал время решение более чем 3 раза. При этом, так же как и в случае отказа от ЛПτ-поиска, т.е. при случайной начальной точке, градиентный поиск достаточно часто "зависал" на начальных итерациях.
Заметим, что решалась задача без ограничений. Для задач условной минимизации учет ограничений в градиентной процедуре не тривиален.
А вот и мораль, свежая и оригинальная.
Нет метода для любой задачи. Потребная точность, затраты на решение (время) определят выбор метода оптимизации или их сочетания и последовательности применения.
Ищите, и обрящете!
|
