|
Как нам подсказывает здравый смысл, не существует эффективного метода на все случаи жизни. Поэтому почти все зависит от того, как выбираются задачи. Наиболее частые и полезные задачи коллекционируют коммерческие компании, и ищут пути их эффективного решения. Если нет доступа к базам задач – то не о чем и говорить, так как неправильное взятие «случайной задачи» исказит сравнение программ оптимизации. Обычно не составляет труда придумать небольшие задачи, на которых пакеты оптимизации дохнут. Правильно придумав выборку случайной задачи, можно вывести в лидеры любую из программ.
Так что есть «случайная задача»?
Есть еще один нюанс, связанный с маргинальными методами оптимизации (GA, PSO и прочие метода отжига). Как, например, возникают задачи, в которой неизвестны производные. Часто это некоторая система, которая описывается дифференциальными уравнениями с параметрами (длина винта, диаметр сопла и еще чего-то там). Нужно найти такие значения параметров, при которых бы достигался минимум/максимум некоторой функции. В древние времена это был черный ящик, на входе которого параметры, на выходе – значение функции оптимизации, а в самом ящике – решение дифференциального уравнения. Разумеется, производная по параметру недоступна при таком подходе. По мере развития численных методов и роста мощности компьютеров стало возможным формулировать и решать проблемы в виде большой задачи нелинейного программирования с более высокой эффективностью. Имеет одну задачу и разные формулировки. В зависимости от того, как сформулирована проблема зависит и «случайная задача», и лучший «метод».
Насколько я информирован, не существует сколь-нибудь простых эффективных методов решения сколь-нибудь нетривиальных задач глобальной оптимизации. Все эффективные решатели – комбинированные. Поэтому вопрос о наиболее эффективном методе - не корректен. Существует множество техник, некоторые из которых можно было бы назвать методами, которые (иногда автоматически) подбираются в зависимости от задачи и используются совместно. Например, генетический метод и метод локальной оптимизации легко скрещиваются. «Любой» метод можно соединить с чем-либо еще – и можно получить более эффективный решатель. Может быть я повторяюсь, но современные эффективные пакеты оптимизации – системы совершенно адской сложности, а не какие-то там «методы», о которых нам рассказывали в ВУЗах. Они могут изучить модель, посмотреть на размер задачи, и интеллектуально подобрать нужные «методы», либо они настраиваются вручную параметрами.
В качестве примеров см. описание систем, "гарантирующих" нахождение глобального максимума:
- CBC - интересна интеллектуальным способом подбора эффективного алгоритма решения, правда это линейные задачи
- Couenne
- BARON
|
