Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
Не понял я вашего алгоритма, хоть и очень старался.
Вы говорите то о цветах и частицах, то о «стенах», глобальных экстремумах и снова о пчелах. Трудно уследить за мыслью.
Вы говорите то о цветах и частицах, то о «стенах», глобальных экстремумах и снова о пчелах. Трудно уследить за мыслью.
Эх, жаль, что не выбрали для описания алгоритм поведения колонии муравьев. Просто есть в нем — в алгоритме поведения реальных муравьев — одна странная (так и хочется назвать это багом, но как-то рука не поднимается написать такое про не человеком созданные алгоритмы, да к тому же каламбур ;) особенность. В определенных ситуациях огромный табун муравьев начинает ходить по кругу, превращаясь в черное кольцо, и не может остановиться, вследствие чего муравьи умирают от изнеможения. Просто вот очень хотелось бы почитать, как это формализуется, так сказать :)
> Просто вот очень хотелось бы почитать, как это формализуется, так сказать :)
ru.wikipedia.org/wiki/Муравьиный_алгоритм
ru.wikipedia.org/wiki/Муравьиный_алгоритм
Муравьи-кочевники никогда не производят индивидуальную фуражировку или разведку, но действуют большими группами (Schneirla, 1971; Gotwald, 1995; Rettenmeyer, 1963). Такая фундаментальная неспособность муравьев-кочевников к индивидуальной фуражировке приводит к необычному феномену бега по кругу (Schneirla, T. C. 1944. Am. Mus. Novit. 1253, 1–26), когда все муравьи бегут по феромонному следу друг за другом по кругу (хоть вокруг большой тарелки) и каждый буквально по рабски ступает след в след впереди бегущему муравью, вплоть до полного изнеможения и смерти!Нашел где-то в интернетах.
Немного промазал с ответом.
Это недостаток алгоритма. Причем не только низшие насекомые ему подвержены :)
У спелеологов есть известный «прикол»:
У спелеологов есть известный «прикол»:
Группу чайников, человек 15, не менее, заводят в сложный лабиринт, водят довольно долго, чтобы притупилось внимание, и они забыли кто за кем шел, и незаметно зацикливают хвост группы к ее голове, а сам ведущий скрытно отползает и наблюдает как толпа носится по кругу.
Мне кажется, или это называется «метод градиентного спуска»?
В методе градиентного спуска выбирается одна начальная точка, шаг и направление. После первого шага вычисляются производные, и в направлении, где производная больше, производится следующий шаг. Но это если говорить грубо. На самом деле вычисляется градиент, и по нему перемещают точку. А в этом алгоритме не вычисляются производные, и начальных точек выбирается много, что является характерной чертой всех естественных алгоритмов.
Извините, но грубое значение производной: df/δk=Δf/δk. Т.е. мы берём различие между предыдущим шагом и новым, смотрим, куда было лучше, смещаемся в ту сторону. Если мы промахнулись, то новый вектор вычисляется как компромисс между новым и старым.
… δk — это обобщённое название частной производной по координате.
В методе градиентного спуска огромное значение имеет выбор начальной точки направления и шага. Попав на втором шаге в локальный минимум градиентный метод никогда не выберется из него, в отличие от описанного метода, который найдёт глобальный минимум. Также, метод градиентного спуска относится к детерминированным алгоритмам, в то время как алгоритм поведения роя пчёл является стахостическим.
Что касается производной, то она основывается на ранее известных данных (предыдущий шаг и текущий). Этот алгоритм оперирует только с двумя известными точками: ПНП и ГНП и корректирует позицию каждой точки основываясь на них, но случайным образом.
Что касается производной, то она основывается на ранее известных данных (предыдущий шаг и текущий). Этот алгоритм оперирует только с двумя известными точками: ПНП и ГНП и корректирует позицию каждой точки основываясь на них, но случайным образом.
Собственно, вопрос, почему рой найдёт глобальный минимум? Ровно так же рой может застрять в локальном минимуме, так как любое отклонение приводит к ухудшению результатов.
Насколько я понимаю, когда рассматривают подобные алгоритмы, полагают, что изучаемая функция определена на ограниченном интервале. При исследовании же методом градиентного спуска функция более привычная математическая, то есть область определения может быть произвольной, в том числе, неограниченной.
Алгоритм роя очевидным образом не сможет покрыть бесконечность, так что его к бесконечным функциям и не применяют. А на конечной функции достаточно использовать метод научного тыка и метод градиентного спуска — на выходе будет ровно тот же результат. Мы будем иметь вероятность попасть в спуск в глобальный минимум и алгоритм, который этот минимум пройдёт.
Насколько я понимаю, когда рассматривают подобные алгоритмы, полагают, что изучаемая функция определена на ограниченном интервале. При исследовании же методом градиентного спуска функция более привычная математическая, то есть область определения может быть произвольной, в том числе, неограниченной.
Алгоритм роя очевидным образом не сможет покрыть бесконечность, так что его к бесконечным функциям и не применяют. А на конечной функции достаточно использовать метод научного тыка и метод градиентного спуска — на выходе будет ровно тот же результат. Мы будем иметь вероятность попасть в спуск в глобальный минимум и алгоритм, который этот минимум пройдёт.
Про муравьёв я собирался написать через пару постов. У них более специфический алгоритм. Он хорош для логистических, а также динамических систем.
Странный какой-то алгоритм. Описанная система пчёл явно эргодическая. Это значит, что во-первых, можно рассматривать не рой пчёл, а одну пчелу, просто дольше (усреднение по ансамблю эквивалентно усреднению по времени); и во-вторых, что эту систему можно анализировать чисто статистическими методами, которые смогут или повысить эффективность алгоритма, или вообще выдать решение сразу, без всяких там роящихся пчёл.
Чем этот алгорим лучше обычного Монте-Карло?
Чем этот алгорим лучше обычного Монте-Карло?
Метод Монте-Карло основывается вероятностных характеристиках. Целью этого метода было получение алгоритма, имитирующего явление живой природы. Анализировать же эти естественные процессы можно и нужно. Я не берусь утверждать, что метод Монте-Карло однозначно хуже, просто есть такой алгоритм и для определённых задач он является эффективным. И мне интересно посмотреть на реализацию статистического анализа этой системы и посмотреть насколько увеличится эффективность алгоритма.
Хочу отметить, что существуют различные комбинации методов, например генетический алгоритм с методом градиентного спуска в каждом поколении, но опять же, производительность каждого из выбранных методов различна для разных задач.
Хочу отметить, что существуют различные комбинации методов, например генетический алгоритм с методом градиентного спуска в каждом поколении, но опять же, производительность каждого из выбранных методов различна для разных задач.
Хорошая вводная статья. Очень хотелось бы, чтобы автор опубликовал несколько прикладных примеров использования алгоритма для решения как простых, так и более сложных задач.
Так же интересно сравнение с ГА — сравнение временной сложности, выбор целевой функции. Если автор больше не планирует продолжать писать про пчёл, возможно он сможет дать несколько ссылок, где об этом пишут поподробнее, и понятным языком. Это было бы замечательно.
Так же интересно сравнение с ГА — сравнение временной сложности, выбор целевой функции. Если автор больше не планирует продолжать писать про пчёл, возможно он сможет дать несколько ссылок, где об этом пишут поподробнее, и понятным языком. Это было бы замечательно.
Было бы неплохо приложить визуализацию какую-нибудь…
Это Partical Swarm Optimization?
видимо это вариант расширения стохастического поиска на паралельную обработку (использование знания о глобальном найденном оптимуме, умозрительно, ускоряет сходимость).
однако, у меня вопрос к автору
ИМХО, необходимо учитывать множитель инерции именно таким образом, т.к. исходя из вашей исходной формулы, скорость неограниченно растет на каждом шаге.
во-вторых, неясны размерности разностей p — x и g-x. p и g это же значение оптимизируемой функции в какой либо точке, а вычитаем из этого координату.
однако, у меня вопрос к автору
ИМХО, необходимо учитывать множитель инерции именно таким образом, т.к. исходя из вашей исходной формулы, скорость неограниченно растет на каждом шаге.
во-вторых, неясны размерности разностей p — x и g-x. p и g это же значение оптимизируемой функции в какой либо точке, а вычитаем из этого координату.
pn — n координата наилучшей персональной позиции, gn — n координата глобальной наилучшей позиции, а не значения целевоя функции в них. Значения в скобках есть расстояния от частицы до ПНП и ГНП соответсвенно. Скорость будет увеличиваться с удалением пчелы от ПНП и ГНП, что вполне нормально, ведь чем дальше улетает пчела, тем сильнее она стремится вернуться, и весовые коэффициенты там тоже имеют значение.
Когда то я ним занимался, запомнил, что генетический на неких данных легко сваливается в локальный минимум, а вот пчёлы почти не попадаются на уловку — всегда выдавали именно глобальный.
Спасибо, что освежили и добавили знаний :).
Спасибо, что освежили и добавили знаний :).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Естественные алгоритмы. Алгоритм поведения роя пчёл