Обсуждение статьи "Популяционные алгоритмы оптимизации: Алгоритм растущих деревьев (Saplings Sowing and Growing up — SSG)"
Какой алгоритм лучше всего подходит для нахождения локальных экстремумов?
Грубо говоря, нужно, чтобы выдавался список параметров, наилучшим образом попадающих в локальные экстремумы (вершины).
На примере ежика, показывать координаты кончиков его иголок.
Скажите, а есть алгоритмы оптимизации, что имеют следующие особенности:
выбор только части параметров при их большом количестве;
оптимизация выбранных параметров происходит только используя генетический алгоритм, или тот алгоритм, который можно заменить генетикой;
алгоритм выбора активных параметров для текущей итерации не имеет значения, допускается изменение диапазонов и шага оптимизации
Какой алгоритм лучше всего подходит для нахождения локальных экстремумов?
Грубо говоря, нужно, чтобы выдавался список параметров, наилучшим образом попадающих в локальные экстремумы (вершины).
На примере ежика, показывать координаты кончиков его иголок.
Для любой задачи глобального поиска лучшим образом подойдут любые алгоритмы сверху таблицы. Можно выбрать индивидуально под задачу более подходящий если известно, например, что функция гладкая, или дискретная, или выбрать по таблице наиболее подходящий по количеству оптимизируемых параметров в задаче.
Обычно не ставят задачу таким образом, что нужно найти локальные экстремумы, потому что в большинстве практических задач неизвестно количество локальных экстремумов (если бы это было не так, то было бы проще использовать аналитические методы), а количество глобальных экстремумов заведомо известно - один (если глобалов с одинаковым значением несколько, то это равносильно тому что он один). Поэтому обычно задачу стараются ставить так, что бы функция была как можно более монотонной, пример - минимизация ошибки.
Алгоритмов для решения задач поиска локалов в общем случае мне не известно, а специфичные алгоритмы под конкретную задачу редко когда бывает целесообразно писать. В таких случаях я бы подумал над тем, как можно представить ФФ, что бы решить задачу. Подходы могут быть разные, например, использование АО как надстройка над кластеризацией. Другой подход к проблеме - разбить ФФ на гипотетические "слои", от глобального минимума до глобального максимума (которые предварительно нужно найти), а потом исследовать каждый слой последовательно, то есть тут уже нужно менеджер пакетных задач для АО делать.
А если коротко, то разочарую - алгоритмов не существует для решения задач поиска локальных экстремумов в общем виде. Проще видоизменить ФФ чем делать специальный алгоритм.
Скажите, а есть алгоритмы оптимизации, что имеют следующие особенности:
1. выбор только части параметров при их большом количестве;
2. оптимизация выбранных параметров происходит только используя генетический алгоритм, или тот алгоритм, который можно заменить генетикой;
3. алгоритм выбора активных параметров для текущей итерации не имеет значения, допускается изменение диапазонов и шага оптимизации
1. Ну так то АОу всё равно, сколько и какие параметры подать ему на оптимизацию, поэтому можно подать все параметры в АО а можно и не все.
2. Можно применять любой алгоритм индивидуально, совместно, последовательно и комбинированно. Алгоритмы в статьях я постарался делать единообразными.
3. Любой из представленных алгоритмов может быть настроен прямо в процессе оптимизации, в принципе. Нужно только поправить инициализацию, что бы не сбрасывалась накопленная популяция. Можно, к примеру, уменьшать шаг оптимизируемых параметров пропорционально пройденным эпохам (или увеличивать).
А если коротко, то разочарую - алгоритмов не существует для решения задач поиска локальных экстремумов в общем виде. Проще видоизменить ФФ чем делать специальный алгоритм.
Спасибо. Косвенно нахожу локальные через принудительное прерывание оптимизации при задействовании большого количества ядер. Грубо говоря, в Тестере 20 агентов, прерываю оптимизацию после 2000 проходов.
Спасибо. Косвенно нахожу локальные через принудительное прерывание оптимизации при задействовании большого количества ядер. Грубо говоря, в Тестере 20 агентов, прерываю оптимизацию после 2000 проходов.
Ну, это же совсем антинаучно!))))) Хотя, находчиво.
Я вот что подумал, есть же алгоритмы повышенного "кучкования", когда популяции свойственно разделяться на группы по локалам, такие как IWO, COA, ABC, BFO, популяции этих алгоритмов можно анализировать на предмет кучек агентов (логическая поисковая единица в АО называется агент) измеряя евклидово расстояние между агентами, т.е. искать группы агентов с минимальным расстоянием между ними.
Можно ещё попробовать в таких откатных (когда агент многократно делает попытки поиска в разные стороны из одного и того же положения) алгоритмах как COA и HS или МА установить счетчик попыток, делать срезы состояний популяции через несколько итераций и агенты с наибольшими количествами попыток и будут локальными экстремумами. У МА и BFO так вообще нативно такой счетчик есть.
Т.е., я говорил что точных способов поиска локалов нет (поиск глобала в этом отношении можно считать "точным"), а приблизительно можно искать как описал выше. Для точного решения необходимо знание дифф-информации о ФФ.
ЗЫ. Интересный вопрос всем кому интересна эта тема: чем отличаются локальные экстремумы от глобальных (не принимая во внимание их разницу значений FF)?
ЗЗЫ Ответив на первый вопрос многие вопросы отпадают сами собой.
К сожалению, некомпетентен совсем, поэтому интересуюсь пусть и приблизительным, но готовым решением.
ЗЫ. Интересный вопрос всем кому интересна эта тема: чем отличаются локальные экстремумы от глобальных (не принимая во внимание их разницу значений FF)?
Если взять уже результат оптимизации в виде набора проходов, то намеки на локальные будут видны после применения кластеризации к пространству входных посчитанных проходов. Далее в каждом кластере добиваем "узкой" оптимизацией.
Какой алгоритм лучше всего подходит для нахождения локальных экстремумов?
Грубо говоря, нужно, чтобы выдавался список параметров, наилучшим образом попадающих в локальные экстремумы (вершины).
На примере ежика, показывать координаты кончиков его иголок.
К сожалению, некомпетентен совсем, поэтому интересуюсь пусть и приблизительным, но готовым решением.
Если взять уже результат оптимизации в виде набора проходов, то намеки на локальные будут видны после применения кластеризации к пространству входных посчитанных проходов. Далее в каждом кластере добиваем "узкой" оптимизацией.
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Опубликована статья Популяционные алгоритмы оптимизации: Алгоритм растущих деревьев (Saplings Sowing and Growing up — SSG):
Алгоритм растущих деревьев (Saplings Sowing and Growing up, SSG) вдохновлен одним из самых жизнестойких организмов на планете, который является замечательным образцом выживания в самых различных условиях.
Алгоритм растущих деревьев один из немногих, который не имеет четкого описания авторами (высказаны лишь общие положения и идеи). Представленные авторами операторы алгоритма также не являются готовыми инструкциями для алгоритмической реализации программы, не имеется четких указаний о дочерних и родительских деревьях и их взаимодействии. Требований к очерёдности выполнения операторов нет и любой пользователь может изменить их порядок с целью получения лучшего саженца.
В широком понимании SSG не является алгоритмом оптимизации, это общий набор правил, который предназначен дополнить другие алгоритмы для повышения качества оптимизации, то есть SSG - надстройка для любых эволюционных популяционных алгоритмов, поэтому у меня имеется простор для фантазии и возможность экспериментировать с конкретной реализацией алгоритма оптимизации. Я применил некоторые собственные соображения и накопленный опыт в процессе написания предыдущих алгоритмов и воспользовался ими для работы с SSG, результаты экспериментов представлены на суд читателя ниже.
Для начала понимания алгоритма нужно представить себе дерево как агента оптимизации. Дерево - решение задачи оптимизации, где каждая ветвь является оптимизируемым параметром задачи. Весьма абстрактно и, я бы сказал, художественно, можно иллюстрировать дочернее дерево и родительское (алгоритм оперирует этими двумя понятиями) на рисунке 1. Ствол дерева - набор оптимизируемых параметров. Каждая ветвь - отдельный оптимизируемый параметр, где длина ветви ограничена допустимым диапазоном значений соответствующего параметра. Направление ветвей не имеет значения и на рисунке представлены только для того, что бы показать что они отличаются.
Автор: Andrey Dik