лучший метод глобальной оптимизации

[allchemist]

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

речь явно не о ГА, скорее о PSO и прочих извращениях типа муравьино-пчелиных алгоритмов. сети Хопфилда сюда же.

Есть ли какие-то сравнения этих методов на сферических задачах в вакууме? Понятно, что это не жесткие алгоритмы, а просто идеи, и даже две реализации одного алгоритма могут работать с существенно разной эффективностью, но тем не менее...

[мат-ламер]

Посмотрите http://dxdy.ru/topic35642.html.

[allchemist]

ну это немного о другом.
мне бы обычную численную оптимизацию...

[mserg]

Как нам подсказывает здравый смысл, не существует эффективного метода на все случаи жизни. Поэтому почти все зависит от того, как выбираются задачи. Наиболее частые и полезные задачи коллекционируют коммерческие компании, и ищут пути их эффективного решения. Если нет доступа к базам задач – то не о чем и говорить, так как неправильное взятие «случайной задачи» исказит сравнение программ оптимизации. Обычно не составляет труда придумать небольшие задачи, на которых пакеты оптимизации дохнут. Правильно придумав выборку случайной задачи, можно вывести в лидеры любую из программ.

Так что есть «случайная задача»?

Есть еще один нюанс, связанный с маргинальными методами оптимизации (GA, PSO и прочие метода отжига). Как, например, возникают задачи, в которой неизвестны производные. Часто это некоторая система, которая описывается дифференциальными уравнениями с параметрами (длина винта, диаметр сопла и еще чего-то там). Нужно найти такие значения параметров, при которых бы достигался минимум/максимум некоторой функции. В древние времена это был черный ящик, на входе которого параметры, на выходе – значение функции оптимизации, а в самом ящике – решение дифференциального уравнения. Разумеется, производная по параметру недоступна при таком подходе. По мере развития численных методов и роста мощности компьютеров стало возможным формулировать и решать проблемы в виде большой задачи нелинейного программирования с более высокой эффективностью. Имеет одну задачу и разные формулировки. В зависимости от того, как сформулирована проблема зависит и «случайная задача», и лучший «метод».

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

В качестве примеров см. описание систем, "гарантирующих" нахождение глобального максимума:
- CBC - интересна интеллектуальным способом подбора эффективного алгоритма решения, правда это линейные задачи
- Couenne
- BARON

[allchemist]

спасибо за подробный ответ

couenne, baron и т.д. - я правильно понял, что это целочесленное программирование, и там используется что-то типа метода ветвей и границ?

сочетание с локальной оптимизацией бывает очень полезным, но иногда производная функции недоступна, или же сама функция задана неаналитически. В последнем случае, насколько я понимаю, используется только вероятностная глобальная оптимизация типа разных модификаций алгоритма Метрополиса, ГА и т.д., которые до сих пор часто используются.

я неточно сформулировал вопрос. пусть будет так: есть ли сейчас стохастические алгоритмы глобальной оптимизации, однозначно более эффективные, чем отжиг и ГА?

[mserg]

Ограничение класса алгоритмов только стохастическими методами ничего не меняет – требуется представительный набор тестовых задач. Сейчас каждый врет и хвалится на тех задачах, которые сам себе придумал. Нет базы для сравнения и выделения наилучшего. Видимо, и не будет. Можно предположить, что на множестве «всех задач» все алгоритмы одинаково тупы.

Модели Couenne и Baron могут содержать и непрерывные переменные; надо понимать, что ветвиться могут не только целочисленные переменные, но и непрерывные, а оценка границ и ветвление – только малая часть техник оптимизации.

Некоторые неаналитические функции можно «аналитизировать» с помощью реформулирования и целочисленных переменных, т.е. неаналитичность – не всегда приговор.

У меня сложилось впечатление, что применение стохастических методов связано с наработками 60-х и 70-х годов. Они неконкурентоспособны в сравнении с навороченными оптимизаторами, которые работают непосредственно с математическими моделями, а не в слепую с невязками и фитнессами.