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

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

Не понял я вашего алгоритма, хоть и очень старался.
Вы говорите то о цветах и частицах, то о «стенах», глобальных экстремумах и снова о пчелах. Трудно уследить за мыслью.
Плотность цветов — значение целевой функции, частицы — те самые «пчелы», стены — границы допустимого множества задачи. Мысль вполне отслеживаема :)
Эх, жаль, что не выбрали для описания алгоритм поведения колонии муравьев. Просто есть в нем — в алгоритме поведения реальных муравьев — одна странная (так и хочется назвать это багом, но как-то рука не поднимается написать такое про не человеком созданные алгоритмы, да к тому же каламбур ;) особенность. В определенных ситуациях огромный табун муравьев начинает ходить по кругу, превращаясь в черное кольцо, и не может остановиться, вследствие чего муравьи умирают от изнеможения. Просто вот очень хотелось бы почитать, как это формализуется, так сказать :)
Муравьи-кочевники никогда не производят индивидуальную фуражировку или разведку, но действуют большими группами (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 это же значение оптимизируемой функции в какой либо точке, а вычитаем из этого координату.
pn — n координата наилучшей персональной позиции, gn — n координата глобальной наилучшей позиции, а не значения целевоя функции в них. Значения в скобках есть расстояния от частицы до ПНП и ГНП соответсвенно. Скорость будет увеличиваться с удалением пчелы от ПНП и ГНП, что вполне нормально, ведь чем дальше улетает пчела, тем сильнее она стремится вернуться, и весовые коэффициенты там тоже имеют значение.
Когда то я ним занимался, запомнил, что генетический на неких данных легко сваливается в локальный минимум, а вот пчёлы почти не попадаются на уловку — всегда выдавали именно глобальный.
Спасибо, что освежили и добавили знаний :).
если генетический алгоритм «не правильно готовить» он почти всегда скатывается в локальный на негладкой функции. в любом случае, уверен, что генетический будет быстрее.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории