Как стать автором
Обновить

Комментарии 16

Очень интересно, но хотелось бы больше иллюстраций. Рой мошек в овраге зацепил, хочется визуализации… Сравнить ваш метод и обычный и показать как мошки распределяются…
Визуализацию сейчас попробую собрать. Но алгоритм конечно не мой, авторы — Rainer Storn и Ken Price.
Добавил в пост простую анимацию. Это то, что Вы имели в виду?
Куда интереснее как себя поведёт эта штука когда есть много локальных минимумов.
Когда баловался подобными алгоритмами — частенько популяция вырождалась, приходилось идти на разные ухищрения, чтоб заставить искать глобальный минимум. Теми или иными способами поддерживал разнообразие популяции, а не просто уточнение на каждом шаге.

А на таких простых функциях гораздо эффективнее классические алгоритмы, типа градиентного спуска.
Увеличивая силу мутации, этот алгоритм можно приблизить по свойствам к обычным стохастическим методам оптимизации, которые практически не используют локальную структуру функции и вырождаются медленно. Но скорость сходимости в этом случае ухудшается очень сильно. Все же настоящая многоэкстремальная задача — это не очень характерно для наиболее распространенных приложений. Чаще присутствует много небольших локальных минимумов, иногда прямо на склонах оврага, которые сильно мешают градиентным методам.

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

Кстати, DE на самом деле при небольшой силе мутации близок к градиентным методам, поскольку за счет подстройки облака точек к структуре функции он фактически строит аппроксимацию градиента (т.н. «стохастический градиент»). Ну и еще сильно помогает возможность гибко настраивать параметры, в зависимости от задачи, либо усиливая градиентные свойства (и увеличивая скорость сходимости), либо усиливая стохастические свойства (и увеличивая устойчивость к мелким локлаьным минимумам за счет скорости содимости).
Лично мне было бы интересно узнать сравнение данного алгоритма (да и генетических вообще) и, скажем, симплекс-метода. Пусть, для функции 5-10 аргументов с несколькими минимума. В случае использования однопоточного CPU; в случае многопоточного GPU.
Если под симплекс-методом Вы понимаете то, что обычно понимают под этим термином, то он применяется совсем в другой области (линейное программирование). В этой области у него нет конкурентов (в теории — кроме метода элипсоидов, но там громадная константа).

Если же Вы имели в виду метод симплекса (aka «метод отражений симплекса», aka «метод летающего симплекса»), то этот метод проигравает DE сразу и без вариантов. Отражения симплекса — простейший метод, хуже него только покоординатный спуск.
errata: «метод летающего симплекса» — > «метод шагающего симплекса»
Я имел в виду тот, который Нелдера-Мида. А какой выигрыш в скорости можно ожидать? Если грубо — это разы или прямо порядки?
Ну, тут тоже несколько разные области применения. Выигрыш в скорости для DE будет проявляться на сложных задачах, для которых симплекс будет быстро уменьшаться в размере и двигаться к минимуму очень медленно. В этом случае преимущество может быть и на порядки. Если же оба метода одинаково легко находят минимум, то метод симплексов может оказаться и быстрее, просто из-за своей логической простоты. Ну и будет еще целый класс задач, для которых DE будет давать правильное решение, а симплекс будет застревать в локальном минимуме.

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

Основное преимущество алгоритма — это хорошая сходимость в практически любых условиях, будь функция практически константная или с кучей локальных минимумов, или ещё с какой «бякой». То есть полная независимость от какого-то дополнительного знания про оптимизируемую функцию.
Тоже хорошее применение. Я его всегда имел в виду, но в моих проектах каждый раз получалось, что придумать адекватную автоматически вычисляемую функцию качества решения не проще, чем саму эвристику.
Интересно, будет ли этот метод работать на задаче совмещения изображений (например, создание панорам)
В принципе должен. Задача совмещения дает (очень) многоэкстремальную функцию ошибки, но главный минимум там получается очень глубокий. Мы как-то делали софт для совмещения последовательных кадров аэрофотосъемки (там нахлест почти 50% размера кадра, использовалось обычное корреляционное совмещение в спектральной области). Потом заказчик попробовал совместить сканы листов генштабовских карт (там нахлест уже маленький, процентов 10-15) и оказалось, что точное совмещение (неправильное) линий сетки дает гораздо меньшую ошибку, чем совмещение самого изображения (хитрость состояла в том, что наша оценка кросскорреляционной функции становилась все менее точной при приближении к краю изображения).
Попробую применить к 3D-облакам… интересно, что получится :)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории